![]() |
Vcsn
2.3a
Be Rational
|
Sparse Set implementation. More...
#include <sparse-set.hh>
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... | |
T | curr_ = 0 |
Current number of elements. More... | |
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.
|
inline |
The template parameter corresponds to indexes so it has to be unsigned.
Definition at line 19 of file sparse-set.hh.
|
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.
|
inline |
Definition at line 98 of file sparse-set.hh.
References vcsn::sparse_set< T >::dense_.
|
inline |
Definition at line 108 of file sparse-set.hh.
References vcsn::sparse_set< T >::dense_.
|
inline |
Flush all elements from the set.
Definition at line 93 of file sparse-set.hh.
References vcsn::sparse_set< T >::curr_.
|
inline |
Definition at line 47 of file sparse-set.hh.
References vcsn::sparse_set< T >::insert().
|
inline |
Definition at line 103 of file sparse-set.hh.
References vcsn::sparse_set< T >::curr_, and vcsn::sparse_set< T >::dense_.
|
inline |
Definition at line 113 of file sparse-set.hh.
References vcsn::sparse_set< T >::curr_, and vcsn::sparse_set< T >::dense_.
|
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_.
|
inline |
Definition at line 71 of file sparse-set.hh.
References vcsn::sparse_set< T >::curr_, vcsn::sparse_set< T >::dense_, and vcsn::sparse_set< T >::sparse_.
Referenced by vcsn::sparse_set< T >::erase(), vcsn::has(), and vcsn::sparse_set< T >::insert().
|
inline |
Insert new value.
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().
|
inline |
Set current vector size.
Definition at line 42 of file sparse-set.hh.
References vcsn::sparse_set< T >::sparse_.
|
private |
Current number of elements.
Definition at line 124 of file sparse-set.hh.
Referenced by vcsn::sparse_set< T >::clear(), vcsn::sparse_set< T >::end(), vcsn::sparse_set< T >::erase(), vcsn::sparse_set< T >::has(), and vcsn::sparse_set< T >::insert().
|
private |
Actual elements of the set, not sorted.
Definition at line 120 of file sparse-set.hh.
Referenced by vcsn::sparse_set< T >::begin(), vcsn::sparse_set< T >::end(), vcsn::sparse_set< T >::erase(), vcsn::sparse_set< T >::has(), and vcsn::sparse_set< T >::insert().
|
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().