Index: base/containers/flat_set.h |
diff --git a/base/containers/flat_set.h b/base/containers/flat_set.h |
index aa7e52eddbdfca8758ae32a22479ccccd046f7cd..e0a7ef714db05ef32ef9b4f38ad56ee3d9a98e42 100644 |
--- a/base/containers/flat_set.h |
+++ b/base/containers/flat_set.h |
@@ -5,10 +5,7 @@ |
#ifndef BASE_CONTAINERS_FLAT_SET_H_ |
#define BASE_CONTAINERS_FLAT_SET_H_ |
-#include <algorithm> |
-#include <functional> |
-#include <utility> |
-#include <vector> |
+#include "base/containers/flat_tree.h" |
namespace base { |
@@ -79,594 +76,85 @@ namespace base { |
// method. |
// TODO(dyaroshev): research an algorithm for range insertion crbug.com/682249. |
-template <class Key, class Compare = std::less<Key>> |
-// Meets the requirements of Container, AssociativeContainer, |
-// ReversibleContainer. |
-// Requires: Key is Movable, Compare is a StrictWeakOrdering on Key. |
-class flat_set { |
- private: |
- using underlying_type = std::vector<Key>; |
- |
- public: |
- // -------------------------------------------------------------------------- |
- // Types. |
- // |
- using key_type = Key; |
- using key_compare = Compare; |
- using value_type = Key; |
- using value_compare = Compare; |
- |
- 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. |
- |
- flat_set(); |
- explicit flat_set(const Compare& comp); |
- |
- template <class InputIterator> |
- flat_set(InputIterator first, |
- InputIterator last, |
- const Compare& comp = Compare()); |
- |
- flat_set(const flat_set&); |
- flat_set(flat_set&&); |
- |
- flat_set(std::initializer_list<value_type> ilist, |
- const Compare& comp = Compare()); |
- |
- ~flat_set(); |
- |
- // -------------------------------------------------------------------------- |
- // Assignments. |
- // |
- // Assume that move assignment invalidates iterators and references. |
- |
- flat_set& operator=(const flat_set&); |
- flat_set& operator=(flat_set&&); |
- flat_set& 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_set 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). See the Notes section in the |
- // class comments on why we do not currently implement range insertion. |
- // Capacity of flat_set grows in an implementation-defined manner. |
- // |
- // NOTE: Prefer to build a new flat_set 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); |
- |
- 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(const_iterator position); |
- iterator erase(const_iterator first, const_iterator last); |
- size_type erase(const key_type& key); |
- |
- // -------------------------------------------------------------------------- |
- // Comparators. |
- |
- key_compare key_comp() const; |
- value_compare value_comp() const; |
- |
- // -------------------------------------------------------------------------- |
- // Search operations. |
- // |
- // Search operations have O(log(size)) complexity. |
- |
- size_type count(const key_type& key) const; |
- |
- iterator find(const key_type& key); |
- const_iterator find(const key_type& key) const; |
- |
- std::pair<iterator, iterator> equal_range(const key_type& ket); |
- std::pair<const_iterator, const_iterator> equal_range( |
- const key_type& key) const; |
- |
- iterator lower_bound(const key_type& key); |
- const_iterator lower_bound(const key_type& key) const; |
- |
- iterator upper_bound(const key_type& key); |
- const_iterator upper_bound(const key_type& key) const; |
- |
- // -------------------------------------------------------------------------- |
- // General operations. |
- // |
- // Assume that swap invalidates iterators and references. |
- // |
- // As with std::set, equality and ordering operations for the whole flat_set |
- // are equivalent to using equal() and lexicographical_compare() on the key |
- // types, rather than using element-wise key_comp() as e.g. lower_bound() |
- // does. 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_set& other); |
- |
- friend bool operator==(const flat_set& lhs, const flat_set& rhs) { |
- return lhs.impl_.body_ == rhs.impl_.body_; |
- } |
- |
- friend bool operator!=(const flat_set& lhs, const flat_set& rhs) { |
- return !(lhs == rhs); |
- } |
- |
- friend bool operator<(const flat_set& lhs, const flat_set& rhs) { |
- return lhs.impl_.body_ < rhs.impl_.body_; |
- } |
- |
- friend bool operator>(const flat_set& lhs, const flat_set& rhs) { |
- return rhs < lhs; |
- } |
- |
- friend bool operator>=(const flat_set& lhs, const flat_set& rhs) { |
- return !(lhs < rhs); |
- } |
- |
- friend bool operator<=(const flat_set& lhs, const flat_set& rhs) { |
- return !(lhs > rhs); |
- } |
- |
- friend void swap(flat_set& lhs, flat_set& rhs) { lhs.swap(rhs); } |
- |
- private: |
- const flat_set& as_const() { return *this; } |
- |
- iterator const_cast_it(const_iterator c_it) { |
- auto distance = std::distance(cbegin(), c_it); |
- return std::next(begin(), distance); |
- } |
- |
- void sort_and_unique() { |
- // std::set sorts elements preserving stability because it doesn't have any |
- // performance wins in not doing that. We do, so we use an unstable sort. |
- std::sort(begin(), end(), value_comp()); |
- erase(std::unique(begin(), end(), |
- [this](const value_type& lhs, const value_type& rhs) { |
- // lhs is already <= rhs due to sort, therefore |
- // !(lhs < rhs) <=> lhs == rhs. |
- return !value_comp()(lhs, rhs); |
- }), |
- end()); |
- } |
- |
- // 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_set 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 Compare { |
- Impl() = default; |
- |
- template <class Cmp, class... Body> |
- explicit Impl(Cmp&& compare_arg, Body&&... underlying_type_args) |
- : Compare(std::forward<Cmp>(compare_arg)), |
- body_(std::forward<Body>(underlying_type_args)...) {} |
- |
- Compare compare() const { return *this; } |
- |
- underlying_type body_; |
- } impl_; |
-}; |
- |
-// ---------------------------------------------------------------------------- |
-// Lifetime. |
- |
-template <class Key, class Compare> |
-flat_set<Key, Compare>::flat_set() = default; |
- |
-template <class Key, class Compare> |
-flat_set<Key, Compare>::flat_set(const Compare& comp) : impl_(comp) {} |
- |
-template <class Key, class Compare> |
-template <class InputIterator> |
-flat_set<Key, Compare>::flat_set(InputIterator first, |
- InputIterator last, |
- const Compare& comp) |
- : impl_(comp, first, last) { |
- sort_and_unique(); |
-} |
- |
-template <class Key, class Compare> |
-flat_set<Key, Compare>::flat_set(const flat_set&) = default; |
- |
-template <class Key, class Compare> |
-flat_set<Key, Compare>::flat_set(flat_set&&) = default; |
- |
-template <class Key, class Compare> |
-flat_set<Key, Compare>::flat_set(std::initializer_list<value_type> ilist, |
- const Compare& comp) |
- : flat_set(std::begin(ilist), std::end(ilist), comp) {} |
- |
-template <class Key, class Compare> |
-flat_set<Key, Compare>::~flat_set() = default; |
- |
-// ---------------------------------------------------------------------------- |
-// Assignments. |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::operator=(const flat_set&) -> flat_set& = default; |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::operator=(flat_set &&) -> flat_set& = default; |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::operator=(std::initializer_list<value_type> ilist) |
- -> flat_set& { |
- impl_.body_ = ilist; |
- sort_and_unique(); |
- return *this; |
-} |
- |
-// ---------------------------------------------------------------------------- |
-// Memory management. |
- |
-template <class Key, class Compare> |
-void flat_set<Key, Compare>::reserve(size_type new_capacity) { |
- impl_.body_.reserve(new_capacity); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::capacity() const -> size_type { |
- return impl_.body_.capacity(); |
-} |
- |
-template <class Key, class Compare> |
-void flat_set<Key, Compare>::shrink_to_fit() { |
- impl_.body_.shrink_to_fit(); |
-} |
- |
-// ---------------------------------------------------------------------------- |
-// Size management. |
- |
-template <class Key, class Compare> |
-void flat_set<Key, Compare>::clear() { |
- impl_.body_.clear(); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::size() const -> size_type { |
- return impl_.body_.size(); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::max_size() const -> size_type { |
- return impl_.body_.max_size(); |
-} |
- |
-template <class Key, class Compare> |
-bool flat_set<Key, Compare>::empty() const { |
- return impl_.body_.empty(); |
-} |
- |
-// ---------------------------------------------------------------------------- |
-// Iterators. |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::begin() -> iterator { |
- return impl_.body_.begin(); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::begin() const -> const_iterator { |
- return impl_.body_.begin(); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::cbegin() const -> const_iterator { |
- return impl_.body_.cbegin(); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::end() -> iterator { |
- return impl_.body_.end(); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::end() const -> const_iterator { |
- return impl_.body_.end(); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::cend() const -> const_iterator { |
- return impl_.body_.cend(); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::rbegin() -> reverse_iterator { |
- return impl_.body_.rbegin(); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::rbegin() const -> const_reverse_iterator { |
- return impl_.body_.rbegin(); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::crbegin() const -> const_reverse_iterator { |
- return impl_.body_.crbegin(); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::rend() -> reverse_iterator { |
- return impl_.body_.rend(); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::rend() const -> const_reverse_iterator { |
- return impl_.body_.rend(); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::crend() const -> const_reverse_iterator { |
- return impl_.body_.crend(); |
-} |
- |
-// ---------------------------------------------------------------------------- |
-// Insert operations. |
+// QUICK REFERENCE |
// |
-// 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 |
+// Most of the core functionality is inherited from flat_tree. Please see |
+// flat_tree.h for more details for most of these functions. As a quick |
+// reference, the functions available are: |
// |
-// We duplicate code between copy and move version so that we can avoid |
-// creating a temporary value. |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::insert(const value_type& val) |
- -> std::pair<iterator, bool> { |
- auto position = lower_bound(val); |
- |
- if (position == end() || value_comp()(val, *position)) |
- return {impl_.body_.insert(position, val), true}; |
- |
- return {position, false}; |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::insert(value_type&& val) |
- -> std::pair<iterator, bool> { |
- auto position = lower_bound(val); |
- |
- if (position == end() || value_comp()(val, *position)) |
- return {impl_.body_.insert(position, std::move(val)), true}; |
- |
- return {position, false}; |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::insert(const_iterator position_hint, |
- const value_type& val) -> iterator { |
- if (position_hint == end() || value_comp()(val, *position_hint)) { |
- if (position_hint == begin() || value_comp()(*(position_hint - 1), val)) |
- // We have to cast away const because of crbug.com/677044. |
- return impl_.body_.insert(const_cast_it(position_hint), val); |
- } |
- return insert(val).first; |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::insert(const_iterator position_hint, |
- value_type&& val) -> iterator { |
- if (position_hint == end() || value_comp()(val, *position_hint)) { |
- if (position_hint == begin() || value_comp()(*(position_hint - 1), val)) |
- // We have to cast away const because of crbug.com/677044. |
- return impl_.body_.insert(const_cast_it(position_hint), std::move(val)); |
- } |
- return insert(std::move(val)).first; |
-} |
- |
-template <class Key, class Compare> |
-template <class... Args> |
-auto flat_set<Key, Compare>::emplace(Args&&... args) |
- -> std::pair<iterator, bool> { |
- return insert(value_type(std::forward<Args>(args)...)); |
-} |
- |
-template <class Key, class Compare> |
-template <class... Args> |
-auto flat_set<Key, Compare>::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 Compare> |
-auto flat_set<Key, Compare>::erase(const_iterator position) -> iterator { |
- // We have to cast away const because of crbug.com/677044. |
- return impl_.body_.erase(const_cast_it(position)); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::erase(const key_type& val) -> size_type { |
- auto eq_range = equal_range(val); |
- auto res = std::distance(eq_range.first, eq_range.second); |
- // We have to cast away const because of crbug.com/677044. |
- erase(const_cast_it(eq_range.first), const_cast_it(eq_range.second)); |
- return res; |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::erase(const_iterator first, const_iterator last) |
- -> iterator { |
- // We have to cast away const because of crbug.com/677044. |
- return impl_.body_.erase(const_cast_it(first), const_cast_it(last)); |
-} |
- |
-// ---------------------------------------------------------------------------- |
-// Comparators. |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::key_comp() const -> key_compare { |
- return impl_.compare(); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::value_comp() const -> value_compare { |
- return impl_.compare(); |
-} |
- |
-// ---------------------------------------------------------------------------- |
-// Search operations. |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::count(const key_type& key) const -> size_type { |
- auto eq_range = equal_range(key); |
- return std::distance(eq_range.first, eq_range.second); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::find(const key_type& key) -> iterator { |
- return const_cast_it(as_const().find(key)); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::find(const key_type& 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 Compare> |
-auto flat_set<Key, Compare>::equal_range(const key_type& 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 Compare> |
-auto flat_set<Key, Compare>::equal_range(const key_type& key) const |
- -> std::pair<const_iterator, const_iterator> { |
- auto lower = lower_bound(key); |
- |
- if (lower == end() || key_comp()(key, *lower)) |
- return {lower, lower}; |
- |
- return {lower, std::next(lower)}; |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::lower_bound(const key_type& key) -> iterator { |
- return const_cast_it(as_const().lower_bound(key)); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::lower_bound(const key_type& key) const |
- -> const_iterator { |
- return std::lower_bound(begin(), end(), key, key_comp()); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::upper_bound(const key_type& key) -> iterator { |
- return const_cast_it(as_const().upper_bound(key)); |
-} |
- |
-template <class Key, class Compare> |
-auto flat_set<Key, Compare>::upper_bound(const key_type& key) const |
- -> const_iterator { |
- return std::upper_bound(begin(), end(), key, key_comp()); |
-} |
- |
-// ---------------------------------------------------------------------------- |
-// General operations. |
- |
-template <class Key, class Compare> |
-void flat_set<Key, Compare>::swap(flat_set& other) { |
- std::swap(impl_, other.impl_); |
-} |
- |
-// ---------------------------------------------------------------------------- |
-// Free functions. |
- |
-// Erases all elements that match predicate. It has O(size) complexity. |
-template <typename Key, typename Compare, typename Predicate> |
-void EraseIf(base::flat_set<Key, Compare>& container, Predicate pred) { |
- container.erase(std::remove_if(container.begin(), container.end(), pred), |
- container.end()); |
-} |
+// Assignment functions: |
+// flat_set& operator=(const flat_set&); |
+// flat_set& operator=(flat_set&&); |
+// flat_set& operator=(initializer_list<Key>); |
+// |
+// Memory management functions: |
+// void reserve(size_t); |
+// size_t capacity() const; |
+// void shrink_to_fit(); |
+// |
+// Size management functions: |
+// void clear(); |
+// size_t size() const; |
+// size_t max_size() const; |
+// bool empty() const; |
+// |
+// Iterator functions: |
+// 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 and accessor functions: |
+// pair<iterator, bool> insert(const Key&); |
+// pair<iterator, bool> insert(Key&&); |
+// pair<iterator, bool> emplace(Args&&...); |
+// iterator emplace_hint(const_iterator, Args&&...); |
+// |
+// Erase functions: |
+// iterator erase(const_iterator); |
+// iterator erase(const_iterator first, const_iterator& last); |
+// size_t erase(const Key& key) |
+// |
+// Comparators (see std::set documentation). |
+// key_compare key_comp() const; |
+// value_compare value_comp() const; |
+// |
+// Search functions: |
+// size_t count(const Key&) const; |
+// iterator find(const Key&); |
+// const_iterator find(const Key&) const; |
+// pair<iterator, iterator> equal_range(Key&) |
+// iterator lower_bound(const Key&); |
+// const_iterator lower_bound(const Key&) const; |
+// iterator upper_bound(const Key&); |
+// const_iterator upper_bound(const Key&) const; |
+// |
+// General functions |
+// void swap(flat_set&&) |
+// |
+// Non-member operators: |
+// bool operator==(const flat_set&, const flat_set); |
+// bool operator!=(const flat_set&, const flat_set); |
+// bool operator<(const flat_set&, const flat_set); |
+// bool operator>(const flat_set&, const flat_set); |
+// bool operator>=(const flat_set&, const flat_set); |
+// bool operator<=(const flat_set&, const flat_set); |
+// |
+template <class Key, class Compare = std::less<Key>> |
+using flat_set = typename ::base::internal::flat_tree< |
+ Key, |
+ Key, |
+ ::base::internal::GetKeyFromValueIdentity<Key>, |
+ Compare>; |
-} // namespace base |
+} // namespace base |
#endif // BASE_CONTAINERS_FLAT_SET_H_ |