]>
Commit | Line | Data |
---|---|---|
9f95a23c | 1 | // Copyright 2018 The Abseil Authors. |
31f18b77 FG |
2 | // |
3 | // Licensed under the Apache License, Version 2.0 (the "License"); | |
4 | // you may not use this file except in compliance with the License. | |
5 | // You may obtain a copy of the License at | |
6 | // | |
9f95a23c | 7 | // https://www.apache.org/licenses/LICENSE-2.0 |
31f18b77 FG |
8 | // |
9 | // Unless required by applicable law or agreed to in writing, software | |
10 | // distributed under the License is distributed on an "AS IS" BASIS, | |
11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
12 | // See the License for the specific language governing permissions and | |
13 | // limitations under the License. | |
14 | // | |
9f95a23c TL |
15 | // ----------------------------------------------------------------------------- |
16 | // File: btree_set.h | |
17 | // ----------------------------------------------------------------------------- | |
18 | // | |
19 | // This header file defines B-tree sets: sorted associative containers of | |
20 | // values. | |
21 | // | |
22 | // * `absl::btree_set<>` | |
23 | // * `absl::btree_multiset<>` | |
24 | // | |
25 | // These B-tree types are similar to the corresponding types in the STL | |
26 | // (`std::set` and `std::multiset`) and generally conform to the STL interfaces | |
27 | // of those types. However, because they are implemented using B-trees, they | |
28 | // are more efficient in most situations. | |
29 | // | |
30 | // Unlike `std::set` and `std::multiset`, which are commonly implemented using | |
31 | // red-black tree nodes, B-tree sets use more generic B-tree nodes able to hold | |
32 | // multiple values per node. Holding multiple values per node often makes | |
33 | // B-tree sets perform better than their `std::set` counterparts, because | |
34 | // multiple entries can be checked within the same cache hit. | |
35 | // | |
36 | // However, these types should not be considered drop-in replacements for | |
37 | // `std::set` and `std::multiset` as there are some API differences, which are | |
38 | // noted in this header file. | |
39 | // | |
40 | // Importantly, insertions and deletions may invalidate outstanding iterators, | |
41 | // pointers, and references to elements. Such invalidations are typically only | |
42 | // an issue if insertion and deletion operations are interleaved with the use of | |
43 | // more than one iterator, pointer, or reference simultaneously. For this | |
44 | // reason, `insert()` and `erase()` return a valid iterator at the current | |
45 | // position. | |
31f18b77 | 46 | |
9f95a23c | 47 | #pragma once |
31f18b77 FG |
48 | |
49 | #include "btree.h" | |
50 | #include "btree_container.h" | |
51 | ||
52 | namespace btree { | |
53 | ||
9f95a23c TL |
54 | // btree::btree_set<> |
55 | // | |
56 | // An `btree::btree_set<K>` is an ordered associative container of unique key | |
57 | // values designed to be a more efficient replacement for `std::set` (in most | |
58 | // cases). | |
59 | // | |
60 | // Keys are sorted using an (optional) comparison function, which defaults to | |
61 | // `std::less<K>`. | |
62 | // | |
63 | // An `btree::btree_set<K>` uses a default allocator of `std::allocator<K>` to | |
64 | // allocate (and deallocate) nodes, and construct and destruct values within | |
65 | // those nodes. You may instead specify a custom allocator `A` (which in turn | |
66 | // requires specifying a custom comparator `C`) as in | |
67 | // `btree::btree_set<K, C, A>`. | |
68 | // | |
69 | template <typename Key, typename Compare = std::less<Key>, | |
70 | typename Alloc = std::allocator<Key>> | |
71 | class btree_set | |
72 | : public internal::btree_set_container< | |
73 | internal::btree<internal::set_params< | |
74 | Key, Compare, Alloc, /*TargetNodeSize=*/256, | |
75 | /*Multi=*/false>>> { | |
76 | using Base = typename btree_set::btree_set_container; | |
31f18b77 FG |
77 | |
78 | public: | |
9f95a23c TL |
79 | // Constructors and Assignment Operators |
80 | // | |
81 | // A `btree_set` supports the same overload set as `std::set` | |
82 | // for construction and assignment: | |
83 | // | |
84 | // * Default constructor | |
85 | // | |
86 | // btree::btree_set<std::string> set1; | |
87 | // | |
88 | // * Initializer List constructor | |
89 | // | |
90 | // btree::btree_set<std::string> set2 = | |
91 | // {{"huey"}, {"dewey"}, {"louie"},}; | |
92 | // | |
93 | // * Copy constructor | |
94 | // | |
95 | // btree::btree_set<std::string> set3(set2); | |
96 | // | |
97 | // * Copy assignment operator | |
98 | // | |
99 | // btree::btree_set<std::string> set4; | |
100 | // set4 = set3; | |
101 | // | |
102 | // * Move constructor | |
103 | // | |
104 | // // Move is guaranteed efficient | |
105 | // btree::btree_set<std::string> set5(std::move(set4)); | |
106 | // | |
107 | // * Move assignment operator | |
108 | // | |
109 | // // May be efficient if allocators are compatible | |
110 | // btree::btree_set<std::string> set6; | |
111 | // set6 = std::move(set5); | |
112 | // | |
113 | // * Range constructor | |
114 | // | |
115 | // std::vector<std::string> v = {"a", "b"}; | |
116 | // btree::btree_set<std::string> set7(v.begin(), v.end()); | |
117 | btree_set() {} | |
118 | using Base::Base; | |
31f18b77 | 119 | |
9f95a23c TL |
120 | // btree_set::begin() |
121 | // | |
122 | // Returns an iterator to the beginning of the `btree_set`. | |
123 | using Base::begin; | |
31f18b77 | 124 | |
9f95a23c TL |
125 | // btree_set::cbegin() |
126 | // | |
127 | // Returns a const iterator to the beginning of the `btree_set`. | |
128 | using Base::cbegin; | |
31f18b77 | 129 | |
9f95a23c TL |
130 | // btree_set::end() |
131 | // | |
132 | // Returns an iterator to the end of the `btree_set`. | |
133 | using Base::end; | |
134 | ||
135 | // btree_set::cend() | |
136 | // | |
137 | // Returns a const iterator to the end of the `btree_set`. | |
138 | using Base::cend; | |
139 | ||
140 | // btree_set::empty() | |
141 | // | |
142 | // Returns whether or not the `btree_set` is empty. | |
143 | using Base::empty; | |
144 | ||
145 | // btree_set::max_size() | |
146 | // | |
147 | // Returns the largest theoretical possible number of elements within a | |
148 | // `btree_set` under current memory constraints. This value can be thought | |
149 | // of as the largest value of `std::distance(begin(), end())` for a | |
150 | // `btree_set<Key>`. | |
151 | using Base::max_size; | |
152 | ||
153 | // btree_set::size() | |
154 | // | |
155 | // Returns the number of elements currently within the `btree_set`. | |
156 | using Base::size; | |
157 | ||
158 | // btree_set::clear() | |
159 | // | |
160 | // Removes all elements from the `btree_set`. Invalidates any references, | |
161 | // pointers, or iterators referring to contained elements. | |
162 | using Base::clear; | |
163 | ||
164 | // btree_set::erase() | |
165 | // | |
166 | // Erases elements within the `btree_set`. Overloads are listed below. | |
167 | // | |
168 | // iterator erase(iterator position): | |
169 | // iterator erase(const_iterator position): | |
170 | // | |
171 | // Erases the element at `position` of the `btree_set`, returning | |
172 | // the iterator pointing to the element after the one that was erased | |
173 | // (or end() if none exists). | |
174 | // | |
175 | // iterator erase(const_iterator first, const_iterator last): | |
176 | // | |
177 | // Erases the elements in the open interval [`first`, `last`), returning | |
178 | // the iterator pointing to the element after the interval that was erased | |
179 | // (or end() if none exists). | |
180 | // | |
181 | // template <typename K> size_type erase(const K& key): | |
182 | // | |
183 | // Erases the element with the matching key, if it exists, returning the | |
184 | // number of elements erased. | |
185 | using Base::erase; | |
186 | ||
187 | // btree_set::insert() | |
188 | // | |
189 | // Inserts an element of the specified value into the `btree_set`, | |
190 | // returning an iterator pointing to the newly inserted element, provided that | |
191 | // an element with the given key does not already exist. If an insertion | |
192 | // occurs, any references, pointers, or iterators are invalidated. | |
193 | // Overloads are listed below. | |
194 | // | |
195 | // std::pair<iterator,bool> insert(const value_type& value): | |
196 | // | |
197 | // Inserts a value into the `btree_set`. Returns a pair consisting of an | |
198 | // iterator to the inserted element (or to the element that prevented the | |
199 | // insertion) and a bool denoting whether the insertion took place. | |
200 | // | |
201 | // std::pair<iterator,bool> insert(value_type&& value): | |
202 | // | |
203 | // Inserts a moveable value into the `btree_set`. Returns a pair | |
204 | // consisting of an iterator to the inserted element (or to the element that | |
205 | // prevented the insertion) and a bool denoting whether the insertion took | |
206 | // place. | |
207 | // | |
208 | // iterator insert(const_iterator hint, const value_type& value): | |
209 | // iterator insert(const_iterator hint, value_type&& value): | |
210 | // | |
211 | // Inserts a value, using the position of `hint` as a non-binding suggestion | |
212 | // for where to begin the insertion search. Returns an iterator to the | |
213 | // inserted element, or to the existing element that prevented the | |
214 | // insertion. | |
215 | // | |
216 | // void insert(InputIterator first, InputIterator last): | |
217 | // | |
218 | // Inserts a range of values [`first`, `last`). | |
219 | // | |
220 | // void insert(std::initializer_list<init_type> ilist): | |
221 | // | |
222 | // Inserts the elements within the initializer list `ilist`. | |
223 | using Base::insert; | |
224 | ||
225 | // btree_set::emplace() | |
226 | // | |
227 | // Inserts an element of the specified value by constructing it in-place | |
228 | // within the `btree_set`, provided that no element with the given key | |
229 | // already exists. | |
230 | // | |
231 | // The element may be constructed even if there already is an element with the | |
232 | // key in the container, in which case the newly constructed element will be | |
233 | // destroyed immediately. | |
234 | // | |
235 | // If an insertion occurs, any references, pointers, or iterators are | |
236 | // invalidated. | |
237 | using Base::emplace; | |
238 | ||
239 | // btree_set::emplace_hint() | |
240 | // | |
241 | // Inserts an element of the specified value by constructing it in-place | |
242 | // within the `btree_set`, using the position of `hint` as a non-binding | |
243 | // suggestion for where to begin the insertion search, and only inserts | |
244 | // provided that no element with the given key already exists. | |
245 | // | |
246 | // The element may be constructed even if there already is an element with the | |
247 | // key in the container, in which case the newly constructed element will be | |
248 | // destroyed immediately. | |
249 | // | |
250 | // If an insertion occurs, any references, pointers, or iterators are | |
251 | // invalidated. | |
252 | using Base::emplace_hint; | |
253 | ||
254 | // btree_set::merge() | |
255 | // | |
256 | // Extracts elements from a given `source` btree_set into this | |
257 | // `btree_set`. If the destination `btree_set` already contains an | |
258 | // element with an equivalent key, that element is not extracted. | |
259 | using Base::merge; | |
260 | ||
261 | // btree_set::swap(btree_set& other) | |
262 | // | |
263 | // Exchanges the contents of this `btree_set` with those of the `other` | |
264 | // btree_set, avoiding invocation of any move, copy, or swap operations on | |
265 | // individual elements. | |
266 | // | |
267 | // All iterators and references on the `btree_set` remain valid, excepting | |
268 | // for the past-the-end iterator, which is invalidated. | |
269 | using Base::swap; | |
270 | ||
271 | // btree_set::contains() | |
272 | // | |
273 | // template <typename K> bool contains(const K& key) const: | |
274 | // | |
275 | // Determines whether an element comparing equal to the given `key` exists | |
276 | // within the `btree_set`, returning `true` if so or `false` otherwise. | |
277 | // | |
278 | // Supports heterogeneous lookup, provided that the set is provided a | |
279 | // compatible heterogeneous comparator. | |
280 | using Base::contains; | |
281 | ||
282 | // btree_set::count() | |
283 | // | |
284 | // template <typename K> size_type count(const K& key) const: | |
285 | // | |
286 | // Returns the number of elements comparing equal to the given `key` within | |
287 | // the `btree_set`. Note that this function will return either `1` or `0` | |
288 | // since duplicate elements are not allowed within a `btree_set`. | |
289 | // | |
290 | // Supports heterogeneous lookup, provided that the set is provided a | |
291 | // compatible heterogeneous comparator. | |
292 | using Base::count; | |
293 | ||
294 | // btree_set::equal_range() | |
295 | // | |
296 | // Returns a closed range [first, last], defined by a `std::pair` of two | |
297 | // iterators, containing all elements with the passed key in the | |
298 | // `btree_set`. | |
299 | using Base::equal_range; | |
300 | ||
301 | // btree_set::find() | |
302 | // | |
303 | // template <typename K> iterator find(const K& key): | |
304 | // template <typename K> const_iterator find(const K& key) const: | |
305 | // | |
306 | // Finds an element with the passed `key` within the `btree_set`. | |
307 | // | |
308 | // Supports heterogeneous lookup, provided that the set is provided a | |
309 | // compatible heterogeneous comparator. | |
310 | using Base::find; | |
311 | ||
312 | // btree_set::get_allocator() | |
313 | // | |
314 | // Returns the allocator function associated with this `btree_set`. | |
315 | using Base::get_allocator; | |
316 | ||
317 | // btree_set::key_comp(); | |
318 | // | |
319 | // Returns the key comparator associated with this `btree_set`. | |
320 | using Base::key_comp; | |
321 | ||
322 | // btree_set::value_comp(); | |
323 | // | |
324 | // Returns the value comparator associated with this `btree_set`. The keys to | |
325 | // sort the elements are the values themselves, therefore `value_comp` and its | |
326 | // sibling member function `key_comp` are equivalent. | |
327 | using Base::value_comp; | |
31f18b77 FG |
328 | }; |
329 | ||
9f95a23c TL |
330 | // btree::swap(btree::btree_set<>, btree::btree_set<>) |
331 | // | |
332 | // Swaps the contents of two `btree::btree_set` containers. | |
333 | template <typename K, typename C, typename A> | |
334 | void swap(btree_set<K, C, A> &x, btree_set<K, C, A> &y) { | |
335 | return x.swap(y); | |
31f18b77 FG |
336 | } |
337 | ||
9f95a23c TL |
338 | // btree::erase_if(btree::btree_set<>, Pred) |
339 | // | |
340 | // Erases all elements that satisfy the predicate pred from the container. | |
341 | template <typename K, typename C, typename A, typename Pred> | |
342 | void erase_if(btree_set<K, C, A> &set, Pred pred) { | |
343 | for (auto it = set.begin(); it != set.end();) { | |
344 | if (pred(*it)) { | |
345 | it = set.erase(it); | |
346 | } else { | |
347 | ++it; | |
348 | } | |
349 | } | |
350 | } | |
31f18b77 | 351 | |
9f95a23c TL |
352 | // btree::btree_multiset<> |
353 | // | |
354 | // An `btree::btree_multiset<K>` is an ordered associative container of | |
355 | // keys and associated values designed to be a more efficient replacement | |
356 | // for `std::multiset` (in most cases). Unlike `btree::btree_set`, a B-tree | |
357 | // multiset allows equivalent elements. | |
358 | // | |
359 | // Keys are sorted using an (optional) comparison function, which defaults to | |
360 | // `std::less<K>`. | |
361 | // | |
362 | // An `btree::btree_multiset<K>` uses a default allocator of `std::allocator<K>` | |
363 | // to allocate (and deallocate) nodes, and construct and destruct values within | |
364 | // those nodes. You may instead specify a custom allocator `A` (which in turn | |
365 | // requires specifying a custom comparator `C`) as in | |
366 | // `btree::btree_multiset<K, C, A>`. | |
367 | // | |
368 | template <typename Key, typename Compare = std::less<Key>, | |
369 | typename Alloc = std::allocator<Key>> | |
370 | class btree_multiset | |
371 | : public internal::btree_multiset_container< | |
372 | internal::btree<internal::set_params< | |
373 | Key, Compare, Alloc, /*TargetNodeSize=*/256, | |
374 | /*Multi=*/true>>> { | |
375 | using Base = typename btree_multiset::btree_multiset_container; | |
31f18b77 FG |
376 | |
377 | public: | |
9f95a23c TL |
378 | // Constructors and Assignment Operators |
379 | // | |
380 | // A `btree_multiset` supports the same overload set as `std::set` | |
381 | // for construction and assignment: | |
382 | // | |
383 | // * Default constructor | |
384 | // | |
385 | // btree::btree_multiset<std::string> set1; | |
386 | // | |
387 | // * Initializer List constructor | |
388 | // | |
389 | // btree::btree_multiset<std::string> set2 = | |
390 | // {{"huey"}, {"dewey"}, {"louie"},}; | |
391 | // | |
392 | // * Copy constructor | |
393 | // | |
394 | // btree::btree_multiset<std::string> set3(set2); | |
395 | // | |
396 | // * Copy assignment operator | |
397 | // | |
398 | // btree::btree_multiset<std::string> set4; | |
399 | // set4 = set3; | |
400 | // | |
401 | // * Move constructor | |
402 | // | |
403 | // // Move is guaranteed efficient | |
404 | // btree::btree_multiset<std::string> set5(std::move(set4)); | |
405 | // | |
406 | // * Move assignment operator | |
407 | // | |
408 | // // May be efficient if allocators are compatible | |
409 | // btree::btree_multiset<std::string> set6; | |
410 | // set6 = std::move(set5); | |
411 | // | |
412 | // * Range constructor | |
413 | // | |
414 | // std::vector<std::string> v = {"a", "b"}; | |
415 | // btree::btree_multiset<std::string> set7(v.begin(), v.end()); | |
416 | btree_multiset() {} | |
417 | using Base::Base; | |
31f18b77 | 418 | |
9f95a23c TL |
419 | // btree_multiset::begin() |
420 | // | |
421 | // Returns an iterator to the beginning of the `btree_multiset`. | |
422 | using Base::begin; | |
31f18b77 | 423 | |
9f95a23c TL |
424 | // btree_multiset::cbegin() |
425 | // | |
426 | // Returns a const iterator to the beginning of the `btree_multiset`. | |
427 | using Base::cbegin; | |
31f18b77 | 428 | |
9f95a23c TL |
429 | // btree_multiset::end() |
430 | // | |
431 | // Returns an iterator to the end of the `btree_multiset`. | |
432 | using Base::end; | |
433 | ||
434 | // btree_multiset::cend() | |
435 | // | |
436 | // Returns a const iterator to the end of the `btree_multiset`. | |
437 | using Base::cend; | |
438 | ||
439 | // btree_multiset::empty() | |
440 | // | |
441 | // Returns whether or not the `btree_multiset` is empty. | |
442 | using Base::empty; | |
443 | ||
444 | // btree_multiset::max_size() | |
445 | // | |
446 | // Returns the largest theoretical possible number of elements within a | |
447 | // `btree_multiset` under current memory constraints. This value can be | |
448 | // thought of as the largest value of `std::distance(begin(), end())` for a | |
449 | // `btree_multiset<Key>`. | |
450 | using Base::max_size; | |
451 | ||
452 | // btree_multiset::size() | |
453 | // | |
454 | // Returns the number of elements currently within the `btree_multiset`. | |
455 | using Base::size; | |
456 | ||
457 | // btree_multiset::clear() | |
458 | // | |
459 | // Removes all elements from the `btree_multiset`. Invalidates any references, | |
460 | // pointers, or iterators referring to contained elements. | |
461 | using Base::clear; | |
462 | ||
463 | // btree_multiset::erase() | |
464 | // | |
465 | // Erases elements within the `btree_multiset`. Overloads are listed below. | |
466 | // | |
467 | // iterator erase(iterator position): | |
468 | // iterator erase(const_iterator position): | |
469 | // | |
470 | // Erases the element at `position` of the `btree_multiset`, returning | |
471 | // the iterator pointing to the element after the one that was erased | |
472 | // (or end() if none exists). | |
473 | // | |
474 | // iterator erase(const_iterator first, const_iterator last): | |
475 | // | |
476 | // Erases the elements in the open interval [`first`, `last`), returning | |
477 | // the iterator pointing to the element after the interval that was erased | |
478 | // (or end() if none exists). | |
479 | // | |
480 | // template <typename K> size_type erase(const K& key): | |
481 | // | |
482 | // Erases the elements matching the key, if any exist, returning the | |
483 | // number of elements erased. | |
484 | using Base::erase; | |
485 | ||
486 | // btree_multiset::insert() | |
487 | // | |
488 | // Inserts an element of the specified value into the `btree_multiset`, | |
489 | // returning an iterator pointing to the newly inserted element. | |
490 | // Any references, pointers, or iterators are invalidated. Overloads are | |
491 | // listed below. | |
492 | // | |
493 | // iterator insert(const value_type& value): | |
494 | // | |
495 | // Inserts a value into the `btree_multiset`, returning an iterator to the | |
496 | // inserted element. | |
497 | // | |
498 | // iterator insert(value_type&& value): | |
499 | // | |
500 | // Inserts a moveable value into the `btree_multiset`, returning an iterator | |
501 | // to the inserted element. | |
502 | // | |
503 | // iterator insert(const_iterator hint, const value_type& value): | |
504 | // iterator insert(const_iterator hint, value_type&& value): | |
505 | // | |
506 | // Inserts a value, using the position of `hint` as a non-binding suggestion | |
507 | // for where to begin the insertion search. Returns an iterator to the | |
508 | // inserted element. | |
509 | // | |
510 | // void insert(InputIterator first, InputIterator last): | |
511 | // | |
512 | // Inserts a range of values [`first`, `last`). | |
513 | // | |
514 | // void insert(std::initializer_list<init_type> ilist): | |
515 | // | |
516 | // Inserts the elements within the initializer list `ilist`. | |
517 | using Base::insert; | |
518 | ||
519 | // btree_multiset::emplace() | |
520 | // | |
521 | // Inserts an element of the specified value by constructing it in-place | |
522 | // within the `btree_multiset`. Any references, pointers, or iterators are | |
523 | // invalidated. | |
524 | using Base::emplace; | |
525 | ||
526 | // btree_multiset::emplace_hint() | |
527 | // | |
528 | // Inserts an element of the specified value by constructing it in-place | |
529 | // within the `btree_multiset`, using the position of `hint` as a non-binding | |
530 | // suggestion for where to begin the insertion search. | |
531 | // | |
532 | // Any references, pointers, or iterators are invalidated. | |
533 | using Base::emplace_hint; | |
534 | ||
9f95a23c TL |
535 | // btree_multiset::merge() |
536 | // | |
537 | // Extracts elements from a given `source` btree_multiset into this | |
538 | // `btree_multiset`. If the destination `btree_multiset` already contains an | |
539 | // element with an equivalent key, that element is not extracted. | |
540 | using Base::merge; | |
541 | ||
542 | // btree_multiset::swap(btree_multiset& other) | |
543 | // | |
544 | // Exchanges the contents of this `btree_multiset` with those of the `other` | |
545 | // btree_multiset, avoiding invocation of any move, copy, or swap operations | |
546 | // on individual elements. | |
547 | // | |
548 | // All iterators and references on the `btree_multiset` remain valid, | |
549 | // excepting for the past-the-end iterator, which is invalidated. | |
550 | using Base::swap; | |
551 | ||
552 | // btree_multiset::contains() | |
553 | // | |
554 | // template <typename K> bool contains(const K& key) const: | |
555 | // | |
556 | // Determines whether an element comparing equal to the given `key` exists | |
557 | // within the `btree_multiset`, returning `true` if so or `false` otherwise. | |
558 | // | |
559 | // Supports heterogeneous lookup, provided that the set is provided a | |
560 | // compatible heterogeneous comparator. | |
561 | using Base::contains; | |
562 | ||
563 | // btree_multiset::count() | |
564 | // | |
565 | // template <typename K> size_type count(const K& key) const: | |
566 | // | |
567 | // Returns the number of elements comparing equal to the given `key` within | |
568 | // the `btree_multiset`. | |
569 | // | |
570 | // Supports heterogeneous lookup, provided that the set is provided a | |
571 | // compatible heterogeneous comparator. | |
572 | using Base::count; | |
573 | ||
574 | // btree_multiset::equal_range() | |
575 | // | |
576 | // Returns a closed range [first, last], defined by a `std::pair` of two | |
577 | // iterators, containing all elements with the passed key in the | |
578 | // `btree_multiset`. | |
579 | using Base::equal_range; | |
580 | ||
581 | // btree_multiset::find() | |
582 | // | |
583 | // template <typename K> iterator find(const K& key): | |
584 | // template <typename K> const_iterator find(const K& key) const: | |
585 | // | |
586 | // Finds an element with the passed `key` within the `btree_multiset`. | |
587 | // | |
588 | // Supports heterogeneous lookup, provided that the set is provided a | |
589 | // compatible heterogeneous comparator. | |
590 | using Base::find; | |
591 | ||
592 | // btree_multiset::get_allocator() | |
593 | // | |
594 | // Returns the allocator function associated with this `btree_multiset`. | |
595 | using Base::get_allocator; | |
596 | ||
597 | // btree_multiset::key_comp(); | |
598 | // | |
599 | // Returns the key comparator associated with this `btree_multiset`. | |
600 | using Base::key_comp; | |
601 | ||
602 | // btree_multiset::value_comp(); | |
603 | // | |
604 | // Returns the value comparator associated with this `btree_multiset`. The | |
605 | // keys to sort the elements are the values themselves, therefore `value_comp` | |
606 | // and its sibling member function `key_comp` are equivalent. | |
607 | using Base::value_comp; | |
31f18b77 FG |
608 | }; |
609 | ||
9f95a23c TL |
610 | // btree::swap(btree::btree_multiset<>, btree::btree_multiset<>) |
611 | // | |
612 | // Swaps the contents of two `btree::btree_multiset` containers. | |
613 | template <typename K, typename C, typename A> | |
614 | void swap(btree_multiset<K, C, A> &x, btree_multiset<K, C, A> &y) { | |
615 | return x.swap(y); | |
31f18b77 FG |
616 | } |
617 | ||
9f95a23c TL |
618 | // btree::erase_if(btree::btree_multiset<>, Pred) |
619 | // | |
620 | // Erases all elements that satisfy the predicate pred from the container. | |
621 | template <typename K, typename C, typename A, typename Pred> | |
622 | void erase_if(btree_multiset<K, C, A> &set, Pred pred) { | |
623 | for (auto it = set.begin(); it != set.end();) { | |
624 | if (pred(*it)) { | |
625 | it = set.erase(it); | |
626 | } else { | |
627 | ++it; | |
628 | } | |
629 | } | |
630 | } | |
31f18b77 | 631 | |
9f95a23c | 632 | } // namespace btree |