summaryrefslogtreecommitdiff
path: root/absl/container/internal/btree_container.h
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container/internal/btree_container.h')
-rw-r--r--absl/container/internal/btree_container.h99
1 files changed, 57 insertions, 42 deletions
diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h
index 137614f8..03be708e 100644
--- a/absl/container/internal/btree_container.h
+++ b/absl/container/internal/btree_container.h
@@ -23,6 +23,7 @@
#include "absl/base/internal/throw_delegate.h"
#include "absl/container/internal/btree.h" // IWYU pragma: export
#include "absl/container/internal/common.h"
+#include "absl/memory/memory.h"
#include "absl/meta/type_traits.h"
namespace absl {
@@ -68,8 +69,21 @@ class btree_container {
explicit btree_container(const key_compare &comp,
const allocator_type &alloc = allocator_type())
: tree_(comp, alloc) {}
- btree_container(const btree_container &other) = default;
- btree_container(btree_container &&other) noexcept = default;
+ explicit btree_container(const allocator_type &alloc)
+ : tree_(key_compare(), alloc) {}
+
+ btree_container(const btree_container &other)
+ : btree_container(other, absl::allocator_traits<allocator_type>::
+ select_on_container_copy_construction(
+ other.get_allocator())) {}
+ btree_container(const btree_container &other, const allocator_type &alloc)
+ : tree_(other.tree_, alloc) {}
+
+ btree_container(btree_container &&other) noexcept(
+ std::is_nothrow_move_constructible<Tree>::value) = default;
+ btree_container(btree_container &&other, const allocator_type &alloc)
+ : tree_(std::move(other.tree_), alloc) {}
+
btree_container &operator=(const btree_container &other) = default;
btree_container &operator=(btree_container &&other) noexcept(
std::is_nothrow_move_assignable<Tree>::value) = default;
@@ -90,6 +104,11 @@ class btree_container {
// Lookup routines.
template <typename K = key_type>
+ size_type count(const key_arg<K> &key) const {
+ auto equal_range = this->equal_range(key);
+ return std::distance(equal_range.first, equal_range.second);
+ }
+ template <typename K = key_type>
iterator find(const key_arg<K> &key) {
return tree_.find(key);
}
@@ -138,6 +157,11 @@ class btree_container {
iterator erase(const_iterator first, const_iterator last) {
return tree_.erase_range(iterator(first), iterator(last)).second;
}
+ template <typename K = key_type>
+ size_type erase(const key_arg<K> &key) {
+ auto equal_range = this->equal_range(key);
+ return tree_.erase_range(equal_range.first, equal_range.second).first;
+ }
// Extract routines.
node_type extract(iterator position) {
@@ -151,7 +175,6 @@ class btree_container {
return extract(iterator(position));
}
- public:
// Utility routines.
void clear() { tree_.clear(); }
void swap(btree_container &other) { tree_.swap(other.tree_); }
@@ -235,7 +258,7 @@ class btree_set_container : public btree_container<Tree> {
using super_type::super_type;
btree_set_container() {}
- // Range constructor.
+ // Range constructors.
template <class InputIterator>
btree_set_container(InputIterator b, InputIterator e,
const key_compare &comp = key_compare(),
@@ -243,18 +266,19 @@ class btree_set_container : public btree_container<Tree> {
: super_type(comp, alloc) {
insert(b, e);
}
+ template <class InputIterator>
+ btree_set_container(InputIterator b, InputIterator e,
+ const allocator_type &alloc)
+ : btree_set_container(b, e, key_compare(), alloc) {}
- // Initializer list constructor.
+ // Initializer list constructors.
btree_set_container(std::initializer_list<init_type> init,
const key_compare &comp = key_compare(),
const allocator_type &alloc = allocator_type())
: btree_set_container(init.begin(), init.end(), comp, alloc) {}
-
- // Lookup routines.
- template <typename K = key_type>
- size_type count(const key_arg<K> &key) const {
- return this->tree_.count_unique(key);
- }
+ btree_set_container(std::initializer_list<init_type> init,
+ const allocator_type &alloc)
+ : btree_set_container(init.begin(), init.end(), alloc) {}
// Insertion routines.
std::pair<iterator, bool> insert(const value_type &v) {
@@ -313,20 +337,13 @@ class btree_set_container : public btree_container<Tree> {
return res.first;
}
- // Deletion routines.
- // TODO(ezb): we should support heterogeneous comparators that have different
- // behavior for K!=key_type.
- template <typename K = key_type>
- size_type erase(const key_arg<K> &key) {
- return this->tree_.erase_unique(key);
- }
- using super_type::erase;
-
// Node extraction routines.
template <typename K = key_type>
node_type extract(const key_arg<K> &key) {
- auto it = this->find(key);
- return it == this->end() ? node_type() : extract(it);
+ const std::pair<iterator, bool> lower_and_equal =
+ this->tree_.lower_bound_equal(key);
+ return lower_and_equal.second ? extract(lower_and_equal.first)
+ : node_type();
}
using super_type::extract;
@@ -344,7 +361,7 @@ class btree_set_container : public btree_container<Tree> {
int> = 0>
void merge(btree_container<T> &src) { // NOLINT
for (auto src_it = src.begin(); src_it != src.end();) {
- if (insert(std::move(*src_it)).second) {
+ if (insert(std::move(params_type::element(src_it.slot()))).second) {
src_it = src.erase(src_it);
} else {
++src_it;
@@ -371,6 +388,7 @@ template <typename Tree>
class btree_map_container : public btree_set_container<Tree> {
using super_type = btree_set_container<Tree>;
using params_type = typename Tree::params_type;
+ friend class BtreeNodePeer;
private:
template <class K>
@@ -535,7 +553,7 @@ class btree_multiset_container : public btree_container<Tree> {
using super_type::super_type;
btree_multiset_container() {}
- // Range constructor.
+ // Range constructors.
template <class InputIterator>
btree_multiset_container(InputIterator b, InputIterator e,
const key_compare &comp = key_compare(),
@@ -543,18 +561,19 @@ class btree_multiset_container : public btree_container<Tree> {
: super_type(comp, alloc) {
insert(b, e);
}
+ template <class InputIterator>
+ btree_multiset_container(InputIterator b, InputIterator e,
+ const allocator_type &alloc)
+ : btree_multiset_container(b, e, key_compare(), alloc) {}
- // Initializer list constructor.
+ // Initializer list constructors.
btree_multiset_container(std::initializer_list<init_type> init,
const key_compare &comp = key_compare(),
const allocator_type &alloc = allocator_type())
: btree_multiset_container(init.begin(), init.end(), comp, alloc) {}
-
- // Lookup routines.
- template <typename K = key_type>
- size_type count(const key_arg<K> &key) const {
- return this->tree_.count_multi(key);
- }
+ btree_multiset_container(std::initializer_list<init_type> init,
+ const allocator_type &alloc)
+ : btree_multiset_container(init.begin(), init.end(), alloc) {}
// Insertion routines.
iterator insert(const value_type &v) { return this->tree_.insert_multi(v); }
@@ -600,18 +619,13 @@ class btree_multiset_container : public btree_container<Tree> {
return res;
}
- // Deletion routines.
- template <typename K = key_type>
- size_type erase(const key_arg<K> &key) {
- return this->tree_.erase_multi(key);
- }
- using super_type::erase;
-
// Node extraction routines.
template <typename K = key_type>
node_type extract(const key_arg<K> &key) {
- auto it = this->find(key);
- return it == this->end() ? node_type() : extract(it);
+ const std::pair<iterator, bool> lower_and_equal =
+ this->tree_.lower_bound_equal(key);
+ return lower_and_equal.second ? extract(lower_and_equal.first)
+ : node_type();
}
using super_type::extract;
@@ -627,8 +641,9 @@ class btree_multiset_container : public btree_container<Tree> {
typename T::params_type::is_map_container>>::value,
int> = 0>
void merge(btree_container<T> &src) { // NOLINT
- insert(std::make_move_iterator(src.begin()),
- std::make_move_iterator(src.end()));
+ for (auto src_it = src.begin(), end = src.end(); src_it != end; ++src_it) {
+ insert(std::move(params_type::element(src_it.slot())));
+ }
src.clear();
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-03 05:53:32 +0000