OLD | NEW |
---|---|
(Empty) | |
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 | |
3 // found in the LICENSE file. | |
4 | |
5 #ifndef BASE_CONTAINERS_FLAT_MAP_H_ | |
6 #define BASE_CONTAINERS_FLAT_MAP_H_ | |
7 | |
8 #include <utility> | |
9 | |
10 #include "base/containers/flat_tree.h" | |
11 #include "base/logging.h" | |
12 | |
13 namespace base { | |
14 | |
15 namespace internal { | |
16 | |
17 // An implementation of the flat_set GetKeyFromValue template parameter that | |
18 // extracts the key as the first element of a pair. | |
19 template <class Key, class Mapped> | |
20 struct GetKeyFromValuePairFirst { | |
21 const Key& operator()(const std::pair<Key, Mapped>& p) const { | |
22 return p.first; | |
23 } | |
24 }; | |
25 | |
26 } // namespace internal | |
27 | |
28 // OVERVIEW | |
29 // | |
30 // This file implements flat_map container. It is an alternative to standard | |
31 // sorted containers that stores its elements in contiguous memory (a vector). | |
32 // | |
33 // Additional documentation and usage advice is in flat_set.h. | |
34 // | |
35 // DOCUMENTATION | |
36 // | |
37 // Most of the core functionality is inherited from flat_tree. Please see | |
38 // flat_tree.h for more details for most of these functions. As a quick | |
39 // reference, the functions available are: | |
40 // | |
41 // Assignment functions: | |
42 // flat_map& operator=(const flat_map&); | |
43 // flat_map& operator=(flat_map&&); | |
44 // flat_map& operator=(initializer_list<pair<Key, Mapped>>); | |
45 // | |
46 // Memory management functions: | |
47 // void reserve(size_t); | |
48 // size_t capacity() const; | |
49 // void shrink_to_fit(); | |
50 // | |
51 // Size management functions: | |
52 // void clear(); | |
53 // size_t size() const; | |
54 // size_t max_size() const; | |
55 // bool empty() const; | |
56 // | |
57 // Iterator functions: | |
58 // iterator begin(); | |
59 // const_iterator begin() const; | |
60 // const_iterator cbegin() const; | |
61 // iterator end(); | |
62 // const_iterator end() const; | |
63 // const_iterator cend() const; | |
64 // reverse_iterator rbegin(); | |
65 // const reverse_iterator rbegin() const; | |
66 // const_reverse_iterator crbegin() const; | |
67 // reverse_iterator rend(); | |
68 // const_reverse_iterator rend() const; | |
69 // const_reverse_iterator crend() const; | |
70 // | |
71 // Insert and accessor functions: | |
72 // Mapped& operator[](const Key&); | |
73 // Mapped& operator[](Key&&); | |
74 // pair<iterator, bool> insert(const pair<Key, Mapped>&); | |
75 // pair<iterator, bool> insert(pair<Key, Mapped>&&); | |
76 // pair<iterator, bool> emplace(Args&&...); | |
77 // iterator emplace_hint(const_iterator, Args&&...); | |
78 // | |
79 // Erase functions: | |
80 // iterator erase(const_iterator); | |
81 // iterator erase(const_iterator first, const_iterator& last); | |
82 // size_t erase(const Key& key) | |
83 // | |
84 // Comparators (see std::map documentation). | |
85 // key_compare key_comp() const; | |
86 // value_compare value_comp() const; | |
87 // | |
88 // Search functions: | |
89 // size_t count(const Key&) const; | |
90 // iterator find(const Key&); | |
91 // const_iterator find(const Key&) const; | |
92 // pair<iterator, iterator> equal_range(Key&) | |
93 // iterator lower_bound(const Key&); | |
94 // const_iterator lower_bound(const Key&) const; | |
95 // iterator upper_bound(const Key&); | |
96 // const_iterator upper_bound(const Key&) const; | |
97 // | |
98 // General functions | |
99 // void swap(flat_map&&) | |
100 // | |
101 // Non-member operators: | |
102 // bool operator==(const flat_map&, const flat_map); | |
103 // bool operator!=(const flat_map&, const flat_map); | |
104 // bool operator<(const flat_map&, const flat_map); | |
105 // bool operator>(const flat_map&, const flat_map); | |
106 // bool operator>=(const flat_map&, const flat_map); | |
107 // bool operator<=(const flat_map&, const flat_map); | |
108 // | |
109 template <class Key, class Mapped, class Compare = std::less<Key>> | |
110 // Meets the requirements of Container, AssociativeContainer, | |
111 // ReversibleContainer. | |
112 // Requires: Key is Movable, Compare is a StrictWeakOrdering on Key. | |
113 class flat_map : public ::base::internal::flat_tree< | |
114 Key, | |
115 std::pair<Key, Mapped>, | |
116 ::base::internal::GetKeyFromValuePairFirst<Key, Mapped>, | |
117 Compare> { | |
118 private: | |
119 using tree = typename ::base::internal::flat_tree< | |
120 Key, | |
121 std::pair<Key, Mapped>, | |
122 ::base::internal::GetKeyFromValuePairFirst<Key, Mapped>, | |
123 Compare>; | |
124 | |
125 public: | |
126 using mapped_type = Mapped; | |
127 using value_type = typename tree::value_type; | |
128 | |
129 // -------------------------------------------------------------------------- | |
130 // Lifetime. | |
131 // | |
132 // Constructors that take range guarantee O(N * log(N)) + O(N) complexity | |
133 // (N is a range length). Thr range constructors are NOT stable. If there are | |
134 // duplicates an arbitrary one will be chosen. | |
135 // | |
136 // Assume that move constructors invalidate iterators and references. | |
137 | |
138 flat_map(); | |
139 explicit flat_map(const Compare& comp); | |
140 | |
141 // Not stable in the presence of duplicates in the initializer list. | |
142 template <class InputIterator> | |
143 flat_map(InputIterator first, | |
144 InputIterator last, | |
145 const Compare& comp = Compare()); | |
146 | |
147 flat_map(const flat_map&); | |
148 flat_map(flat_map&&); | |
149 | |
150 // Not stable in the presence of duplicates in the initializer list. | |
151 flat_map(std::initializer_list<value_type> ilist, | |
152 const Compare& comp = Compare()); | |
153 | |
154 ~flat_map(); | |
155 | |
156 // -------------------------------------------------------------------------- | |
157 // Assignments. | |
158 // | |
159 // Assume that move assignment invalidates iterators and references. | |
160 | |
161 flat_map& operator=(const flat_map&); | |
162 flat_map& operator=(flat_map&&); | |
163 // Not stable in the presence of duplicates in the initializer list. | |
164 flat_map& operator=(std::initializer_list<value_type> ilist); | |
165 | |
166 // -------------------------------------------------------------------------- | |
167 // Map-specific insert operations. | |
168 // | |
169 // Normal insert() functions are inherited from flat_tree. | |
170 // | |
171 // Assume that every operation invalidates iterators and references. | |
172 // Insertion of one element can take O(size). | |
173 | |
174 mapped_type& operator[](const Key& key); | |
175 mapped_type& operator[](Key&& key); | |
176 | |
177 // -------------------------------------------------------------------------- | |
178 // General operations. | |
179 // | |
180 // Assume that swap invalidates iterators and references. | |
181 | |
182 void swap(flat_map& other); | |
183 | |
184 friend void swap(flat_map& lhs, flat_map& rhs) { lhs.swap(rhs); } | |
185 }; | |
186 | |
187 // ---------------------------------------------------------------------------- | |
188 // Lifetime. | |
189 | |
190 template <class Key, class Mapped, class Compare> | |
191 flat_map<Key, Mapped, Compare>::flat_map() = default; | |
192 | |
193 template <class Key, class Mapped, class Compare> | |
194 flat_map<Key, Mapped, Compare>::flat_map(const Compare& comp) : tree(comp) {} | |
195 | |
196 template <class Key, class Mapped, class Compare> | |
197 template <class InputIterator> | |
198 flat_map<Key, Mapped, Compare>::flat_map(InputIterator first, | |
199 InputIterator last, | |
200 const Compare& comp) | |
201 : tree(first, last, comp) {} | |
202 | |
203 template <class Key, class Mapped, class Compare> | |
204 flat_map<Key, Mapped, Compare>::flat_map(const flat_map&) = default; | |
205 | |
206 template <class Key, class Mapped, class Compare> | |
207 flat_map<Key, Mapped, Compare>::flat_map(flat_map&&) = default; | |
208 | |
209 template <class Key, class Mapped, class Compare> | |
210 flat_map<Key, Mapped, Compare>::flat_map( | |
211 std::initializer_list<value_type> ilist, | |
212 const Compare& comp) | |
213 : flat_map(std::begin(ilist), std::end(ilist), comp) {} | |
214 | |
215 template <class Key, class Mapped, class Compare> | |
216 flat_map<Key, Mapped, Compare>::~flat_map() = default; | |
217 | |
218 // ---------------------------------------------------------------------------- | |
219 // Assignments. | |
220 | |
221 template <class Key, class Mapped, class Compare> | |
222 auto flat_map<Key, Mapped, Compare>::operator=(const flat_map&) | |
223 -> flat_map& = default; | |
224 | |
225 template <class Key, class Mapped, class Compare> | |
226 auto flat_map<Key, Mapped, Compare>::operator=(flat_map &&) | |
227 -> flat_map& = default; | |
228 | |
229 template <class Key, class Mapped, class Compare> | |
230 auto flat_map<Key, Mapped, Compare>::operator=( | |
231 std::initializer_list<value_type> ilist) -> flat_map& { | |
232 tree::operator=(ilist); | |
233 return *this; | |
234 } | |
235 | |
236 // ---------------------------------------------------------------------------- | |
237 // Insert operations. | |
238 | |
239 template <class Key, class Mapped, class Compare> | |
240 auto flat_map<Key, Mapped, Compare>::operator[](const Key& key) -> Mapped& { | |
241 typename tree::iterator found = tree::lower_bound(key); | |
242 if (found == tree::end() || tree::key_comp()(key, found->first)) | |
243 found = unsafe_emplace(found, key, Mapped()); | |
DaleCurtis
2017/03/29 01:16:42
Did you mean tree::unsafe_emplace() here? It doesn
dyaroshev
2017/03/29 11:13:21
And we probably don't have a test for it.
I think
| |
244 return found->second; | |
245 } | |
246 | |
247 template <class Key, class Mapped, class Compare> | |
248 auto flat_map<Key, Mapped, Compare>::operator[](Key&& key) -> Mapped& { | |
249 const Key& key_ref = key; | |
250 typename tree::iterator found = tree::lower_bound(key_ref); | |
251 if (found == tree::end() || tree::key_comp()(key, found->first)) | |
252 found = tree::unsafe_emplace(found, std::move(key), Mapped()); | |
253 return found->second; | |
254 } | |
255 | |
256 // ---------------------------------------------------------------------------- | |
257 // General operations. | |
258 | |
259 template <class Key, class Mapped, class Compare> | |
260 void flat_map<Key, Mapped, Compare>::swap(flat_map& other) { | |
261 tree::swap(other); | |
262 } | |
263 | |
264 } // namespace base | |
265 | |
266 #endif // BASE_CONTAINERS_FLAT_MAP_H_ | |
OLD | NEW |