// 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 #include #include #include #include #include #include "base/as_const.h" #include "base/check.h" #include "base/compiler_specific.h" #include "base/functional/not_fn.h" #include "base/ranges/algorithm.h" namespace base { // Tag type that allows skipping the sort_and_unique step when constructing a // flat_tree in case the underlying container is already sorted and has no // duplicate elements. struct sorted_unique_t { constexpr explicit sorted_unique_t() = default; }; extern sorted_unique_t sorted_unique; namespace internal { // Helper functions used in DCHECKs below to make sure that inputs tagged with // sorted_unique are indeed sorted and unique. template constexpr bool is_sorted_and_unique(const Range& range, Comp comp) { // Being unique implies that there are no adjacent elements that // compare equal. So this checks that each element is strictly less // than the element after it. return ranges::adjacent_find(range, base::not_fn(comp)) == ranges::end(range); } // This is a convenience trait inheriting from std::true_type if Iterator is at // least a ForwardIterator and thus supports multiple passes over a range. template using is_multipass = std::is_base_of< std::forward_iterator_tag, typename std::iterator_traits::iterator_category>; // Uses SFINAE to detect whether type has is_transparent member. template struct IsTransparentCompare : std::false_type {}; template struct IsTransparentCompare> : std::true_type {}; // Helper inspired by C++20's std::to_array to convert a C-style array to a // std::array. As opposed to the C++20 version this implementation does not // provide an overload for rvalues and does not strip cv qualifers from the // returned std::array::value_type. The returned value_type needs to be // specified explicitly, allowing the construction of std::arrays with const // elements. // // Reference: https://en.cppreference.com/w/cpp/container/array/to_array template constexpr std::array ToArrayImpl(const T (&data)[N], std::index_sequence) { return {{data[I]...}}; } template constexpr std::array ToArray(const T (&data)[N]) { return ToArrayImpl(data, std::make_index_sequence()); } // Helper that calls `container.reserve(std::size(source))`. template constexpr void ReserveIfSupported(const T&, const U&) {} template auto ReserveIfSupported(T& container, const U& source) -> decltype(container.reserve(std::size(source)), void()) { container.reserve(std::size(source)); } // std::pair's operator= is not constexpr prior to C++20. Thus we need this // small helper to invoke operator= on the .first and .second member explicitly. template constexpr void Assign(T& lhs, T&& rhs) { lhs = std::move(rhs); } template constexpr void Assign(std::pair& lhs, std::pair&& rhs) { Assign(lhs.first, std::move(rhs.first)); Assign(lhs.second, std::move(rhs.second)); } // constexpr swap implementation. std::swap is not constexpr prior to C++20. template constexpr void Swap(T& lhs, T& rhs) { T tmp = std::move(lhs); Assign(lhs, std::move(rhs)); Assign(rhs, std::move(tmp)); } // constexpr prev implementation. std::prev is not constexpr prior to C++17. template constexpr BidirIt Prev(BidirIt it) { return --it; } // constexpr next implementation. std::next is not constexpr prior to C++17. template constexpr InputIt Next(InputIt it) { return ++it; } // constexpr sort implementation. std::sort is not constexpr prior to C++20. // While insertion sort has a quadratic worst case complexity, it was chosen // because it has linear complexity for nearly sorted data, is stable, and // simple to implement. template constexpr void InsertionSort(BidirIt first, BidirIt last, const Compare& comp) { if (first == last) return; for (auto it = Next(first); it != last; ++it) { for (auto curr = it; curr != first && comp(*curr, *Prev(curr)); --curr) Swap(*curr, *Prev(curr)); } } // Implementation ------------------------------------------------------------- // Implementation for the sorted associative flat_set and flat_map using a // sorted vector as the backing store. 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 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 flat_tree { public: // -------------------------------------------------------------------------- // Types. // using key_type = Key; using key_compare = KeyCompare; using value_type = typename Container::value_type; // Wraps the templated key comparison to compare values. struct value_compare { constexpr bool operator()(const value_type& left, const value_type& right) const { GetKeyFromValue extractor; return comp(extractor(left), extractor(right)); } NO_UNIQUE_ADDRESS key_compare comp; }; using pointer = typename Container::pointer; using const_pointer = typename Container::const_pointer; using reference = typename Container::reference; using const_reference = typename Container::const_reference; using size_type = typename Container::size_type; using difference_type = typename Container::difference_type; using iterator = typename Container::iterator; using const_iterator = typename Container::const_iterator; using reverse_iterator = typename Container::reverse_iterator; using const_reverse_iterator = typename Container::const_reverse_iterator; using container_type = Container; // -------------------------------------------------------------------------- // 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. // // When passing the base::sorted_unique tag as the first argument no sort and // unique step takes places. This is useful if the underlying container // already has the required properties. flat_tree() = default; flat_tree(const flat_tree&) = default; flat_tree(flat_tree&&) = default; explicit flat_tree(const key_compare& comp); template flat_tree(InputIterator first, InputIterator last, const key_compare& comp = key_compare()); flat_tree(const container_type& items, const key_compare& comp = key_compare()); flat_tree(container_type&& items, const key_compare& comp = key_compare()); flat_tree(std::initializer_list ilist, const key_compare& comp = key_compare()); template flat_tree(sorted_unique_t, InputIterator first, InputIterator last, const key_compare& comp = key_compare()); flat_tree(sorted_unique_t, const container_type& items, const key_compare& comp = key_compare()); constexpr flat_tree(sorted_unique_t, container_type&& items, const key_compare& comp = key_compare()); flat_tree(sorted_unique_t, std::initializer_list ilist, const key_compare& comp = key_compare()); ~flat_tree() = default; // -------------------------------------------------------------------------- // Assignments. // // Assume that move assignment invalidates iterators and references. flat_tree& operator=(const flat_tree&) = default; flat_tree& operator=(flat_tree&&) = default; // Takes the first if there are duplicates in the initializer list. flat_tree& operator=(std::initializer_list ilist); // -------------------------------------------------------------------------- // Memory management. // // Beware that shrink_to_fit() simply forwards the request to the // container_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(); constexpr size_type size() const; constexpr size_type max_size() const; constexpr bool empty() const; // -------------------------------------------------------------------------- // Iterators. // // Iterators follow the ordering defined by the key comparator used in // construction of the flat_tree. iterator begin(); constexpr const_iterator begin() const; const_iterator cbegin() const; iterator end(); constexpr 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 insert(const value_type& val); std::pair 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. template void insert(InputIterator first, InputIterator last); template std::pair emplace(Args&&... args); template iterator emplace_hint(const_iterator position_hint, Args&&... args); // -------------------------------------------------------------------------- // Underlying type operations. // // Assume that either operation invalidates iterators and references. // Extracts the container_type and returns it to the caller. Ensures that // `this` is `empty()` afterwards. container_type extract() &&; // Replaces the container_type with `body`. Expects that `body` is sorted // and has no repeated elements with regard to value_comp(). void replace(container_type&& body); // -------------------------------------------------------------------------- // 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); // Artificially templatized to break ambiguity if `iterator` and // `const_iterator` are the same type. template iterator erase(const_iterator position); iterator erase(const_iterator first, const_iterator last); template size_type erase(const K& key); // -------------------------------------------------------------------------- // Comparators. constexpr key_compare key_comp() const; constexpr value_compare value_comp() const; // -------------------------------------------------------------------------- // Search operations. // // Search operations have O(log(size)) complexity. template size_type count(const K& key) const; template iterator find(const K& key); template const_iterator find(const K& key) const; template bool contains(const K& key) const; template std::pair equal_range(const K& key); template std::pair equal_range(const K& key) const; template iterator lower_bound(const K& key); template const_iterator lower_bound(const K& key) const; template iterator upper_bound(const K& key); template 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.body_ == rhs.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.body_ < rhs.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 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 std::pair emplace_key_args(const K& key, Args&&... args); // Similar to |emplace_key_args|, but checks |hint| first as a possible // insertion position. template std::pair 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& comp) : comp_(comp) {} template bool operator()(const T& lhs, const U& rhs) const { return 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 const K& extract_if_value_type(const K& k) const { return k; } const key_compare& comp_; }; 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 std::pair insert_or_assign(V&& val) { auto position = lower_bound(GetKeyFromValue()(val)); if (position == end() || value_comp()(val, *position)) return {body_.emplace(position, std::forward(val)), true}; *position = std::forward(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 std::pair 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); body_.emplace_back(std::forward(val)); return {std::next(begin(), distance), true}; } *position = std::forward(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 std::pair 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); body_.emplace_back(std::forward(val)); return {std::next(begin(), distance), true}; } return {position, false}; } void sort_and_unique(iterator first, iterator last) { // Preserve stability for the unique code below. std::stable_sort(first, last, value_comp()); // lhs is already <= rhs due to sort, therefore !(lhs < rhs) <=> lhs == rhs. auto equal_comp = base::not_fn(value_comp()); erase(std::unique(first, last, equal_comp), last); } void sort_and_unique() { sort_and_unique(begin(), end()); } // To support comparators that may not be possible to default-construct, we // have to store an instance of Compare. Since Compare commonly is stateless, // we use the NO_UNIQUE_ADDRESS attribute to save space. NO_UNIQUE_ADDRESS key_compare comp_; // Declare after |key_compare_comp_| to workaround GCC ICE. For details // see https://crbug.com/1156268 container_type body_; // If the compare is not transparent we want to construct key_type once. template using KeyTypeOrK = typename std:: conditional::value, K, key_type>::type; }; // ---------------------------------------------------------------------------- // Lifetime. template flat_tree::flat_tree( const KeyCompare& comp) : comp_(comp) {} template template flat_tree::flat_tree( InputIterator first, InputIterator last, const KeyCompare& comp) : comp_(comp), body_(first, last) { sort_and_unique(); } template flat_tree::flat_tree( const container_type& items, const KeyCompare& comp) : comp_(comp), body_(items) { sort_and_unique(); } template flat_tree::flat_tree( container_type&& items, const KeyCompare& comp) : comp_(comp), body_(std::move(items)) { sort_and_unique(); } template flat_tree::flat_tree( std::initializer_list ilist, const KeyCompare& comp) : flat_tree(std::begin(ilist), std::end(ilist), comp) {} template template flat_tree::flat_tree( sorted_unique_t, InputIterator first, InputIterator last, const KeyCompare& comp) : comp_(comp), body_(first, last) { DCHECK(is_sorted_and_unique(*this, value_comp())); } template flat_tree::flat_tree( sorted_unique_t, const container_type& items, const KeyCompare& comp) : comp_(comp), body_(items) { DCHECK(is_sorted_and_unique(*this, value_comp())); } template constexpr flat_tree::flat_tree( sorted_unique_t, container_type&& items, const KeyCompare& comp) : comp_(comp), body_(std::move(items)) { DCHECK(is_sorted_and_unique(*this, value_comp())); } template flat_tree::flat_tree( sorted_unique_t, std::initializer_list ilist, const KeyCompare& comp) : flat_tree(sorted_unique, std::begin(ilist), std::end(ilist), comp) {} // ---------------------------------------------------------------------------- // Assignments. template auto flat_tree::operator=( std::initializer_list ilist) -> flat_tree& { body_ = ilist; sort_and_unique(); return *this; } // ---------------------------------------------------------------------------- // Memory management. template void flat_tree::reserve( size_type new_capacity) { body_.reserve(new_capacity); } template auto flat_tree::capacity() const -> size_type { return body_.capacity(); } template void flat_tree::shrink_to_fit() { body_.shrink_to_fit(); } // ---------------------------------------------------------------------------- // Size management. template void flat_tree::clear() { body_.clear(); } template constexpr auto flat_tree::size() const -> size_type { return body_.size(); } template constexpr auto flat_tree::max_size() const -> size_type { return body_.max_size(); } template constexpr bool flat_tree::empty() const { return body_.empty(); } // ---------------------------------------------------------------------------- // Iterators. template auto flat_tree::begin() -> iterator { return body_.begin(); } template constexpr auto flat_tree::begin() const -> const_iterator { return ranges::begin(body_); } template auto flat_tree::cbegin() const -> const_iterator { return body_.cbegin(); } template auto flat_tree::end() -> iterator { return body_.end(); } template constexpr auto flat_tree::end() const -> const_iterator { return ranges::end(body_); } template auto flat_tree::cend() const -> const_iterator { return body_.cend(); } template auto flat_tree::rbegin() -> reverse_iterator { return body_.rbegin(); } template auto flat_tree::rbegin() const -> const_reverse_iterator { return body_.rbegin(); } template auto flat_tree::crbegin() const -> const_reverse_iterator { return body_.crbegin(); } template auto flat_tree::rend() -> reverse_iterator { return body_.rend(); } template auto flat_tree::rend() const -> const_reverse_iterator { return body_.rend(); } template auto flat_tree::crend() const -> const_reverse_iterator { return 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 auto flat_tree::insert( const value_type& val) -> std::pair { return emplace_key_args(GetKeyFromValue()(val), val); } template auto flat_tree::insert( value_type&& val) -> std::pair { return emplace_key_args(GetKeyFromValue()(val), std::move(val)); } template auto flat_tree::insert( const_iterator position_hint, const value_type& val) -> iterator { return emplace_hint_key_args(position_hint, GetKeyFromValue()(val), val) .first; } template auto flat_tree::insert( const_iterator position_hint, value_type&& val) -> iterator { return emplace_hint_key_args(position_hint, GetKeyFromValue()(val), std::move(val)) .first; } template template void flat_tree::insert( InputIterator first, InputIterator last) { if (first == last) return; // Dispatch to single element insert if the input range contains a single // element. if (is_multipass() && std::next(first) == last) { insert(end(), *first); 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. auto middle = [this, size = size()] { return std::next(begin(), static_cast(size)); }; // For batch updates initialize the first insertion point. auto pos_first_new = static_cast(size()); // Loop over the input range while appending new values and overwriting // existing ones, if applicable. Keep track of the first insertion point. for (; first != last; ++first) { std::pair 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()); std::inplace_merge(std::next(begin(), pos_first_new), middle(), end(), value_comp()); } template template auto flat_tree::emplace( Args&&... args) -> std::pair { return insert(value_type(std::forward(args)...)); } template template auto flat_tree::emplace_hint( const_iterator position_hint, Args&&... args) -> iterator { return insert(position_hint, value_type(std::forward(args)...)); } // ---------------------------------------------------------------------------- // Underlying type operations. template auto flat_tree:: extract() && -> container_type { return std::exchange(body_, container_type()); } template void flat_tree::replace( container_type&& body) { // Ensure that `body` is sorted and has no repeated elements according to // `value_comp()`. DCHECK(is_sorted_and_unique(body, value_comp())); body_ = std::move(body); } // ---------------------------------------------------------------------------- // Erase operations. template auto flat_tree::erase( iterator position) -> iterator { CHECK(position != body_.end()); return body_.erase(position); } template template auto flat_tree::erase( const_iterator position) -> iterator { CHECK(position != body_.end()); return body_.erase(position); } template template auto flat_tree::erase(const K& val) -> size_type { auto eq_range = equal_range(val); auto res = static_cast(std::distance(eq_range.first, eq_range.second)); erase(eq_range.first, eq_range.second); return res; } template auto flat_tree::erase( const_iterator first, const_iterator last) -> iterator { return body_.erase(first, last); } // ---------------------------------------------------------------------------- // Comparators. template constexpr auto flat_tree::key_comp() const -> key_compare { return comp_; } template constexpr auto flat_tree::value_comp() const -> value_compare { return value_compare{comp_}; } // ---------------------------------------------------------------------------- // Search operations. template template auto flat_tree::count( const K& key) const -> size_type { auto eq_range = equal_range(key); return static_cast(std::distance(eq_range.first, eq_range.second)); } template template auto flat_tree::find(const K& key) -> iterator { return const_cast_it(base::as_const(*this).find(key)); } template template auto flat_tree::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 template bool flat_tree::contains( const K& key) const { auto lower = lower_bound(key); return lower != end() && !comp_(key, GetKeyFromValue()(*lower)); } template template auto flat_tree::equal_range( const K& key) -> std::pair { auto res = base::as_const(*this).equal_range(key); return {const_cast_it(res.first), const_cast_it(res.second)}; } template template auto flat_tree::equal_range( const K& key) const -> std::pair { auto lower = lower_bound(key); KeyValueCompare comp(comp_); if (lower == end() || comp(key, *lower)) return {lower, lower}; return {lower, std::next(lower)}; } template template auto flat_tree::lower_bound( const K& key) -> iterator { return const_cast_it(base::as_const(*this).lower_bound(key)); } template template auto flat_tree::lower_bound( const K& key) const -> const_iterator { static_assert(std::is_convertible&, const K&>::value, "Requested type cannot be bound to the container's key_type " "which is required for a non-transparent compare."); const KeyTypeOrK& key_ref = key; KeyValueCompare comp(comp_); return ranges::lower_bound(*this, key_ref, comp); } template template auto flat_tree::upper_bound( const K& key) -> iterator { return const_cast_it(base::as_const(*this).upper_bound(key)); } template template auto flat_tree::upper_bound( const K& key) const -> const_iterator { static_assert(std::is_convertible&, const K&>::value, "Requested type cannot be bound to the container's key_type " "which is required for a non-transparent compare."); const KeyTypeOrK& key_ref = key; KeyValueCompare comp(comp_); return ranges::upper_bound(*this, key_ref, comp); } // ---------------------------------------------------------------------------- // General operations. template void flat_tree::swap( flat_tree& other) noexcept { std::swap(*this, other); } template template auto flat_tree::unsafe_emplace( const_iterator position, Args&&... args) -> iterator { return body_.emplace(position, std::forward(args)...); } template template auto flat_tree::emplace_key_args( const K& key, Args&&... args) -> std::pair { auto lower = lower_bound(key); if (lower == end() || comp_(key, GetKeyFromValue()(*lower))) return {unsafe_emplace(lower, std::forward(args)...), true}; return {lower, false}; } template template auto flat_tree:: emplace_hint_key_args(const_iterator hint, const K& key, Args&&... args) -> std::pair { KeyValueCompare comp(comp_); if ((hint == begin() || comp(*std::prev(hint), key))) { if (hint == end() || comp(key, *hint)) { // *(hint - 1) < key < *hint => key did not exist and hint is correct. return {unsafe_emplace(hint, std::forward(args)...), true}; } if (!comp(*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)...); } } // namespace internal // ---------------------------------------------------------------------------- // Free functions. // Erases all elements that match predicate. It has O(size) complexity. template size_t EraseIf( base::internal::flat_tree& container, Predicate pred) { auto it = ranges::remove_if(container, pred); size_t removed = std::distance(it, container.end()); container.erase(it, container.end()); return removed; } } // namespace base #endif // BASE_CONTAINERS_FLAT_TREE_H_