Index: base/containers/flat_set.h |
diff --git a/base/containers/flat_set.h b/base/containers/flat_set.h |
index ae444c2c8e21c38ebec295ee023a365b84b3e057..4ac935d0432cf9b6cb0b3c38519d16b81d6c761b 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 { |
@@ -85,28 +82,36 @@ template <class Key, class Compare = std::less<Key>> |
// Requires: Key is Movable, Compare is a StrictWeakOrdering on Key. |
class flat_set { |
private: |
- using underlying_type = std::vector<Key>; |
+ // In a set, the key is the same as the value. |
+ struct NullKeyExtractor { |
+ const Key& operator()(const Key& k) const { return k; } |
+ }; |
+ using tree = |
+ typename ::base::internal::flat_tree<Key, Key, NullKeyExtractor, Compare>; |
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; |
+ using key_type = typename tree::key_type; |
+ using key_compare = typename tree::key_compare; |
+ using value_type = typename tree::value_type; |
+ // Use the original Compare class rather than the one tree makes (which will |
+ // wrap the Compare class with a NoOp for a set. It's nicer for callers to |
+ // see the same type they passed in, and the wrapped class derives from |
+ // Compare so it can be converted. |
+ using value_compare = typename Compare; |
+ |
+ using pointer = typename tree::pointer; |
+ using const_pointer = typename tree::const_pointer; |
+ using reference = typename tree::reference; |
+ using const_reference = typename tree::const_reference; |
+ using size_type = typename tree::size_type; |
+ using difference_type = typename tree::difference_type; |
+ using iterator = typename tree::iterator; |
+ using const_iterator = typename tree::const_iterator; |
+ using reverse_iterator = typename tree::reverse_iterator; |
+ using const_reverse_iterator = typename tree::const_reverse_iterator; |
// -------------------------------------------------------------------------- |
// Lifetime. |
@@ -266,7 +271,7 @@ class flat_set { |
void swap(flat_set& other); |
friend bool operator==(const flat_set& lhs, const flat_set& rhs) { |
- return lhs.impl_.body_ == rhs.impl_.body_; |
+ return lhs.tree_ == rhs.tree_; |
} |
friend bool operator!=(const flat_set& lhs, const flat_set& rhs) { |
@@ -274,7 +279,7 @@ class flat_set { |
} |
friend bool operator<(const flat_set& lhs, const flat_set& rhs) { |
- return lhs.impl_.body_ < rhs.impl_.body_; |
+ return lhs.tree_ < rhs.tree_; |
} |
friend bool operator>(const flat_set& lhs, const flat_set& rhs) { |
@@ -292,43 +297,7 @@ class flat_set { |
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_; |
+ tree tree_; |
}; |
// ---------------------------------------------------------------------------- |
@@ -338,16 +307,14 @@ 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) {} |
+flat_set<Key, Compare>::flat_set(const Compare& comp) : tree_(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(); |
-} |
+ : tree_(first, last, comp) {} |
template <class Key, class Compare> |
flat_set<Key, Compare>::flat_set(const flat_set&) = default; |
@@ -375,8 +342,7 @@ 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(); |
+ tree_ = ilist; |
return *this; |
} |
@@ -385,17 +351,17 @@ auto flat_set<Key, Compare>::operator=(std::initializer_list<value_type> ilist) |
template <class Key, class Compare> |
void flat_set<Key, Compare>::reserve(size_type new_capacity) { |
- impl_.body_.reserve(new_capacity); |
+ tree_.reserve(new_capacity); |
} |
template <class Key, class Compare> |
auto flat_set<Key, Compare>::capacity() const -> size_type { |
- return impl_.body_.capacity(); |
+ return tree_.capacity(); |
} |
template <class Key, class Compare> |
void flat_set<Key, Compare>::shrink_to_fit() { |
- impl_.body_.shrink_to_fit(); |
+ tree_.shrink_to_fit(); |
} |
// ---------------------------------------------------------------------------- |
@@ -403,22 +369,22 @@ void flat_set<Key, Compare>::shrink_to_fit() { |
template <class Key, class Compare> |
void flat_set<Key, Compare>::clear() { |
- impl_.body_.clear(); |
+ tree_.clear(); |
} |
template <class Key, class Compare> |
auto flat_set<Key, Compare>::size() const -> size_type { |
- return impl_.body_.size(); |
+ return tree_.size(); |
} |
template <class Key, class Compare> |
auto flat_set<Key, Compare>::max_size() const -> size_type { |
- return impl_.body_.max_size(); |
+ return tree_.max_size(); |
} |
template <class Key, class Compare> |
bool flat_set<Key, Compare>::empty() const { |
- return impl_.body_.empty(); |
+ return tree_.empty(); |
} |
// ---------------------------------------------------------------------------- |
@@ -426,62 +392,62 @@ bool flat_set<Key, Compare>::empty() const { |
template <class Key, class Compare> |
auto flat_set<Key, Compare>::begin() -> iterator { |
- return impl_.body_.begin(); |
+ return tree_.begin(); |
} |
template <class Key, class Compare> |
auto flat_set<Key, Compare>::begin() const -> const_iterator { |
- return impl_.body_.begin(); |
+ return tree_.begin(); |
} |
template <class Key, class Compare> |
auto flat_set<Key, Compare>::cbegin() const -> const_iterator { |
- return impl_.body_.cbegin(); |
+ return tree_.cbegin(); |
} |
template <class Key, class Compare> |
auto flat_set<Key, Compare>::end() -> iterator { |
- return impl_.body_.end(); |
+ return tree_.end(); |
} |
template <class Key, class Compare> |
auto flat_set<Key, Compare>::end() const -> const_iterator { |
- return impl_.body_.end(); |
+ return tree_.end(); |
} |
template <class Key, class Compare> |
auto flat_set<Key, Compare>::cend() const -> const_iterator { |
- return impl_.body_.cend(); |
+ return tree_.cend(); |
} |
template <class Key, class Compare> |
auto flat_set<Key, Compare>::rbegin() -> reverse_iterator { |
- return impl_.body_.rbegin(); |
+ return tree_.rbegin(); |
} |
template <class Key, class Compare> |
auto flat_set<Key, Compare>::rbegin() const -> const_reverse_iterator { |
- return impl_.body_.rbegin(); |
+ return tree_.rbegin(); |
} |
template <class Key, class Compare> |
auto flat_set<Key, Compare>::crbegin() const -> const_reverse_iterator { |
- return impl_.body_.crbegin(); |
+ return tree_.crbegin(); |
} |
template <class Key, class Compare> |
auto flat_set<Key, Compare>::rend() -> reverse_iterator { |
- return impl_.body_.rend(); |
+ return tree_.rend(); |
} |
template <class Key, class Compare> |
auto flat_set<Key, Compare>::rend() const -> const_reverse_iterator { |
- return impl_.body_.rend(); |
+ return tree_.rend(); |
} |
template <class Key, class Compare> |
auto flat_set<Key, Compare>::crend() const -> const_reverse_iterator { |
- return impl_.body_.crend(); |
+ return tree_.crend(); |
} |
// ---------------------------------------------------------------------------- |
@@ -496,59 +462,39 @@ auto flat_set<Key, Compare>::crend() const -> const_reverse_iterator { |
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}; |
+ return tree_.insert(val); |
} |
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}; |
+ return tree_.insert(std::move(val)); |
} |
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; |
+ return tree_.insert(position_hint, val); |
} |
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; |
+ return tree_.insert(position_hint, std::move(val)); |
} |
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)...)); |
+ return tree_.emplace(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)...)); |
+ return tree_.emplace_hint(position_hint, std::forward<Args>(args)...); |
} |
// ---------------------------------------------------------------------------- |
@@ -556,24 +502,18 @@ auto flat_set<Key, Compare>::emplace_hint(const_iterator position_hint, |
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)); |
+ return tree_.erase(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; |
+ return tree_.erase(val); |
} |
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)); |
+ return tree_.erase(first, last); |
} |
// ---------------------------------------------------------------------------- |
@@ -581,12 +521,12 @@ auto flat_set<Key, Compare>::erase(const_iterator first, const_iterator last) |
template <class Key, class Compare> |
auto flat_set<Key, Compare>::key_comp() const -> key_compare { |
- return impl_.compare(); |
+ return tree_.key_comp(); |
} |
template <class Key, class Compare> |
auto flat_set<Key, Compare>::value_comp() const -> value_compare { |
- return impl_.compare(); |
+ return tree_.value_comp(); |
} |
// ---------------------------------------------------------------------------- |
@@ -594,59 +534,51 @@ auto flat_set<Key, Compare>::value_comp() const -> value_compare { |
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); |
+ return tree_.count(key); |
} |
template <class Key, class Compare> |
auto flat_set<Key, Compare>::find(const key_type& key) -> iterator { |
- return const_cast_it(as_const().find(key)); |
+ return tree_.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; |
+ return tree_.find(key); |
} |
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)}; |
+ return tree_.equal_range(key); |
} |
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)}; |
+ return tree_.equal_range(key); |
} |
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)); |
+ return tree_.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()); |
+ return tree_.lower_bound(key); |
} |
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)); |
+ return tree_.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()); |
+ return tree_.upper_bound(key); |
} |
// ---------------------------------------------------------------------------- |
@@ -654,9 +586,9 @@ auto flat_set<Key, Compare>::upper_bound(const key_type& key) const |
template <class Key, class Compare> |
void flat_set<Key, Compare>::swap(flat_set& other) { |
- std::swap(impl_, other.impl_); |
+ std::swap(tree_, other.tree_); |
} |
-} // namespace base |
+} // namespace base |
#endif // BASE_CONTAINERS_FLAT_SET_H_ |