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

T	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

◆ sparse_set() [1/2]

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.

References vcsn::sparse_set< T >::set_max_size(), vcsn::rat::size(), and vcsn::sparse_set< T >::sparse_.

Here is the call graph for this function:

◆ sparse_set() [2/2]

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.

References vcsn::sparse_set< T >::insert(), vcsn::sparse_set< T >::set_max_size(), and vcsn::sparse_set< T >::sparse_.

Here is the call graph for this function:

Member Function Documentation

◆ begin() [1/2]

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_.

◆ begin() [2/2]

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_.

◆ clear()

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_.

◆ emplace()

template<typename T>

bool vcsn::sparse_set< T >::emplace ( T 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:

◆ end() [1/2]

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_.

◆ end() [2/2]

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_.

◆ erase()

template<typename T>

void vcsn::sparse_set< T >::erase ( T 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:

◆ has()

template<typename T>

bool vcsn::sparse_set< T >::has ( T e ) const

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

◆ insert()

template<typename T>

bool vcsn::sparse_set< T >::insert ( T 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(), and vcsn::sparse_set< T >::sparse_set().

Here is the call graph for this function:

◆ set_max_size()

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_.

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

Member Data Documentation

◆ curr_

template<typename T>

T vcsn::sparse_set< T >::curr_ = 0

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

◆ dense_

template<typename T>

std::vector<T> vcsn::sparse_set< T >::dense_

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

◆ sparse_

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(), vcsn::sparse_set< T >::set_max_size(), and vcsn::sparse_set< T >::sparse_set().

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

vcsn/misc/sparse-set.hh

Public Member Functions

Private Attributes

Detailed Description

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

Constructor & Destructor Documentation

◆ sparse_set() [1/2]

◆ sparse_set() [2/2]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ clear()

◆ emplace()

◆ end() [1/2]

◆ end() [2/2]

◆ erase()

◆ has()

◆ insert()

◆ set_max_size()

Member Data Documentation

◆ curr_

◆ dense_

◆ sparse_

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