Parameterize raw_linked_hash_set via InstantiateRawLinkedHashSet. Omit trailing default Hash, Eq, and Alloc template arguments from raw_linked_hash_set mangled symbol names using ApplyWithoutDefaultSuffix, and generalize merge and SpliceFrom over OtherParams... accordingly. PiperOrigin-RevId: 1023933763
diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 253898d..407b72a 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake
@@ -100,6 +100,7 @@ "container/internal/raw_hash_set.cc" "container/internal/raw_hash_set.h" "container/internal/raw_hash_set_resize_impl.h" + "container/internal/raw_linked_hash_set.h" "container/linked_hash_map.h" "container/linked_hash_set.h" "container/node_hash_map.h"
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index fbf0d56..3214fb0 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel
@@ -1374,16 +1374,28 @@ ) cc_library( + name = "raw_linked_hash_set", + hdrs = ["internal/raw_linked_hash_set.h"], + copts = ABSL_DEFAULT_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + deps = [ + ":common", + ":flat_hash_set", + "//absl/base:config", + "//absl/base:core_headers", + ], +) + +cc_library( name = "linked_hash_set", hdrs = ["linked_hash_set.h"], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, visibility = ["//visibility:public"], deps = [ - ":common", - ":flat_hash_set", + ":hash_container_defaults", + ":raw_linked_hash_set", "//absl/base:config", - "//absl/base:core_headers", ], ) @@ -1434,8 +1446,8 @@ linkopts = ABSL_DEFAULT_LINKOPTS, visibility = ["//visibility:public"], deps = [ - ":common", - ":flat_hash_set", + ":hash_container_defaults", + ":raw_linked_hash_set", "//absl/base:config", "//absl/base:core_headers", "//absl/base:throw_delegate",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 2d234aa..3634d96 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt
@@ -1156,6 +1156,25 @@ TESTONLY ) +# Internal-only target, do not depend on directly. +absl_cc_library( + NAME + raw_linked_hash_set + HDRS + "internal/raw_linked_hash_set.h" + COPTS + ${ABSL_DEFAULT_COPTS} + LINKOPTS + ${ABSL_DEFAULT_LINKOPTS} + DEPS + absl::config + absl::container_common + absl::core_headers + absl::flat_hash_set + absl::hash_container_defaults + PUBLIC +) + absl_cc_library( NAME linked_hash_set @@ -1167,9 +1186,7 @@ ${ABSL_DEFAULT_LINKOPTS} DEPS absl::config - absl::container_common - absl::core_headers - absl::flat_hash_set + absl::raw_linked_hash_set ) absl_cc_test( @@ -1208,9 +1225,8 @@ ${ABSL_DEFAULT_LINKOPTS} DEPS absl::config - absl::container_common absl::core_headers - absl::flat_hash_set + absl::raw_linked_hash_set absl::throw_delegate )
diff --git a/absl/container/internal/raw_linked_hash_set.h b/absl/container/internal/raw_linked_hash_set.h new file mode 100644 index 0000000..02d02d0 --- /dev/null +++ b/absl/container/internal/raw_linked_hash_set.h
@@ -0,0 +1,627 @@ +// Copyright 2025 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#ifndef ABSL_CONTAINER_INTERNAL_RAW_LINKED_HASH_SET_H_ +#define ABSL_CONTAINER_INTERNAL_RAW_LINKED_HASH_SET_H_ + +#include <cassert> +#include <cstddef> +#include <initializer_list> +#include <iterator> +#include <list> +#include <memory> +#include <tuple> +#include <type_traits> +#include <utility> + +#include "absl/base/attributes.h" +#include "absl/base/config.h" +#include "absl/container/flat_hash_set.h" +#include "absl/container/internal/common.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace container_internal { + +template <typename Policy, typename... Params> +class raw_linked_hash_set; + +template <typename Policy, typename Hash, typename Eq, typename Alloc> +struct InstantiateRawLinkedHashSet { + using type = typename ApplyWithoutDefaultSuffix< + raw_linked_hash_set, + TypeList<void, typename Policy::DefaultHash, typename Policy::DefaultEq, + typename Policy::DefaultAlloc>, + TypeList<Policy, Hash, Eq, Alloc>>::type; +}; + +// Shared container implementation backing both `absl::linked_hash_set` and +// `absl::linked_hash_map`. +template <typename Policy, typename... Params> +class raw_linked_hash_set { + using Hash = GetFromListOr<typename Policy::DefaultHash, 0, Params...>; + using Eq = GetFromListOr<typename Policy::DefaultEq, 1, Params...>; + using Alloc = GetFromListOr<typename Policy::DefaultAlloc, 2, Params...>; + + static_assert( + std::is_same_v< + typename InstantiateRawLinkedHashSet<Policy, Hash, Eq, Alloc>::type, + raw_linked_hash_set>, + "Redundant template parameters were passed. Use " + "InstantiateRawLinkedHashSet<> instead"); + + protected: + static constexpr bool kIsTransparent = + IsTransparent<Eq>::value && IsTransparent<Hash>::value; + using KeyArgImpl = KeyArg<kIsTransparent>; + + public: + using key_type = typename Policy::key_type; + using value_type = typename Policy::value_type; + using hasher = Hash; + using key_equal = Eq; + using allocator_type = Alloc; + using difference_type = ptrdiff_t; + + protected: + template <class K> + using key_arg = typename KeyArgImpl::template Select<K, key_type>; + + using ListType = std::list<value_type, allocator_type>; + + template <typename Derived, bool kIsMap = Policy::kIsMap> + class NodeHandleAccess { + public: + using key_type = typename Policy::key_type; + using mapped_type = typename Policy::mapped_type; + + const key_type& key() const { + return static_cast<const Derived*>(this)->list_.front().first; + } + mapped_type& mapped() { + return static_cast<Derived*>(this)->list_.front().second; + } + }; + + template <typename Derived> + class NodeHandleAccess<Derived, /*kIsMap=*/false> { + public: + using value_type = typename Policy::value_type; + + value_type& value() { return static_cast<Derived*>(this)->list_.front(); } + }; + + class NodeHandle : public NodeHandleAccess<NodeHandle> { + public: + using allocator_type = raw_linked_hash_set::allocator_type; + + constexpr NodeHandle() noexcept = default; + NodeHandle(NodeHandle&& nh) noexcept = default; + ~NodeHandle() = default; + NodeHandle& operator=(NodeHandle&& node) noexcept = default; + bool empty() const noexcept { return list_.empty(); } + explicit operator bool() const noexcept { return !empty(); } + allocator_type get_allocator() const { return list_.get_allocator(); } + void swap(NodeHandle& nh) noexcept { list_.swap(nh.list_); } + friend void swap(NodeHandle& a, NodeHandle& b) noexcept { a.swap(b); } + + private: + friend class NodeHandleAccess<NodeHandle>; + friend raw_linked_hash_set; + + explicit NodeHandle(ListType list) : list_(std::move(list)) {} + ListType list_; + }; + + template <class Fn> + class Wrapped { + template <typename K> + static const K& ToKey(const K& k) { + return k; + } + static const key_type& ToKey(typename ListType::const_iterator it) { + return Policy::key(*it); + } + static const key_type& ToKey(typename ListType::iterator it) { + return Policy::key(*it); + } + + Fn fn_; + + friend raw_linked_hash_set; + + public: + using is_transparent = void; + + Wrapped() = default; + explicit Wrapped(Fn fn) : fn_(std::move(fn)) {} + + template <class... Args> + auto operator()(Args&&... args) const + -> decltype(this->fn_(ToKey(args)...)) { + return fn_(ToKey(args)...); + } + }; + + using SetType = + absl::flat_hash_set<typename ListType::iterator, Wrapped<hasher>, + Wrapped<key_equal>, allocator_type>; + + public: + using iterator = + std::conditional_t<Policy::kIsMap, typename ListType::iterator, + typename ListType::const_iterator>; + using const_iterator = typename ListType::const_iterator; + using reverse_iterator = + std::conditional_t<Policy::kIsMap, typename ListType::reverse_iterator, + typename ListType::const_reverse_iterator>; + using const_reverse_iterator = typename ListType::const_reverse_iterator; + using reference = typename ListType::reference; + using const_reference = typename ListType::const_reference; + using size_type = typename ListType::size_type; + using pointer = typename std::allocator_traits<allocator_type>::pointer; + using const_pointer = + typename std::allocator_traits<allocator_type>::const_pointer; + using node_type = NodeHandle; + using insert_return_type = InsertReturnType<iterator, node_type>; + + raw_linked_hash_set() = default; + + explicit raw_linked_hash_set(size_t reservation_size, + const hasher& hash = hasher(), + const key_equal& eq = key_equal(), + const allocator_type& alloc = allocator_type()) + : set_(reservation_size, Wrapped<hasher>(hash), Wrapped<key_equal>(eq), + alloc), + list_(alloc) {} + + raw_linked_hash_set(size_t reservation_size, const hasher& hash, + const allocator_type& alloc) + : raw_linked_hash_set(reservation_size, hash, key_equal(), alloc) {} + + raw_linked_hash_set(size_t reservation_size, const allocator_type& alloc) + : raw_linked_hash_set(reservation_size, hasher(), key_equal(), alloc) {} + + explicit raw_linked_hash_set(const allocator_type& alloc) + : raw_linked_hash_set(0, hasher(), key_equal(), alloc) {} + + template <class InputIt> + raw_linked_hash_set(InputIt first, InputIt last, size_t reservation_size = 0, + const hasher& hash = hasher(), + const key_equal& eq = key_equal(), + const allocator_type& alloc = allocator_type()) + : raw_linked_hash_set(reservation_size, hash, eq, alloc) { + for (; first != last; ++first) InsertValueAt(list_.cend(), *first); + } + + template <class InputIt> + raw_linked_hash_set(InputIt first, InputIt last, size_t reservation_size, + const hasher& hash, const allocator_type& alloc) + : raw_linked_hash_set(first, last, reservation_size, hash, key_equal(), + alloc) {} + + template <class InputIt> + raw_linked_hash_set(InputIt first, InputIt last, size_t reservation_size, + const allocator_type& alloc) + : raw_linked_hash_set(first, last, reservation_size, hasher(), + key_equal(), alloc) {} + + template <class InputIt> + raw_linked_hash_set(InputIt first, InputIt last, const allocator_type& alloc) + : raw_linked_hash_set(first, last, /*reservation_size=*/0, hasher(), + key_equal(), alloc) {} + + raw_linked_hash_set(std::initializer_list<value_type> init, + size_t reservation_size = 0, + const hasher& hash = hasher(), + const key_equal& eq = key_equal(), + const allocator_type& alloc = allocator_type()) + : raw_linked_hash_set(init.begin(), init.end(), reservation_size, hash, + eq, alloc) {} + + raw_linked_hash_set(std::initializer_list<value_type> init, + size_t reservation_size, const hasher& hash, + const allocator_type& alloc) + : raw_linked_hash_set(init, reservation_size, hash, key_equal(), alloc) {} + + raw_linked_hash_set(std::initializer_list<value_type> init, + size_t reservation_size, const allocator_type& alloc) + : raw_linked_hash_set(init, reservation_size, hasher(), key_equal(), + alloc) {} + + raw_linked_hash_set(std::initializer_list<value_type> init, + const allocator_type& alloc) + : raw_linked_hash_set(init, /*reservation_size=*/0, hasher(), key_equal(), + alloc) {} + + raw_linked_hash_set(const raw_linked_hash_set& other) + : raw_linked_hash_set(0, other.hash_function(), other.key_eq(), + other.get_allocator()) { + reserve(other.size()); + CopyFrom(other); + } + + raw_linked_hash_set(const raw_linked_hash_set& other, + const allocator_type& alloc) + : raw_linked_hash_set(0, other.hash_function(), other.key_eq(), alloc) { + reserve(other.size()); + CopyFrom(other); + } + + raw_linked_hash_set(raw_linked_hash_set&& other) noexcept + : set_(std::move(other.set_)), list_(std::move(other.list_)) { + // Since the list and set must agree for other to end up "valid", + // explicitly clear them. + other.set_.clear(); + other.list_.clear(); + } + + raw_linked_hash_set(raw_linked_hash_set&& other, const allocator_type& alloc) + : raw_linked_hash_set(0, other.hash_function(), other.key_eq(), alloc) { + if (get_allocator() == other.get_allocator()) { + *this = std::move(other); + } else { + reserve(other.size()); + CopyFrom(std::move(other)); + } + } + + raw_linked_hash_set& operator=(const raw_linked_hash_set& other) { + if (this != &other) { + // Make a new set, with other's hash/eq/alloc. + set_ = SetType(0, other.set_.hash_function(), other.set_.key_eq(), + other.get_allocator()); + set_.reserve(other.size()); + // Copy the list, with other's allocator. + list_ = ListType(other.get_allocator()); + CopyFrom(other); + } + return *this; + } + + raw_linked_hash_set& operator=(raw_linked_hash_set&& other) noexcept { + if (this != &other) { + using AllocTraits = std::allocator_traits<allocator_type>; + if constexpr (AllocTraits::propagate_on_container_move_assignment:: + value) { + set_ = std::move(other.set_); + list_ = std::move(other.list_); + other.clear(); + } else if (AllocTraits::is_always_equal::value || + get_allocator() == other.get_allocator()) { + // The allocators are equal, so the list can take over other's nodes. + // std::list's move assignment can not be used here: with an allocator + // that does not propagate on move assignment it element-assigns, which + // is ill-formed for value types that are not assignable, such as + // linked_hash_map's std::pair<const K, V>. + clear(); + set_ = std::move(other.set_); + list_.splice(list_.end(), other.list_); + other.set_.clear(); + } else if constexpr (!AllocTraits::is_always_equal::value) { + // The list can not take over other's nodes, so move each element into + // a new node allocated with this container's allocator and rebuild the + // index over them, adopting other's hash and equality state. This is + // the same pattern as raw_hash_set::move_assign. + clear(); + set_ = SetType(other.size(), other.set_.hash_function(), + other.set_.key_eq(), get_allocator()); + CopyFrom(std::move(other)); + } + } + return *this; + } + + raw_linked_hash_set& operator=(std::initializer_list<value_type> values) { + clear(); + reserve(values.size()); + for (const auto& v : values) InsertValueAt(list_.cend(), v); + return *this; + } + + // Derive size from set_, as list::size might be O(N). + size_type size() const { return set_.size(); } + size_type max_size() const noexcept { return ~size_type{}; } + bool empty() const { return set_.empty(); } + + // Iteration is list-like, in insertion order. + // These are all forwarded. + iterator begin() { return list_.begin(); } + iterator end() { return list_.end(); } + const_iterator begin() const { return list_.begin(); } + const_iterator end() const { return list_.end(); } + const_iterator cbegin() const { return list_.cbegin(); } + const_iterator cend() const { return list_.cend(); } + reverse_iterator rbegin() { return list_.rbegin(); } + reverse_iterator rend() { return list_.rend(); } + const_reverse_iterator rbegin() const { return list_.rbegin(); } + const_reverse_iterator rend() const { return list_.rend(); } + const_reverse_iterator crbegin() const { return list_.crbegin(); } + const_reverse_iterator crend() const { return list_.crend(); } + reference front() { return list_.front(); } + reference back() { return list_.back(); } + const_reference front() const { return list_.front(); } + const_reference back() const { return list_.back(); } + + void pop_front() { erase(begin()); } + void pop_back() { erase(std::prev(end())); } + + ABSL_ATTRIBUTE_REINITIALIZES void clear() { + set_.clear(); + list_.clear(); + } + + void reserve(size_t n) { set_.reserve(n); } + size_t capacity() const { return set_.capacity(); } + size_t bucket_count() const { return set_.bucket_count(); } + float load_factor() const { return set_.load_factor(); } + + hasher hash_function() const { return set_.hash_function().fn_; } + key_equal key_eq() const { return set_.key_eq().fn_; } + allocator_type get_allocator() const { return list_.get_allocator(); } + + template <class K = key_type> + size_type erase(const key_arg<K>& key) { + auto found = set_.find(key); + if (found == set_.end()) return 0; + auto list_it = *found; + // Erase set entry first since it refers to the list element. + set_.erase(found); + list_.erase(list_it); + return 1; + } + + iterator erase(const_iterator position) { + auto found = set_.find(position); + assert(*found == position); + set_.erase(found); + return list_.erase(position); + } + + template <bool kMap = Policy::kIsMap, std::enable_if_t<kMap, int> = 0> + iterator erase(iterator position) { + return erase(static_cast<const_iterator>(position)); + } + + template <bool kMap = Policy::kIsMap, std::enable_if_t<kMap, int> = 0> + iterator erase(iterator first, iterator last) { + while (first != last) first = erase(first); + return first; + } + + iterator erase(const_iterator first, const_iterator last) { + while (first != last) first = erase(first); + if constexpr (Policy::kIsMap) { + if (first == end()) return end(); + return *set_.find(first); + } else { + return first; + } + } + + template <class K = key_type> + iterator find(const key_arg<K>& key) { + auto found = set_.find(key); + if (found == set_.end()) return end(); + return *found; + } + + template <class K = key_type> + const_iterator find(const key_arg<K>& key) const { + auto found = set_.find(key); + if (found == set_.end()) return end(); + return *found; + } + + template <class K = key_type> + size_type count(const key_arg<K>& key) const { + return contains(key) ? 1 : 0; + } + template <class K = key_type> + bool contains(const key_arg<K>& key) const { + return set_.contains(key); + } + + template <class K = key_type> + std::pair<iterator, iterator> equal_range(const key_arg<K>& key) { + auto iter = set_.find(key); + if (iter == set_.end()) return {end(), end()}; + return {*iter, std::next(*iter)}; + } + + template <class K = key_type> + std::pair<const_iterator, const_iterator> equal_range( + const key_arg<K>& key) const { + auto iter = set_.find(key); + if (iter == set_.end()) return {end(), end()}; + return {*iter, std::next(*iter)}; + } + + insert_return_type insert(node_type&& node) { + if (node.empty()) return {end(), false, node_type()}; + if (auto [set_itr, inserted] = set_.emplace(node.list_.begin()); inserted) { + list_.splice(list_.end(), node.list_); + return {*set_itr, true, node_type()}; + } else { + return {*set_itr, false, std::move(node)}; + } + } + + iterator insert(const_iterator, node_type&& node) { + return insert(std::move(node)).position; + } + + template <typename... Args> + std::pair<iterator, bool> emplace(Args&&... args) { + return EmplaceAt(list_.end(), std::forward<Args>(args)...); + } + + template <typename... Args> + iterator emplace_hint(const_iterator hint, Args&&... args) { + return EmplaceAt(Policy::kIsMap ? list_.cend() : hint, + std::forward<Args>(args)...) + .first; + } + + template <typename... OtherParams, + typename = std::enable_if_t<std::is_same_v< + Alloc, typename raw_linked_hash_set< + Policy, OtherParams...>::allocator_type>>> + void merge(raw_linked_hash_set<Policy, OtherParams...>& src) { + auto itr = src.begin(); + while (itr != src.end()) { + if (contains(Policy::key(*itr))) { + ++itr; + } else { + insert(src.extract(itr++)); + } + } + } + + template <typename... OtherParams, + typename = std::enable_if_t<std::is_same_v< + Alloc, typename raw_linked_hash_set< + Policy, OtherParams...>::allocator_type>>> + void merge(raw_linked_hash_set<Policy, OtherParams...>&& src) { + merge(src); + } + + node_type extract(const_iterator position) { + set_.erase(Policy::key(*position)); + ListType extracted_node_list(get_allocator()); + extracted_node_list.splice(extracted_node_list.end(), list_, position); + return node_type(std::move(extracted_node_list)); + } + + template <class K = key_type, + std::enable_if_t<!std::is_same_v<K, iterator>, int> = 0> + node_type extract(const key_arg<K>& key) { + auto node = set_.extract(key); + if (node.empty()) return node_type(); + ListType extracted_node_list(get_allocator()); + extracted_node_list.splice(extracted_node_list.end(), list_, node.value()); + return node_type(std::move(extracted_node_list)); + } + + void swap(raw_linked_hash_set& other) noexcept { + using std::swap; + swap(set_, other.set_); + swap(list_, other.list_); + } + + friend bool operator==(const raw_linked_hash_set& a, + const raw_linked_hash_set& b) { + if (a.size() != b.size()) return false; + const raw_linked_hash_set* outer = &a; + const raw_linked_hash_set* inner = &b; + if (outer->capacity() > inner->capacity()) std::swap(outer, inner); + for (const value_type& elem : *outer) { + if constexpr (Policy::kIsMap) { + auto it = inner->find(elem.first); + if (it == inner->end()) return false; + if (it->second != elem.second) return false; + } else { + if (!inner->contains(elem)) return false; + } + } + return true; + } + + friend bool operator!=(const raw_linked_hash_set& a, + const raw_linked_hash_set& b) { + return !(a == b); + } + + void rehash(size_t n) { set_.rehash(n); } + + protected: + template <typename, typename...> + friend class raw_linked_hash_set; + + template <typename U> + std::pair<iterator, bool> InsertValueAt(const_iterator hint, U&& val) { + bool constructed = false; + auto set_iter = set_.lazy_emplace(Policy::key(val), [&](const auto& ctor) { + constructed = true; + ctor(list_.emplace(hint, std::forward<U>(val))); + }); + return {*set_iter, constructed}; + } + + template <typename... Args> + std::pair<iterator, bool> EmplaceAt(const_iterator hint, Args&&... args) { + ListType node_donor(get_allocator()); + auto list_iter = + node_donor.emplace(node_donor.end(), std::forward<Args>(args)...); + auto ins = set_.insert(list_iter); + if (!ins.second) return {*ins.first, false}; + list_.splice(hint, node_donor, list_iter); + return {list_iter, true}; + } + + template <typename K, typename... Args> + std::pair<iterator, bool> LazyEmplaceMap(K&& key, Args&&... args) { + bool constructed = false; + auto set_iter = set_.lazy_emplace( + key, [this, &constructed, &key, &args...](const auto& ctor) { + auto list_iter = + list_.emplace(list_.end(), std::piecewise_construct, + std::forward_as_tuple(std::forward<K>(key)), + std::forward_as_tuple(std::forward<Args>(args)...)); + constructed = true; + ctor(list_iter); + }); + return {*set_iter, constructed}; + } + + template <typename... OtherParams> + void SpliceFrom(raw_linked_hash_set<Policy, OtherParams...>& list, + const_iterator it) { + if constexpr (std::is_same_v<raw_linked_hash_set<Policy, OtherParams...>, + raw_linked_hash_set>) { + if (&list == this) { + list_.splice(list_.end(), list.list_, it); + return; + } + } + insert(list.extract(it)); + } + + private: + template <typename Other> + void CopyFrom(Other&& other) { + for (auto& elem : other.list_) { + set_.insert(list_.insert(list_.end(), std::move(elem))); + } + if constexpr (!std::is_const_v<std::remove_reference_t<Other>>) { + // When moving from `other`, `std::move(elem)` above mutates the elements + // of `other.list_` in place, invalidating `other.set_`'s index over them. + // Clear `other` so its `set_` and `list_` remain consistent and empty. + other.clear(); + } + assert(set_.size() == list_.size()); + } + + // The set component, used for speedy lookups. + SetType set_; + + // The list component, used for maintaining insertion order. + ListType list_; +}; + +} // namespace container_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_CONTAINER_INTERNAL_RAW_LINKED_HASH_SET_H_
diff --git a/absl/container/linked_hash_map.h b/absl/container/linked_hash_map.h index b89e433..1e8dd16 100644 --- a/absl/container/linked_hash_map.h +++ b/absl/container/linked_hash_map.h
@@ -32,380 +32,70 @@ #ifndef ABSL_CONTAINER_LINKED_HASH_MAP_H_ #define ABSL_CONTAINER_LINKED_HASH_MAP_H_ -#include <cassert> -#include <cstddef> #include <initializer_list> -#include <list> #include <memory> -#include <string> -#include <tuple> #include <type_traits> #include <utility> -#include "absl/base/attributes.h" #include "absl/base/config.h" #include "absl/base/optimization.h" #include "absl/base/throw_delegate.h" -#include "absl/container/flat_hash_set.h" -#include "absl/container/internal/common.h" +#include "absl/container/hash_container_defaults.h" +#include "absl/container/internal/raw_linked_hash_set.h" namespace absl { ABSL_NAMESPACE_BEGIN +namespace container_internal { -template <typename Key, typename Value, - typename KeyHash = typename absl::flat_hash_set<Key>::hasher, - typename KeyEq = - typename absl::flat_hash_set<Key, KeyHash>::key_equal, - typename Alloc = std::allocator<std::pair<const Key, Value>>> -class linked_hash_map { - using KeyArgImpl = absl::container_internal::KeyArg< - absl::container_internal::IsTransparent<KeyEq>::value && - absl::container_internal::IsTransparent<KeyHash>::value>; - - public: +template <typename Key, typename Value> +struct LinkedHashMapPolicy { using key_type = Key; using mapped_type = Value; - using hasher = KeyHash; - using key_equal = KeyEq; using value_type = std::pair<const key_type, mapped_type>; - using allocator_type = Alloc; - using difference_type = ptrdiff_t; + using DefaultHash = absl::DefaultHashContainerHash<Key>; + using DefaultEq = absl::DefaultHashContainerEq<Key>; + using DefaultAlloc = std::allocator<value_type>; + static constexpr bool kIsMap = true; - private: + static const key_type& key(const value_type& v) { return v.first; } +}; + +} // namespace container_internal + +template <typename Key, typename Value, + typename KeyHash = typename container_internal::LinkedHashMapPolicy< + Key, Value>::DefaultHash, + typename KeyEq = typename container_internal::LinkedHashMapPolicy< + Key, Value>::DefaultEq, + typename Alloc = typename container_internal::LinkedHashMapPolicy< + Key, Value>::DefaultAlloc> +class linked_hash_map : public container_internal::InstantiateRawLinkedHashSet< + container_internal::LinkedHashMapPolicy<Key, Value>, + KeyHash, KeyEq, Alloc>::type { + using Policy = container_internal::LinkedHashMapPolicy<Key, Value>; + using Base = typename linked_hash_map::raw_linked_hash_set; template <class K> - using key_arg = typename KeyArgImpl::template Select<K, key_type>; - - using ListType = std::list<value_type, Alloc>; - - template <class Fn> - class Wrapped { - template <typename K> - static const K& ToKey(const K& k) { - return k; - } - static const key_type& ToKey(typename ListType::const_iterator it) { - return it->first; - } - static const key_type& ToKey(typename ListType::iterator it) { - return it->first; - } - - Fn fn_; - - friend linked_hash_map; - - public: - using is_transparent = void; - - Wrapped() = default; - explicit Wrapped(Fn fn) : fn_(std::move(fn)) {} - - template <class... Args> - auto operator()(Args&&... args) const - -> decltype(this->fn_(ToKey(args)...)) { - return fn_(ToKey(args)...); - } - }; - using SetType = - absl::flat_hash_set<typename ListType::iterator, Wrapped<hasher>, - Wrapped<key_equal>, Alloc>; - - class NodeHandle { - public: - using key_type = linked_hash_map::key_type; - using mapped_type = linked_hash_map::mapped_type; - using allocator_type = linked_hash_map::allocator_type; - - constexpr NodeHandle() noexcept = default; - NodeHandle(NodeHandle&& nh) noexcept = default; - ~NodeHandle() = default; - NodeHandle& operator=(NodeHandle&& node) noexcept = default; - bool empty() const noexcept { return list_.empty(); } - explicit operator bool() const noexcept { return !empty(); } - allocator_type get_allocator() const { return list_.get_allocator(); } - const key_type& key() const { return list_.front().first; } - mapped_type& mapped() { return list_.front().second; } - void swap(NodeHandle& nh) noexcept { list_.swap(nh.list_); } - - private: - friend linked_hash_map; - - explicit NodeHandle(ListType list) : list_(std::move(list)) {} - ListType list_; - }; - - template <class Iterator, class NodeType> - struct InsertReturnType { - Iterator position; - bool inserted; - NodeType node; - }; + using key_arg = typename Base::template key_arg<K>; public: - using iterator = typename ListType::iterator; - using const_iterator = typename ListType::const_iterator; - using reverse_iterator = typename ListType::reverse_iterator; - using const_reverse_iterator = typename ListType::const_reverse_iterator; - using reference = typename ListType::reference; - using const_reference = typename ListType::const_reference; - using size_type = typename ListType::size_type; - using pointer = typename std::allocator_traits<allocator_type>::pointer; - using const_pointer = - typename std::allocator_traits<allocator_type>::const_pointer; - using node_type = NodeHandle; - using insert_return_type = InsertReturnType<iterator, node_type>; + using mapped_type = Value; + using typename Base::const_iterator; + using typename Base::iterator; + using typename Base::key_type; + using typename Base::value_type; - linked_hash_map() {} - - explicit linked_hash_map(size_t reservation_size, - const hasher& hash = hasher(), - const key_equal& eq = key_equal(), - const allocator_type& alloc = allocator_type()) - : set_(reservation_size, Wrapped<hasher>(hash), Wrapped<key_equal>(eq), - alloc), - list_(alloc) {} - - linked_hash_map(size_t reservation_size, const hasher& hash, - const allocator_type& alloc) - : linked_hash_map(reservation_size, hash, key_equal(), alloc) {} - - linked_hash_map(size_t reservation_size, const allocator_type& alloc) - : linked_hash_map(reservation_size, hasher(), key_equal(), alloc) {} - - explicit linked_hash_map(const allocator_type& alloc) - : linked_hash_map(0, hasher(), key_equal(), alloc) {} - - template <class InputIt> - linked_hash_map(InputIt first, InputIt last, size_t reservation_size = 0, - const hasher& hash = hasher(), - const key_equal& eq = key_equal(), - const allocator_type& alloc = allocator_type()) - : linked_hash_map(reservation_size, hash, eq, alloc) { - insert(first, last); - } - - template <class InputIt> - linked_hash_map(InputIt first, InputIt last, size_t reservation_size, - const hasher& hash, const allocator_type& alloc) - : linked_hash_map(first, last, reservation_size, hash, key_equal(), - alloc) {} - - template <class InputIt> - linked_hash_map(InputIt first, InputIt last, size_t reservation_size, - const allocator_type& alloc) - : linked_hash_map(first, last, reservation_size, hasher(), key_equal(), - alloc) {} - - template <class InputIt> - linked_hash_map(InputIt first, InputIt last, const allocator_type& alloc) - : linked_hash_map(first, last, /*reservation_size=*/0, hasher(), - key_equal(), alloc) {} - - linked_hash_map(std::initializer_list<value_type> init, - size_t reservation_size = 0, const hasher& hash = hasher(), - const key_equal& eq = key_equal(), - const allocator_type& alloc = allocator_type()) - : linked_hash_map(init.begin(), init.end(), reservation_size, hash, eq, - alloc) {} - - linked_hash_map(std::initializer_list<value_type> init, - size_t reservation_size, const hasher& hash, - const allocator_type& alloc) - : linked_hash_map(init, reservation_size, hash, key_equal(), alloc) {} - - linked_hash_map(std::initializer_list<value_type> init, - size_t reservation_size, const allocator_type& alloc) - : linked_hash_map(init, reservation_size, hasher(), key_equal(), alloc) {} - - linked_hash_map(std::initializer_list<value_type> init, - const allocator_type& alloc) - : linked_hash_map(init, /*reservation_size=*/0, hasher(), key_equal(), - alloc) {} - - linked_hash_map(const linked_hash_map& other) - : linked_hash_map(0, other.hash_function(), other.key_eq(), - other.get_allocator()) { - reserve(other.size()); - CopyFrom(other); - } - - linked_hash_map(const linked_hash_map& other, const allocator_type& alloc) - : linked_hash_map(0, other.hash_function(), other.key_eq(), alloc) { - reserve(other.size()); - CopyFrom(other); - } - - linked_hash_map(linked_hash_map&& other) noexcept - : set_(std::move(other.set_)), list_(std::move(other.list_)) { - // Since the list and set must agree for other to end up "valid", - // explicitly clear them. - other.set_.clear(); - other.list_.clear(); - } - - linked_hash_map(linked_hash_map&& other, const allocator_type& alloc) - : linked_hash_map(0, other.hash_function(), other.key_eq(), alloc) { - if (get_allocator() == other.get_allocator()) { - *this = std::move(other); - } else { - reserve(other.size()); - CopyFrom(std::move(other)); - } - } - - linked_hash_map& operator=(const linked_hash_map& other) { - if (this != &other) { - // Make a new set, with other's hash/eq/alloc. - set_ = SetType(0, other.set_.hash_function(), other.set_.key_eq(), - other.get_allocator()); - set_.reserve(other.size()); - // Copy the list, with other's allocator. - list_ = ListType(other.get_allocator()); - CopyFrom(other); - } - return *this; - } - - linked_hash_map& operator=(linked_hash_map&& other) noexcept { - if (this != &other) { - using AllocTraits = std::allocator_traits<Alloc>; - if constexpr (AllocTraits::propagate_on_container_move_assignment:: - value) { - set_ = std::move(other.set_); - list_ = std::move(other.list_); - other.clear(); - } else if (AllocTraits::is_always_equal::value || - get_allocator() == other.get_allocator()) { - // The allocators are equal, so the list can take over other's nodes. - // std::list's move assignment can not be used here: with an allocator - // that does not propagate on move assignment it element-assigns, which - // is ill-formed for value_type, std::pair<const K, V>. - clear(); - set_ = std::move(other.set_); - list_.splice(list_.end(), other.list_); - other.set_.clear(); - } else if constexpr (!AllocTraits::is_always_equal::value) { - // The list can not take over other's nodes, so move each element into - // a new node allocated with this map's allocator and rebuild the index - // over them, adopting other's hash and equality state. This is the - // same pattern as raw_hash_set::move_assign. - clear(); - set_ = SetType(other.size(), other.set_.hash_function(), - other.set_.key_eq(), get_allocator()); - CopyFrom(std::move(other)); - } - } - return *this; - } + linked_hash_map() = default; + using Base::Base; linked_hash_map& operator=(std::initializer_list<value_type> values) { - clear(); - reserve(values.size()); - insert(values.begin(), values.end()); + Base::operator=(values); return *this; } - // Derive size_ from set_, as list::size might be O(N). - size_type size() const { return set_.size(); } - size_type max_size() const noexcept { return ~size_type{}; } - bool empty() const { return set_.empty(); } - - // Iteration is list-like, in insertion order. - // These are all forwarded. - iterator begin() { return list_.begin(); } - iterator end() { return list_.end(); } - const_iterator begin() const { return list_.begin(); } - const_iterator end() const { return list_.end(); } - const_iterator cbegin() const { return list_.cbegin(); } - const_iterator cend() const { return list_.cend(); } - reverse_iterator rbegin() { return list_.rbegin(); } - reverse_iterator rend() { return list_.rend(); } - const_reverse_iterator rbegin() const { return list_.rbegin(); } - const_reverse_iterator rend() const { return list_.rend(); } - const_reverse_iterator crbegin() const { return list_.crbegin(); } - const_reverse_iterator crend() const { return list_.crend(); } - reference front() { return list_.front(); } - reference back() { return list_.back(); } - const_reference front() const { return list_.front(); } - const_reference back() const { return list_.back(); } - - void pop_front() { erase(begin()); } - void pop_back() { erase(std::prev(end())); } - - ABSL_ATTRIBUTE_REINITIALIZES void clear() { - set_.clear(); - list_.clear(); - } - - void reserve(size_t n) { set_.reserve(n); } - size_t capacity() const { return set_.capacity(); } - size_t bucket_count() const { return set_.bucket_count(); } - float load_factor() const { return set_.load_factor(); } - - hasher hash_function() const { return set_.hash_function().fn_; } - key_equal key_eq() const { return set_.key_eq().fn_; } - allocator_type get_allocator() const { return list_.get_allocator(); } - - template <class K = key_type> - size_type erase(const key_arg<K>& key) { - auto found = set_.find(key); - if (found == set_.end()) return 0; - auto list_it = *found; - // Erase set entry first since it refers to the list element. - set_.erase(found); - list_.erase(list_it); - return 1; - } - - iterator erase(const_iterator position) { - auto found = set_.find(position); - assert(*found == position); - set_.erase(found); - return list_.erase(position); - } - - iterator erase(iterator position) { - return erase(static_cast<const_iterator>(position)); - } - - iterator erase(iterator first, iterator last) { - while (first != last) first = erase(first); - return first; - } - - iterator erase(const_iterator first, const_iterator last) { - while (first != last) first = erase(first); - if (first == end()) return end(); - return *set_.find(first); - } - - template <class K = key_type> - iterator find(const key_arg<K>& key) { - auto found = set_.find(key); - if (found == set_.end()) return end(); - return *found; - } - - template <class K = key_type> - const_iterator find(const key_arg<K>& key) const { - auto found = set_.find(key); - if (found == set_.end()) return end(); - return *found; - } - - template <class K = key_type> - size_type count(const key_arg<K>& key) const { - return contains(key) ? 1 : 0; - } - template <class K = key_type> - bool contains(const key_arg<K>& key) const { - return set_.contains(key); - } - template <class K = key_type> mapped_type& at(const key_arg<K>& key) { - auto it = find(key); - if (ABSL_PREDICT_FALSE(it == end())) { + auto it = this->find(key); + if (ABSL_PREDICT_FALSE(it == this->end())) { ThrowStdOutOfRange("absl::linked_hash_map::at"); } return it->second; @@ -417,36 +107,23 @@ } template <class K = key_type> - std::pair<iterator, iterator> equal_range(const key_arg<K>& key) { - auto iter = set_.find(key); - if (iter == set_.end()) return {end(), end()}; - return {*iter, std::next(*iter)}; - } - - template <class K = key_type> - std::pair<const_iterator, const_iterator> equal_range( - const key_arg<K>& key) const { - auto iter = set_.find(key); - if (iter == set_.end()) return {end(), end()}; - return {*iter, std::next(*iter)}; - } - - template <class K = key_type> mapped_type& operator[](const key_arg<K>& key) { - return LazyEmplaceInternal(key).first->second; + return this->LazyEmplaceMap(key).first->second; } template <class K = key_type, std::enable_if_t<!std::is_reference_v<K>, int> = 0> mapped_type& operator[](key_arg<K>&& key) { - return LazyEmplaceInternal(std::forward<key_arg<K>>(key)).first->second; + return this->LazyEmplaceMap(std::forward<key_arg<K>>(key)).first->second; } + using Base::insert; + std::pair<iterator, bool> insert(const value_type& v) { - return InsertInternal(v); + return this->InsertValueAt(this->end(), v); } std::pair<iterator, bool> insert(value_type&& v) { - return InsertInternal(std::move(v)); + return this->InsertValueAt(this->end(), std::move(v)); } iterator insert(const_iterator, const value_type& v) { @@ -465,20 +142,6 @@ for (; first != last; ++first) insert(*first); } - insert_return_type insert(node_type&& node) { - if (node.empty()) return {end(), false, node_type()}; - if (auto [set_itr, inserted] = set_.emplace(node.list_.begin()); inserted) { - list_.splice(list_.end(), node.list_); - return {*set_itr, true, node_type()}; - } else { - return {*set_itr, false, std::move(node)}; - } - } - - iterator insert(const_iterator, node_type&& node) { - return insert(std::move(node)).first; - } - // The last two template parameters ensure that both arguments are rvalues // (lvalue arguments are handled by the overloads below). This is necessary // for supporting bitfield arguments. @@ -536,17 +199,6 @@ return insert_or_assign(k, v).first; } - template <typename... Args> - std::pair<iterator, bool> emplace(Args&&... args) { - ListType node_donor(get_allocator()); - auto list_iter = - node_donor.emplace(node_donor.end(), std::forward<Args>(args)...); - auto ins = set_.insert(list_iter); - if (!ins.second) return {*ins.first, false}; - list_.splice(list_.end(), node_donor, list_iter); - return {list_iter, true}; - } - template <class K = key_type, class... Args, std::enable_if_t<!std::is_reference_v<K>, int> = 0> iterator try_emplace(const_iterator, key_arg<K>&& k, Args&&... args) { @@ -554,154 +206,44 @@ .first; } - template <typename... Args> - iterator emplace_hint(const_iterator, Args&&... args) { - return emplace(std::forward<Args>(args)...).first; - } - template <class K = key_type, typename... Args, std::enable_if_t<!std::is_reference_v<K>, int> = 0> std::pair<iterator, bool> try_emplace(key_arg<K>&& key, Args&&... args) { - return LazyEmplaceInternal(std::forward<key_arg<K>>(key), - std::forward<Args>(args)...); + return this->LazyEmplaceMap(std::forward<key_arg<K>>(key), + std::forward<Args>(args)...); } - template <typename H, typename E> - void merge(linked_hash_map<Key, Value, H, E, Alloc>& src) { - auto itr = src.list_.begin(); - while (itr != src.list_.end()) { - if (contains(itr->first)) { - ++itr; - } else { - insert(src.extract(itr++)); - } - } - } - - template <typename H, typename E> - void merge(linked_hash_map<Key, Value, H, E, Alloc>&& src) { - merge(src); - } - - node_type extract(const_iterator position) { - set_.erase(position->first); - ListType extracted_node_list(get_allocator()); - extracted_node_list.splice(extracted_node_list.end(), list_, position); - return node_type(std::move(extracted_node_list)); - } - - template <class K = key_type, - std::enable_if_t<!std::is_same_v<K, iterator>, int> = 0> - node_type extract(const key_arg<K>& key) { - auto node = set_.extract(key); - if (node.empty()) return node_type(); - ListType extracted_node_list(get_allocator()); - extracted_node_list.splice(extracted_node_list.end(), list_, node.value()); - return node_type(std::move(extracted_node_list)); - } + using Base::merge; template <typename H, typename E> void splice(const_iterator, linked_hash_map<Key, Value, H, E, Alloc>& list, const_iterator it) { - if (&list == this) { - list_.splice(list_.end(), list.list_, it); - } else { - insert(list.extract(it)); - } + this->SpliceFrom(list, it); } template <class K = key_type, typename... Args> std::pair<iterator, bool> try_emplace(const key_arg<K>& key, Args&&... args) { - return LazyEmplaceInternal(key, std::forward<Args>(args)...); + return this->LazyEmplaceMap(key, std::forward<Args>(args)...); } template <class K = key_type, typename... Args> iterator try_emplace(const_iterator, const key_arg<K>& key, Args&&... args) { - return LazyEmplaceInternal(key, std::forward<Args>(args)...).first; + return this->LazyEmplaceMap(key, std::forward<Args>(args)...).first; } - void swap(linked_hash_map& other) noexcept { - using std::swap; - swap(set_, other.set_); - swap(list_, other.list_); - } - - friend bool operator==(const linked_hash_map& a, const linked_hash_map& b) { - if (a.size() != b.size()) return false; - const linked_hash_map* outer = &a; - const linked_hash_map* inner = &b; - if (outer->capacity() > inner->capacity()) std::swap(outer, inner); - for (const value_type& elem : *outer) { - auto it = inner->find(elem.first); - if (it == inner->end()) return false; - if (it->second != elem.second) return false; - } - - return true; - } - - friend bool operator!=(const linked_hash_map& a, const linked_hash_map& b) { - return !(a == b); - } - - void rehash(size_t n) { set_.rehash(n); } + void swap(linked_hash_map& other) noexcept { Base::swap(other); } private: - template <typename Other> - void CopyFrom(Other&& other) { - for (auto& elem : other.list_) { - set_.insert(list_.insert(list_.end(), std::move(elem))); - } - if constexpr (!std::is_const_v<std::remove_reference_t<Other>>) { - // When moving from `other`, `std::move(elem)` above mutates the elements - // of `other.list_` in place, invalidating `other.set_`'s index over them. - // Clear `other` so its `set_` and `list_` remain consistent and empty. - other.clear(); - } - assert(set_.size() == list_.size()); - } - - template <typename U> - std::pair<iterator, bool> InsertInternal(U&& pair) { // NOLINT(build/c++11) - bool constructed = false; - auto set_iter = set_.lazy_emplace(pair.first, [&](const auto& ctor) { - constructed = true; - ctor(list_.emplace(list_.end(), std::forward<U>(pair))); - }); - return {*set_iter, constructed}; - } - template <class K, class V> std::pair<iterator, bool> InsertOrAssignInternal(K&& k, V&& v) { auto [it, inserted] = - LazyEmplaceInternal(std::forward<K>(k), std::forward<V>(v)); + this->LazyEmplaceMap(std::forward<K>(k), std::forward<V>(v)); if (!inserted) { // NOLINTNEXTLINE(bugprone-use-after-move) it->second = std::forward<V>(v); } return {it, inserted}; } - - template <typename K, typename... Args> - std::pair<iterator, bool> LazyEmplaceInternal(K&& key, Args&&... args) { - bool constructed = false; - auto set_iter = set_.lazy_emplace( - key, [this, &constructed, &key, &args...](const auto& ctor) { - auto list_iter = - list_.emplace(list_.end(), std::piecewise_construct, - std::forward_as_tuple(std::forward<K>(key)), - std::forward_as_tuple(std::forward<Args>(args)...)); - constructed = true; - ctor(list_iter); - }); - return {*set_iter, constructed}; - } - - // The set component, used for speedy lookups. - SetType set_; - - // The list component, used for maintaining insertion order. - ListType list_; }; ABSL_NAMESPACE_END
diff --git a/absl/container/linked_hash_set.h b/absl/container/linked_hash_set.h index b1c0024..a158a50 100644 --- a/absl/container/linked_hash_set.h +++ b/absl/container/linked_hash_set.h
@@ -32,379 +32,78 @@ #ifndef ABSL_CONTAINER_LINKED_HASH_SET_H_ #define ABSL_CONTAINER_LINKED_HASH_SET_H_ -#include <cassert> -#include <cstddef> #include <initializer_list> -#include <list> #include <memory> #include <type_traits> #include <utility> -#include "absl/base/attributes.h" #include "absl/base/config.h" -#include "absl/container/flat_hash_set.h" -#include "absl/container/internal/common.h" +#include "absl/container/hash_container_defaults.h" +#include "absl/container/internal/raw_linked_hash_set.h" namespace absl { ABSL_NAMESPACE_BEGIN +namespace container_internal { + +template <typename Key> +struct LinkedHashSetPolicy { + using key_type = Key; + using value_type = Key; + using DefaultHash = absl::DefaultHashContainerHash<Key>; + using DefaultEq = absl::DefaultHashContainerEq<Key>; + using DefaultAlloc = std::allocator<Key>; + static constexpr bool kIsMap = false; + + template <typename V> + static const V& key(const V& v) { + return v; + } +}; + +} // namespace container_internal template < - typename Key, typename KeyHash = typename absl::flat_hash_set<Key>::hasher, - typename KeyEq = typename absl::flat_hash_set<Key, KeyHash>::key_equal, - typename Alloc = std::allocator<Key>> -class linked_hash_set { - using KeyArgImpl = absl::container_internal::KeyArg< - absl::container_internal::IsTransparent<KeyEq>::value && - absl::container_internal::IsTransparent<KeyHash>::value>; - - public: - using key_type = Key; - using hasher = KeyHash; - using key_equal = KeyEq; - using value_type = key_type; - using allocator_type = Alloc; - using difference_type = ptrdiff_t; - - private: + typename Key, + typename KeyHash = + typename container_internal::LinkedHashSetPolicy<Key>::DefaultHash, + typename KeyEq = + typename container_internal::LinkedHashSetPolicy<Key>::DefaultEq, + typename Alloc = + typename container_internal::LinkedHashSetPolicy<Key>::DefaultAlloc> +class linked_hash_set : public container_internal::InstantiateRawLinkedHashSet< + container_internal::LinkedHashSetPolicy<Key>, + KeyHash, KeyEq, Alloc>::type { + using Base = typename linked_hash_set::raw_linked_hash_set; template <class K> - using key_arg = typename KeyArgImpl::template Select<K, key_type>; - - using ListType = std::list<key_type, Alloc>; - - template <class Fn> - class Wrapped { - template <typename K> - static const K& ToKey(const K& k) { - return k; - } - static const key_type& ToKey(typename ListType::const_iterator it) { - return *it; - } - static const key_type& ToKey(typename ListType::iterator it) { return *it; } - - Fn fn_; - - friend linked_hash_set; - - public: - using is_transparent = void; - - Wrapped() = default; - explicit Wrapped(Fn fn) : fn_(std::move(fn)) {} - - template <class... Args> - auto operator()(Args&&... args) const - -> decltype(this->fn_(ToKey(args)...)) { - return fn_(ToKey(args)...); - } - }; - using SetType = - absl::flat_hash_set<typename ListType::iterator, Wrapped<hasher>, - Wrapped<key_equal>, Alloc>; - - class NodeHandle { - public: - using allocator_type = linked_hash_set::allocator_type; - using value_type = linked_hash_set::value_type; - - constexpr NodeHandle() noexcept = default; - NodeHandle(NodeHandle&& nh) noexcept = default; - ~NodeHandle() = default; - NodeHandle& operator=(NodeHandle&& node) noexcept = default; - bool empty() const noexcept { return list_.empty(); } - explicit operator bool() const noexcept { return !empty(); } - allocator_type get_allocator() const { return list_.get_allocator(); } - value_type& value() { return list_.front(); } - void swap(NodeHandle& nh) noexcept { list_.swap(nh.list_); } - - private: - friend linked_hash_set; - - explicit NodeHandle(ListType list) : list_(std::move(list)) {} - ListType list_; - }; - - template <class Iterator, class NodeType> - struct InsertReturnType { - Iterator position; - bool inserted; - NodeType node; - }; + using key_arg = typename Base::template key_arg<K>; public: - using iterator = typename ListType::const_iterator; - using const_iterator = typename ListType::const_iterator; - using reverse_iterator = typename ListType::const_reverse_iterator; - using const_reverse_iterator = typename ListType::const_reverse_iterator; - using reference = typename ListType::reference; - using const_reference = typename ListType::const_reference; - using pointer = typename std::allocator_traits<allocator_type>::pointer; - using const_pointer = - typename std::allocator_traits<allocator_type>::const_pointer; - using size_type = typename ListType::size_type; - using node_type = NodeHandle; - using insert_return_type = InsertReturnType<iterator, node_type>; + using typename Base::allocator_type; + using typename Base::const_iterator; + using typename Base::hasher; + using typename Base::iterator; + using typename Base::key_equal; + using typename Base::key_type; + using typename Base::value_type; - linked_hash_set() {} + linked_hash_set() = default; + using Base::Base; - explicit linked_hash_set(size_t reservation_size, - const hasher& hash = hasher(), - const key_equal& eq = key_equal(), - const allocator_type& alloc = allocator_type()) - : set_(reservation_size, Wrapped<hasher>(hash), Wrapped<key_equal>(eq), - alloc), - list_(alloc) {} - - linked_hash_set(size_t reservation_size, const hasher& hash, - const allocator_type& alloc) - : linked_hash_set(reservation_size, hash, key_equal(), alloc) {} - - linked_hash_set(size_t reservation_size, const allocator_type& alloc) - : linked_hash_set(reservation_size, hasher(), key_equal(), alloc) {} - - explicit linked_hash_set(const allocator_type& alloc) - : linked_hash_set(0, hasher(), key_equal(), alloc) {} - - template <class InputIt> - linked_hash_set(InputIt first, InputIt last, size_t reservation_size = 0, - const hasher& hash = hasher(), - const key_equal& eq = key_equal(), - const allocator_type& alloc = allocator_type()) - : linked_hash_set(reservation_size, hash, eq, alloc) { - insert(first, last); - } - - template <class InputIter> - linked_hash_set(InputIter first, InputIter last, size_t reservation_size, - const hasher& hash, const allocator_type& alloc) - : linked_hash_set(first, last, reservation_size, hash, key_equal(), - alloc) {} - - template <class InputIter> - linked_hash_set(InputIter first, InputIter last, size_t reservation_size, - const allocator_type& alloc) - : linked_hash_set(first, last, reservation_size, hasher(), key_equal(), - alloc) {} - - template <class InputIt> - linked_hash_set(InputIt first, InputIt last, const allocator_type& alloc) - : linked_hash_set(first, last, /*reservation_size=*/0, hasher(), - key_equal(), alloc) {} - - linked_hash_set(std::initializer_list<key_type> init, - size_t reservation_size = 0, const hasher& hash = hasher(), - const key_equal& eq = key_equal(), - const allocator_type& alloc = allocator_type()) - : linked_hash_set(init.begin(), init.end(), reservation_size, hash, eq, - alloc) {} - - linked_hash_set(std::initializer_list<key_type> init, size_t reservation_size, - const allocator_type& alloc) - : linked_hash_set(init, reservation_size, hasher(), key_equal(), alloc) {} - - linked_hash_set(std::initializer_list<key_type> init, size_t reservation_size, - const hasher& hash, const allocator_type& alloc) - : linked_hash_set(init, reservation_size, hash, key_equal(), alloc) {} - - linked_hash_set(std::initializer_list<key_type> init, - const allocator_type& alloc) - : linked_hash_set(init, /*reservation_size=*/0, hasher(), key_equal(), - alloc) {} - - linked_hash_set(const linked_hash_set& other) - : linked_hash_set(0, other.hash_function(), other.key_eq(), - other.get_allocator()) { - reserve(other.size()); - CopyFrom(other); - } - - linked_hash_set(const linked_hash_set& other, const allocator_type& alloc) - : linked_hash_set(0, other.hash_function(), other.key_eq(), alloc) { - reserve(other.size()); - CopyFrom(other); - } - - linked_hash_set(linked_hash_set&& other) noexcept - : set_(std::move(other.set_)), list_(std::move(other.list_)) { - // Since the list and set must agree for other to end up "valid", - // explicitly clear them. - other.set_.clear(); - other.list_.clear(); - } - - linked_hash_set(linked_hash_set&& other, const allocator_type& alloc) - : linked_hash_set(0, other.hash_function(), other.key_eq(), alloc) { - if (get_allocator() == other.get_allocator()) { - *this = std::move(other); - } else { - reserve(other.size()); - CopyFrom(std::move(other)); - } - } - - linked_hash_set& operator=(const linked_hash_set& other) { - if (this != &other) { - // Make a new set, with other's hash/eq/alloc. - set_ = SetType(0, other.set_.hash_function(), - other.set_.key_eq(), other.get_allocator()); - set_.reserve(other.size()); - // Copy the list, with other's allocator. - list_ = ListType(other.get_allocator()); - CopyFrom(other); - } + linked_hash_set& operator=(std::initializer_list<value_type> values) { + Base::operator=(values); return *this; } - linked_hash_set& operator=(linked_hash_set&& other) noexcept { - if (this != &other) { - using AllocTraits = std::allocator_traits<Alloc>; - if constexpr (AllocTraits::propagate_on_container_move_assignment:: - value) { - set_ = std::move(other.set_); - list_ = std::move(other.list_); - other.clear(); - } else if (AllocTraits::is_always_equal::value || - get_allocator() == other.get_allocator()) { - // The allocators are equal, so the list can take over other's nodes. - // std::list's move assignment can not be used here: with an allocator - // that does not propagate on move assignment it element-assigns, which - // is ill-formed for value types that are not assignable, such as - // linked_hash_map's std::pair<const K, V>. - clear(); - set_ = std::move(other.set_); - list_.splice(list_.end(), other.list_); - other.set_.clear(); - } else if constexpr (!AllocTraits::is_always_equal::value) { - // The list can not take over other's nodes, so move each element into - // a new node allocated with this set's allocator and rebuild the index - // over them, adopting other's hash and equality state. This is the - // same pattern as raw_hash_set::move_assign. - clear(); - set_ = SetType(other.size(), other.set_.hash_function(), - other.set_.key_eq(), get_allocator()); - CopyFrom(std::move(other)); - } - } - return *this; - } - - linked_hash_set& operator=(std::initializer_list<key_type> values) { - clear(); - reserve(values.size()); - insert(values.begin(), values.end()); - return *this; - } - - // Derive size from set_, as list::size might be O(N). - size_type size() const { return set_.size(); } - size_type max_size() const noexcept { return ~size_type{}; } - bool empty() const { return set_.empty(); } - - // Iteration is list-like, in insertion order. - // These are all forwarded. - iterator begin() { return list_.begin(); } - iterator end() { return list_.end(); } - const_iterator begin() const { return list_.begin(); } - const_iterator end() const { return list_.end(); } - const_iterator cbegin() const { return list_.cbegin(); } - const_iterator cend() const { return list_.cend(); } - reverse_iterator rbegin() { return list_.rbegin(); } - reverse_iterator rend() { return list_.rend(); } - const_reverse_iterator rbegin() const { return list_.rbegin(); } - const_reverse_iterator rend() const { return list_.rend(); } - const_reverse_iterator crbegin() const { return list_.crbegin(); } - const_reverse_iterator crend() const { return list_.crend(); } - reference front() { return list_.front(); } - reference back() { return list_.back(); } - const_reference front() const { return list_.front(); } - const_reference back() const { return list_.back(); } - - void pop_front() { erase(begin()); } - void pop_back() { erase(std::prev(end())); } - - ABSL_ATTRIBUTE_REINITIALIZES void clear() { - set_.clear(); - list_.clear(); - } - - void reserve(size_t n) { set_.reserve(n); } - size_t bucket_count() const { return set_.bucket_count(); } - size_t capacity() const { return set_.capacity(); } - float load_factor() const { return set_.load_factor(); } - - hasher hash_function() const { return set_.hash_function().fn_; } - key_equal key_eq() const { return set_.key_eq().fn_; } - allocator_type get_allocator() const { return list_.get_allocator(); } - - template <typename K = key_type> - size_type erase(const key_arg<K>& key) { - auto found = set_.find(key); - if (found == set_.end()) return 0; - auto list_it = *found; - // Erase set entry first since it refers to the list element. - set_.erase(found); - list_.erase(list_it); - return 1; - } - - iterator erase(const_iterator position) { - auto found = set_.find(position); - assert(*found == position); - set_.erase(found); - return list_.erase(position); - } - - iterator erase(const_iterator first, const_iterator last) { - while (first != last) first = erase(first); - return first; - } - - template <typename K = key_type> - iterator find(const key_arg<K>& key) { - auto found = set_.find(key); - if (found == set_.end()) return end(); - return *found; - } - - template <typename K = key_type> - const_iterator find(const key_arg<K>& key) const { - auto found = set_.find(key); - if (found == set_.end()) return end(); - return *found; - } - - template <typename K = key_type> - size_t count(const key_arg<K>& key) const { - return contains(key) ? 1 : 0; - } - template <typename K = key_type> - bool contains(const key_arg<K>& key) const { - return set_.contains(key); - } - - template <typename K = key_type> - std::pair<iterator, iterator> equal_range(const key_arg<K>& key) { - auto iter = set_.find(key); - if (iter == set_.end()) return {end(), end()}; - return {*iter, std::next(*iter)}; - } - - template <typename K = key_type> - std::pair<const_iterator, const_iterator> equal_range( - const key_arg<K>& key) const { - auto iter = set_.find(key); - if (iter == set_.end()) return {end(), end()}; - return {*iter, std::next(*iter)}; - } + using Base::insert; template <typename K = key_type> std::pair<iterator, bool> insert(const key_arg<K>& k) { - return InsertInternal(list_.end(), k); + return this->InsertValueAt(this->end(), k); } template <typename K = key_type, std::enable_if_t<!std::is_reference_v<K>, int> = 0> std::pair<iterator, bool> insert(key_arg<K>&& k) { - return InsertInternal(list_.end(), std::move(k)); + return this->InsertValueAt(this->end(), std::move(k)); } template <typename K = key_type, @@ -413,7 +112,7 @@ !std::is_convertible_v<const key_arg<K>&, iterator>, int> = 0> iterator insert(const_iterator hint, const key_arg<K>& k) { - return InsertInternal(hint, k).first; + return this->InsertValueAt(hint, k).first; } template <typename K = key_type, std::enable_if_t< @@ -422,7 +121,7 @@ !std::is_convertible_v<key_arg<K>&&, iterator>, int> = 0> iterator insert(const_iterator hint, key_arg<K>&& k) { - return InsertInternal(hint, std::move(k)).first; + return this->InsertValueAt(hint, std::move(k)).first; } void insert(std::initializer_list<key_type> ilist) { @@ -434,129 +133,9 @@ for (; first != last; ++first) insert(*first); } - insert_return_type insert(node_type&& node) { - if (node.empty()) return {end(), false, node_type()}; - if (auto [set_itr, inserted] = set_.emplace(node.list_.begin()); inserted) { - list_.splice(list_.end(), node.list_); - return {*set_itr, true, node_type()}; - } else { - return {*set_itr, false, std::move(node)}; - } - } + using Base::merge; - iterator insert(const_iterator, node_type&& node) { - return insert(std::move(node)).first; - } - - template <typename... Args> - std::pair<iterator, bool> emplace(Args&&... args) { - return EmplaceInternal(list_.end(), std::forward<Args>(args)...); - } - - template <typename... Args> - iterator emplace_hint(const_iterator hint, Args&&... args) { - return EmplaceInternal(hint, std::forward<Args>(args)...).first; - } - - template <typename H, typename E> - void merge(linked_hash_set<Key, H, E, Alloc>& src) { - auto itr = src.list_.begin(); - while (itr != src.list_.end()) { - if (contains(*itr)) { - ++itr; - } else { - insert(src.extract(itr++)); - } - } - } - - template <typename H, typename E> - void merge(linked_hash_set<Key, H, E, Alloc>&& src) { - merge(src); - } - - node_type extract(const_iterator position) { - set_.erase(position); - ListType extracted_node_list(get_allocator()); - extracted_node_list.splice(extracted_node_list.end(), list_, position); - return node_type(std::move(extracted_node_list)); - } - - template <class K = key_type, - typename std::enable_if_t<!std::is_same_v<K, iterator>, int> = 0> - node_type extract(const key_arg<K>& key) { - auto node = set_.extract(key); - if (node.empty()) return node_type(); - ListType extracted_node_list(get_allocator()); - extracted_node_list.splice(extracted_node_list.end(), list_, node.value()); - return node_type(std::move(extracted_node_list)); - } - - void swap(linked_hash_set& other) noexcept { - using std::swap; - swap(set_, other.set_); - swap(list_, other.list_); - } - - friend bool operator==(const linked_hash_set& a, const linked_hash_set& b) { - if (a.size() != b.size()) return false; - const linked_hash_set* outer = &a; - const linked_hash_set* inner = &b; - if (outer->capacity() > inner->capacity()) std::swap(outer, inner); - for (const value_type& elem : *outer) - if (!inner->contains(elem)) return false; - return true; - } - - friend bool operator!=(const linked_hash_set& a, const linked_hash_set& b) { - return !(a == b); - } - - void rehash(size_t n) { set_.rehash(n); } - - private: - template <typename Other> - void CopyFrom(Other&& other) { - for (auto& elem : other.list_) { - set_.insert(list_.insert(list_.end(), std::move(elem))); - } - if constexpr (!std::is_const_v<std::remove_reference_t<Other>>) { - // When moving from `other`, `std::move(elem)` above mutates the elements - // of `other.list_` in place, invalidating `other.set_`'s index over them. - // Clear `other` so its `set_` and `list_` remain consistent and empty. - other.clear(); - } - assert(set_.size() == list_.size()); - } - - template <typename... Args> - std::pair<iterator, bool> EmplaceInternal(const_iterator hint, - Args&&... args) { - ListType node_donor(get_allocator()); - auto list_iter = - node_donor.emplace(node_donor.end(), std::forward<Args>(args)...); - auto ins = set_.insert(list_iter); - if (!ins.second) return {*ins.first, false}; - list_.splice(hint, node_donor, list_iter); - return {list_iter, true}; - } - - template <typename U> - std::pair<iterator, bool> InsertInternal(const_iterator hint, - U&& key) { // NOLINT(build/c++11) - bool constructed = false; - auto set_iter = set_.lazy_emplace(key, [&](const auto& ctor) { - constructed = true; - ctor(list_.emplace(hint, std::forward<U>(key))); - }); - return {*set_iter, constructed}; - } - - // The set component, used for speedy lookups. - SetType set_; - - // The list component, used for maintaining insertion order. - ListType list_; + void swap(linked_hash_set& other) noexcept { Base::swap(other); } }; ABSL_NAMESPACE_END