Base class with map-specific function. It is recommended to use the specializations simple_map, simple_mapC, simple_multimap, simple_multimapC, orbmap, orbmapC, orbmultimap and orbmultimapC to define and instantiate this class instead of this interface directly. More...
#include <orbtree.h>
Inheritance diagram for orbtree::orbtreemap< NodeAllocator, Compare, NVFunc, simple >:
Collaboration diagram for orbtree::orbtreemap< NodeAllocator, Compare, NVFunc, simple >:
Public Types | |
| typedef orbtree< NodeAllocator, Compare, NVFunc, false, simple >::value_type | value_type |
| typedef orbtree< NodeAllocator, Compare, NVFunc, false, simple >::key_type | key_type |
| typedef orbtree< NodeAllocator, Compare, NVFunc, false, simple >::size_type | size_type |
| typedef orbtree< NodeAllocator, Compare, NVFunc, false, simple >::difference_type | difference_type |
| typedef orbtree< NodeAllocator, Compare, NVFunc, false, simple >::iterator | iterator |
| typedef orbtree< NodeAllocator, Compare, NVFunc, false, simple >::const_iterator | const_iterator |
| typedef NodeAllocator::KeyValue::MappedType | mapped_type |
| type of values stored in this map | |
 Public Types inherited from orbtree::orbtree< NodeAllocator, Compare, NVFunc, false, simple > | |
| 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 | |
| orbtreemap (const NVFunc &f_=NVFunc(), const Compare &c_=Compare()) | |
| orbtreemap (NVFunc &&f_, const Compare &c_=Compare()) | |
| template<class T > | |
| orbtreemap (const T &t, const Compare &c_=Compare()) | |
| const mapped_type & | at (const key_type &k) const |
| Access mapped value for a given key, throws an exception if key is not found. More... | |
| template<class K > | |
| const mapped_type & | at (const K &k) const |
| Access mapped value for a key that compares equal to k, throws an exception if not such key is found. More... | |
| const mapped_type & | operator[] (const key_type &k) |
| Access mapped value for a given key, inserts a new element with the default value if not found. More... | |
| bool | set_value (const key_type &k, const mapped_type &v) |
| set value associated with the given key or insert new element More... | |
| bool | set_value (key_type &&k, const mapped_type &v) |
| set value associated with the given key or insert new element More... | |
| bool | set_value (const key_type &k, mapped_type &&v) |
| set value associated with the given key or insert new element More... | |
| bool | set_value (key_type &&k, mapped_type &&v) |
| set value associated with the given key or insert new element More... | |
| void | update_value (const key_type &k, const mapped_type &v) |
| update the value of an existing element – throws exception if the key does not exist | |
| void | update_value (const key_type &k, mapped_type &&v) |
| update the value of an existing element – throws exception if the key does not exist | |
| Public Member Functions inherited from orbtree::orbtree< NodeAllocator, Compare, NVFunc, false, simple > | |
| orbtree (const NVFunc &f_=NVFunc(), const Compare &c_=Compare()) | |
| orbtree (NVFunc &&f_, const Compare &c_=Compare()) | |
| 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... | |
| void | insert (InputIt first, InputIt last) |
| insert all elements in the range [first,last) | |
| insert_type | emplace (Args &&... args) |
| construct new element in-place | |
| 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 | |
| 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... | |
| iterator | find (const K &k) |
| iteraror that allows the modification of the stored value (for maps) find(const key_type& k) More... | |
| 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 | |
| iterator | lower_bound (const K &k) |
| return an iterator to the first element with key not less than 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 | |
| iterator | upper_bound (const K &k) |
| return an iterator to the first element with key greater than 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 | |
| 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 | |
| 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 | |
| bool | contains (const K &k) const |
| returns if an element with key equivalent to k exists in this tree | |
| 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... | |
| 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... | |
| 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... | |
| 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... | |
| 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... | |
| 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... | |
| 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). | |
| 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< NodeAllocator, Compare, NVFunc, false, simple >::NodeHandle | NodeHandle |
| typedef orbtree< NodeAllocator, Compare, NVFunc, false, simple >::KeyValue | KeyValue |
| Protected Types inherited from orbtree::orbtree< NodeAllocator, Compare, NVFunc, false, simple > | |
| 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) | |
Additional Inherited Members | |
| Protected Member Functions inherited from orbtree::orbtree< NodeAllocator, Compare, NVFunc, false, simple > | |
| std::enable_if< multi_, insert_type >::type | insert_helper (const value_type &v) |
| std::enable_if<!multi_, insert_type >::type | insert_helper (const value_type &v) |
| std::enable_if< multi_, insert_type >::type | insert_helper (value_type &&v) |
| std::enable_if<!multi_, insert_type >::type | insert_helper (value_type &&v) |
| std::enable_if< multi_, insert_type >::type | emplace_helper (Args &... args) |
| 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) | |
| 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 simple = false>
class orbtree::orbtreemap< NodeAllocator, Compare, NVFunc, simple >
Base class with map-specific function. It is recommended to use the specializations simple_map, simple_mapC, simple_multimap, simple_multimapC, orbmap, orbmapC, orbmultimap and orbmultimapC to define and instantiate this class instead of this interface directly.
Provides implementation for map-specific interface.
@tparam NodeAllocator internal base class to store nodes
- Template Parameters
-
Comapre comparison functor NVFunc function that calculates values associated with elements based on key and value
Member Function Documentation
◆ at() [1/2]
template<class NodeAllocator, class Compare, class NVFunc, bool simple = false>
|
inline |
Access mapped value for a given key, throws an exception if key is not found.
Cannot be used to modify value since that can require updating the tree internally. Use the functions set_value() or update_value() for that purpose instead.
◆ at() [2/2]
template<class NodeAllocator, class Compare, class NVFunc, bool simple = false>
template<class K >
|
inline |
Access mapped value for a key that compares equal to k, throws an exception if not such key is found.
Cannot be used to modify value since that can require updating the tree internally. Use the functions set_value() or update_value() for that purpose instead.
◆ operator[]()
template<class NodeAllocator, class Compare, class NVFunc, bool simple = false>
|
inline |
Access mapped value for a given key, inserts a new element with the default value if not found.
Cannot be used to modify value since that can require updating the tree internally. Use the functions set_value() or update_value() for that purpose instead.
◆ set_value() [1/4]
template<class NodeAllocator, class Compare, class NVFunc, bool simple = false>
|
inline |
set value associated with the given key or insert new element
Returns true if a new element was inserted, false if the value of an existing element was updated.
◆ set_value() [2/4]
template<class NodeAllocator, class Compare, class NVFunc, bool simple = false>
|
inline |
set value associated with the given key or insert new element
Returns true if a new element was inserted, false if the value of an existing element was updated.
◆ set_value() [3/4]
template<class NodeAllocator, class Compare, class NVFunc, bool simple = false>
|
inline |
set value associated with the given key or insert new element
Returns true if a new element was inserted, false if the value of an existing element was updated.
◆ set_value() [4/4]
template<class NodeAllocator, class Compare, class NVFunc, bool simple = false>
|
inline |
set value associated with the given key or insert new element
Returns true if a new element was inserted, false if the value of an existing element was updated.
The documentation for this class was generated from the following file:
