|
Pigweed
|
|
|
Pigweed
|
|
#include <aa_tree.h>
Classes | |
| class | Item |
| class | Pair |
An extension of Item that includes storage for a key. More... | |
Public Types | |
| using | Key = K |
| using | Compare = Function< bool(Key, Key)> |
| using | GetKey = Function< Key(const V &)> |
| using | iterator = AATreeIterator<> |
 Public Types inherited from pw::containers::internal::GenericAATree | |
| using | iterator = AATreeIterator<> |
Public Member Functions | |
| constexpr | AATree (bool unique_keys, Compare &&compare, GetKey &&get_key) |
| std::pair< iterator, bool > | insert (AATreeItem &item) |
| template<class Iterator > | |
| void | insert (Iterator first, Iterator last) |
| size_t | erase_all (Key key) |
| void | merge (AATree< K, V > &other) |
| size_t | count (Key key) |
| iterator | find (Key key) |
| std::pair< iterator, iterator > | equal_range (Key key) |
| iterator | lower_bound (Key key) |
| iterator | upper_bound (Key key) |
| iterator | erase_one (AATreeItem &item) |
| iterator | erase_range (AATreeItem &first, AATreeItem &last) |
| Public Member Functions inherited from pw::containers::internal::GenericAATree | |
| constexpr | GenericAATree (bool unique_keys) |
| ~GenericAATree () | |
| Destructor. | |
| GenericAATree (const GenericAATree &)=delete | |
| GenericAATree & | operator= (const GenericAATree &)=delete |
| constexpr bool | unique_keys () const |
| void | SetRoot (AATreeItem *item) |
| Sets the tree's root item. | |
| constexpr iterator | begin () noexcept |
| Returns a pointer to the first item, if any. | |
| constexpr iterator | end () noexcept |
| Returns a pointer to the last item, if any. | |
| constexpr bool | empty () const |
| Returns whether the tree has zero items or not. | |
| size_t | size () const |
| Returns the number of items in the tree. | |
| constexpr size_t | max_size () const noexcept |
| void | clear () |
| iterator | erase_one (AATreeItem &item) |
| iterator | erase_range (AATreeItem &first, AATreeItem &last) |
| void | swap (GenericAATree &other) |
Exchanges this tree's items with the other tree's items. | |
An AA tree, as described by Arne Andersson in https://user.it.uu.se/~arneande/ps/simp.pdf. AA trees are simplified red-black which offer almost as much performance with much simpler and smaller code.
The tree provides an ordered collection of keyed items, and is used to implement pw::IntrusiveMap and pw::IntrusiveMultiMap. Keys are retrieved and compared using the functions provided via template parameters.
| Compare | Function with the signature `bool(Key, Key) that is used to order items. |
|
inlineconstexpr |
Constructs an empty AA tree.
| unique_keys | Indicates if this tree requires unique keys or allows duplicate keys. |
| size_t pw::containers::internal::AATree< K, V >::count | ( | Key | key | ) |
Returns the number of items in the tree with the given key.
If the tree requires unique keys, this simply 0 or 1.
| std::pair< GenericAATree::iterator, GenericAATree::iterator > pw::containers::internal::AATree< K, V >::equal_range | ( | Key | key | ) |
Returns a pair of items where the first points to the item with the smallest key that is not less than the given key, and the second points to the item with the smallest key that is greater than the given key.
| size_t pw::containers::internal::AATree< K, V >::erase_all | ( | Key | key | ) |
Removes items that match the given key, and returns an iterator to the item after the removed items and the number of items removed.
| iterator pw::containers::internal::GenericAATree::erase_one | ( | AATreeItem & | item | ) |
Removes an item from the tree and returns an iterator to the item after the removed item.
The items themselves are not destructed.
| iterator pw::containers::internal::GenericAATree::erase_range | ( | AATreeItem & | first, |
| AATreeItem & | last | ||
| ) |
Removes the items from first, inclusive, to last, exclusive from the tree and returns an iterator to the item after the last removed item.
The items themselves are not destructed.
| GenericAATree::iterator pw::containers::internal::AATree< K, V >::find | ( | Key | key | ) |
Returns a pointer to an item with the given key, or null if the tree does not contain such an item.
| std::pair< GenericAATree::iterator, bool > pw::containers::internal::AATree< K, V >::insert | ( | AATreeItem & | item | ) |
Attempts to add the given item to the tree.
The item will be added if the tree does not already contain an item with the given item's key or if the tree does not require unique keys.
true, or a pointer to the existing item with same key and false. | void pw::containers::internal::AATree< K, V >::insert | ( | Iterator | first, |
| Iterator | last | ||
| ) |
Inserts each item from first, inclusive, to last, exclusive. If the tree does not all duplicates and an equivalent item is already in the tree, the item is ignored.
| GenericAATree::iterator pw::containers::internal::AATree< K, V >::lower_bound | ( | Key | key | ) |
Returns the item in the tree with the smallest key that is greater than or equal to the given key, or null if the tree is empty.
| void pw::containers::internal::AATree< K, V >::merge | ( | AATree< K, V > & | other | ) |
Splices items from the other tree into this one.
The receiving tree's Compare and GetKey functions are used when inserting items.
| GenericAATree::iterator pw::containers::internal::AATree< K, V >::upper_bound | ( | Key | key | ) |
Returns the item in the tree with the smallest key that is strictly greater than the given key, or null if the tree is empty.
1.9.6