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/functional.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 // - Uses base::less which allows for an easy use with smart pointers. |
26 // | 27 // |
27 // CONS | 28 // CONS |
28 // | 29 // |
29 // - Inserts and removals are O(n). | 30 // - Inserts and removals are O(n). |
30 // | 31 // |
31 // IMPORTANT NOTES | 32 // IMPORTANT NOTES |
32 // | 33 // |
33 // - Iterators are invalidated across mutations. | 34 // - Iterators are invalidated across mutations. |
34 // - If possible, construct a flat_set in one operation by inserting into | 35 // - 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. | 36 // 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; | 76 // const_iterator end() const; |
76 // const_iterator cend() const; | 77 // const_iterator cend() const; |
77 // reverse_iterator rbegin(); | 78 // reverse_iterator rbegin(); |
78 // const reverse_iterator rbegin() const; | 79 // const reverse_iterator rbegin() const; |
79 // const_reverse_iterator crbegin() const; | 80 // const_reverse_iterator crbegin() const; |
80 // reverse_iterator rend(); | 81 // reverse_iterator rend(); |
81 // const_reverse_iterator rend() const; | 82 // const_reverse_iterator rend() const; |
82 // const_reverse_iterator crend() const; | 83 // const_reverse_iterator crend() const; |
83 // | 84 // |
84 // Insert and accessor functions: | 85 // Insert and accessor functions: |
85 // pair<iterator, bool> insert(const Key&); | 86 // pair<iterator, bool> insert(const key_type&); |
86 // pair<iterator, bool> insert(Key&&); | 87 // pair<iterator, bool> insert(key_type&&); |
87 // void insert(InputIterator first, InputIterator last, | 88 // void insert(InputIterator first, InputIterator last, |
88 // FlatContainerDupes); | 89 // FlatContainerDupes); |
| 90 // template <typename ...Args> |
89 // pair<iterator, bool> emplace(Args&&...); | 91 // pair<iterator, bool> emplace(Args&&...); |
| 92 // template <typename ...Args> |
90 // iterator emplace_hint(const_iterator, Args&&...); | 93 // iterator emplace_hint(const_iterator, Args&&...); |
91 // | 94 // |
92 // Erase functions: | 95 // Erase functions: |
| 96 // iterator erase(iterator); |
93 // iterator erase(const_iterator); | 97 // iterator erase(const_iterator); |
94 // iterator erase(const_iterator first, const_iterator& last); | 98 // iterator erase(const_iterator first, const_iterator& last); |
95 // size_t erase(const Key& key) | 99 // template <typename K> |
| 100 // size_t erase(const K& key) |
96 // | 101 // |
97 // Comparators (see std::set documentation). | 102 // Comparators (see std::set documentation). |
98 // key_compare key_comp() const; | 103 // key_compare key_comp() const; |
99 // value_compare value_comp() const; | 104 // value_compare value_comp() const; |
100 // | 105 // |
101 // Search functions: | 106 // Search functions: |
102 // size_t count(const Key&) const; | 107 // template <typename K> |
103 // iterator find(const Key&); | 108 // size_t count(const K&) const; |
104 // const_iterator find(const Key&) const; | 109 // template <typename K> |
105 // pair<iterator, iterator> equal_range(Key&) | 110 // iterator find(const K&); |
106 // iterator lower_bound(const Key&); | 111 // template <typename K> |
107 // const_iterator lower_bound(const Key&) const; | 112 // const_iterator find(const K&) const; |
108 // iterator upper_bound(const Key&); | 113 // template <typename K> |
109 // const_iterator upper_bound(const Key&) const; | 114 // pair<iterator, iterator> equal_range(K&) |
| 115 // template <typename K> |
| 116 // iterator lower_bound(const K&); |
| 117 // template <typename K> |
| 118 // const_iterator lower_bound(const K&) const; |
| 119 // template <typename K> |
| 120 // iterator upper_bound(const K&); |
| 121 // template <typename K> |
| 122 // const_iterator upper_bound(const K&) const; |
110 // | 123 // |
111 // General functions: | 124 // General functions: |
112 // void swap(flat_set&&) | 125 // void swap(flat_set&&) |
113 // | 126 // |
114 // Non-member operators: | 127 // Non-member operators: |
115 // bool operator==(const flat_set&, const flat_set); | 128 // bool operator==(const flat_set&, const flat_set); |
116 // bool operator!=(const flat_set&, const flat_set); | 129 // bool operator!=(const flat_set&, const flat_set); |
117 // bool operator<(const flat_set&, const flat_set); | 130 // bool operator<(const flat_set&, const flat_set); |
118 // bool operator>(const flat_set&, const flat_set); | 131 // bool operator>(const flat_set&, const flat_set); |
119 // bool operator>=(const flat_set&, const flat_set); | 132 // bool operator>=(const flat_set&, const flat_set); |
120 // bool operator<=(const flat_set&, const flat_set); | 133 // bool operator<=(const flat_set&, const flat_set); |
121 // | 134 // |
122 template <class Key, class Compare = std::less<Key>> | 135 template <class Key, class Compare = less> |
123 using flat_set = typename ::base::internal::flat_tree< | 136 using flat_set = typename ::base::internal::flat_tree< |
124 Key, | 137 Key, |
125 Key, | 138 Key, |
126 ::base::internal::GetKeyFromValueIdentity<Key>, | 139 ::base::internal::GetKeyFromValueIdentity<Key>, |
127 Compare>; | 140 Compare>; |
128 | 141 |
129 } // namespace base | 142 } // namespace base |
130 | 143 |
131 #endif // BASE_CONTAINERS_FLAT_SET_H_ | 144 #endif // BASE_CONTAINERS_FLAT_SET_H_ |
OLD | NEW |