| // Copyright 2017 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef BASE_CONTAINERS_FLAT_TREE_H_ |
| #define BASE_CONTAINERS_FLAT_TREE_H_ |
| |
| #include <algorithm> |
| #include <iterator> |
| #include <type_traits> |
| #include <vector> |
| |
| #include "base/template_util.h" |
| |
| namespace base { |
| |
| enum FlatContainerDupes { |
| KEEP_FIRST_OF_DUPES, |
| KEEP_LAST_OF_DUPES, |
| }; |
| |
| namespace internal { |
| |
| // This is a convenience method returning true if Iterator is at least a |
| // ForwardIterator and thus supports multiple passes over a range. |
| template <class Iterator> |
| constexpr bool is_multipass() { |
| return std::is_base_of< |
| std::forward_iterator_tag, |
| typename std::iterator_traits<Iterator>::iterator_category>::value; |
| } |
| |
| // This algorithm is like unique() from the standard library except it |
| // selects only the last of consecutive values instead of the first. |
| template <class Iterator, class BinaryPredicate> |
| Iterator LastUnique(Iterator first, Iterator last, BinaryPredicate compare) { |
| Iterator replacable = std::adjacent_find(first, last, compare); |
| |
| // No duplicate elements found. |
| if (replacable == last) |
| return last; |
| |
| first = std::next(replacable); |
| |
| // Last element is a duplicate but all others are unique. |
| if (first == last) |
| return replacable; |
| |
| // This loop is based on std::adjacent_find but std::adjacent_find doesn't |
| // quite cut it. |
| for (Iterator next = std::next(first); next != last; ++next, ++first) { |
| if (!compare(*first, *next)) |
| *replacable++ = std::move(*first); |
| } |
| |
| // Last element should be copied unconditionally. |
| *replacable++ = std::move(*first); |
| return replacable; |
| } |
| |
| // Uses SFINAE to detect whether type has is_transparent member. |
| template <typename T, typename = void> |
| struct IsTransparentCompare : std::false_type {}; |
| template <typename T> |
| struct IsTransparentCompare<T, std::void_t<typename T::is_transparent>> |
| : std::true_type {}; |
| |
| // Implementation ------------------------------------------------------------- |
| |
| // Implementation of a sorted vector for backing flat_set and flat_map. Do not |
| // use directly. |
| // |
| // The use of "value" in this is like std::map uses, meaning it's the thing |
| // contained (in the case of map it's a <Kay, Mapped> pair). The Key is how |
| // things are looked up. In the case of a set, Key == Value. In the case of |
| // a map, the Key is a component of a Value. |
| // |
| // The helper class GetKeyFromValue provides the means to extract a key from a |
| // value for comparison purposes. It should implement: |
| // const Key& operator()(const Value&). |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| class flat_tree { |
| private: |
| using underlying_type = std::vector<Value>; |
| |
| public: |
| // -------------------------------------------------------------------------- |
| // Types. |
| // |
| using key_type = Key; |
| using key_compare = KeyCompare; |
| using value_type = Value; |
| |
| // Wraps the templated key comparison to compare values. |
| class value_compare : public key_compare { |
| public: |
| value_compare() = default; |
| |
| template <class Cmp> |
| explicit value_compare(Cmp&& compare_arg) |
| : KeyCompare(std::forward<Cmp>(compare_arg)) {} |
| |
| bool operator()(const value_type& left, const value_type& right) const { |
| GetKeyFromValue extractor; |
| return key_compare::operator()(extractor(left), extractor(right)); |
| } |
| }; |
| |
| using pointer = typename underlying_type::pointer; |
| using const_pointer = typename underlying_type::const_pointer; |
| using reference = typename underlying_type::reference; |
| using const_reference = typename underlying_type::const_reference; |
| using size_type = typename underlying_type::size_type; |
| using difference_type = typename underlying_type::difference_type; |
| using iterator = typename underlying_type::iterator; |
| using const_iterator = typename underlying_type::const_iterator; |
| using reverse_iterator = typename underlying_type::reverse_iterator; |
| using const_reverse_iterator = |
| typename underlying_type::const_reverse_iterator; |
| |
| // -------------------------------------------------------------------------- |
| // Lifetime. |
| // |
| // Constructors that take range guarantee O(N * log^2(N)) + O(N) complexity |
| // and take O(N * log(N)) + O(N) if extra memory is available (N is a range |
| // length). |
| // |
| // Assume that move constructors invalidate iterators and references. |
| // |
| // The constructors that take ranges, lists, and vectors do not require that |
| // the input be sorted. |
| |
| flat_tree(); |
| explicit flat_tree(const key_compare& comp); |
| |
| template <class InputIterator> |
| flat_tree(InputIterator first, |
| InputIterator last, |
| FlatContainerDupes dupe_handling = KEEP_FIRST_OF_DUPES, |
| const key_compare& comp = key_compare()); |
| |
| flat_tree(const flat_tree&); |
| flat_tree(flat_tree&&) noexcept = default; |
| |
| flat_tree(std::vector<value_type> items, |
| FlatContainerDupes dupe_handling = KEEP_FIRST_OF_DUPES, |
| const key_compare& comp = key_compare()); |
| |
| flat_tree(std::initializer_list<value_type> ilist, |
| FlatContainerDupes dupe_handling = KEEP_FIRST_OF_DUPES, |
| const key_compare& comp = key_compare()); |
| |
| ~flat_tree(); |
| |
| // -------------------------------------------------------------------------- |
| // Assignments. |
| // |
| // Assume that move assignment invalidates iterators and references. |
| |
| flat_tree& operator=(const flat_tree&); |
| flat_tree& operator=(flat_tree&&); |
| // Takes the first if there are duplicates in the initializer list. |
| flat_tree& operator=(std::initializer_list<value_type> ilist); |
| |
| // -------------------------------------------------------------------------- |
| // Memory management. |
| // |
| // Beware that shrink_to_fit() simply forwards the request to the |
| // underlying_type and its implementation is free to optimize otherwise and |
| // leave capacity() to be greater that its size. |
| // |
| // reserve() and shrink_to_fit() invalidate iterators and references. |
| |
| void reserve(size_type new_capacity); |
| size_type capacity() const; |
| void shrink_to_fit(); |
| |
| // -------------------------------------------------------------------------- |
| // Size management. |
| // |
| // clear() leaves the capacity() of the flat_tree unchanged. |
| |
| void clear(); |
| |
| size_type size() const; |
| size_type max_size() const; |
| bool empty() const; |
| |
| // -------------------------------------------------------------------------- |
| // Iterators. |
| |
| iterator begin(); |
| const_iterator begin() const; |
| const_iterator cbegin() const; |
| |
| iterator end(); |
| const_iterator end() const; |
| const_iterator cend() const; |
| |
| reverse_iterator rbegin(); |
| const_reverse_iterator rbegin() const; |
| const_reverse_iterator crbegin() const; |
| |
| reverse_iterator rend(); |
| const_reverse_iterator rend() const; |
| const_reverse_iterator crend() const; |
| |
| // -------------------------------------------------------------------------- |
| // Insert operations. |
| // |
| // Assume that every operation invalidates iterators and references. |
| // Insertion of one element can take O(size). Capacity of flat_tree grows in |
| // an implementation-defined manner. |
| // |
| // NOTE: Prefer to build a new flat_tree from a std::vector (or similar) |
| // instead of calling insert() repeatedly. |
| |
| std::pair<iterator, bool> insert(const value_type& val); |
| std::pair<iterator, bool> insert(value_type&& val); |
| |
| iterator insert(const_iterator position_hint, const value_type& x); |
| iterator insert(const_iterator position_hint, value_type&& x); |
| |
| // This method inserts the values from the range [first, last) into the |
| // current tree. In case of KEEP_LAST_OF_DUPES newly added elements can |
| // overwrite existing values. |
| template <class InputIterator> |
| void insert(InputIterator first, |
| InputIterator last, |
| FlatContainerDupes dupes = KEEP_FIRST_OF_DUPES); |
| |
| template <class... Args> |
| std::pair<iterator, bool> emplace(Args&&... args); |
| |
| template <class... Args> |
| iterator emplace_hint(const_iterator position_hint, Args&&... args); |
| |
| // -------------------------------------------------------------------------- |
| // Erase operations. |
| // |
| // Assume that every operation invalidates iterators and references. |
| // |
| // erase(position), erase(first, last) can take O(size). |
| // erase(key) may take O(size) + O(log(size)). |
| // |
| // Prefer base::EraseIf() or some other variation on erase(remove(), end()) |
| // idiom when deleting multiple non-consecutive elements. |
| |
| iterator erase(iterator position); |
| iterator erase(const_iterator position); |
| iterator erase(const_iterator first, const_iterator last); |
| template <typename K> |
| size_type erase(const K& key); |
| |
| // -------------------------------------------------------------------------- |
| // Comparators. |
| |
| key_compare key_comp() const; |
| value_compare value_comp() const; |
| |
| // -------------------------------------------------------------------------- |
| // Search operations. |
| // |
| // Search operations have O(log(size)) complexity. |
| |
| template <typename K> |
| size_type count(const K& key) const; |
| |
| template <typename K> |
| iterator find(const K& key); |
| |
| template <typename K> |
| const_iterator find(const K& key) const; |
| |
| template <typename K> |
| std::pair<iterator, iterator> equal_range(const K& key); |
| |
| template <typename K> |
| std::pair<const_iterator, const_iterator> equal_range(const K& key) const; |
| |
| template <typename K> |
| iterator lower_bound(const K& key); |
| |
| template <typename K> |
| const_iterator lower_bound(const K& key) const; |
| |
| template <typename K> |
| iterator upper_bound(const K& key); |
| |
| template <typename K> |
| const_iterator upper_bound(const K& key) const; |
| |
| // -------------------------------------------------------------------------- |
| // General operations. |
| // |
| // Assume that swap invalidates iterators and references. |
| // |
| // Implementation note: currently we use operator==() and operator<() on |
| // std::vector, because they have the same contract we need, so we use them |
| // directly for brevity and in case it is more optimal than calling equal() |
| // and lexicograhpical_compare(). If the underlying container type is changed, |
| // this code may need to be modified. |
| |
| void swap(flat_tree& other) noexcept; |
| |
| friend bool operator==(const flat_tree& lhs, const flat_tree& rhs) { |
| return lhs.impl_.body_ == rhs.impl_.body_; |
| } |
| |
| friend bool operator!=(const flat_tree& lhs, const flat_tree& rhs) { |
| return !(lhs == rhs); |
| } |
| |
| friend bool operator<(const flat_tree& lhs, const flat_tree& rhs) { |
| return lhs.impl_.body_ < rhs.impl_.body_; |
| } |
| |
| friend bool operator>(const flat_tree& lhs, const flat_tree& rhs) { |
| return rhs < lhs; |
| } |
| |
| friend bool operator>=(const flat_tree& lhs, const flat_tree& rhs) { |
| return !(lhs < rhs); |
| } |
| |
| friend bool operator<=(const flat_tree& lhs, const flat_tree& rhs) { |
| return !(lhs > rhs); |
| } |
| |
| friend void swap(flat_tree& lhs, flat_tree& rhs) noexcept { lhs.swap(rhs); } |
| |
| protected: |
| // Emplaces a new item into the tree that is known not to be in it. This |
| // is for implementing map operator[]. |
| template <class... Args> |
| iterator unsafe_emplace(const_iterator position, Args&&... args); |
| |
| // Attempts to emplace a new element with key |key|. Only if |key| is not yet |
| // present, construct value_type from |args| and insert it. Returns an |
| // iterator to the element with key |key| and a bool indicating whether an |
| // insertion happened. |
| template <class K, class... Args> |
| std::pair<iterator, bool> emplace_key_args(const K& key, Args&&... args); |
| |
| // Similar to |emplace_key_args|, but checks |hint| first as a possible |
| // insertion position. |
| template <class K, class... Args> |
| std::pair<iterator, bool> emplace_hint_key_args(const_iterator hint, |
| const K& key, |
| Args&&... args); |
| |
| private: |
| // Helper class for e.g. lower_bound that can compare a value on the left |
| // to a key on the right. |
| struct KeyValueCompare { |
| // The key comparison object must outlive this class. |
| explicit KeyValueCompare(const key_compare& key_comp) |
| : key_comp_(key_comp) {} |
| |
| template <typename T, typename U> |
| bool operator()(const T& lhs, const U& rhs) const { |
| return key_comp_(extract_if_value_type(lhs), extract_if_value_type(rhs)); |
| } |
| |
| private: |
| const key_type& extract_if_value_type(const value_type& v) const { |
| GetKeyFromValue extractor; |
| return extractor(v); |
| } |
| |
| template <typename K> |
| const K& extract_if_value_type(const K& k) const { |
| return k; |
| } |
| |
| const key_compare& key_comp_; |
| }; |
| |
| const flat_tree& as_const() { return *this; } |
| |
| iterator const_cast_it(const_iterator c_it) { |
| auto distance = std::distance(cbegin(), c_it); |
| return std::next(begin(), distance); |
| } |
| |
| // This method is inspired by both std::map::insert(P&&) and |
| // std::map::insert_or_assign(const K&, V&&). It inserts val if an equivalent |
| // element is not present yet, otherwise it overwrites. It returns an iterator |
| // to the modified element and a flag indicating whether insertion or |
| // assignment happened. |
| template <class V> |
| std::pair<iterator, bool> insert_or_assign(V&& val) { |
| auto position = lower_bound(GetKeyFromValue()(val)); |
| |
| if (position == end() || value_comp()(val, *position)) |
| return {impl_.body_.emplace(position, std::forward<V>(val)), true}; |
| |
| *position = std::forward<V>(val); |
| return {position, false}; |
| } |
| |
| // This method is similar to insert_or_assign, with the following differences: |
| // - Instead of searching [begin(), end()) it only searches [first, last). |
| // - In case no equivalent element is found, val is appended to the end of the |
| // underlying body and an iterator to the next bigger element in [first, |
| // last) is returned. |
| template <class V> |
| std::pair<iterator, bool> append_or_assign(iterator first, |
| iterator last, |
| V&& val) { |
| auto position = std::lower_bound(first, last, val, value_comp()); |
| |
| if (position == last || value_comp()(val, *position)) { |
| // emplace_back might invalidate position, which is why distance needs to |
| // be cached. |
| const difference_type distance = std::distance(begin(), position); |
| impl_.body_.emplace_back(std::forward<V>(val)); |
| return {std::next(begin(), distance), true}; |
| } |
| |
| *position = std::forward<V>(val); |
| return {position, false}; |
| } |
| |
| // This method is similar to insert, with the following differences: |
| // - Instead of searching [begin(), end()) it only searches [first, last). |
| // - In case no equivalent element is found, val is appended to the end of the |
| // underlying body and an iterator to the next bigger element in [first, |
| // last) is returned. |
| template <class V> |
| std::pair<iterator, bool> append_unique(iterator first, |
| iterator last, |
| V&& val) { |
| auto position = std::lower_bound(first, last, val, value_comp()); |
| |
| if (position == last || value_comp()(val, *position)) { |
| // emplace_back might invalidate position, which is why distance needs to |
| // be cached. |
| const difference_type distance = std::distance(begin(), position); |
| impl_.body_.emplace_back(std::forward<V>(val)); |
| return {std::next(begin(), distance), true}; |
| } |
| |
| return {position, false}; |
| } |
| |
| void sort_and_unique(iterator first, |
| iterator last, |
| FlatContainerDupes dupes) { |
| // Preserve stability for the unique code below. |
| std::stable_sort(first, last, impl_.get_value_comp()); |
| |
| auto comparator = [this](const value_type& lhs, const value_type& rhs) { |
| // lhs is already <= rhs due to sort, therefore |
| // !(lhs < rhs) <=> lhs == rhs. |
| return !impl_.get_value_comp()(lhs, rhs); |
| }; |
| |
| iterator erase_after; |
| switch (dupes) { |
| case KEEP_FIRST_OF_DUPES: |
| erase_after = std::unique(first, last, comparator); |
| break; |
| case KEEP_LAST_OF_DUPES: |
| erase_after = LastUnique(first, last, comparator); |
| break; |
| } |
| erase(erase_after, last); |
| } |
| |
| // To support comparators that may not be possible to default-construct, we |
| // have to store an instance of Compare. Using this to store all internal |
| // state of flat_tree and using private inheritance to store compare lets us |
| // take advantage of an empty base class optimization to avoid extra space in |
| // the common case when Compare has no state. |
| struct Impl : private value_compare { |
| Impl() = default; |
| |
| template <class Cmp, class... Body> |
| explicit Impl(Cmp&& compare_arg, Body&&... underlying_type_args) |
| : value_compare(std::forward<Cmp>(compare_arg)), |
| body_(std::forward<Body>(underlying_type_args)...) {} |
| |
| const value_compare& get_value_comp() const { return *this; } |
| const key_compare& get_key_comp() const { return *this; } |
| |
| underlying_type body_; |
| } impl_; |
| |
| // If the compare is not transparent we want to construct key_type once. |
| template <typename K> |
| using KeyTypeOrK = typename std:: |
| conditional<IsTransparentCompare<key_compare>::value, K, key_type>::type; |
| }; |
| |
| // ---------------------------------------------------------------------------- |
| // Lifetime. |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree() = default; |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree( |
| const KeyCompare& comp) |
| : impl_(comp) {} |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| template <class InputIterator> |
| flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree( |
| InputIterator first, |
| InputIterator last, |
| FlatContainerDupes dupe_handling, |
| const KeyCompare& comp) |
| : impl_(comp, first, last) { |
| sort_and_unique(begin(), end(), dupe_handling); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree( |
| const flat_tree&) = default; |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree( |
| std::vector<value_type> items, |
| FlatContainerDupes dupe_handling, |
| const KeyCompare& comp) |
| : impl_(comp, std::move(items)) { |
| sort_and_unique(begin(), end(), dupe_handling); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree( |
| std::initializer_list<value_type> ilist, |
| FlatContainerDupes dupe_handling, |
| const KeyCompare& comp) |
| : flat_tree(std::begin(ilist), std::end(ilist), dupe_handling, comp) {} |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::~flat_tree() = default; |
| |
| // ---------------------------------------------------------------------------- |
| // Assignments. |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::operator=( |
| const flat_tree&) -> flat_tree& = default; |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::operator=(flat_tree&&) |
| -> flat_tree& = default; |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::operator=( |
| std::initializer_list<value_type> ilist) -> flat_tree& { |
| impl_.body_ = ilist; |
| sort_and_unique(begin(), end(), KEEP_FIRST_OF_DUPES); |
| return *this; |
| } |
| |
| // ---------------------------------------------------------------------------- |
| // Memory management. |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::reserve( |
| size_type new_capacity) { |
| impl_.body_.reserve(new_capacity); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::capacity() const |
| -> size_type { |
| return impl_.body_.capacity(); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::shrink_to_fit() { |
| impl_.body_.shrink_to_fit(); |
| } |
| |
| // ---------------------------------------------------------------------------- |
| // Size management. |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::clear() { |
| impl_.body_.clear(); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::size() const |
| -> size_type { |
| return impl_.body_.size(); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::max_size() const |
| -> size_type { |
| return impl_.body_.max_size(); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| bool flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::empty() const { |
| return impl_.body_.empty(); |
| } |
| |
| // ---------------------------------------------------------------------------- |
| // Iterators. |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::begin() -> iterator { |
| return impl_.body_.begin(); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::begin() const |
| -> const_iterator { |
| return impl_.body_.begin(); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::cbegin() const |
| -> const_iterator { |
| return impl_.body_.cbegin(); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::end() -> iterator { |
| return impl_.body_.end(); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::end() const |
| -> const_iterator { |
| return impl_.body_.end(); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::cend() const |
| -> const_iterator { |
| return impl_.body_.cend(); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::rbegin() |
| -> reverse_iterator { |
| return impl_.body_.rbegin(); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::rbegin() const |
| -> const_reverse_iterator { |
| return impl_.body_.rbegin(); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::crbegin() const |
| -> const_reverse_iterator { |
| return impl_.body_.crbegin(); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::rend() |
| -> reverse_iterator { |
| return impl_.body_.rend(); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::rend() const |
| -> const_reverse_iterator { |
| return impl_.body_.rend(); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::crend() const |
| -> const_reverse_iterator { |
| return impl_.body_.crend(); |
| } |
| |
| // ---------------------------------------------------------------------------- |
| // Insert operations. |
| // |
| // Currently we use position_hint the same way as eastl or boost: |
| // https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set.h#L493 |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert( |
| const value_type& val) -> std::pair<iterator, bool> { |
| return emplace_key_args(GetKeyFromValue()(val), val); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert( |
| value_type&& val) -> std::pair<iterator, bool> { |
| return emplace_key_args(GetKeyFromValue()(val), std::move(val)); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert( |
| const_iterator position_hint, |
| const value_type& val) -> iterator { |
| return emplace_hint_key_args(position_hint, GetKeyFromValue()(val), val) |
| .first; |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert( |
| const_iterator position_hint, |
| value_type&& val) -> iterator { |
| return emplace_hint_key_args(position_hint, GetKeyFromValue()(val), |
| std::move(val)) |
| .first; |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| template <class InputIterator> |
| void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert( |
| InputIterator first, |
| InputIterator last, |
| FlatContainerDupes dupes) { |
| if (first == last) |
| return; |
| |
| // Cache results whether existing elements should be overwritten and whether |
| // inserting new elements happens immediately or will be done in a batch. |
| const bool overwrite_existing = dupes == KEEP_LAST_OF_DUPES; |
| const bool insert_inplace = |
| is_multipass<InputIterator>() && std::next(first) == last; |
| |
| if (insert_inplace) { |
| if (overwrite_existing) { |
| for (; first != last; ++first) |
| insert_or_assign(*first); |
| } else |
| std::copy(first, last, std::inserter(*this, end())); |
| return; |
| } |
| |
| // Provide a convenience lambda to obtain an iterator pointing past the last |
| // old element. This needs to be dymanic due to possible re-allocations. |
| const size_type original_size = size(); |
| auto middle = [this, original_size]() { |
| return std::next(begin(), original_size); |
| }; |
| |
| // For batch updates initialize the first insertion point. |
| difference_type pos_first_new = original_size; |
| |
| // Loop over the input range while appending new values and overwriting |
| // existing ones, if applicable. Keep track of the first insertion point. |
| if (overwrite_existing) { |
| for (; first != last; ++first) { |
| std::pair<iterator, bool> result = |
| append_or_assign(begin(), middle(), *first); |
| if (result.second) { |
| pos_first_new = |
| std::min(pos_first_new, std::distance(begin(), result.first)); |
| } |
| } |
| } else { |
| for (; first != last; ++first) { |
| std::pair<iterator, bool> result = |
| append_unique(begin(), middle(), *first); |
| if (result.second) { |
| pos_first_new = |
| std::min(pos_first_new, std::distance(begin(), result.first)); |
| } |
| } |
| } |
| |
| // The new elements might be unordered and contain duplicates, so post-process |
| // the just inserted elements and merge them with the rest, inserting them at |
| // the previously found spot. |
| sort_and_unique(middle(), end(), dupes); |
| std::inplace_merge(std::next(begin(), pos_first_new), middle(), end(), |
| value_comp()); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| template <class... Args> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace(Args&&... args) |
| -> std::pair<iterator, bool> { |
| return insert(value_type(std::forward<Args>(args)...)); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| template <class... Args> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace_hint( |
| const_iterator position_hint, |
| Args&&... args) -> iterator { |
| return insert(position_hint, value_type(std::forward<Args>(args)...)); |
| } |
| |
| // ---------------------------------------------------------------------------- |
| // Erase operations. |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( |
| iterator position) -> iterator { |
| return impl_.body_.erase(position); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( |
| const_iterator position) -> iterator { |
| return impl_.body_.erase(position); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| template <typename K> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase(const K& val) |
| -> size_type { |
| auto eq_range = equal_range(val); |
| auto res = std::distance(eq_range.first, eq_range.second); |
| erase(eq_range.first, eq_range.second); |
| return res; |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( |
| const_iterator first, |
| const_iterator last) -> iterator { |
| return impl_.body_.erase(first, last); |
| } |
| |
| // ---------------------------------------------------------------------------- |
| // Comparators. |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::key_comp() const |
| -> key_compare { |
| return impl_.get_key_comp(); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::value_comp() const |
| -> value_compare { |
| return impl_.get_value_comp(); |
| } |
| |
| // ---------------------------------------------------------------------------- |
| // Search operations. |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| template <typename K> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::count( |
| const K& key) const -> size_type { |
| auto eq_range = equal_range(key); |
| return std::distance(eq_range.first, eq_range.second); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| template <typename K> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::find(const K& key) |
| -> iterator { |
| return const_cast_it(as_const().find(key)); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| template <typename K> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::find( |
| const K& key) const -> const_iterator { |
| auto eq_range = equal_range(key); |
| return (eq_range.first == eq_range.second) ? end() : eq_range.first; |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| template <typename K> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::equal_range( |
| const K& key) -> std::pair<iterator, iterator> { |
| auto res = as_const().equal_range(key); |
| return {const_cast_it(res.first), const_cast_it(res.second)}; |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| template <typename K> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::equal_range( |
| const K& key) const -> std::pair<const_iterator, const_iterator> { |
| auto lower = lower_bound(key); |
| |
| GetKeyFromValue extractor; |
| if (lower == end() || impl_.get_key_comp()(key, extractor(*lower))) |
| return {lower, lower}; |
| |
| return {lower, std::next(lower)}; |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| template <typename K> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::lower_bound( |
| const K& key) -> iterator { |
| return const_cast_it(as_const().lower_bound(key)); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| template <typename K> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::lower_bound( |
| const K& key) const -> const_iterator { |
| static_assert(std::is_convertible<const KeyTypeOrK<K>&, const K&>::value, |
| "Requested type cannot be bound to the container's key_type " |
| "which is required for a non-transparent compare."); |
| |
| const KeyTypeOrK<K>& key_ref = key; |
| |
| KeyValueCompare key_value(impl_.get_key_comp()); |
| return std::lower_bound(begin(), end(), key_ref, key_value); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| template <typename K> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::upper_bound( |
| const K& key) -> iterator { |
| return const_cast_it(as_const().upper_bound(key)); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| template <typename K> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::upper_bound( |
| const K& key) const -> const_iterator { |
| static_assert(std::is_convertible<const KeyTypeOrK<K>&, const K&>::value, |
| "Requested type cannot be bound to the container's key_type " |
| "which is required for a non-transparent compare."); |
| |
| const KeyTypeOrK<K>& key_ref = key; |
| |
| KeyValueCompare key_value(impl_.get_key_comp()); |
| return std::upper_bound(begin(), end(), key_ref, key_value); |
| } |
| |
| // ---------------------------------------------------------------------------- |
| // General operations. |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::swap( |
| flat_tree& other) noexcept { |
| std::swap(impl_, other.impl_); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| template <class... Args> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::unsafe_emplace( |
| const_iterator position, |
| Args&&... args) -> iterator { |
| return impl_.body_.emplace(position, std::forward<Args>(args)...); |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| template <class K, class... Args> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace_key_args( |
| const K& key, |
| Args&&... args) -> std::pair<iterator, bool> { |
| auto lower = lower_bound(key); |
| if (lower == end() || key_comp()(key, GetKeyFromValue()(*lower))) |
| return {unsafe_emplace(lower, std::forward<Args>(args)...), true}; |
| return {lower, false}; |
| } |
| |
| template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| template <class K, class... Args> |
| auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace_hint_key_args( |
| const_iterator hint, |
| const K& key, |
| Args&&... args) -> std::pair<iterator, bool> { |
| GetKeyFromValue extractor; |
| if ((hint == begin() || key_comp()(extractor(*std::prev(hint)), key))) { |
| if (hint == end() || key_comp()(key, extractor(*hint))) { |
| // *(hint - 1) < key < *hint => key did not exist and hint is correct. |
| return {unsafe_emplace(hint, std::forward<Args>(args)...), true}; |
| } |
| if (!key_comp()(extractor(*hint), key)) { |
| // key == *hint => no-op, return correct hint. |
| return {const_cast_it(hint), false}; |
| } |
| } |
| // hint was not helpful, dispatch to hintless version. |
| return emplace_key_args(key, std::forward<Args>(args)...); |
| } |
| |
| // For containers like sets, the key is the same as the value. This implements |
| // the GetKeyFromValue template parameter to flat_tree for this case. |
| template <class Key> |
| struct GetKeyFromValueIdentity { |
| const Key& operator()(const Key& k) const { return k; } |
| }; |
| |
| } // namespace internal |
| |
| // ---------------------------------------------------------------------------- |
| // Free functions. |
| |
| // Erases all elements that match predicate. It has O(size) complexity. |
| template <class Key, |
| class Value, |
| class GetKeyFromValue, |
| class KeyCompare, |
| typename Predicate> |
| void EraseIf(base::internal::flat_tree<Key, Value, GetKeyFromValue, KeyCompare>& |
| container, |
| Predicate pred) { |
| container.erase(std::remove_if(container.begin(), container.end(), pred), |
| container.end()); |
| } |
| |
| } // namespace base |
| |
| #endif // BASE_CONTAINERS_FLAT_TREE_H_ |