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_MAP_H_ | 5 #ifndef BASE_CONTAINERS_FLAT_MAP_H_ |
6 #define BASE_CONTAINERS_FLAT_MAP_H_ | 6 #define BASE_CONTAINERS_FLAT_MAP_H_ |
7 | 7 |
8 #include <utility> | 8 #include <utility> |
9 | 9 |
10 #include "base/containers/flat_tree.h" | 10 #include "base/containers/flat_tree.h" |
11 #include "base/logging.h" | 11 #include "base/logging.h" |
| 12 #include "base/template_util.h" |
12 | 13 |
13 namespace base { | 14 namespace base { |
14 | 15 |
15 namespace internal { | 16 namespace internal { |
16 | 17 |
17 // An implementation of the flat_tree GetKeyFromValue template parameter that | 18 // An implementation of the flat_tree GetKeyFromValue template parameter that |
18 // extracts the key as the first element of a pair. | 19 // extracts the key as the first element of a pair. |
19 template <class Key, class Mapped> | 20 template <class Key, class Mapped> |
20 struct GetKeyFromValuePairFirst { | 21 struct GetKeyFromValuePairFirst { |
21 const Key& operator()(const std::pair<Key, Mapped>& p) const { | 22 const Key& operator()(const std::pair<Key, Mapped>& p) const { |
22 return p.first; | 23 return p.first; |
23 } | 24 } |
24 }; | 25 }; |
25 | 26 |
26 } // namespace internal | 27 } // namespace internal |
27 | 28 |
28 // flat_map is a container with a std::map-like interface that stores its | 29 // flat_map is a container with a std::map-like interface that stores its |
29 // contents in a sorted vector. | 30 // contents in a sorted vector. |
30 // | 31 // |
31 // Please see //base/containers/README.md for an overview of which container | 32 // Please see //base/containers/README.md for an overview of which container |
32 // to select. | 33 // to select. |
33 // | 34 // |
34 // PROS | 35 // PROS |
35 // | 36 // |
36 // - Good memory locality. | 37 // - Good memory locality. |
37 // - Low overhead, especially for smaller maps. | 38 // - Low overhead, especially for smaller maps. |
38 // - Performance is good for more workloads than you might expect (see | 39 // - Performance is good for more workloads than you might expect (see |
39 // overview link above). | 40 // overview link above). |
| 41 // - Supports C++14 map interface. |
40 // | 42 // |
41 // CONS | 43 // CONS |
42 // | 44 // |
43 // - Inserts and removals are O(n). | 45 // - Inserts and removals are O(n). |
44 // | 46 // |
45 // IMPORTANT NOTES | 47 // IMPORTANT NOTES |
46 // | 48 // |
47 // - Iterators are invalidated across mutations. | 49 // - Iterators are invalidated across mutations. |
48 // - If possible, construct a flat_map in one operation by inserting into | 50 // - If possible, construct a flat_map in one operation by inserting into |
49 // a std::vector and moving that vector into the flat_map constructor. | 51 // a std::vector and moving that vector into the flat_map constructor. |
(...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
87 // const_iterator end() const; | 89 // const_iterator end() const; |
88 // const_iterator cend() const; | 90 // const_iterator cend() const; |
89 // reverse_iterator rbegin(); | 91 // reverse_iterator rbegin(); |
90 // const reverse_iterator rbegin() const; | 92 // const reverse_iterator rbegin() const; |
91 // const_reverse_iterator crbegin() const; | 93 // const_reverse_iterator crbegin() const; |
92 // reverse_iterator rend(); | 94 // reverse_iterator rend(); |
93 // const_reverse_iterator rend() const; | 95 // const_reverse_iterator rend() const; |
94 // const_reverse_iterator crend() const; | 96 // const_reverse_iterator crend() const; |
95 // | 97 // |
96 // Insert and accessor functions: | 98 // Insert and accessor functions: |
97 // Mapped& operator[](const Key&); | 99 // Mapped& operator[](const key_type&); |
98 // Mapped& operator[](Key&&); | 100 // Mapped& operator[](key_type&&); |
99 // pair<iterator, bool> insert(const pair<Key, Mapped>&); | 101 // pair<iterator, bool> insert(const value_type&); |
100 // pair<iterator, bool> insert(pair<Key, Mapped>&&); | 102 // pair<iterator, bool> insert(value_type&&); |
101 // void insert(InputIterator first, InputIterator last, | 103 // void insert(InputIterator first, InputIterator last, |
102 // FlatContainerDupes); | 104 // FlatContainerDupes); |
103 // pair<iterator, bool> emplace(Args&&...); | 105 // pair<iterator, bool> emplace(Args&&...); |
104 // iterator emplace_hint(const_iterator, Args&&...); | 106 // iterator emplace_hint(const_iterator, Args&&...); |
105 // | 107 // |
106 // Erase functions: | 108 // Erase functions: |
| 109 // iterator erase(iterator); |
107 // iterator erase(const_iterator); | 110 // iterator erase(const_iterator); |
108 // iterator erase(const_iterator first, const_iterator& last); | 111 // iterator erase(const_iterator first, const_iterator& last); |
109 // size_t erase(const Key& key) | 112 // template <class K> size_t erase(const K& key) |
110 // | 113 // |
111 // Comparators (see std::map documentation). | 114 // Comparators (see std::map documentation). |
112 // key_compare key_comp() const; | 115 // key_compare key_comp() const; |
113 // value_compare value_comp() const; | 116 // value_compare value_comp() const; |
114 // | 117 // |
115 // Search functions: | 118 // Search functions: |
116 // size_t count(const Key&) const; | 119 // template <typename K> size_t count(const K&) const; |
117 // iterator find(const Key&); | 120 // template <typename K> iterator find(const K&); |
118 // const_iterator find(const Key&) const; | 121 // template <typename K> const_iterator find(const K&) const; |
119 // pair<iterator, iterator> equal_range(Key&) | 122 // template <typename K> pair<iterator, iterator> equal_range(const K&); |
120 // iterator lower_bound(const Key&); | 123 // template <typename K> iterator lower_bound(const K&); |
121 // const_iterator lower_bound(const Key&) const; | 124 // template <typename K> const_iterator lower_bound(const K&) const; |
122 // iterator upper_bound(const Key&); | 125 // template <typename K> iterator upper_bound(const K&); |
123 // const_iterator upper_bound(const Key&) const; | 126 // template <typename K> const_iterator upper_bound(const K&) const; |
124 // | 127 // |
125 // General functions: | 128 // General functions: |
126 // void swap(flat_map&&) | 129 // void swap(flat_map&&) |
127 // | 130 // |
128 // Non-member operators: | 131 // Non-member operators: |
129 // bool operator==(const flat_map&, const flat_map); | 132 // bool operator==(const flat_map&, const flat_map); |
130 // bool operator!=(const flat_map&, const flat_map); | 133 // bool operator!=(const flat_map&, const flat_map); |
131 // bool operator<(const flat_map&, const flat_map); | 134 // bool operator<(const flat_map&, const flat_map); |
132 // bool operator>(const flat_map&, const flat_map); | 135 // bool operator>(const flat_map&, const flat_map); |
133 // bool operator>=(const flat_map&, const flat_map); | 136 // bool operator>=(const flat_map&, const flat_map); |
134 // bool operator<=(const flat_map&, const flat_map); | 137 // bool operator<=(const flat_map&, const flat_map); |
135 // | 138 // |
136 template <class Key, class Mapped, class Compare = std::less<Key>> | 139 template <class Key, class Mapped, class Compare = ::base::less> |
137 // Meets the requirements of Container, AssociativeContainer, | 140 // Meets the requirements of Container, AssociativeContainer, |
138 // ReversibleContainer. | 141 // ReversibleContainer. |
139 // Requires: Key is Movable, Compare is a StrictWeakOrdering on Key. | 142 // Requires: Key is Movable, Compare is a StrictWeakOrdering on Key. |
140 class flat_map : public ::base::internal::flat_tree< | 143 class flat_map : public ::base::internal::flat_tree< |
141 Key, | 144 Key, |
142 std::pair<Key, Mapped>, | 145 std::pair<Key, Mapped>, |
143 ::base::internal::GetKeyFromValuePairFirst<Key, Mapped>, | 146 ::base::internal::GetKeyFromValuePairFirst<Key, Mapped>, |
144 Compare> { | 147 Compare> { |
145 private: | 148 private: |
146 using tree = typename ::base::internal::flat_tree< | 149 using tree = typename ::base::internal::flat_tree< |
(...skipping 152 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
299 // General operations. | 302 // General operations. |
300 | 303 |
301 template <class Key, class Mapped, class Compare> | 304 template <class Key, class Mapped, class Compare> |
302 void flat_map<Key, Mapped, Compare>::swap(flat_map& other) { | 305 void flat_map<Key, Mapped, Compare>::swap(flat_map& other) { |
303 tree::swap(other); | 306 tree::swap(other); |
304 } | 307 } |
305 | 308 |
306 } // namespace base | 309 } // namespace base |
307 | 310 |
308 #endif // BASE_CONTAINERS_FLAT_MAP_H_ | 311 #endif // BASE_CONTAINERS_FLAT_MAP_H_ |
OLD | NEW |