]>
git.proxmox.com Git - ceph.git/blob - ceph/src/include/cpp-btree/btree_set.h
1 // Copyright 2018 The Abseil Authors.
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
7 // https://www.apache.org/licenses/LICENSE-2.0
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.
15 // -----------------------------------------------------------------------------
17 // -----------------------------------------------------------------------------
19 // This header file defines B-tree sets: sorted associative containers of
22 // * `absl::btree_set<>`
23 // * `absl::btree_multiset<>`
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.
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.
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.
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
50 #include "btree_container.h"
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
60 // Keys are sorted using an (optional) comparison function, which defaults to
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>`.
69 template <typename Key
, typename Compare
= std::less
<Key
>,
70 typename Alloc
= std::allocator
<Key
>>
72 : public internal::btree_set_container
<
73 internal::btree
<internal::set_params
<
74 Key
, Compare
, Alloc
, /*TargetNodeSize=*/256,
76 using Base
= typename
btree_set::btree_set_container
;
79 // Constructors and Assignment Operators
81 // A `btree_set` supports the same overload set as `std::set`
82 // for construction and assignment:
84 // * Default constructor
86 // btree::btree_set<std::string> set1;
88 // * Initializer List constructor
90 // btree::btree_set<std::string> set2 =
91 // {{"huey"}, {"dewey"}, {"louie"},};
95 // btree::btree_set<std::string> set3(set2);
97 // * Copy assignment operator
99 // btree::btree_set<std::string> set4;
102 // * Move constructor
104 // // Move is guaranteed efficient
105 // btree::btree_set<std::string> set5(std::move(set4));
107 // * Move assignment operator
109 // // May be efficient if allocators are compatible
110 // btree::btree_set<std::string> set6;
111 // set6 = std::move(set5);
113 // * Range constructor
115 // std::vector<std::string> v = {"a", "b"};
116 // btree::btree_set<std::string> set7(v.begin(), v.end());
120 // btree_set::begin()
122 // Returns an iterator to the beginning of the `btree_set`.
125 // btree_set::cbegin()
127 // Returns a const iterator to the beginning of the `btree_set`.
132 // Returns an iterator to the end of the `btree_set`.
137 // Returns a const iterator to the end of the `btree_set`.
140 // btree_set::empty()
142 // Returns whether or not the `btree_set` is empty.
145 // btree_set::max_size()
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
151 using Base::max_size
;
155 // Returns the number of elements currently within the `btree_set`.
158 // btree_set::clear()
160 // Removes all elements from the `btree_set`. Invalidates any references,
161 // pointers, or iterators referring to contained elements.
164 // btree_set::erase()
166 // Erases elements within the `btree_set`. Overloads are listed below.
168 // iterator erase(iterator position):
169 // iterator erase(const_iterator position):
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).
175 // iterator erase(const_iterator first, const_iterator last):
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).
181 // template <typename K> size_type erase(const K& key):
183 // Erases the element with the matching key, if it exists, returning the
184 // number of elements erased.
187 // btree_set::insert()
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.
195 // std::pair<iterator,bool> insert(const value_type& value):
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.
201 // std::pair<iterator,bool> insert(value_type&& value):
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
208 // iterator insert(const_iterator hint, const value_type& value):
209 // iterator insert(const_iterator hint, value_type&& value):
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
216 // void insert(InputIterator first, InputIterator last):
218 // Inserts a range of values [`first`, `last`).
220 // void insert(std::initializer_list<init_type> ilist):
222 // Inserts the elements within the initializer list `ilist`.
225 // btree_set::emplace()
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
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.
235 // If an insertion occurs, any references, pointers, or iterators are
239 // btree_set::emplace_hint()
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.
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.
250 // If an insertion occurs, any references, pointers, or iterators are
252 using Base::emplace_hint
;
254 // btree_set::merge()
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.
261 // btree_set::swap(btree_set& other)
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.
267 // All iterators and references on the `btree_set` remain valid, excepting
268 // for the past-the-end iterator, which is invalidated.
271 // btree_set::contains()
273 // template <typename K> bool contains(const K& key) const:
275 // Determines whether an element comparing equal to the given `key` exists
276 // within the `btree_set`, returning `true` if so or `false` otherwise.
278 // Supports heterogeneous lookup, provided that the set is provided a
279 // compatible heterogeneous comparator.
280 using Base::contains
;
282 // btree_set::count()
284 // template <typename K> size_type count(const K& key) const:
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`.
290 // Supports heterogeneous lookup, provided that the set is provided a
291 // compatible heterogeneous comparator.
294 // btree_set::equal_range()
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
299 using Base::equal_range
;
303 // template <typename K> iterator find(const K& key):
304 // template <typename K> const_iterator find(const K& key) const:
306 // Finds an element with the passed `key` within the `btree_set`.
308 // Supports heterogeneous lookup, provided that the set is provided a
309 // compatible heterogeneous comparator.
312 // btree_set::get_allocator()
314 // Returns the allocator function associated with this `btree_set`.
315 using Base::get_allocator
;
317 // btree_set::key_comp();
319 // Returns the key comparator associated with this `btree_set`.
320 using Base::key_comp
;
322 // btree_set::value_comp();
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
;
330 // btree::swap(btree::btree_set<>, btree::btree_set<>)
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
) {
338 // btree::erase_if(btree::btree_set<>, Pred)
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();) {
352 // btree::btree_multiset<>
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.
359 // Keys are sorted using an (optional) comparison function, which defaults to
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>`.
368 template <typename Key
, typename Compare
= std::less
<Key
>,
369 typename Alloc
= std::allocator
<Key
>>
371 : public internal::btree_multiset_container
<
372 internal::btree
<internal::set_params
<
373 Key
, Compare
, Alloc
, /*TargetNodeSize=*/256,
375 using Base
= typename
btree_multiset::btree_multiset_container
;
378 // Constructors and Assignment Operators
380 // A `btree_multiset` supports the same overload set as `std::set`
381 // for construction and assignment:
383 // * Default constructor
385 // btree::btree_multiset<std::string> set1;
387 // * Initializer List constructor
389 // btree::btree_multiset<std::string> set2 =
390 // {{"huey"}, {"dewey"}, {"louie"},};
392 // * Copy constructor
394 // btree::btree_multiset<std::string> set3(set2);
396 // * Copy assignment operator
398 // btree::btree_multiset<std::string> set4;
401 // * Move constructor
403 // // Move is guaranteed efficient
404 // btree::btree_multiset<std::string> set5(std::move(set4));
406 // * Move assignment operator
408 // // May be efficient if allocators are compatible
409 // btree::btree_multiset<std::string> set6;
410 // set6 = std::move(set5);
412 // * Range constructor
414 // std::vector<std::string> v = {"a", "b"};
415 // btree::btree_multiset<std::string> set7(v.begin(), v.end());
419 // btree_multiset::begin()
421 // Returns an iterator to the beginning of the `btree_multiset`.
424 // btree_multiset::cbegin()
426 // Returns a const iterator to the beginning of the `btree_multiset`.
429 // btree_multiset::end()
431 // Returns an iterator to the end of the `btree_multiset`.
434 // btree_multiset::cend()
436 // Returns a const iterator to the end of the `btree_multiset`.
439 // btree_multiset::empty()
441 // Returns whether or not the `btree_multiset` is empty.
444 // btree_multiset::max_size()
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
;
452 // btree_multiset::size()
454 // Returns the number of elements currently within the `btree_multiset`.
457 // btree_multiset::clear()
459 // Removes all elements from the `btree_multiset`. Invalidates any references,
460 // pointers, or iterators referring to contained elements.
463 // btree_multiset::erase()
465 // Erases elements within the `btree_multiset`. Overloads are listed below.
467 // iterator erase(iterator position):
468 // iterator erase(const_iterator position):
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).
474 // iterator erase(const_iterator first, const_iterator last):
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).
480 // template <typename K> size_type erase(const K& key):
482 // Erases the elements matching the key, if any exist, returning the
483 // number of elements erased.
486 // btree_multiset::insert()
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
493 // iterator insert(const value_type& value):
495 // Inserts a value into the `btree_multiset`, returning an iterator to the
498 // iterator insert(value_type&& value):
500 // Inserts a moveable value into the `btree_multiset`, returning an iterator
501 // to the inserted element.
503 // iterator insert(const_iterator hint, const value_type& value):
504 // iterator insert(const_iterator hint, value_type&& value):
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
510 // void insert(InputIterator first, InputIterator last):
512 // Inserts a range of values [`first`, `last`).
514 // void insert(std::initializer_list<init_type> ilist):
516 // Inserts the elements within the initializer list `ilist`.
519 // btree_multiset::emplace()
521 // Inserts an element of the specified value by constructing it in-place
522 // within the `btree_multiset`. Any references, pointers, or iterators are
526 // btree_multiset::emplace_hint()
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.
532 // Any references, pointers, or iterators are invalidated.
533 using Base::emplace_hint
;
535 // btree_multiset::extract()
537 // Extracts the indicated element, erasing it in the process, and returns it
538 // as a C++17-compatible node handle. Overloads are listed below.
540 // node_type extract(const_iterator position):
542 // Extracts the element at the indicated position and returns a node handle
543 // owning that extracted data.
545 // template <typename K> node_type extract(const K& x):
547 // Extracts the element with the key matching the passed key value and
548 // returns a node handle owning that extracted data. If the `btree_multiset`
549 // does not contain an element with a matching key, this function returns an
550 // empty node handle.
552 // NOTE: In this context, `node_type` refers to the C++17 concept of a
553 // move-only type that owns and provides access to the elements in associative
554 // containers (https://en.cppreference.com/w/cpp/container/node_handle).
555 // It does NOT refer to the data layout of the underlying btree.
558 // btree_multiset::merge()
560 // Extracts elements from a given `source` btree_multiset into this
561 // `btree_multiset`. If the destination `btree_multiset` already contains an
562 // element with an equivalent key, that element is not extracted.
565 // btree_multiset::swap(btree_multiset& other)
567 // Exchanges the contents of this `btree_multiset` with those of the `other`
568 // btree_multiset, avoiding invocation of any move, copy, or swap operations
569 // on individual elements.
571 // All iterators and references on the `btree_multiset` remain valid,
572 // excepting for the past-the-end iterator, which is invalidated.
575 // btree_multiset::contains()
577 // template <typename K> bool contains(const K& key) const:
579 // Determines whether an element comparing equal to the given `key` exists
580 // within the `btree_multiset`, returning `true` if so or `false` otherwise.
582 // Supports heterogeneous lookup, provided that the set is provided a
583 // compatible heterogeneous comparator.
584 using Base::contains
;
586 // btree_multiset::count()
588 // template <typename K> size_type count(const K& key) const:
590 // Returns the number of elements comparing equal to the given `key` within
591 // the `btree_multiset`.
593 // Supports heterogeneous lookup, provided that the set is provided a
594 // compatible heterogeneous comparator.
597 // btree_multiset::equal_range()
599 // Returns a closed range [first, last], defined by a `std::pair` of two
600 // iterators, containing all elements with the passed key in the
602 using Base::equal_range
;
604 // btree_multiset::find()
606 // template <typename K> iterator find(const K& key):
607 // template <typename K> const_iterator find(const K& key) const:
609 // Finds an element with the passed `key` within the `btree_multiset`.
611 // Supports heterogeneous lookup, provided that the set is provided a
612 // compatible heterogeneous comparator.
615 // btree_multiset::get_allocator()
617 // Returns the allocator function associated with this `btree_multiset`.
618 using Base::get_allocator
;
620 // btree_multiset::key_comp();
622 // Returns the key comparator associated with this `btree_multiset`.
623 using Base::key_comp
;
625 // btree_multiset::value_comp();
627 // Returns the value comparator associated with this `btree_multiset`. The
628 // keys to sort the elements are the values themselves, therefore `value_comp`
629 // and its sibling member function `key_comp` are equivalent.
630 using Base::value_comp
;
633 // btree::swap(btree::btree_multiset<>, btree::btree_multiset<>)
635 // Swaps the contents of two `btree::btree_multiset` containers.
636 template <typename K
, typename C
, typename A
>
637 void swap(btree_multiset
<K
, C
, A
> &x
, btree_multiset
<K
, C
, A
> &y
) {
641 // btree::erase_if(btree::btree_multiset<>, Pred)
643 // Erases all elements that satisfy the predicate pred from the container.
644 template <typename K
, typename C
, typename A
, typename Pred
>
645 void erase_if(btree_multiset
<K
, C
, A
> &set
, Pred pred
) {
646 for (auto it
= set
.begin(); it
!= set
.end();) {