Extract shared raw_linked_hash_set base for linked hash containers.
absl::linked_hash_map and absl::linked_hash_set duplicate nearly identical std::list and absl::flat_hash_set container plumbing. Extract their common implementation into container_internal::raw_linked_hash_set parameterized by LinkedHashSetPolicy and LinkedHashMapPolicy while preparing to replace the backing node list and hash index.
Because constructors are now inherited via using Base::Base;, implicit class template argument deduction (CTAD) is no longer supported (for example, absl::linked_hash_set s = {1, 2, 3}; and CTAD on absl::linked_hash_map without explicit template arguments no longer deduce template parameters).
PiperOrigin-RevId: 1023620042
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..c0c35b6 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -1156,6 +1156,24 @@
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
+ PUBLIC
+)
+
absl_cc_library(
NAME
linked_hash_set
@@ -1167,9 +1185,8 @@
${ABSL_DEFAULT_LINKOPTS}
DEPS
absl::config
- absl::container_common
- absl::core_headers
- absl::flat_hash_set
+ absl::hash_container_defaults
+ absl::raw_linked_hash_set
)
absl_cc_test(
@@ -1208,9 +1225,9 @@
${ABSL_DEFAULT_LINKOPTS}
DEPS
absl::config
- absl::container_common
absl::core_headers
- absl::flat_hash_set
+ absl::hash_container_defaults
+ 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..141bb68
--- /dev/null
+++ b/absl/container/internal/raw_linked_hash_set.h
@@ -0,0 +1,603 @@
+// 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 {
+
+// Shared container implementation backing both `absl::linked_hash_set` and
+// `absl::linked_hash_map`.
+template <typename Policy, typename Hash, typename Eq, typename Alloc>
+class raw_linked_hash_set {
+ 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_); }
+
+ 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) {
+ if constexpr ((Policy::kIsMap || !kIsTransparent) &&
+ !std::is_same_v<std::decay_t<decltype(*first)>,
+ value_type>) {
+ value_type elem = *first;
+ InsertValueAt(list_.cend(), std::move(elem));
+ } else {
+ 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 value_type& 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 OtherHash, typename OtherEq>
+ void merge(raw_linked_hash_set<Policy, OtherHash, OtherEq, Alloc>& src) {
+ auto itr = src.begin();
+ while (itr != src.end()) {
+ if (contains(Policy::key(*itr))) {
+ ++itr;
+ } else {
+ insert(src.extract(itr++));
+ }
+ }
+ }
+
+ template <typename OtherHash, typename OtherEq>
+ void merge(raw_linked_hash_set<Policy, OtherHash, OtherEq, Alloc>&& 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 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 H, typename E>
+ void SpliceFrom(raw_linked_hash_set<Policy, H, E, Alloc>& list,
+ const_iterator it) {
+ if constexpr (std::is_same_v<raw_linked_hash_set<Policy, H, E, Alloc>,
+ 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 5f73a26..63b53de 100644
--- a/absl/container/linked_hash_map.h
+++ b/absl/container/linked_hash_map.h
@@ -32,380 +32,69 @@
#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::raw_linked_hash_set<
+ container_internal::LinkedHashMapPolicy<Key, Value>,
+ KeyHash, KeyEq, Alloc> {
+ 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 +106,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 +141,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)).position;
- }
-
// 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 +198,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 +205,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_map_test.cc b/absl/container/linked_hash_map_test.cc
index 7c1edc5..b87331b 100644
--- a/absl/container/linked_hash_map_test.cc
+++ b/absl/container/linked_hash_map_test.cc
@@ -18,6 +18,7 @@
#include <cstddef>
#include <cstdint>
#include <functional>
+#include <iterator>
#include <memory>
#include <stdexcept>
#include <string>
@@ -159,6 +160,15 @@
EXPECT_EQ(234, *found->second);
}
+TEST(LinkedHashMapTest, CanRangeConstructMoveOnly) {
+ std::vector<std::pair<int, std::unique_ptr<int>>> vec;
+ vec.emplace_back(1, std::make_unique<int>(10));
+ vec.emplace_back(2, std::make_unique<int>(20));
+ linked_hash_map<int, std::unique_ptr<int>> ranged(
+ std::make_move_iterator(vec.begin()), std::make_move_iterator(vec.end()));
+ EXPECT_THAT(ranged, ElementsAre(Pair(1, Pointee(10)), Pair(2, Pointee(20))));
+}
+
struct NoCopy {
explicit NoCopy(int x) : x(x) {}
NoCopy(const NoCopy&) = delete;
diff --git a/absl/container/linked_hash_set.h b/absl/container/linked_hash_set.h
index 490ed94..2273d02 100644
--- a/absl/container/linked_hash_set.h
+++ b/absl/container/linked_hash_set.h
@@ -32,379 +32,75 @@
#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::raw_linked_hash_set<
+ container_internal::LinkedHashSetPolicy<Key>, KeyHash, KeyEq, Alloc> {
+ 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::const_iterator;
+ using typename Base::iterator;
+ 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 +109,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 +118,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 +130,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)).position;
- }
-
- 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
diff --git a/absl/container/linked_hash_set_test.cc b/absl/container/linked_hash_set_test.cc
index 59a4b3b..70c83d9 100644
--- a/absl/container/linked_hash_set_test.cc
+++ b/absl/container/linked_hash_set_test.cc
@@ -181,6 +181,10 @@
s.insert(absl::string_view("bar"));
s.insert(absl::string_view("foo"));
EXPECT_THAT(s, ElementsAre("foo", "bar"));
+
+ std::vector<absl::string_view> svs = {"baz", "qux", "baz"};
+ linked_hash_set<std::string> ranged(svs.begin(), svs.end());
+ EXPECT_THAT(ranged, ElementsAre("baz", "qux"));
}
// Tests that iteration from begin() to end() works
@@ -834,6 +838,21 @@
EXPECT_THAT(s, ElementsAre(7, 2, 17, 19));
}
+TEST(LinkedHashSet, NonTransparentRangeConstructorConvertsElementsOnce) {
+ struct PolyHash {
+ size_t operator()(int x) const { return static_cast<size_t>(x) ^ 0x1234; }
+ size_t operator()(double x) const { return static_cast<size_t>(x); }
+ };
+ struct PolyEq {
+ bool operator()(int a, int b) const { return a == b; }
+ bool operator()(double a, double b) const { return a == b; }
+ };
+ std::vector<int> input = {1, 2, 1};
+ linked_hash_set<double, PolyHash, PolyEq> s(input.begin(), input.end());
+ EXPECT_THAT(s, ElementsAre(1.0, 2.0));
+ EXPECT_TRUE(s.contains(2.0));
+}
+
// Verify that emplacing and extracting nodes results in the same stateful
// allocator being used for splicing purposes, rather than another instance
// (say, a default-constructed one), which could otherwise silently corrupt