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.h229
1 files changed, 112 insertions, 117 deletions
diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h
index f2e4c3a5..137614f8 100644
--- a/absl/container/internal/btree_container.h
+++ b/absl/container/internal/btree_container.h
@@ -68,10 +68,10 @@ class btree_container {
explicit btree_container(const key_compare &comp,
const allocator_type &alloc = allocator_type())
: tree_(comp, alloc) {}
- btree_container(const btree_container &x) = default;
- btree_container(btree_container &&x) noexcept = default;
- btree_container &operator=(const btree_container &x) = default;
- btree_container &operator=(btree_container &&x) noexcept(
+ btree_container(const btree_container &other) = default;
+ btree_container(btree_container &&other) noexcept = default;
+ btree_container &operator=(const btree_container &other) = default;
+ btree_container &operator=(btree_container &&other) noexcept(
std::is_nothrow_move_assignable<Tree>::value) = default;
// Iterator routines.
@@ -154,7 +154,7 @@ class btree_container {
public:
// Utility routines.
void clear() { tree_.clear(); }
- void swap(btree_container &x) { tree_.swap(x.tree_); }
+ void swap(btree_container &other) { tree_.swap(other.tree_); }
void verify() const { tree_.verify(); }
// Size routines.
@@ -257,42 +257,40 @@ class btree_set_container : public btree_container<Tree> {
}
// Insertion routines.
- std::pair<iterator, bool> insert(const value_type &x) {
- return this->tree_.insert_unique(params_type::key(x), x);
+ std::pair<iterator, bool> insert(const value_type &v) {
+ return this->tree_.insert_unique(params_type::key(v), v);
}
- std::pair<iterator, bool> insert(value_type &&x) {
- return this->tree_.insert_unique(params_type::key(x), std::move(x));
+ std::pair<iterator, bool> insert(value_type &&v) {
+ return this->tree_.insert_unique(params_type::key(v), std::move(v));
}
template <typename... Args>
std::pair<iterator, bool> emplace(Args &&... args) {
init_type v(std::forward<Args>(args)...);
return this->tree_.insert_unique(params_type::key(v), std::move(v));
}
- iterator insert(const_iterator position, const value_type &x) {
+ iterator insert(const_iterator hint, const value_type &v) {
return this->tree_
- .insert_hint_unique(iterator(position), params_type::key(x), x)
+ .insert_hint_unique(iterator(hint), params_type::key(v), v)
.first;
}
- iterator insert(const_iterator position, value_type &&x) {
+ iterator insert(const_iterator hint, value_type &&v) {
return this->tree_
- .insert_hint_unique(iterator(position), params_type::key(x),
- std::move(x))
+ .insert_hint_unique(iterator(hint), params_type::key(v), std::move(v))
.first;
}
template <typename... Args>
- iterator emplace_hint(const_iterator position, Args &&... args) {
+ iterator emplace_hint(const_iterator hint, Args &&... args) {
init_type v(std::forward<Args>(args)...);
return this->tree_
- .insert_hint_unique(iterator(position), params_type::key(v),
- std::move(v))
+ .insert_hint_unique(iterator(hint), params_type::key(v), std::move(v))
.first;
}
template <typename InputIterator>
void insert(InputIterator b, InputIterator e) {
- this->tree_.insert_iterator_unique(b, e);
+ this->tree_.insert_iterator_unique(b, e, 0);
}
void insert(std::initializer_list<init_type> init) {
- this->tree_.insert_iterator_unique(init.begin(), init.end());
+ this->tree_.insert_iterator_unique(init.begin(), init.end(), 0);
}
insert_return_type insert(node_type &&node) {
if (!node) return {this->end(), false, node_type()};
@@ -316,6 +314,8 @@ class btree_set_container : public btree_container<Tree> {
}
// 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);
@@ -392,111 +392,72 @@ class btree_map_container : public btree_set_container<Tree> {
// Insertion routines.
// Note: the nullptr template arguments and extra `const M&` overloads allow
// for supporting bitfield arguments.
- // Note: when we call `std::forward<M>(obj)` twice, it's safe because
- // insert_unique/insert_hint_unique are guaranteed to not consume `obj` when
- // `ret.second` is false.
- template <class M>
- std::pair<iterator, bool> insert_or_assign(const key_type &k, const M &obj) {
- const std::pair<iterator, bool> ret = this->tree_.insert_unique(k, k, obj);
- if (!ret.second) ret.first->second = obj;
- return ret;
+ template <typename K = key_type, class M>
+ std::pair<iterator, bool> insert_or_assign(const key_arg<K> &k,
+ const M &obj) {
+ return insert_or_assign_impl(k, obj);
}
- template <class M, key_type * = nullptr>
- std::pair<iterator, bool> insert_or_assign(key_type &&k, const M &obj) {
- const std::pair<iterator, bool> ret =
- this->tree_.insert_unique(k, std::move(k), obj);
- if (!ret.second) ret.first->second = obj;
- return ret;
+ template <typename K = key_type, class M, K * = nullptr>
+ std::pair<iterator, bool> insert_or_assign(key_arg<K> &&k, const M &obj) {
+ return insert_or_assign_impl(std::forward<K>(k), obj);
}
- template <class M, M * = nullptr>
- std::pair<iterator, bool> insert_or_assign(const key_type &k, M &&obj) {
- const std::pair<iterator, bool> ret =
- this->tree_.insert_unique(k, k, std::forward<M>(obj));
- if (!ret.second) ret.first->second = std::forward<M>(obj);
- return ret;
+ template <typename K = key_type, class M, M * = nullptr>
+ std::pair<iterator, bool> insert_or_assign(const key_arg<K> &k, M &&obj) {
+ return insert_or_assign_impl(k, std::forward<M>(obj));
}
- template <class M, key_type * = nullptr, M * = nullptr>
- std::pair<iterator, bool> insert_or_assign(key_type &&k, M &&obj) {
- const std::pair<iterator, bool> ret =
- this->tree_.insert_unique(k, std::move(k), std::forward<M>(obj));
- if (!ret.second) ret.first->second = std::forward<M>(obj);
- return ret;
+ template <typename K = key_type, class M, K * = nullptr, M * = nullptr>
+ std::pair<iterator, bool> insert_or_assign(key_arg<K> &&k, M &&obj) {
+ return insert_or_assign_impl(std::forward<K>(k), std::forward<M>(obj));
}
- template <class M>
- iterator insert_or_assign(const_iterator position, const key_type &k,
+ template <typename K = key_type, class M>
+ iterator insert_or_assign(const_iterator hint, const key_arg<K> &k,
const M &obj) {
- const std::pair<iterator, bool> ret =
- this->tree_.insert_hint_unique(iterator(position), k, k, obj);
- if (!ret.second) ret.first->second = obj;
- return ret.first;
+ return insert_or_assign_hint_impl(hint, k, obj);
}
- template <class M, key_type * = nullptr>
- iterator insert_or_assign(const_iterator position, key_type &&k,
- const M &obj) {
- const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique(
- iterator(position), k, std::move(k), obj);
- if (!ret.second) ret.first->second = obj;
- return ret.first;
+ template <typename K = key_type, class M, K * = nullptr>
+ iterator insert_or_assign(const_iterator hint, key_arg<K> &&k, const M &obj) {
+ return insert_or_assign_hint_impl(hint, std::forward<K>(k), obj);
}
- template <class M, M * = nullptr>
- iterator insert_or_assign(const_iterator position, const key_type &k,
- M &&obj) {
- const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique(
- iterator(position), k, k, std::forward<M>(obj));
- if (!ret.second) ret.first->second = std::forward<M>(obj);
- return ret.first;
+ template <typename K = key_type, class M, M * = nullptr>
+ iterator insert_or_assign(const_iterator hint, const key_arg<K> &k, M &&obj) {
+ return insert_or_assign_hint_impl(hint, k, std::forward<M>(obj));
}
- template <class M, key_type * = nullptr, M * = nullptr>
- iterator insert_or_assign(const_iterator position, key_type &&k, M &&obj) {
- const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique(
- iterator(position), k, std::move(k), std::forward<M>(obj));
- if (!ret.second) ret.first->second = std::forward<M>(obj);
- return ret.first;
+ template <typename K = key_type, class M, K * = nullptr, M * = nullptr>
+ iterator insert_or_assign(const_iterator hint, key_arg<K> &&k, M &&obj) {
+ return insert_or_assign_hint_impl(hint, std::forward<K>(k),
+ std::forward<M>(obj));
}
- template <typename... Args>
- std::pair<iterator, bool> try_emplace(const key_type &k, Args &&... args) {
- return this->tree_.insert_unique(
- k, std::piecewise_construct, std::forward_as_tuple(k),
- std::forward_as_tuple(std::forward<Args>(args)...));
+
+ template <typename K = key_type, typename... Args,
+ typename absl::enable_if_t<
+ !std::is_convertible<K, const_iterator>::value, int> = 0>
+ std::pair<iterator, bool> try_emplace(const key_arg<K> &k, Args &&... args) {
+ return try_emplace_impl(k, std::forward<Args>(args)...);
}
- template <typename... Args>
- std::pair<iterator, bool> try_emplace(key_type &&k, Args &&... args) {
- // Note: `key_ref` exists to avoid a ClangTidy warning about moving from `k`
- // and then using `k` unsequenced. This is safe because the move is into a
- // forwarding reference and insert_unique guarantees that `key` is never
- // referenced after consuming `args`.
- const key_type &key_ref = k;
- return this->tree_.insert_unique(
- key_ref, std::piecewise_construct, std::forward_as_tuple(std::move(k)),
- std::forward_as_tuple(std::forward<Args>(args)...));
+ template <typename K = key_type, typename... Args,
+ typename absl::enable_if_t<
+ !std::is_convertible<K, const_iterator>::value, int> = 0>
+ std::pair<iterator, bool> try_emplace(key_arg<K> &&k, Args &&... args) {
+ return try_emplace_impl(std::forward<K>(k), std::forward<Args>(args)...);
}
- template <typename... Args>
- iterator try_emplace(const_iterator hint, const key_type &k,
+ template <typename K = key_type, typename... Args>
+ iterator try_emplace(const_iterator hint, const key_arg<K> &k,
Args &&... args) {
- return this->tree_
- .insert_hint_unique(iterator(hint), k, std::piecewise_construct,
- std::forward_as_tuple(k),
- std::forward_as_tuple(std::forward<Args>(args)...))
- .first;
+ return try_emplace_hint_impl(hint, k, std::forward<Args>(args)...);
}
- template <typename... Args>
- iterator try_emplace(const_iterator hint, key_type &&k, Args &&... args) {
- // Note: `key_ref` exists to avoid a ClangTidy warning about moving from `k`
- // and then using `k` unsequenced. This is safe because the move is into a
- // forwarding reference and insert_hint_unique guarantees that `key` is
- // never referenced after consuming `args`.
- const key_type &key_ref = k;
- return this->tree_
- .insert_hint_unique(iterator(hint), key_ref, std::piecewise_construct,
- std::forward_as_tuple(std::move(k)),
- std::forward_as_tuple(std::forward<Args>(args)...))
- .first;
+ template <typename K = key_type, typename... Args>
+ iterator try_emplace(const_iterator hint, key_arg<K> &&k, Args &&... args) {
+ return try_emplace_hint_impl(hint, std::forward<K>(k),
+ std::forward<Args>(args)...);
}
- mapped_type &operator[](const key_type &k) {
+
+ template <typename K = key_type>
+ mapped_type &operator[](const key_arg<K> &k) {
return try_emplace(k).first->second;
}
- mapped_type &operator[](key_type &&k) {
- return try_emplace(std::move(k)).first->second;
+ template <typename K = key_type>
+ mapped_type &operator[](key_arg<K> &&k) {
+ return try_emplace(std::forward<K>(k)).first->second;
}
template <typename K = key_type>
@@ -513,6 +474,40 @@ class btree_map_container : public btree_set_container<Tree> {
base_internal::ThrowStdOutOfRange("absl::btree_map::at");
return it->second;
}
+
+ private:
+ // Note: when we call `std::forward<M>(obj)` twice, it's safe because
+ // insert_unique/insert_hint_unique are guaranteed to not consume `obj` when
+ // `ret.second` is false.
+ template <class K, class M>
+ std::pair<iterator, bool> insert_or_assign_impl(K &&k, M &&obj) {
+ const std::pair<iterator, bool> ret =
+ this->tree_.insert_unique(k, std::forward<K>(k), std::forward<M>(obj));
+ if (!ret.second) ret.first->second = std::forward<M>(obj);
+ return ret;
+ }
+ template <class K, class M>
+ iterator insert_or_assign_hint_impl(const_iterator hint, K &&k, M &&obj) {
+ const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique(
+ iterator(hint), k, std::forward<K>(k), std::forward<M>(obj));
+ if (!ret.second) ret.first->second = std::forward<M>(obj);
+ return ret.first;
+ }
+
+ template <class K, class... Args>
+ std::pair<iterator, bool> try_emplace_impl(K &&k, Args &&... args) {
+ return this->tree_.insert_unique(
+ k, std::piecewise_construct, std::forward_as_tuple(std::forward<K>(k)),
+ std::forward_as_tuple(std::forward<Args>(args)...));
+ }
+ template <class K, class... Args>
+ iterator try_emplace_hint_impl(const_iterator hint, K &&k, Args &&... args) {
+ return this->tree_
+ .insert_hint_unique(iterator(hint), k, std::piecewise_construct,
+ std::forward_as_tuple(std::forward<K>(k)),
+ std::forward_as_tuple(std::forward<Args>(args)...))
+ .first;
+ }
};
// A common base class for btree_multiset and btree_multimap.
@@ -562,15 +557,15 @@ class btree_multiset_container : public btree_container<Tree> {
}
// Insertion routines.
- iterator insert(const value_type &x) { return this->tree_.insert_multi(x); }
- iterator insert(value_type &&x) {
- return this->tree_.insert_multi(std::move(x));
+ iterator insert(const value_type &v) { return this->tree_.insert_multi(v); }
+ iterator insert(value_type &&v) {
+ return this->tree_.insert_multi(std::move(v));
}
- iterator insert(const_iterator position, const value_type &x) {
- return this->tree_.insert_hint_multi(iterator(position), x);
+ iterator insert(const_iterator hint, const value_type &v) {
+ return this->tree_.insert_hint_multi(iterator(hint), v);
}
- iterator insert(const_iterator position, value_type &&x) {
- return this->tree_.insert_hint_multi(iterator(position), std::move(x));
+ iterator insert(const_iterator hint, value_type &&v) {
+ return this->tree_.insert_hint_multi(iterator(hint), std::move(v));
}
template <typename InputIterator>
void insert(InputIterator b, InputIterator e) {
@@ -584,9 +579,9 @@ class btree_multiset_container : public btree_container<Tree> {
return this->tree_.insert_multi(init_type(std::forward<Args>(args)...));
}
template <typename... Args>
- iterator emplace_hint(const_iterator position, Args &&... args) {
+ iterator emplace_hint(const_iterator hint, Args &&... args) {
return this->tree_.insert_hint_multi(
- iterator(position), init_type(std::forward<Args>(args)...));
+ iterator(hint), init_type(std::forward<Args>(args)...));
}
iterator insert(node_type &&node) {
if (!node) return this->end();
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-04 15:03:59 +0000