Vcsn  2.3
Be Rational
Public Member Functions | Private Attributes | List of all members
vcsn::sparse_map< Key, Value > Class Template Reference

Sparse Map implementation. More...

#include <sparse-map.hh>

Collaboration diagram for vcsn::sparse_map< Key, Value >:

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
 

Detailed Description

template<typename Key, typename Value>
class vcsn::sparse_map< Key, Value >

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.

Constructor & Destructor Documentation

template<typename Key, typename Value>
vcsn::sparse_map< Key, Value >::sparse_map ( size_t  max_size = 0)
inline

The Keys correspond to indexes so they have to be unsigned.

Definition at line 22 of file sparse-map.hh.

Member Function Documentation

template<typename Key, typename Value>
auto vcsn::sparse_map< Key, Value >::begin ( )
inline

Definition at line 99 of file sparse-map.hh.

References vcsn::sparse_map< Key, Value >::dense_.

template<typename Key, typename Value>
auto vcsn::sparse_map< Key, Value >::begin ( ) const
inline

Definition at line 109 of file sparse-map.hh.

References vcsn::sparse_map< Key, Value >::dense_.

template<typename Key, typename Value>
void vcsn::sparse_map< Key, Value >::clear ( )
inline

Flush all elements from the set.

Definition at line 94 of file sparse-map.hh.

References vcsn::sparse_map< Key, Value >::curr_.

template<typename Key, typename Value>
template<typename K , typename V >
bool vcsn::sparse_map< Key, Value >::emplace ( K &&  k,
V &&  v 
)
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[]().

Here is the call graph for this function:

template<typename Key, typename Value>
auto vcsn::sparse_map< Key, Value >::end ( )
inline

Definition at line 104 of file sparse-map.hh.

References vcsn::sparse_map< Key, Value >::curr_, and vcsn::sparse_map< Key, Value >::dense_.

template<typename Key, typename Value>
auto vcsn::sparse_map< Key, Value >::end ( ) const
inline

Definition at line 114 of file sparse-map.hh.

References vcsn::sparse_map< Key, Value >::curr_, and vcsn::sparse_map< Key, Value >::dense_.

template<typename Key, typename Value>
void vcsn::sparse_map< Key, Value >::erase ( Key  k)
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_.

Here is the call graph for this function:

template<typename Key, typename Value>
bool vcsn::sparse_map< Key, Value >::has ( Key  k) const
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[]().

template<typename Key, typename Value>
bool vcsn::sparse_map< Key, Value >::insert ( const std::pair< Key, Value > &  p)
inline

Insert new value.

Returns
true if the element was succesfully inserted, false if it was

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().

Here is the call graph for this function:

template<typename Key, typename Value>
Value& vcsn::sparse_map< Key, Value >::operator[] ( Key  k)
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_.

Here is the call graph for this function:

template<typename Key, typename Value>
void vcsn::sparse_map< Key, Value >::set_max_size ( size_t  max_size)
inline

Definition at line 29 of file sparse-map.hh.

References vcsn::sparse_map< Key, Value >::sparse_.

Member Data Documentation

template<typename Key, typename Value>
Key vcsn::sparse_map< Key, Value >::curr_ = 0
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().

template<typename Key, typename Value>
std::vector<std::pair<Key, Value> > vcsn::sparse_map< Key, Value >::dense_
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[]().

template<typename Key, typename Value>
std::vector<Key> vcsn::sparse_map< Key, Value >::sparse_
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().

The documentation for this class was generated from the following file: