diff options
Diffstat (limited to 'absl/container/node_hash_map.h')
| -rw-r--r-- | absl/container/node_hash_map.h | 71 |
1 files changed, 63 insertions, 8 deletions
diff --git a/absl/container/node_hash_map.h b/absl/container/node_hash_map.h index a396de2e..5615e496 100644 --- a/absl/container/node_hash_map.h +++ b/absl/container/node_hash_map.h @@ -32,21 +32,25 @@ // migration, because it guarantees pointer stability. Consider migrating to // `node_hash_map` and perhaps converting to a more efficient `flat_hash_map` // upon further review. +// +// `node_hash_map` is not exception-safe. #ifndef ABSL_CONTAINER_NODE_HASH_MAP_H_ #define ABSL_CONTAINER_NODE_HASH_MAP_H_ -#include <tuple> +#include <cstddef> +#include <memory> #include <type_traits> #include <utility> #include "absl/algorithm/container.h" -#include "absl/base/macros.h" +#include "absl/base/attributes.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/node_slot_policy.h" #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 @@ -66,7 +70,7 @@ class NodeHashMapPolicy; // // * 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. // * Contains a `capacity()` member function indicating the number of element // slots (open, deleted, and empty) within the hash map. // * Returns `void` from the `erase(iterator)` overload. @@ -82,6 +86,19 @@ class NodeHashMapPolicy; // 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. +// // Example: // // // Create a node hash map of three strings (that map to strings) @@ -100,11 +117,10 @@ class NodeHashMapPolicy; // if (result != ducks.end()) { // std::cout << "Result: " << result->second << std::endl; // } -template <class Key, class Value, - class Hash = absl::container_internal::hash_default_hash<Key>, - class Eq = absl::container_internal::hash_default_eq<Key>, +template <class Key, class Value, class Hash = DefaultHashContainerHash<Key>, + class Eq = DefaultHashContainerEq<Key>, class Alloc = std::allocator<std::pair<const Key, Value>>> -class node_hash_map +class ABSL_INTERNAL_ATTRIBUTE_OWNER node_hash_map : public absl::container_internal::raw_hash_map< absl::container_internal::NodeHashMapPolicy<Key, Value>, Hash, Eq, Alloc> { @@ -544,6 +560,38 @@ typename node_hash_map<K, V, H, E, A>::size_type erase_if( namespace container_internal { +// c_for_each_fast(node_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 node_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(node_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(node_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 Key, class Value> class NodeHashMapPolicy : public absl::container_internal::node_slot_policy< @@ -590,6 +638,13 @@ class NodeHashMapPolicy static Value& value(value_type* elem) { return elem->second; } static const Value& value(const value_type* elem) { return elem->second; } + + template <class Hash> + static constexpr HashSlotFn get_hash_slot_fn() { + return memory_internal::IsLayoutCompatible<Key, Value>::value + ? &TypeErasedDerefAndApplyToSlotFn<Hash, Key> + : nullptr; + } }; } // namespace container_internal |