OLD | NEW |
1 // Copyright 2017 The Chromium Authors. All rights reserved. | 1 // Copyright 2017 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef BASE_CONTAINERS_FLAT_SET_H_ | 5 #ifndef BASE_CONTAINERS_FLAT_SET_H_ |
6 #define BASE_CONTAINERS_FLAT_SET_H_ | 6 #define BASE_CONTAINERS_FLAT_SET_H_ |
7 | 7 |
8 #include <functional> | |
9 | |
10 #include "base/containers/flat_tree.h" | 8 #include "base/containers/flat_tree.h" |
| 9 #include "base/template_util.h" |
11 | 10 |
12 namespace base { | 11 namespace base { |
13 | 12 |
14 // flat_set is a container with a std::set-like interface that stores its | 13 // flat_set is a container with a std::set-like interface that stores its |
15 // contents in a sorted vector. | 14 // contents in a sorted vector. |
16 // | 15 // |
17 // Please see //base/containers/README.md for an overview of which container | 16 // Please see //base/containers/README.md for an overview of which container |
18 // to select. | 17 // to select. |
19 // | 18 // |
20 // PROS | 19 // PROS |
21 // | 20 // |
22 // - Good memory locality. | 21 // - Good memory locality. |
23 // - Low overhead, especially for smaller sets. | 22 // - Low overhead, especially for smaller sets. |
24 // - Performance is good for more workloads than you might expect (see | 23 // - Performance is good for more workloads than you might expect (see |
25 // overview link above). | 24 // overview link above). |
| 25 // - Supports C++14 set interface. |
26 // | 26 // |
27 // CONS | 27 // CONS |
28 // | 28 // |
29 // - Inserts and removals are O(n). | 29 // - Inserts and removals are O(n). |
30 // | 30 // |
31 // IMPORTANT NOTES | 31 // IMPORTANT NOTES |
32 // | 32 // |
33 // - Iterators are invalidated across mutations. | 33 // - Iterators are invalidated across mutations. |
34 // - If possible, construct a flat_set in one operation by inserting into | 34 // - If possible, construct a flat_set in one operation by inserting into |
35 // a std::vector and moving that vector into the flat_set constructor. | 35 // a std::vector and moving that vector into the flat_set constructor. |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
75 // const_iterator end() const; | 75 // const_iterator end() const; |
76 // const_iterator cend() const; | 76 // const_iterator cend() const; |
77 // reverse_iterator rbegin(); | 77 // reverse_iterator rbegin(); |
78 // const reverse_iterator rbegin() const; | 78 // const reverse_iterator rbegin() const; |
79 // const_reverse_iterator crbegin() const; | 79 // const_reverse_iterator crbegin() const; |
80 // reverse_iterator rend(); | 80 // reverse_iterator rend(); |
81 // const_reverse_iterator rend() const; | 81 // const_reverse_iterator rend() const; |
82 // const_reverse_iterator crend() const; | 82 // const_reverse_iterator crend() const; |
83 // | 83 // |
84 // Insert and accessor functions: | 84 // Insert and accessor functions: |
85 // pair<iterator, bool> insert(const Key&); | 85 // pair<iterator, bool> insert(const key_type&); |
86 // pair<iterator, bool> insert(Key&&); | 86 // pair<iterator, bool> insert(key_type&&); |
87 // void insert(InputIterator first, InputIterator last, | 87 // void insert(InputIterator first, InputIterator last, |
88 // FlatContainerDupes); | 88 // FlatContainerDupes); |
89 // pair<iterator, bool> emplace(Args&&...); | 89 // pair<iterator, bool> emplace(Args&&...); |
90 // iterator emplace_hint(const_iterator, Args&&...); | 90 // iterator emplace_hint(const_iterator, Args&&...); |
91 // | 91 // |
92 // Erase functions: | 92 // Erase functions: |
| 93 // iterator erase(iterator); |
93 // iterator erase(const_iterator); | 94 // iterator erase(const_iterator); |
94 // iterator erase(const_iterator first, const_iterator& last); | 95 // iterator erase(const_iterator first, const_iterator& last); |
95 // size_t erase(const Key& key) | 96 // template <typename K> size_t erase(const K& key) |
96 // | 97 // |
97 // Comparators (see std::set documentation). | 98 // Comparators (see std::set documentation). |
98 // key_compare key_comp() const; | 99 // key_compare key_comp() const; |
99 // value_compare value_comp() const; | 100 // value_compare value_comp() const; |
100 // | 101 // |
101 // Search functions: | 102 // Search functions: |
102 // size_t count(const Key&) const; | 103 // template <typename K> size_t count(const K&) const; |
103 // iterator find(const Key&); | 104 // template <typename K> iterator find(const K&); |
104 // const_iterator find(const Key&) const; | 105 // template <typename K> const_iterator find(const K&) const; |
105 // pair<iterator, iterator> equal_range(Key&) | 106 // template <typename K> pair<iterator, iterator> equal_range(K&) |
106 // iterator lower_bound(const Key&); | 107 // template <typename K> iterator lower_bound(const K&); |
107 // const_iterator lower_bound(const Key&) const; | 108 // template <typename K> const_iterator lower_bound(const K&) const; |
108 // iterator upper_bound(const Key&); | 109 // template <typename K> iterator upper_bound(const K&); |
109 // const_iterator upper_bound(const Key&) const; | 110 // template <typename K> const_iterator upper_bound(const K&) const; |
110 // | 111 // |
111 // General functions: | 112 // General functions: |
112 // void swap(flat_set&&) | 113 // void swap(flat_set&&) |
113 // | 114 // |
114 // Non-member operators: | 115 // Non-member operators: |
115 // bool operator==(const flat_set&, const flat_set); | 116 // bool operator==(const flat_set&, const flat_set); |
116 // bool operator!=(const flat_set&, const flat_set); | 117 // bool operator!=(const flat_set&, const flat_set); |
117 // bool operator<(const flat_set&, const flat_set); | 118 // bool operator<(const flat_set&, const flat_set); |
118 // bool operator>(const flat_set&, const flat_set); | 119 // bool operator>(const flat_set&, const flat_set); |
119 // bool operator>=(const flat_set&, const flat_set); | 120 // bool operator>=(const flat_set&, const flat_set); |
120 // bool operator<=(const flat_set&, const flat_set); | 121 // bool operator<=(const flat_set&, const flat_set); |
121 // | 122 // |
122 template <class Key, class Compare = std::less<Key>> | 123 template <class Key, class Compare = ::base::less> |
123 using flat_set = typename ::base::internal::flat_tree< | 124 using flat_set = typename ::base::internal::flat_tree< |
124 Key, | 125 Key, |
125 Key, | 126 Key, |
126 ::base::internal::GetKeyFromValueIdentity<Key>, | 127 ::base::internal::GetKeyFromValueIdentity<Key>, |
127 Compare>; | 128 Compare>; |
128 | 129 |
129 } // namespace base | 130 } // namespace base |
130 | 131 |
131 #endif // BASE_CONTAINERS_FLAT_SET_H_ | 132 #endif // BASE_CONTAINERS_FLAT_SET_H_ |
OLD | NEW |