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 <algorithm> | 8 #include "base/containers/flat_tree.h" |
9 #include <functional> | |
10 #include <utility> | |
11 #include <vector> | |
12 | 9 |
13 namespace base { | 10 namespace base { |
14 | 11 |
15 // Overview: | 12 // Overview: |
16 // This file implements flat_set container. It is an alternative to standard | 13 // This file implements flat_set container. It is an alternative to standard |
17 // sorted containers that stores it's elements in contiguous memory (current | 14 // sorted containers that stores it's elements in contiguous memory (current |
18 // version uses sorted std::vector). | 15 // version uses sorted std::vector). |
19 // Discussion that preceded introduction of this container can be found here: | 16 // Discussion that preceded introduction of this container can be found here: |
20 // https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector
$20based/chromium-dev/4uQMma9vj9w/HaQ-WvMOAwAJ | 17 // https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector
$20based/chromium-dev/4uQMma9vj9w/HaQ-WvMOAwAJ |
21 // | 18 // |
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
72 // | 69 // |
73 // Notes: | 70 // Notes: |
74 // Current implementation is based on boost::containers::flat_set, | 71 // Current implementation is based on boost::containers::flat_set, |
75 // eastl::vector_set and folly::sorted_vector. All of these implementations do | 72 // eastl::vector_set and folly::sorted_vector. All of these implementations do |
76 // insert(first, last) as insertion one by one (some implementations with hints | 73 // insert(first, last) as insertion one by one (some implementations with hints |
77 // and/or reserve). Boost documentation claims this algorithm to be O(n*log(n)) | 74 // and/or reserve). Boost documentation claims this algorithm to be O(n*log(n)) |
78 // but it seems to be a quadratic algorithm. For now we do not implement this | 75 // but it seems to be a quadratic algorithm. For now we do not implement this |
79 // method. | 76 // method. |
80 // TODO(dyaroshev): research an algorithm for range insertion crbug.com/682249. | 77 // TODO(dyaroshev): research an algorithm for range insertion crbug.com/682249. |
81 | 78 |
| 79 // QUICK REFERENCE |
| 80 // |
| 81 // Most of the core functionality is inherited from flat_tree. Please see |
| 82 // flat_tree.h for more details for most of these functions. As a quick |
| 83 // reference, the functions available are: |
| 84 // |
| 85 // Assignment functions: |
| 86 // flat_set& operator=(const flat_set&); |
| 87 // flat_set& operator=(flat_set&&); |
| 88 // flat_set& operator=(initializer_list<Key>); |
| 89 // |
| 90 // Memory management functions: |
| 91 // void reserve(size_t); |
| 92 // size_t capacity() const; |
| 93 // void shrink_to_fit(); |
| 94 // |
| 95 // Size management functions: |
| 96 // void clear(); |
| 97 // size_t size() const; |
| 98 // size_t max_size() const; |
| 99 // bool empty() const; |
| 100 // |
| 101 // Iterator functions: |
| 102 // iterator begin(); |
| 103 // const_iterator begin() const; |
| 104 // const_iterator cbegin() const; |
| 105 // iterator end(); |
| 106 // const_iterator end() const; |
| 107 // const_iterator cend() const; |
| 108 // reverse_iterator rbegin(); |
| 109 // const reverse_iterator rbegin() const; |
| 110 // const_reverse_iterator crbegin() const; |
| 111 // reverse_iterator rend(); |
| 112 // const_reverse_iterator rend() const; |
| 113 // const_reverse_iterator crend() const; |
| 114 // |
| 115 // Insert and accessor functions: |
| 116 // pair<iterator, bool> insert(const Key&); |
| 117 // pair<iterator, bool> insert(Key&&); |
| 118 // pair<iterator, bool> emplace(Args&&...); |
| 119 // iterator emplace_hint(const_iterator, Args&&...); |
| 120 // |
| 121 // Erase functions: |
| 122 // iterator erase(const_iterator); |
| 123 // iterator erase(const_iterator first, const_iterator& last); |
| 124 // size_t erase(const Key& key) |
| 125 // |
| 126 // Comparators (see std::set documentation). |
| 127 // key_compare key_comp() const; |
| 128 // value_compare value_comp() const; |
| 129 // |
| 130 // Search functions: |
| 131 // size_t count(const Key&) const; |
| 132 // iterator find(const Key&); |
| 133 // const_iterator find(const Key&) const; |
| 134 // pair<iterator, iterator> equal_range(Key&) |
| 135 // iterator lower_bound(const Key&); |
| 136 // const_iterator lower_bound(const Key&) const; |
| 137 // iterator upper_bound(const Key&); |
| 138 // const_iterator upper_bound(const Key&) const; |
| 139 // |
| 140 // General functions |
| 141 // void swap(flat_set&&) |
| 142 // |
| 143 // Non-member operators: |
| 144 // bool operator==(const flat_set&, const flat_set); |
| 145 // bool operator!=(const flat_set&, const flat_set); |
| 146 // bool operator<(const flat_set&, const flat_set); |
| 147 // bool operator>(const flat_set&, const flat_set); |
| 148 // bool operator>=(const flat_set&, const flat_set); |
| 149 // bool operator<=(const flat_set&, const flat_set); |
| 150 // |
82 template <class Key, class Compare = std::less<Key>> | 151 template <class Key, class Compare = std::less<Key>> |
83 // Meets the requirements of Container, AssociativeContainer, | 152 using flat_set = typename ::base::internal::flat_tree< |
84 // ReversibleContainer. | 153 Key, |
85 // Requires: Key is Movable, Compare is a StrictWeakOrdering on Key. | 154 Key, |
86 class flat_set { | 155 ::base::internal::GetKeyFromValueIdentity<Key>, |
87 private: | 156 Compare>; |
88 using underlying_type = std::vector<Key>; | |
89 | 157 |
90 public: | 158 } // namespace base |
91 // -------------------------------------------------------------------------- | |
92 // Types. | |
93 // | |
94 using key_type = Key; | |
95 using key_compare = Compare; | |
96 using value_type = Key; | |
97 using value_compare = Compare; | |
98 | |
99 using pointer = typename underlying_type::pointer; | |
100 using const_pointer = typename underlying_type::const_pointer; | |
101 using reference = typename underlying_type::reference; | |
102 using const_reference = typename underlying_type::const_reference; | |
103 using size_type = typename underlying_type::size_type; | |
104 using difference_type = typename underlying_type::difference_type; | |
105 using iterator = typename underlying_type::iterator; | |
106 using const_iterator = typename underlying_type::const_iterator; | |
107 using reverse_iterator = typename underlying_type::reverse_iterator; | |
108 using const_reverse_iterator = | |
109 typename underlying_type::const_reverse_iterator; | |
110 | |
111 // -------------------------------------------------------------------------- | |
112 // Lifetime. | |
113 // | |
114 // Constructors that take range guarantee O(N * log^2(N)) + O(N) complexity | |
115 // and take O(N * log(N)) + O(N) if extra memory is available (N is a range | |
116 // length). | |
117 // | |
118 // Assume that move constructors invalidate iterators and references. | |
119 | |
120 flat_set(); | |
121 explicit flat_set(const Compare& comp); | |
122 | |
123 template <class InputIterator> | |
124 flat_set(InputIterator first, | |
125 InputIterator last, | |
126 const Compare& comp = Compare()); | |
127 | |
128 flat_set(const flat_set&); | |
129 flat_set(flat_set&&); | |
130 | |
131 flat_set(std::initializer_list<value_type> ilist, | |
132 const Compare& comp = Compare()); | |
133 | |
134 ~flat_set(); | |
135 | |
136 // -------------------------------------------------------------------------- | |
137 // Assignments. | |
138 // | |
139 // Assume that move assignment invalidates iterators and references. | |
140 | |
141 flat_set& operator=(const flat_set&); | |
142 flat_set& operator=(flat_set&&); | |
143 flat_set& operator=(std::initializer_list<value_type> ilist); | |
144 | |
145 // -------------------------------------------------------------------------- | |
146 // Memory management. | |
147 // | |
148 // Beware that shrink_to_fit() simply forwards the request to the | |
149 // underlying_type and its implementation is free to optimize otherwise and | |
150 // leave capacity() to be greater that its size. | |
151 // | |
152 // reserve() and shrink_to_fit() invalidate iterators and references. | |
153 | |
154 void reserve(size_type new_capacity); | |
155 size_type capacity() const; | |
156 void shrink_to_fit(); | |
157 | |
158 // -------------------------------------------------------------------------- | |
159 // Size management. | |
160 // | |
161 // clear() leaves the capacity() of the flat_set unchanged. | |
162 | |
163 void clear(); | |
164 | |
165 size_type size() const; | |
166 size_type max_size() const; | |
167 bool empty() const; | |
168 | |
169 // -------------------------------------------------------------------------- | |
170 // Iterators. | |
171 | |
172 iterator begin(); | |
173 const_iterator begin() const; | |
174 const_iterator cbegin() const; | |
175 | |
176 iterator end(); | |
177 const_iterator end() const; | |
178 const_iterator cend() const; | |
179 | |
180 reverse_iterator rbegin(); | |
181 const_reverse_iterator rbegin() const; | |
182 const_reverse_iterator crbegin() const; | |
183 | |
184 reverse_iterator rend(); | |
185 const_reverse_iterator rend() const; | |
186 const_reverse_iterator crend() const; | |
187 | |
188 // -------------------------------------------------------------------------- | |
189 // Insert operations. | |
190 // | |
191 // Assume that every operation invalidates iterators and references. | |
192 // Insertion of one element can take O(size). See the Notes section in the | |
193 // class comments on why we do not currently implement range insertion. | |
194 // Capacity of flat_set grows in an implementation-defined manner. | |
195 // | |
196 // NOTE: Prefer to build a new flat_set from a std::vector (or similar) | |
197 // instead of calling insert() repeatedly. | |
198 | |
199 std::pair<iterator, bool> insert(const value_type& val); | |
200 std::pair<iterator, bool> insert(value_type&& val); | |
201 | |
202 iterator insert(const_iterator position_hint, const value_type& x); | |
203 iterator insert(const_iterator position_hint, value_type&& x); | |
204 | |
205 template <class... Args> | |
206 std::pair<iterator, bool> emplace(Args&&... args); | |
207 | |
208 template <class... Args> | |
209 iterator emplace_hint(const_iterator position_hint, Args&&... args); | |
210 | |
211 // -------------------------------------------------------------------------- | |
212 // Erase operations. | |
213 // | |
214 // Assume that every operation invalidates iterators and references. | |
215 // | |
216 // erase(position), erase(first, last) can take O(size). | |
217 // erase(key) may take O(size) + O(log(size)). | |
218 // | |
219 // Prefer base::EraseIf() or some other variation on erase(remove(), end()) | |
220 // idiom when deleting multiple non-consecutive elements. | |
221 | |
222 iterator erase(const_iterator position); | |
223 iterator erase(const_iterator first, const_iterator last); | |
224 size_type erase(const key_type& key); | |
225 | |
226 // -------------------------------------------------------------------------- | |
227 // Comparators. | |
228 | |
229 key_compare key_comp() const; | |
230 value_compare value_comp() const; | |
231 | |
232 // -------------------------------------------------------------------------- | |
233 // Search operations. | |
234 // | |
235 // Search operations have O(log(size)) complexity. | |
236 | |
237 size_type count(const key_type& key) const; | |
238 | |
239 iterator find(const key_type& key); | |
240 const_iterator find(const key_type& key) const; | |
241 | |
242 std::pair<iterator, iterator> equal_range(const key_type& ket); | |
243 std::pair<const_iterator, const_iterator> equal_range( | |
244 const key_type& key) const; | |
245 | |
246 iterator lower_bound(const key_type& key); | |
247 const_iterator lower_bound(const key_type& key) const; | |
248 | |
249 iterator upper_bound(const key_type& key); | |
250 const_iterator upper_bound(const key_type& key) const; | |
251 | |
252 // -------------------------------------------------------------------------- | |
253 // General operations. | |
254 // | |
255 // Assume that swap invalidates iterators and references. | |
256 // | |
257 // As with std::set, equality and ordering operations for the whole flat_set | |
258 // are equivalent to using equal() and lexicographical_compare() on the key | |
259 // types, rather than using element-wise key_comp() as e.g. lower_bound() | |
260 // does. Implementation note: currently we use operator==() and operator<() on | |
261 // std::vector, because they have the same contract we need, so we use them | |
262 // directly for brevity and in case it is more optimal than calling equal() | |
263 // and lexicograhpical_compare(). If the underlying container type is changed, | |
264 // this code may need to be modified. | |
265 | |
266 void swap(flat_set& other); | |
267 | |
268 friend bool operator==(const flat_set& lhs, const flat_set& rhs) { | |
269 return lhs.impl_.body_ == rhs.impl_.body_; | |
270 } | |
271 | |
272 friend bool operator!=(const flat_set& lhs, const flat_set& rhs) { | |
273 return !(lhs == rhs); | |
274 } | |
275 | |
276 friend bool operator<(const flat_set& lhs, const flat_set& rhs) { | |
277 return lhs.impl_.body_ < rhs.impl_.body_; | |
278 } | |
279 | |
280 friend bool operator>(const flat_set& lhs, const flat_set& rhs) { | |
281 return rhs < lhs; | |
282 } | |
283 | |
284 friend bool operator>=(const flat_set& lhs, const flat_set& rhs) { | |
285 return !(lhs < rhs); | |
286 } | |
287 | |
288 friend bool operator<=(const flat_set& lhs, const flat_set& rhs) { | |
289 return !(lhs > rhs); | |
290 } | |
291 | |
292 friend void swap(flat_set& lhs, flat_set& rhs) { lhs.swap(rhs); } | |
293 | |
294 private: | |
295 const flat_set& as_const() { return *this; } | |
296 | |
297 iterator const_cast_it(const_iterator c_it) { | |
298 auto distance = std::distance(cbegin(), c_it); | |
299 return std::next(begin(), distance); | |
300 } | |
301 | |
302 void sort_and_unique() { | |
303 // std::set sorts elements preserving stability because it doesn't have any | |
304 // performance wins in not doing that. We do, so we use an unstable sort. | |
305 std::sort(begin(), end(), value_comp()); | |
306 erase(std::unique(begin(), end(), | |
307 [this](const value_type& lhs, const value_type& rhs) { | |
308 // lhs is already <= rhs due to sort, therefore | |
309 // !(lhs < rhs) <=> lhs == rhs. | |
310 return !value_comp()(lhs, rhs); | |
311 }), | |
312 end()); | |
313 } | |
314 | |
315 // To support comparators that may not be possible to default-construct, we | |
316 // have to store an instance of Compare. Using this to store all internal | |
317 // state of flat_set and using private inheritance to store compare lets us | |
318 // take advantage of an empty base class optimization to avoid extra space in | |
319 // the common case when Compare has no state. | |
320 struct Impl : private Compare { | |
321 Impl() = default; | |
322 | |
323 template <class Cmp, class... Body> | |
324 explicit Impl(Cmp&& compare_arg, Body&&... underlying_type_args) | |
325 : Compare(std::forward<Cmp>(compare_arg)), | |
326 body_(std::forward<Body>(underlying_type_args)...) {} | |
327 | |
328 Compare compare() const { return *this; } | |
329 | |
330 underlying_type body_; | |
331 } impl_; | |
332 }; | |
333 | |
334 // ---------------------------------------------------------------------------- | |
335 // Lifetime. | |
336 | |
337 template <class Key, class Compare> | |
338 flat_set<Key, Compare>::flat_set() = default; | |
339 | |
340 template <class Key, class Compare> | |
341 flat_set<Key, Compare>::flat_set(const Compare& comp) : impl_(comp) {} | |
342 | |
343 template <class Key, class Compare> | |
344 template <class InputIterator> | |
345 flat_set<Key, Compare>::flat_set(InputIterator first, | |
346 InputIterator last, | |
347 const Compare& comp) | |
348 : impl_(comp, first, last) { | |
349 sort_and_unique(); | |
350 } | |
351 | |
352 template <class Key, class Compare> | |
353 flat_set<Key, Compare>::flat_set(const flat_set&) = default; | |
354 | |
355 template <class Key, class Compare> | |
356 flat_set<Key, Compare>::flat_set(flat_set&&) = default; | |
357 | |
358 template <class Key, class Compare> | |
359 flat_set<Key, Compare>::flat_set(std::initializer_list<value_type> ilist, | |
360 const Compare& comp) | |
361 : flat_set(std::begin(ilist), std::end(ilist), comp) {} | |
362 | |
363 template <class Key, class Compare> | |
364 flat_set<Key, Compare>::~flat_set() = default; | |
365 | |
366 // ---------------------------------------------------------------------------- | |
367 // Assignments. | |
368 | |
369 template <class Key, class Compare> | |
370 auto flat_set<Key, Compare>::operator=(const flat_set&) -> flat_set& = default; | |
371 | |
372 template <class Key, class Compare> | |
373 auto flat_set<Key, Compare>::operator=(flat_set &&) -> flat_set& = default; | |
374 | |
375 template <class Key, class Compare> | |
376 auto flat_set<Key, Compare>::operator=(std::initializer_list<value_type> ilist) | |
377 -> flat_set& { | |
378 impl_.body_ = ilist; | |
379 sort_and_unique(); | |
380 return *this; | |
381 } | |
382 | |
383 // ---------------------------------------------------------------------------- | |
384 // Memory management. | |
385 | |
386 template <class Key, class Compare> | |
387 void flat_set<Key, Compare>::reserve(size_type new_capacity) { | |
388 impl_.body_.reserve(new_capacity); | |
389 } | |
390 | |
391 template <class Key, class Compare> | |
392 auto flat_set<Key, Compare>::capacity() const -> size_type { | |
393 return impl_.body_.capacity(); | |
394 } | |
395 | |
396 template <class Key, class Compare> | |
397 void flat_set<Key, Compare>::shrink_to_fit() { | |
398 impl_.body_.shrink_to_fit(); | |
399 } | |
400 | |
401 // ---------------------------------------------------------------------------- | |
402 // Size management. | |
403 | |
404 template <class Key, class Compare> | |
405 void flat_set<Key, Compare>::clear() { | |
406 impl_.body_.clear(); | |
407 } | |
408 | |
409 template <class Key, class Compare> | |
410 auto flat_set<Key, Compare>::size() const -> size_type { | |
411 return impl_.body_.size(); | |
412 } | |
413 | |
414 template <class Key, class Compare> | |
415 auto flat_set<Key, Compare>::max_size() const -> size_type { | |
416 return impl_.body_.max_size(); | |
417 } | |
418 | |
419 template <class Key, class Compare> | |
420 bool flat_set<Key, Compare>::empty() const { | |
421 return impl_.body_.empty(); | |
422 } | |
423 | |
424 // ---------------------------------------------------------------------------- | |
425 // Iterators. | |
426 | |
427 template <class Key, class Compare> | |
428 auto flat_set<Key, Compare>::begin() -> iterator { | |
429 return impl_.body_.begin(); | |
430 } | |
431 | |
432 template <class Key, class Compare> | |
433 auto flat_set<Key, Compare>::begin() const -> const_iterator { | |
434 return impl_.body_.begin(); | |
435 } | |
436 | |
437 template <class Key, class Compare> | |
438 auto flat_set<Key, Compare>::cbegin() const -> const_iterator { | |
439 return impl_.body_.cbegin(); | |
440 } | |
441 | |
442 template <class Key, class Compare> | |
443 auto flat_set<Key, Compare>::end() -> iterator { | |
444 return impl_.body_.end(); | |
445 } | |
446 | |
447 template <class Key, class Compare> | |
448 auto flat_set<Key, Compare>::end() const -> const_iterator { | |
449 return impl_.body_.end(); | |
450 } | |
451 | |
452 template <class Key, class Compare> | |
453 auto flat_set<Key, Compare>::cend() const -> const_iterator { | |
454 return impl_.body_.cend(); | |
455 } | |
456 | |
457 template <class Key, class Compare> | |
458 auto flat_set<Key, Compare>::rbegin() -> reverse_iterator { | |
459 return impl_.body_.rbegin(); | |
460 } | |
461 | |
462 template <class Key, class Compare> | |
463 auto flat_set<Key, Compare>::rbegin() const -> const_reverse_iterator { | |
464 return impl_.body_.rbegin(); | |
465 } | |
466 | |
467 template <class Key, class Compare> | |
468 auto flat_set<Key, Compare>::crbegin() const -> const_reverse_iterator { | |
469 return impl_.body_.crbegin(); | |
470 } | |
471 | |
472 template <class Key, class Compare> | |
473 auto flat_set<Key, Compare>::rend() -> reverse_iterator { | |
474 return impl_.body_.rend(); | |
475 } | |
476 | |
477 template <class Key, class Compare> | |
478 auto flat_set<Key, Compare>::rend() const -> const_reverse_iterator { | |
479 return impl_.body_.rend(); | |
480 } | |
481 | |
482 template <class Key, class Compare> | |
483 auto flat_set<Key, Compare>::crend() const -> const_reverse_iterator { | |
484 return impl_.body_.crend(); | |
485 } | |
486 | |
487 // ---------------------------------------------------------------------------- | |
488 // Insert operations. | |
489 // | |
490 // Currently we use position_hint the same way as eastl or boost: | |
491 // https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set.
h#L493 | |
492 // | |
493 // We duplicate code between copy and move version so that we can avoid | |
494 // creating a temporary value. | |
495 | |
496 template <class Key, class Compare> | |
497 auto flat_set<Key, Compare>::insert(const value_type& val) | |
498 -> std::pair<iterator, bool> { | |
499 auto position = lower_bound(val); | |
500 | |
501 if (position == end() || value_comp()(val, *position)) | |
502 return {impl_.body_.insert(position, val), true}; | |
503 | |
504 return {position, false}; | |
505 } | |
506 | |
507 template <class Key, class Compare> | |
508 auto flat_set<Key, Compare>::insert(value_type&& val) | |
509 -> std::pair<iterator, bool> { | |
510 auto position = lower_bound(val); | |
511 | |
512 if (position == end() || value_comp()(val, *position)) | |
513 return {impl_.body_.insert(position, std::move(val)), true}; | |
514 | |
515 return {position, false}; | |
516 } | |
517 | |
518 template <class Key, class Compare> | |
519 auto flat_set<Key, Compare>::insert(const_iterator position_hint, | |
520 const value_type& val) -> iterator { | |
521 if (position_hint == end() || value_comp()(val, *position_hint)) { | |
522 if (position_hint == begin() || value_comp()(*(position_hint - 1), val)) | |
523 // We have to cast away const because of crbug.com/677044. | |
524 return impl_.body_.insert(const_cast_it(position_hint), val); | |
525 } | |
526 return insert(val).first; | |
527 } | |
528 | |
529 template <class Key, class Compare> | |
530 auto flat_set<Key, Compare>::insert(const_iterator position_hint, | |
531 value_type&& val) -> iterator { | |
532 if (position_hint == end() || value_comp()(val, *position_hint)) { | |
533 if (position_hint == begin() || value_comp()(*(position_hint - 1), val)) | |
534 // We have to cast away const because of crbug.com/677044. | |
535 return impl_.body_.insert(const_cast_it(position_hint), std::move(val)); | |
536 } | |
537 return insert(std::move(val)).first; | |
538 } | |
539 | |
540 template <class Key, class Compare> | |
541 template <class... Args> | |
542 auto flat_set<Key, Compare>::emplace(Args&&... args) | |
543 -> std::pair<iterator, bool> { | |
544 return insert(value_type(std::forward<Args>(args)...)); | |
545 } | |
546 | |
547 template <class Key, class Compare> | |
548 template <class... Args> | |
549 auto flat_set<Key, Compare>::emplace_hint(const_iterator position_hint, | |
550 Args&&... args) -> iterator { | |
551 return insert(position_hint, value_type(std::forward<Args>(args)...)); | |
552 } | |
553 | |
554 // ---------------------------------------------------------------------------- | |
555 // Erase operations. | |
556 | |
557 template <class Key, class Compare> | |
558 auto flat_set<Key, Compare>::erase(const_iterator position) -> iterator { | |
559 // We have to cast away const because of crbug.com/677044. | |
560 return impl_.body_.erase(const_cast_it(position)); | |
561 } | |
562 | |
563 template <class Key, class Compare> | |
564 auto flat_set<Key, Compare>::erase(const key_type& val) -> size_type { | |
565 auto eq_range = equal_range(val); | |
566 auto res = std::distance(eq_range.first, eq_range.second); | |
567 // We have to cast away const because of crbug.com/677044. | |
568 erase(const_cast_it(eq_range.first), const_cast_it(eq_range.second)); | |
569 return res; | |
570 } | |
571 | |
572 template <class Key, class Compare> | |
573 auto flat_set<Key, Compare>::erase(const_iterator first, const_iterator last) | |
574 -> iterator { | |
575 // We have to cast away const because of crbug.com/677044. | |
576 return impl_.body_.erase(const_cast_it(first), const_cast_it(last)); | |
577 } | |
578 | |
579 // ---------------------------------------------------------------------------- | |
580 // Comparators. | |
581 | |
582 template <class Key, class Compare> | |
583 auto flat_set<Key, Compare>::key_comp() const -> key_compare { | |
584 return impl_.compare(); | |
585 } | |
586 | |
587 template <class Key, class Compare> | |
588 auto flat_set<Key, Compare>::value_comp() const -> value_compare { | |
589 return impl_.compare(); | |
590 } | |
591 | |
592 // ---------------------------------------------------------------------------- | |
593 // Search operations. | |
594 | |
595 template <class Key, class Compare> | |
596 auto flat_set<Key, Compare>::count(const key_type& key) const -> size_type { | |
597 auto eq_range = equal_range(key); | |
598 return std::distance(eq_range.first, eq_range.second); | |
599 } | |
600 | |
601 template <class Key, class Compare> | |
602 auto flat_set<Key, Compare>::find(const key_type& key) -> iterator { | |
603 return const_cast_it(as_const().find(key)); | |
604 } | |
605 | |
606 template <class Key, class Compare> | |
607 auto flat_set<Key, Compare>::find(const key_type& key) const -> const_iterator { | |
608 auto eq_range = equal_range(key); | |
609 return (eq_range.first == eq_range.second) ? end() : eq_range.first; | |
610 } | |
611 | |
612 template <class Key, class Compare> | |
613 auto flat_set<Key, Compare>::equal_range(const key_type& key) | |
614 -> std::pair<iterator, iterator> { | |
615 auto res = as_const().equal_range(key); | |
616 return {const_cast_it(res.first), const_cast_it(res.second)}; | |
617 } | |
618 | |
619 template <class Key, class Compare> | |
620 auto flat_set<Key, Compare>::equal_range(const key_type& key) const | |
621 -> std::pair<const_iterator, const_iterator> { | |
622 auto lower = lower_bound(key); | |
623 | |
624 if (lower == end() || key_comp()(key, *lower)) | |
625 return {lower, lower}; | |
626 | |
627 return {lower, std::next(lower)}; | |
628 } | |
629 | |
630 template <class Key, class Compare> | |
631 auto flat_set<Key, Compare>::lower_bound(const key_type& key) -> iterator { | |
632 return const_cast_it(as_const().lower_bound(key)); | |
633 } | |
634 | |
635 template <class Key, class Compare> | |
636 auto flat_set<Key, Compare>::lower_bound(const key_type& key) const | |
637 -> const_iterator { | |
638 return std::lower_bound(begin(), end(), key, key_comp()); | |
639 } | |
640 | |
641 template <class Key, class Compare> | |
642 auto flat_set<Key, Compare>::upper_bound(const key_type& key) -> iterator { | |
643 return const_cast_it(as_const().upper_bound(key)); | |
644 } | |
645 | |
646 template <class Key, class Compare> | |
647 auto flat_set<Key, Compare>::upper_bound(const key_type& key) const | |
648 -> const_iterator { | |
649 return std::upper_bound(begin(), end(), key, key_comp()); | |
650 } | |
651 | |
652 // ---------------------------------------------------------------------------- | |
653 // General operations. | |
654 | |
655 template <class Key, class Compare> | |
656 void flat_set<Key, Compare>::swap(flat_set& other) { | |
657 std::swap(impl_, other.impl_); | |
658 } | |
659 | |
660 // ---------------------------------------------------------------------------- | |
661 // Free functions. | |
662 | |
663 // Erases all elements that match predicate. It has O(size) complexity. | |
664 template <typename Key, typename Compare, typename Predicate> | |
665 void EraseIf(base::flat_set<Key, Compare>& container, Predicate pred) { | |
666 container.erase(std::remove_if(container.begin(), container.end(), pred), | |
667 container.end()); | |
668 } | |
669 | |
670 } // namespace base | |
671 | 159 |
672 #endif // BASE_CONTAINERS_FLAT_SET_H_ | 160 #endif // BASE_CONTAINERS_FLAT_SET_H_ |
OLD | NEW |