diff options
Diffstat (limited to 'absl/container/internal/btree_container.h')
-rw-r--r-- | absl/container/internal/btree_container.h | 199 |
1 files changed, 96 insertions, 103 deletions
diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h index d0fc6451..3b2e8a9e 100644 --- a/absl/container/internal/btree_container.h +++ b/absl/container/internal/btree_container.h @@ -268,23 +268,21 @@ class btree_set_container : public btree_container<Tree> { 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 &v) { + iterator insert(const_iterator hint, const value_type &v) { return this->tree_ - .insert_hint_unique(iterator(position), params_type::key(v), v) + .insert_hint_unique(iterator(hint), params_type::key(v), v) .first; } - iterator insert(const_iterator position, value_type &&v) { + iterator insert(const_iterator hint, value_type &&v) { 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... 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> @@ -392,111 +390,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 +472,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. @@ -566,11 +559,11 @@ class btree_multiset_container : public btree_container<Tree> { iterator insert(value_type &&v) { return this->tree_.insert_multi(std::move(v)); } - iterator insert(const_iterator position, const value_type &v) { - return this->tree_.insert_hint_multi(iterator(position), v); + 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 &&v) { - return this->tree_.insert_hint_multi(iterator(position), std::move(v)); + 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 +577,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(); |