Vcsn  2.3
Be Rational
vcsn::sparse_set< T > Class Template Reference

Sparse Set implementation. More...

#include <sparse-set.hh>

Collaboration diagram for vcsn::sparse_set< T >:

Public Member Functions

 sparse_set (size_t max_size=0)
 The template parameter corresponds to indexes so it has to be unsigned. More...
 
template<template< typename Elt > class Container, typename = decltype(std::declval<Container<T>>().size())>
 sparse_set (const Container< T > &cont)
 Construct with a container. More...
 
void set_max_size (size_t max_size)
 Set current vector size. More...
 
bool emplace (T e)
 
bool insert (T e)
 Insert new value. More...
 
bool has (T e) const
 
void erase (T e)
 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< T > dense_
 Actual elements of the set, not sorted. More...
 
std::vector< T > sparse_
 Indexes of elements in the dense_ vector. More...
 
curr_ = 0
 Current number of elements. More...
 

Detailed Description

template<typename T>
class vcsn::sparse_set< T >

Sparse Set implementation.

Based on Russ Cox trick allowing constant operations: http://research.swtch.com/sparse

Definition at line 12 of file sparse-set.hh.

Constructor & Destructor Documentation

template<typename T>
vcsn::sparse_set< T >::sparse_set ( size_t  max_size = 0)
inline

The template parameter corresponds to indexes so it has to be unsigned.

Definition at line 19 of file sparse-set.hh.

template<typename T>
template<template< typename Elt > class Container, typename = decltype(std::declval<Container<T>>().size())>
vcsn::sparse_set< T >::sparse_set ( const Container< T > &  cont)
inline

Construct with a container.

Use size for SFINAE as it is not featured in sparse_set. Hence, this is not a copy-constructor.

Definition at line 32 of file sparse-set.hh.

Member Function Documentation

template<typename T>
auto vcsn::sparse_set< T >::begin ( )
inline

Definition at line 98 of file sparse-set.hh.

References vcsn::sparse_set< T >::dense_.

template<typename T>
auto vcsn::sparse_set< T >::begin ( ) const
inline

Definition at line 108 of file sparse-set.hh.

References vcsn::sparse_set< T >::dense_.

template<typename T>
void vcsn::sparse_set< T >::clear ( )
inline

Flush all elements from the set.

Definition at line 93 of file sparse-set.hh.

References vcsn::sparse_set< T >::curr_.

template<typename T>
bool vcsn::sparse_set< T >::emplace ( e)
inline

Definition at line 47 of file sparse-set.hh.

References vcsn::sparse_set< T >::insert().

Here is the call graph for this function:

template<typename T>
auto vcsn::sparse_set< T >::end ( )
inline

Definition at line 103 of file sparse-set.hh.

References vcsn::sparse_set< T >::curr_, and vcsn::sparse_set< T >::dense_.

template<typename T>
auto vcsn::sparse_set< T >::end ( ) const
inline

Definition at line 113 of file sparse-set.hh.

References vcsn::sparse_set< T >::curr_, and vcsn::sparse_set< T >::dense_.

template<typename T>
void vcsn::sparse_set< T >::erase ( e)
inline

Erase an element.

Does nothing if the element is not present.

Definition at line 81 of file sparse-set.hh.

References vcsn::sparse_set< T >::curr_, vcsn::sparse_set< T >::dense_, vcsn::sparse_set< T >::has(), and vcsn::sparse_set< T >::sparse_.

Here is the call graph for this function:

template<typename T>
bool vcsn::sparse_set< T >::has ( e) const
inline
template<typename T>
bool vcsn::sparse_set< T >::insert ( e)
inline

Insert new value.

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

Definition at line 56 of file sparse-set.hh.

References vcsn::sparse_set< T >::curr_, vcsn::sparse_set< T >::dense_, vcsn::sparse_set< T >::has(), and vcsn::sparse_set< T >::sparse_.

Referenced by vcsn::sparse_set< T >::emplace().

Here is the call graph for this function:

template<typename T>
void vcsn::sparse_set< T >::set_max_size ( size_t  max_size)
inline

Set current vector size.

Definition at line 42 of file sparse-set.hh.

References vcsn::sparse_set< T >::sparse_.

Member Data Documentation

template<typename T>
T vcsn::sparse_set< T >::curr_ = 0
private
template<typename T>
std::vector<T> vcsn::sparse_set< T >::dense_
private
template<typename T>
std::vector<T> vcsn::sparse_set< T >::sparse_
private

Indexes of elements in the dense_ vector.

Definition at line 122 of file sparse-set.hh.

Referenced by vcsn::sparse_set< T >::erase(), vcsn::sparse_set< T >::has(), vcsn::sparse_set< T >::insert(), and vcsn::sparse_set< T >::set_max_size().


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