Generalized order statistic tree main interface. It is recommended to use the templates orbset, orbsetC, orbmultiset, orbmultisetC, orbmap, orbmapC, orbmultimap and orbmultimapC to instantiate various versions instead of directly using this class template. More...
#include <orbtree.h>
Inheritance diagram for orbtree::orbtree< NodeAllocator, Compare, NVFunc, multi, simple >:
Collaboration diagram for orbtree::orbtree< NodeAllocator, Compare, NVFunc, multi, simple >:
Classes | |
| struct | iterator_base |
| Iterators. More... | |
Public Types | |
| typedef NodeAllocator::KeyValue::ValueType | value_type |
| Values stored in this tree. Either the key (for sets) or an std::pair or orbtree::trivial_pair of key and value. | |
| typedef NodeAllocator::KeyValue::KeyType | key_type |
| Key type of nodes that determines ordering. | |
| typedef NodeAllocator::NVType | NVType |
| Type of values associated by nodes (calculated by NVFunc) | |
| typedef size_t | size_type |
| typedef size_t | difference_type |
| typedef iterator_base< true > | const_iterator |
| iterator that does not allow modification | |
| typedef std::conditional< NodeAllocator::KeyValue::keyonly, iterator_base< true >, iterator_base< false > >::type | iterator |
| iteraror that allows the modification of the stored value (for maps) | |
| typedef std::conditional< multi, iterator, std::pair< iterator, bool > >::type | insert_type |
| return type of insert functions | |
 Public Types inherited from orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi > | |
| typedef NodeAllocator::NVType | NVType |
| Type the function NVFunc returns. | |
Public Member Functions | |
| orbtree (const NVFunc &f_=NVFunc(), const Compare &c_=Compare()) | |
| orbtree (NVFunc &&f_, const Compare &c_=Compare()) | |
| template<class T > | |
| orbtree (const T &t, const Compare &c_=Compare()) | |
| iterator | begin () |
| const_iterator | begin () const |
| get an iterator to the beginning (node with the lowest key value) | |
| const_iterator | cbegin () const |
| get an iterator to the beginning (node with the lowest key value) | |
| iterator | end () |
| get an iterator to the beginning (node with the lowest key value) | |
| const_iterator | end () const |
| get the past-the-end iterator | |
| const_iterator | cend () const |
| get the past-the-end iterator | |
| bool | empty () const |
| get the past-the-end iterator | |
| size_t | size () const |
| check if the tree is empty | |
| constexpr size_t | max_size () const |
| return the maximum possible number of elements More... | |
| insert_type | insert (const value_type &v) |
| Insert new element. More... | |
| insert_type | insert (value_type &&v) |
| Insert new element. More... | |
| iterator | insert (const_iterator hint, const value_type &v) |
| Insert new element with hint. More... | |
| iterator | insert (const_iterator hint, value_type &&v) |
| iteraror that allows the modification of the stored value (for maps) insert(const_iterator hint, const value_type& v) More... | |
| template<class InputIt > | |
| void | insert (InputIt first, InputIt last) |
| insert all elements in the range [first,last) | |
| template<class... Args> | |
| insert_type | emplace (Args &&... args) |
| construct new element in-place | |
| template<class... Args> | |
| iterator | emplace_hint (const_iterator hint, Args &&... args) |
| construct new element in-place, using the given hint in a same way as insert() with a hint | |
| iterator | erase (const_iterator pos) |
| erase element pointed to by the given iterator; returns the element after it (in order) | |
| iterator | erase (const_iterator first, const_iterator last) |
| erase elements in the range [first,last); returns last | |
| size_t | erase (const key_type &k) |
| erase all elements with the given key; returns the number of elements erased | |
| size_t | count (const key_type &k) const |
| count number of elements with key | |
| template<class K > | |
| size_t | count (const K &k) const |
| count the number of elements whose key compares equal to k | |
| iterator | find (const key_type &k) |
| Find an element with the given key and return an iterator to it. More... | |
| const_iterator | find (const key_type &k) const |
| iteraror that allows the modification of the stored value (for maps) find(const key_type& k) More... | |
| template<class K > | |
| iterator | find (const K &k) |
| iteraror that allows the modification of the stored value (for maps) find(const key_type& k) More... | |
| template<class K > | |
| const_iterator | find (const K &k) const |
| iteraror that allows the modification of the stored value (for maps) find(const key_type& k) More... | |
| iterator | lower_bound (const key_type &k) |
| return an iterator to the first element with key not less than k | |
| const_iterator | lower_bound (const key_type &k) const |
| return an iterator to the first element with key not less than k | |
| template<class K > | |
| iterator | lower_bound (const K &k) |
| return an iterator to the first element with key not less than k | |
| template<class K > | |
| const_iterator | lower_bound (const K &k) const |
| return an iterator to the first element with key not less than k | |
| iterator | upper_bound (const key_type &k) |
| return an iterator to the first element with key greater than k | |
| const_iterator | upper_bound (const key_type &k) const |
| return an iterator to the first element with key greater than k | |
| template<class K > | |
| iterator | upper_bound (const K &k) |
| return an iterator to the first element with key greater than k | |
| template<class K > | |
| const_iterator | upper_bound (const K &k) const |
| return an iterator to the first element with key greater than k | |
| std::pair< iterator, iterator > | equal_range (const key_type &k) |
| return a pair of iterators corresponding to the range of all elements with key equal to k | |
| std::pair< const_iterator, const_iterator > | equal_range (const key_type &k) const |
| return a pair of iterators corresponding to the range of all elements with key equal to k | |
| template<class K > | |
| std::pair< iterator, iterator > | equal_range (const K &k) |
| return a pair of iterators corresponding to the range of all elements with keys that compares equal to k | |
| template<class K > | |
| std::pair< const_iterator, const_iterator > | equal_range (const K &k) const |
| return a pair of iterators corresponding to the range of all elements with keys that compares equal to k | |
| bool | contains (const key_type &k) const |
| returns if an element with key equivalent to k exists in this tree | |
| template<class K > | |
| bool | contains (const K &k) const |
| returns if an element with key equivalent to k exists in this tree | |
| template<bool simple_ = simple> | |
| void | get_sum_node (const_iterator it, typename std::enable_if<!simple_, NVType *>::type res) const |
| Calculate partial sum of the weights of nodes that come before the one pointed to by it. More... | |
| template<bool simple_ = simple> | |
| NVType | get_sum_node (typename std::enable_if< simple_, const_iterator >::type it) const |
| Calculate partial sum of nodes that come before the one pointed to by it. More... | |
| template<bool simple_ = simple> | |
| void | get_sum (const key_type &k, typename std::enable_if<!simple_, NVType *>::type res) const |
| Calculate partial sum of weights for keys that come before k. More... | |
| template<bool simple_ = simple> | |
| NVType | get_sum (typename std::enable_if< simple_, const key_type &>::type k) const |
| Calculate partial sum of weights for keys that come before k. More... | |
| template<class K , bool simple_ = simple> | |
| void | get_sum (const K &k, typename std::enable_if<!simple_, NVType *>::type res) const |
| Calculate partial sum of weights for keys that come before k. More... | |
| template<class K , bool simple_ = simple> | |
| NVType | get_sum (typename std::enable_if< simple_, const K &>::type k) const |
| Calculate partial sum of weights for keys that come before k. More... | |
| template<bool simple_ = simple> | |
| void | get_norm (typename std::enable_if<!simple_, NVType *>::type res) const |
| Calculate normalization, i.e. sum of all weights. Equivalent to get_sum(cend(),res). | |
| template<bool simple_ = simple> | |
| NVType | get_norm (typename std::enable_if< simple_, void *>::type k=0) const |
| Calculate normalization, i.e. sum of all weights. Equivalent to get_sum(cend()). | |
| Public Member Functions inherited from orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi > | |
| void | clear () |
| erase all nodes | |
| template<class K > | |
| void | get_sum_fv (const K &k, NVType *res) const |
| get the generalized rank for a key, i.e. the sum of NVFunc for all nodes with node.key < k | |
| void | get_sum_fv_node (NodeHandle x, NVType *res) const |
| get the generalized rank for a given node, i.e. the sum of NVFunv for all nodes before it in order | |
| void | get_norm_fv (NVType *res) const |
| get the normalization factor, i.e. the sum of all keys | |
| void | check_tree (double epsilon=-1.0) const |
| check that the tree is valid More... | |
| template<class... T> | |
| auto | emplace (T &&... t) -> std::pair< NodeHandle, bool > |
| template<class... T> | |
| auto | emplace_hint (NodeHandle hint, T &&... t) -> NodeHandle |
Protected Types | |
| typedef orbtree_base< NodeAllocator, Compare, NVFunc, multi >::NodeHandle | NodeHandle |
| typedef orbtree_base< NodeAllocator, Compare, NVFunc, multi >::KeyValue | KeyValue |
| Protected Types inherited from orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi > | |
| typedef NodeAllocator::Node | Node |
| node objects | |
| typedef NodeAllocator::KeyValue | KeyValue |
| typedef NodeAllocator::KeyValue::KeyType | KeyType |
| typedef NodeAllocator::KeyValue::ValueType | ValueType |
| typedef NodeAllocator::NodeHandle | NodeHandle |
| handle to refer nodes to (pointer or integer) | |
Protected Member Functions | |
| template<bool multi_ = multi> | |
| std::enable_if< multi_, insert_type >::type | insert_helper (const value_type &v) |
| template<bool multi_ = multi> | |
| std::enable_if<!multi_, insert_type >::type | insert_helper (const value_type &v) |
| template<bool multi_ = multi> | |
| std::enable_if< multi_, insert_type >::type | insert_helper (value_type &&v) |
| template<bool multi_ = multi> | |
| std::enable_if<!multi_, insert_type >::type | insert_helper (value_type &&v) |
| template<class... Args, bool multi_ = multi> | |
| std::enable_if< multi_, insert_type >::type | emplace_helper (Args &... args) |
| template<class... Args, bool multi_ = multi> | |
| std::enable_if<!multi_, insert_type >::type | emplace_helper (Args &... args) |
| Protected Member Functions inherited from orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi > | |
| void | NVAdd (NVType *x, const NVType *y) const |
| function to add NVType values; checks for overflow and throws exception in the case of integral types | |
| void | NVSubtract (NVType *x, const NVType *y) const |
| function to subtract NVType values; checks for overflow and throws exception in the case of integral types | |
| void | create_sentinels () |
| Node & | get_node (NodeHandle n) |
| convenience function that returns node object for a node handle | |
| const Node & | get_node (NodeHandle n) const |
| convenience function that returns node object for a node handle | |
| NodeHandle | root () const |
| handle of root sentinel | |
| NodeHandle | nil () const |
| handle of nil sentinel | |
| orbtree_base (const NVFunc &f_, const Compare &c_) | |
| orbtree_base (NVFunc &&f_, const Compare &c_) | |
| template<class T > | |
| orbtree_base (const T &t, const Compare &c_) | |
| std::pair< NodeHandle, bool > | insert (ValueType &&kv) |
| Insert new element. More... | |
| std::pair< NodeHandle, bool > | insert (const ValueType &kv) |
| Insert new element. More... | |
| NodeHandle | insert (NodeHandle hint, ValueType &&kv) |
| Insert new element with hint. More... | |
| NodeHandle | insert (NodeHandle hint, const ValueType &kv) |
| Insert new element with hint. More... | |
| template<class... T> | |
| std::pair< NodeHandle, bool > | emplace (T &&... t) |
| Construct new element in place. More... | |
| template<class... T> | |
| NodeHandle | emplace_hint (NodeHandle hint, T &&... t) |
| Construct new element in place with hint. More... | |
| bool | insert_search (const KeyType &k, NodeHandle &n, bool &insert_left) const |
| helper for insert – find the location where to insert More... | |
| bool | insert_search_hint (NodeHandle hint, const KeyType &k, NodeHandle &n, bool &insert_left) const |
| helper for insert – find the location where to insert More... | |
| void | insert_helper (NodeHandle n, NodeHandle n1, bool insert_left) |
| helper function to do the real work for insert More... | |
| template<class K > | |
| auto | find (const K &key) const -> NodeHandle |
| find any node with the given key More... | |
| template<class K > | |
| auto | lower_bound (const K &key) const -> NodeHandle |
| find the first node not less than the given key – returns nil if none found | |
| template<class K > | |
| auto | upper_bound (const K &key) const -> NodeHandle |
| find the first node larger than the given key – returns nil if none found | |
| const KeyType & | get_node_key (NodeHandle n) const |
| convenience function to get the key of a node | |
| bool | compare_key_equals (NodeHandle n, const KeyType &k) const |
| helper for erase to compare elements | |
| void | get_node_grvalue (NodeHandle n, NVType *res) const |
| get the value of NVFunc for the given node More... | |
| NodeHandle | first () const |
| get first node (or nil) | |
| NodeHandle | last () const |
| get last node (or nil) | |
| NodeHandle | next (NodeHandle n) const |
| get node after n (or nil) – note: next(nil) == nil | |
| NodeHandle | previous (NodeHandle n) const |
| get node before n (or nil) – note: previous(nil) == last() to make it easier to implement end() iterator | |
| NodeHandle | erase (NodeHandle n) |
| remove the given node – return the next node (i.e. next(n) before deleting n) | |
| Node & | get_left (NodeHandle n) |
| convenience helper to get node object that is the left child of the given node handle | |
| const Node & | get_left (NodeHandle n) const |
| convenience helper to get node object that is the left child of the given node handle | |
| Node & | get_right (NodeHandle n) |
| convenience helper to get node object that is the right child of the given node handle | |
| const Node & | get_right (NodeHandle n) const |
| convenience helper to get node object that is the right child of the given node handle | |
| Node & | get_parent (NodeHandle n) |
| convenience helper to get node object that is the parent of the given node handle | |
| const Node & | get_parent (NodeHandle n) const |
| convenience helper to get node object that is the parent of the given node handle | |
| NodeHandle | get_sibling_handle (NodeHandle n) const |
| convenience helper to get the handle of a node's sibling (i.e. parent's other child) | |
| Node & | get_sibling (NodeHandle n) |
| convenience helper to get the node object of a node's sibling (i.e. parent's other child) | |
| const Node & | get_sibling (NodeHandle n) const |
| convenience helper to get the node object of a node's sibling (i.e. parent's other child) | |
| bool | is_left_side (NodeHandle n) const |
| check which side child is n (i.e. returns true if n is the left child of its parent) – requires that n != root | |
| void | update_sum (NodeHandle n) |
| update the sum only inside n | |
| void | update_sum_r (NodeHandle n) |
| update the sum recursively up the tree | |
| template<class KeyValue_ = KeyValue> | |
| void | update_value (NodeHandle n, typename KeyValue_::MappedType const &v) |
| update value in a node – only if this is a map; update sum recursively based on it as well | |
| template<class KeyValue_ = KeyValue> | |
| void | update_value (NodeHandle n, typename KeyValue_::MappedType &&v) |
| update value in a node – only if this is a map; update sum recursively based on it as well | |
| void | rotate_left (NodeHandle x) |
| left rotate More... | |
| void | rotate_right (NodeHandle x) |
| right rotate More... | |
| void | rotate_parent (NodeHandle x) |
| rotate by parent of x (x takes parent's place), this calls either rotate_left() or rotate_right() with the parent of x | |
| void | check_tree_r (double epsilon, NodeHandle x, size_t black_count, size_t &previous_black_count) const |
| recursive helper for check_tree(double) | |
| Protected Member Functions inherited from orbtree::NVFunc_wrapper< NVFunc > | |
| NVFunc_wrapper (const NVFunc &f_) | |
| NVFunc_wrapper (NVFunc &&f_) | |
| template<class T > | |
| NVFunc_wrapper (const T &t) | |
Additional Inherited Members | |
| Protected Attributes inherited from orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi > | |
| size_t | size1 |
| keep track of the number of inserted elements | |
| NVFunc & | f |
| Compare | c |
| Protected Attributes inherited from orbtree::NVFunc_wrapper< NVFunc > | |
| NVFunc | f |
Detailed Description
template<class NodeAllocator, class Compare, class NVFunc, bool multi, bool simple = false>
class orbtree::orbtree< NodeAllocator, Compare, NVFunc, multi, simple >
Generalized order statistic tree main interface. It is recommended to use the templates orbset, orbsetC, orbmultiset, orbmultisetC, orbmap, orbmapC, orbmultimap and orbmultimapC to instantiate various versions instead of directly using this class template.
Generalized order statistic tree main interface. This class provides common functionality for sets, maps, multisets and multimaps, depending on the templates provided. Most of the interface is defined here. Interface should be as similar as possible to std::set, std::multiset, std::map and std::multimap.
- Template Parameters
-
NodeAllocator internal base class to store nodes Comapre comparison functor NVFunc function that calculates values associated with elements based on key and value multi determines if this is a multiset / multimap (keys can be present multiple times) or not simple determines if the weight function returns one value (if true) or multiple values (if false). This changes the return value of get_sum()
Member Function Documentation
◆ find() [1/4]
template<class NodeAllocator, class Compare, class NVFunc, bool multi, bool simple = false>
|
inline |
Find an element with the given key and return an iterator to it.
Returns the past-the-end iterator if no such element is found.
In case of multimap / multiset, any element with such key can be returned. Use lower_bound() and upper_bound() if the beginning or end of a range is required.
◆ find() [2/4]
template<class NodeAllocator, class Compare, class NVFunc, bool multi, bool simple = false>
|
inline |
iteraror that allows the modification of the stored value (for maps) find(const key_type& k)
find(const key_type& k) Returns const iterator for const tree.
◆ find() [3/4]
template<class NodeAllocator, class Compare, class NVFunc, bool multi, bool simple = false>
template<class K >
|
inline |
iteraror that allows the modification of the stored value (for maps) find(const key_type& k)
find(const key_type& k) Works for any type K that is comparable to the keys.
◆ find() [4/4]
template<class NodeAllocator, class Compare, class NVFunc, bool multi, bool simple = false>
template<class K >
|
inline |
iteraror that allows the modification of the stored value (for maps) find(const key_type& k)
find(const key_type& k) Works for any type K that is comparable to the keys.
Returns const iterator for const tree.
◆ get_sum() [1/4]
template<class NodeAllocator, class Compare, class NVFunc, bool multi, bool simple = false>
template<bool simple_ = simple>
|
inline |
Calculate partial sum of weights for keys that come before k.
Result is returned in res, which must point to an array large enough (with elements corresponding to the number of components returned by NVFunc).
◆ get_sum() [2/4]
template<class NodeAllocator, class Compare, class NVFunc, bool multi, bool simple = false>
template<bool simple_ = simple>
|
inline |
Calculate partial sum of weights for keys that come before k.
Specialized version for simple containers (i.e. where the weight function returns only one component) that returns the result directly instead of using a pointer.
◆ get_sum() [3/4]
template<class NodeAllocator, class Compare, class NVFunc, bool multi, bool simple = false>
template<class K , bool simple_ = simple>
|
inline |
Calculate partial sum of weights for keys that come before k.
Result is returned in res, which must point to an array large enough (with elements corresponding to the number of components returned by NVFunc).
◆ get_sum() [4/4]
template<class NodeAllocator, class Compare, class NVFunc, bool multi, bool simple = false>
template<class K , bool simple_ = simple>
|
inline |
Calculate partial sum of weights for keys that come before k.
Specialized version for simple containers (i.e. where the weight function returns only one component) that returns the result directly instead of using a pointer.
◆ get_sum_node() [1/2]
template<class NodeAllocator, class Compare, class NVFunc, bool multi, bool simple = false>
template<bool simple_ = simple>
|
inline |
Calculate partial sum of the weights of nodes that come before the one pointed to by it.
Result is returned in res, which must point to an array large enough (e.g. with at least as many elements as the components calculated by NVFunc)
◆ get_sum_node() [2/2]
template<class NodeAllocator, class Compare, class NVFunc, bool multi, bool simple = false>
template<bool simple_ = simple>
|
inline |
Calculate partial sum of nodes that come before the one pointed to by it.
Specialized version for simple containers (i.e. where the weight function returns only one component) that returns the result directly instead of using a pointer.
◆ insert() [1/4]
template<class NodeAllocator, class Compare, class NVFunc, bool multi, bool simple = false>
|
inline |
Insert new element.
For non-multi map/set, the return type is std::pair<iterator,bool>, where the second element indicates if insert was successful. If an element with the same key already existed, the insert fails and false is returned.
For multi map/set, inserting always succeeds and the return type is an iterator to the new element. In this case, a new element is always inserted after any existing elements with the same key
◆ insert() [2/4]
template<class NodeAllocator, class Compare, class NVFunc, bool multi, bool simple = false>
|
inline |
Insert new element.
For non-multi map/set, the return type is std::pair<iterator,bool>, where the second element indicates if insert was successful. If an element with the same key already existed, the insert fails and false is returned.
For multi map/set, inserting always succeeds and the return type is an iterator to the new element. In this case, a new element is always inserted after any existing elements with the same key
◆ insert() [3/4]
template<class NodeAllocator, class Compare, class NVFunc, bool multi, bool simple = false>
|
inline |
Insert new element with hint.
Caller suggests a position which is before the element pointed to by the supplied iterator.
For non-multi tree (map/set; i.e. duplicates are not allowed):
- if the hint points to the correct position (i.e. the new element should go before the element referenced by the hint iterator), then a search is not performed, so the insertion cost is amortized constant
- in all other cases, the hint is ignored
For multi tree (duplicate keys are allowed):
- if the key is equal to the key of element referenced by the hint iterator, then the new element is inserted before it
- otherwise, the new element is inserted as close as possible
◆ insert() [4/4]
template<class NodeAllocator, class Compare, class NVFunc, bool multi, bool simple = false>
|
inline |
iteraror that allows the modification of the stored value (for maps) insert(const_iterator hint, const value_type& v)
◆ max_size()
template<class NodeAllocator, class Compare, class NVFunc, bool multi, bool simple = false>
|
inline |
return the maximum possible number of elements
return the number of elemets
The documentation for this class was generated from the following file:
