![]() |
Vcsn
2.3a
Be Rational
|
Sparse Map implementation. More...
#include <sparse-map.hh>
Public Member Functions | |
sparse_map (size_t max_size=0) | |
The Keys correspond to indexes so they have to be unsigned. More... | |
void | set_max_size (size_t max_size) |
template<typename K , typename V > | |
bool | emplace (K &&k, V &&v) |
bool | insert (const std::pair< Key, Value > &p) |
Insert new value. More... | |
bool | has (Key k) const |
Value & | operator[] (Key k) |
Access an element. More... | |
void | erase (Key k) |
Erase an element. More... | |
void | clear () |
Flush all elements from the set. More... | |
auto | begin () |
auto | end () |
auto | begin () const |
auto | end () const |
Private Attributes | |
std::vector< std::pair< Key, Value > > | dense_ |
std::vector< Key > | sparse_ |
Key | curr_ = 0 |
Sparse Map implementation.
Based on Russ Cox trick allowing constant operations for sets: http://research.swtch.com/sparse Porting this concept to maps.
Definition at line 15 of file sparse-map.hh.
|
inline |
The Keys correspond to indexes so they have to be unsigned.
Definition at line 22 of file sparse-map.hh.
|
inline |
Definition at line 99 of file sparse-map.hh.
References vcsn::sparse_map< Key, Value >::dense_.
|
inline |
Definition at line 109 of file sparse-map.hh.
References vcsn::sparse_map< Key, Value >::dense_.
|
inline |
Flush all elements from the set.
Definition at line 94 of file sparse-map.hh.
References vcsn::sparse_map< Key, Value >::curr_.
|
inline |
Definition at line 35 of file sparse-map.hh.
References vcsn::sparse_map< Key, Value >::insert(), and vcsn::v.
Referenced by vcsn::sparse_map< Key, Value >::operator[]().
|
inline |
Definition at line 104 of file sparse-map.hh.
References vcsn::sparse_map< Key, Value >::curr_, and vcsn::sparse_map< Key, Value >::dense_.
|
inline |
Definition at line 114 of file sparse-map.hh.
References vcsn::sparse_map< Key, Value >::curr_, and vcsn::sparse_map< Key, Value >::dense_.
|
inline |
Erase an element.
Does nothing if the element is not present.
Definition at line 82 of file sparse-map.hh.
References vcsn::sparse_map< Key, Value >::curr_, vcsn::sparse_map< Key, Value >::dense_, vcsn::sparse_map< Key, Value >::has(), and vcsn::sparse_map< Key, Value >::sparse_.
|
inline |
Definition at line 62 of file sparse-map.hh.
References vcsn::sparse_map< Key, Value >::curr_, vcsn::sparse_map< Key, Value >::dense_, and vcsn::sparse_map< Key, Value >::sparse_.
Referenced by vcsn::sparse_map< Key, Value >::erase(), vcsn::has(), vcsn::sparse_map< Key, Value >::insert(), and vcsn::sparse_map< Key, Value >::operator[]().
|
inline |
Insert new value.
Definition at line 44 of file sparse-map.hh.
References vcsn::sparse_map< Key, Value >::curr_, vcsn::sparse_map< Key, Value >::dense_, vcsn::sparse_map< Key, Value >::has(), and vcsn::sparse_map< Key, Value >::sparse_.
Referenced by vcsn::sparse_map< Key, Value >::emplace().
|
inline |
Access an element.
Creates a new value if the key is not present
Definition at line 72 of file sparse-map.hh.
References vcsn::sparse_map< Key, Value >::dense_, vcsn::sparse_map< Key, Value >::emplace(), vcsn::sparse_map< Key, Value >::has(), and vcsn::sparse_map< Key, Value >::sparse_.
|
inline |
Definition at line 29 of file sparse-map.hh.
References vcsn::sparse_map< Key, Value >::sparse_.
|
private |
Definition at line 123 of file sparse-map.hh.
Referenced by vcsn::sparse_map< Key, Value >::clear(), vcsn::sparse_map< Key, Value >::end(), vcsn::sparse_map< Key, Value >::erase(), vcsn::sparse_map< Key, Value >::has(), and vcsn::sparse_map< Key, Value >::insert().
|
private |
Definition at line 121 of file sparse-map.hh.
Referenced by vcsn::sparse_map< Key, Value >::begin(), vcsn::sparse_map< Key, Value >::end(), vcsn::sparse_map< Key, Value >::erase(), vcsn::sparse_map< Key, Value >::has(), vcsn::sparse_map< Key, Value >::insert(), and vcsn::sparse_map< Key, Value >::operator[]().
|
private |
Definition at line 122 of file sparse-map.hh.
Referenced by vcsn::sparse_map< Key, Value >::erase(), vcsn::sparse_map< Key, Value >::has(), vcsn::sparse_map< Key, Value >::insert(), vcsn::sparse_map< Key, Value >::operator[](), and vcsn::sparse_map< Key, Value >::set_max_size().