diff options
Diffstat (limited to 'absl/container/flat_hash_map.h')
| -rw-r--r-- | absl/container/flat_hash_map.h | 80 |
1 files changed, 68 insertions, 12 deletions
diff --git a/absl/container/flat_hash_map.h b/absl/container/flat_hash_map.h index acd013b0..ebd9ed67 100644 --- a/absl/container/flat_hash_map.h +++ b/absl/container/flat_hash_map.h @@ -26,21 +26,24 @@ // // In most cases, your default choice for a hash map should be a map of type // `flat_hash_map`. +// +// `flat_hash_map` is not exception-safe. #ifndef ABSL_CONTAINER_FLAT_HASH_MAP_H_ #define ABSL_CONTAINER_FLAT_HASH_MAP_H_ #include <cstddef> -#include <new> +#include <memory> #include <type_traits> #include <utility> #include "absl/algorithm/container.h" +#include "absl/base/attributes.h" #include "absl/base/macros.h" +#include "absl/container/hash_container_defaults.h" #include "absl/container/internal/container_memory.h" -#include "absl/container/internal/hash_function_defaults.h" // IWYU pragma: export #include "absl/container/internal/raw_hash_map.h" // IWYU pragma: export -#include "absl/memory/memory.h" +#include "absl/meta/type_traits.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -62,7 +65,7 @@ struct FlatHashMapPolicy; // * Requires values that are MoveConstructible // * Supports heterogeneous lookup, through `find()`, `operator[]()` and // `insert()`, provided that the map is provided a compatible heterogeneous -// hashing function and equality operator. +// hashing function and equality operator. See below for details. // * Invalidates any references and pointers to elements within the table after // `rehash()` and when the table is moved. // * Contains a `capacity()` member function indicating the number of element @@ -80,6 +83,19 @@ struct FlatHashMapPolicy; // libraries (e.g. .dll, .so) is unsupported due to way `absl::Hash` values may // be randomized across dynamically loaded libraries. // +// To achieve heterogeneous lookup for custom types either `Hash` and `Eq` type +// parameters can be used or `T` should have public inner types +// `absl_container_hash` and (optionally) `absl_container_eq`. In either case, +// `typename Hash::is_transparent` and `typename Eq::is_transparent` should be +// well-formed. Both types are basically functors: +// * `Hash` should support `size_t operator()(U val) const` that returns a hash +// for the given `val`. +// * `Eq` should support `bool operator()(U lhs, V rhs) const` that returns true +// if `lhs` is equal to `rhs`. +// +// In most cases `T` needs only to provide the `absl_container_hash`. In this +// case `std::equal_to<void>` will be used instead of `eq` part. +// // NOTE: A `flat_hash_map` stores its value types directly inside its // implementation array to avoid memory indirection. Because a `flat_hash_map` // is designed to move data when rehashed, map values will not retain pointer @@ -106,13 +122,13 @@ struct FlatHashMapPolicy; // if (result != ducks.end()) { // std::cout << "Result: " << result->second << std::endl; // } -template <class K, class V, - class Hash = absl::container_internal::hash_default_hash<K>, - class Eq = absl::container_internal::hash_default_eq<K>, +template <class K, class V, class Hash = DefaultHashContainerHash<K>, + class Eq = DefaultHashContainerEq<K>, class Allocator = std::allocator<std::pair<const K, V>>> -class flat_hash_map : public absl::container_internal::raw_hash_map< - absl::container_internal::FlatHashMapPolicy<K, V>, - Hash, Eq, Allocator> { +class ABSL_INTERNAL_ATTRIBUTE_OWNER flat_hash_map + : public absl::container_internal::raw_hash_map< + absl::container_internal::FlatHashMapPolicy<K, V>, Hash, Eq, + Allocator> { using Base = typename flat_hash_map::raw_hash_map; public: @@ -560,6 +576,38 @@ typename flat_hash_map<K, V, H, E, A>::size_type erase_if( namespace container_internal { +// c_for_each_fast(flat_hash_map<>, Function) +// +// Container-based version of the <algorithm> `std::for_each()` function to +// apply a function to a container's elements. +// There is no guarantees on the order of the function calls. +// Erasure and/or insertion of elements in the function is not allowed. +template <typename K, typename V, typename H, typename E, typename A, + typename Function> +decay_t<Function> c_for_each_fast(const flat_hash_map<K, V, H, E, A>& c, + Function&& f) { + container_internal::ForEach(f, &c); + return f; +} +template <typename K, typename V, typename H, typename E, typename A, + typename Function> +decay_t<Function> c_for_each_fast(flat_hash_map<K, V, H, E, A>& c, + Function&& f) { + container_internal::ForEach(f, &c); + return f; +} +template <typename K, typename V, typename H, typename E, typename A, + typename Function> +decay_t<Function> c_for_each_fast(flat_hash_map<K, V, H, E, A>&& c, + Function&& f) { + container_internal::ForEach(f, &c); + return f; +} + +} // namespace container_internal + +namespace container_internal { + template <class K, class V> struct FlatHashMapPolicy { using slot_policy = container_internal::map_slot_policy<K, V>; @@ -573,9 +621,10 @@ struct FlatHashMapPolicy { slot_policy::construct(alloc, slot, std::forward<Args>(args)...); } + // Returns std::true_type in case destroy is trivial. template <class Allocator> - static void destroy(Allocator* alloc, slot_type* slot) { - slot_policy::destroy(alloc, slot); + static auto destroy(Allocator* alloc, slot_type* slot) { + return slot_policy::destroy(alloc, slot); } template <class Allocator> @@ -592,6 +641,13 @@ struct FlatHashMapPolicy { std::forward<Args>(args)...); } + template <class Hash> + static constexpr HashSlotFn get_hash_slot_fn() { + return memory_internal::IsLayoutCompatible<K, V>::value + ? &TypeErasedApplyToSlotFn<Hash, K> + : nullptr; + } + static size_t space_used(const slot_type*) { return 0; } static std::pair<const K, V>& element(slot_type* slot) { return slot->value; } |