DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator > Struct Template Reference

#include <DGtal/kernel/UnorderedSetByBlock.h>

Inheritance diagram for DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >:

Data Structures
struct	const_iterator
	Read iterator on set elements. Model of ForwardIterator. More...
struct	iterator
	Read-write iterator on set elements. Model of ForwardIterator. More...

Public Types
typedef UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual >	Self
typedef TSplitter	Splitter
typedef Splitter::Word	Word
typedef Splitter::Coordinate	Coordinate
typedef std::unordered_map< Key, Word, Hash, KeyEqual, UnorderedMapAllocator >	Container
	The underlying container, an unordered_map. More...
typedef Key	key_type
	Key. More...
typedef Key	value_type
	Key. More...
typedef Container::size_type	size_type
	Unsigned integer type (usually std::size_t) More...
typedef Container::difference_type	difference_type
	Signed integer type (usually std::ptrdiff_t) More...
typedef Hash	hasher
	Hash. More...
typedef KeyEqual	key_equal
	KeyEqual. More...
typedef Container::allocator_type	allocator_type
	Allocator. More...
typedef Key &	reference
	Reference to value_type/Key. More...
typedef const Key &	const_reference
	Const reference to value_type/Key. More...
typedef Key *	pointer
	Pointer to value_type/Key. More...
typedef const Key *	const_pointer
	Const Pointer to value_type/Key. More...

Public Member Functions
Standard services (construction, initialization, assignment)
	UnorderedSetByBlock (size_type bucket_count=23, const Splitter &splitter=Splitter(), const Hash &hash=Hash(), const key_equal &equal=key_equal(), const UnorderedMapAllocator &alloc=UnorderedMapAllocator())
	~UnorderedSetByBlock ()=default
	Default destructor. More...
	UnorderedSetByBlock (const Self &other)
	UnorderedSetByBlock (Self &&other)
Self &	operator= (const Self &other)
Self &	operator= (Self &&other)
Iterator services
iterator	begin ()
iterator	end ()
const_iterator	begin () const
const_iterator	end () const
const_iterator	cbegin () const
const_iterator	cend () const
Capacity services
bool	empty () const noexcept
size_type	size () const noexcept
size_type	max_size () const noexcept
size_type	blocks () const noexcept
size_type	memory_usage () const noexcept
size_type	memory_usage_unordered_set () const noexcept
Modifier services
void	clear () noexcept
	Clears the container. More...
void	swap (Self &other) noexcept
std::pair< iterator, bool >	insert (const value_type &value)
	Attempts to insert an element into the set. More...
template<typename InputIterator >
void	insert (InputIterator first, InputIterator last)
	Inserts a range of element into the set. More...
template<typename... _Args>
std::pair< iterator, bool >	emplace (_Args &&... __args)
	Attempts to build and insert an element into the set. More...
iterator	erase (const_iterator pos) noexcept
iterator	erase (const_iterator first, const_iterator last) noexcept
size_type	erase (const key_type &key)
Lookup services
iterator	find (const Key &key)
const_iterator	find (const Key &key) const
size_type	count (const Key &key) const
std::pair< iterator, iterator >	equal_range (const Key &key)
std::pair< const_iterator, const_iterator >	equal_range (const Key &key) const
Hash policy services
void	reserve (size_type block_count)

Private Attributes
Splitter	my_splitter
	The splitter object. More...
Container	my_elements
	the unordered_set containing the elements More...
size_type	my_size
	the number of elements More...

Set services
bool	includes (const Self &other) const
bool	internal_includes_by_map_iterator (const Self &other) const
bool	internal_trace_includes_by_map_iterator (const Self &other) const
bool	internal_includes_by_iterator (const Self &other) const
bool	internal_trace_includes_by_iterator (const Self &other) const

Detailed Description

template<typename Key, typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>
struct DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >

This data structure represents a set of elements that must be integral arrays (i.e. digital points). It is similar to an unordered_set, but much more compact in general. The container used is a unordered_map from point to a 32-bit word. The idea is to group consecutive elements/points along x axis by blocks of 32 bits. If any point in a block is present, the corresponding element is present in the unordered_map and bits set to 1 in the word correspond to points present in the set. On average, memory occupancy is divided by four, the structure is four times faster for traversal and approximately same speed for queries/insertion/erase.

Almost all standard operations of unordered_set in c++11 are implemented.

Template Parameters

Key	the type of integral array.
TSplitter	the type for splitting a key into a block and a bit (see Splitter).
Hash	the type that provides a hasher for Key.
KeyEqual	the type that provides an equality comparator for Key.
UnorderedMapAllocator	the type that provides an allocator for the underlying unordered_map container.

Specialized versions of Splitter are written for usual digital points of Z2i or Z3i.

#include "DGtal/kernel/UnorderedSetByBlock.h"
...
typedef DGtal::PointVector< 3, int >  Point3i; // digital point in Z3;
std::unordered_set< Point3i >         aSet;    // usual data structure
DGtal::UnorderedSetByBlock< Point3i > aSet2;   // this data structure
// same code after for aSet or aSet2.

Definition at line 163 of file UnorderedSetByBlock.h.

Member Typedef Documentation

allocator_type

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

typedef Container::allocator_type DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::allocator_type

Allocator.

Definition at line 186 of file UnorderedSetByBlock.h.

const_pointer

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

typedef const Key* DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::const_pointer

Const Pointer to value_type/Key.

Definition at line 194 of file UnorderedSetByBlock.h.

const_reference

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

typedef const Key& DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::const_reference

Const reference to value_type/Key.

Definition at line 190 of file UnorderedSetByBlock.h.

Container

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

typedef std::unordered_map< Key, Word, Hash, KeyEqual, UnorderedMapAllocator > DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::Container

The underlying container, an unordered_map.

Definition at line 170 of file UnorderedSetByBlock.h.

Coordinate

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

typedef Splitter::Coordinate DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::Coordinate

Definition at line 167 of file UnorderedSetByBlock.h.

difference_type

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

typedef Container::difference_type DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::difference_type

Signed integer type (usually std::ptrdiff_t)

Definition at line 180 of file UnorderedSetByBlock.h.

hasher

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

typedef Hash DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::hasher

Hash.

Definition at line 182 of file UnorderedSetByBlock.h.

key_equal

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

typedef KeyEqual DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::key_equal

KeyEqual.

Definition at line 184 of file UnorderedSetByBlock.h.

key_type

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

typedef Key DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::key_type

Key.

Definition at line 174 of file UnorderedSetByBlock.h.

pointer

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

typedef Key* DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::pointer

Pointer to value_type/Key.

Definition at line 192 of file UnorderedSetByBlock.h.

reference

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

typedef Key& DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::reference

Reference to value_type/Key.

Definition at line 188 of file UnorderedSetByBlock.h.

Self

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

typedef UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual > DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::Self

Definition at line 164 of file UnorderedSetByBlock.h.

size_type

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

typedef Container::size_type DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::size_type

Unsigned integer type (usually std::size_t)

Definition at line 178 of file UnorderedSetByBlock.h.

Splitter

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

typedef TSplitter DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::Splitter

Definition at line 165 of file UnorderedSetByBlock.h.

value_type

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

typedef Key DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::value_type

Key.

Definition at line 176 of file UnorderedSetByBlock.h.

Word

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

typedef Splitter::Word DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::Word

Definition at line 166 of file UnorderedSetByBlock.h.

Constructor & Destructor Documentation

UnorderedSetByBlock() [1/3]

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::UnorderedSetByBlock ( size_type  bucket_count = 23, const Splitter &  splitter = Splitter(), const Hash &  hash = Hash(), const key_equal &  equal = key_equal(), const UnorderedMapAllocator &  alloc = UnorderedMapAllocator()  )

inline

Main constructor.

Parameters

bucket_count	the initial number of buckets for the underlying container.
splitter	the splitter object for keys.
hash	the hash object for keys.
equal	the key equality comparator object for keys.
alloc	the allocator for the underlying container.

Definition at line 474 of file UnorderedSetByBlock.h.

      : my_splitter( splitter ),
        my_elements( bucket_count, hash, equal, alloc ),
        my_size( 0 ) {}

~UnorderedSetByBlock()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::~UnorderedSetByBlock ( )

default

Default destructor.

UnorderedSetByBlock() [2/3]

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::UnorderedSetByBlock ( const Self &  other )

inline

Copy constructor

Parameters

other

the object to clone

Definition at line 488 of file UnorderedSetByBlock.h.

      : my_splitter( other.my_splitter ),
        my_elements( other.my_elements ),
        my_size( other.my_size )
    {}

UnorderedSetByBlock() [3/3]

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::UnorderedSetByBlock ( Self &&  other )

inline

Move constructor

Parameters

other

the object to clone

Definition at line 496 of file UnorderedSetByBlock.h.

      : my_splitter( std::move( other.my_splitter ) ),
        my_elements( std::move( other.my_elements ) ),
        my_size( std::move( other.my_size ) )
    {}

Member Function Documentation

begin() [1/2]

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

iterator DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::begin ( )

inline

Returns

an iterator of the first stored element

Definition at line 534 of file UnorderedSetByBlock.h.

    {
      return iterator( *this, my_elements.begin() );
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements.

begin() [2/2]

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

const_iterator DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::begin ( ) const

inline

Returns

an iterator of the first stored element

Definition at line 545 of file UnorderedSetByBlock.h.

    {
      return const_iterator( *this, my_elements.cbegin() );
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements.

blocks()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

size_type DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::blocks ( ) const

inlinenoexcept

Note

Specific to this data structure.

Returns

the number of blocks stored in the container.

Definition at line 582 of file UnorderedSetByBlock.h.

{ return my_elements.size(); }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements.

Referenced by DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::memory_usage().

cbegin()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

const_iterator DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::cbegin ( ) const

inline

Returns

an iterator of the first stored element

Definition at line 556 of file UnorderedSetByBlock.h.

    {
      return const_iterator( *this, my_elements.cbegin() );
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements.

Referenced by DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::internal_includes_by_iterator(), and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::internal_trace_includes_by_iterator().

cend()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

const_iterator DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::cend ( ) const

inline

Returns

an iterator past the last stored element

Definition at line 561 of file UnorderedSetByBlock.h.

    {
      return const_iterator( *this, my_elements.cend() );
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements.

Referenced by DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::erase(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::find(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::internal_includes_by_iterator(), and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::internal_trace_includes_by_iterator().

clear()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

void DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::clear ( )

inlinenoexcept

Clears the container.

Definition at line 620 of file UnorderedSetByBlock.h.

    {
      my_elements.clear();
      my_size = 0;
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements, and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_size.

count()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

size_type DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::count ( const Key &  key ) const

inline

Parameters

key	the value to look-up.

Returns

the number of elements with key that compares equal to the specified argument key, which is either 1 or 0 since this container does not allow duplicates.

Definition at line 896 of file UnorderedSetByBlock.h.

    {
      const auto se = my_splitter.split( key );
      const auto it = my_elements.find( se.first );
      if ( it == my_elements.cend() ) return 0;
      const bool exist = it->second & ( static_cast<Word>(1) << se.second );
      return exist ? 1 : 0;
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements, and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_splitter.

emplace()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

template<typename... _Args>

std::pair<iterator, bool> DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::emplace ( _Args &&...  __args )

inline

Attempts to build and insert an element into the set.

Parameters

__args

Arguments used to generate an element.

Returns

A pair, of which the first element is an iterator that points to the possibly inserted element, and the second is a bool that is true if the element was actually inserted.

This function attempts to build and insert an element into the set. A set relies on unique keys and thus an element is only inserted if it is not already present in the set.

Insertion takes amortized constant time.

Definition at line 714 of file UnorderedSetByBlock.h.

    {
      const auto se = my_splitter.split( Key( std::forward<_Args>(__args)... ) );
      auto it = my_elements.find( se.first );
      if ( it == my_elements.end() )
        {
          auto   p =
            my_elements.insert( std::make_pair( se.first,
                                                static_cast<Word>(1) << se.second ) );
          my_size += 1;
          return std::make_pair( iterator( *this, p.first, se.second ), true );
        }
      else
        {
          bool exist = it->second & ( static_cast<Word>(1) << se.second );
          if ( ! exist )
            {
              it->second |= static_cast<Word>(1) << se.second;
              my_size    += 1;
            }
          return std::make_pair( iterator( *this, it, se.second ), ! exist );
        }
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements, DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_size, and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_splitter.

empty()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

bool DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::empty ( ) const

inlinenoexcept

Returns

'true' iff the container is empty

Definition at line 574 of file UnorderedSetByBlock.h.

{ return my_elements.empty(); }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements.

end() [1/2]

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

iterator DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::end ( )

inline

Returns

an iterator past the last stored element

Definition at line 539 of file UnorderedSetByBlock.h.

    {
      return iterator( *this, my_elements.end() );
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements.

Referenced by DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::equal_range(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::erase(), and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::find().

end() [2/2]

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

const_iterator DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::end ( ) const

inline

Returns

an iterator past the last stored element

Definition at line 550 of file UnorderedSetByBlock.h.

    {
      return const_iterator( *this, my_elements.cend() );
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements.

equal_range() [1/2]

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

std::pair<iterator,iterator> DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::equal_range ( const Key &  key )

inline

Returns the bounds of a range that includes all the elements that compare equal to k. In set containers, where keys are unique, the range will include one element at most.

Parameters

key	the value to look-up.

Returns

a range containing the sought element or an empty range if key is not in this set.

Definition at line 914 of file UnorderedSetByBlock.h.

    {
      iterator first = find( key );
      if ( first != end() )
        {
          iterator last = first;
          return std::make_pair( first, ++last );
        }
      else return std::make_pair( first, first );
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::end(), and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::find().

equal_range() [2/2]

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

std::pair<const_iterator,const_iterator> DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::equal_range ( const Key &  key ) const

inline

Returns the bounds of a range that includes all the elements that compare equal to k. In set containers, where keys are unique, the range will include one element at most.

Parameters

key	the value to look-up.

Returns

a range containing the sought element or an empty range if key is not in this set.

Definition at line 934 of file UnorderedSetByBlock.h.

    {
      const_iterator first = find( key );
      if ( first != end() )
        {
          const_iterator last = first;
          return std::make_pair( first, ++last );
        }
      else return std::make_pair( first, first );
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::end(), and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::find().

erase() [1/3]

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

size_type DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::erase ( const key_type &  key )

inline

Removes specified element from the container, if it exists.

Parameters

key	the value to erase from the set

Returns

the number of value removed from the set (either 0 or 1 ).

Note

References and iterators to the erased elements are invalidated. Other iterators and references are not invalidated.

Definition at line 844 of file UnorderedSetByBlock.h.

    {
      auto it = find( key );
      if ( it != end() )
        {
          erase( it );
          return 1;
        }
      else return 0;
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::end(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::erase(), and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::find().

erase() [2/3]

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

iterator DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::erase ( const_iterator  first, const_iterator  last  )

inlinenoexcept

Removes the elements in the range [first; last), which must be a valid range in *this.

Parameters

first	an iterator such that [first; last) is a valid range in this data structure
last	an iterator such that [first; last) is a valid range in this data structure

Returns

the iterator following the last removed element.

Note

References and iterators to the erased elements are invalidated. Other iterators and references are not invalidated.

Definition at line 779 of file UnorderedSetByBlock.h.

    {
      ASSERT( this == first.collection );
      ASSERT( this == last.collection );
      if ( first == cend() ) return end();
      auto itB = first.it;
      auto itE = last.it;
      Word mask = static_cast<Word>(0);
      // Take care of range over one block only
      if ( itB == itE )
        {
          while ( first != last )
            {
              mask    |= static_cast<Word>(1) << first.bit;
              my_size -= 1;
              ++first;
            }
          my_elements[ itB->first ] &= ~mask;
          return iterator( *this,
                           my_elements.find( itE->first ),
                           last.bit ); // must be valid
        }
      // Take care of first element.
      while ( first.it == itB )
        {
          mask    |= static_cast<Word>(1) << first.bit;
          my_size -= 1;
          ++first;
        }
      // Erase first block if empty
      if ( ( my_elements[ itB->first ] &= ~mask )
           == static_cast<Word>(0) )
        my_elements.erase( itB );
      // Count erased elements in main range.
      for ( itB = first.it; itB != itE; ++itB )
        my_size -= Bits::nbSetBits( itB->second );
      // Erase elements in main range
      my_elements.erase( first.it, itE );
      // Take care of last element.
      if ( itE == my_elements.cend() ) return end();
      itB   = itE;
      first = const_iterator( *this, itB );
      mask  = static_cast<Word>(0);
      while ( first != last )
        {
          mask    |= static_cast<Word>(1) << first.bit;
          my_size -= 1;
          ++first;
        }
      // Erase last block if empty
      if ( ( my_elements[ itB->first ] &= ~mask )
           == static_cast<Word>(0) )
        my_elements.erase( itB );
      return iterator( *this,
                       my_elements.find( itE->first ),
                       last.bit ); // must be valid or end.
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::cend(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::end(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements, DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_size, and DGtal::Bits::nbSetBits().

erase() [3/3]

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

iterator DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::erase ( const_iterator  pos )

inlinenoexcept

Removes specified element from the container.

Parameters

pos	a valid iterator in this data structure

Returns

the iterator following the last removed element.

Note

References and iterators to the erased elements are invalidated. Other iterators and references are not invalidated.

Precondition

The iterator pos must be valid and dereferenceable. Thus the end() iterator (which is valid, but is not dereferenceable) cannot be used as a value for pos.

Definition at line 749 of file UnorderedSetByBlock.h.

    {
      ASSERT( this == pos.collection );
      ASSERT( pos  != cend() );
      ASSERT( ( pos.it->second & ( static_cast<Word>(1) << pos.bit ) )
              != static_cast<Word>(0) );
      my_size -= 1;
      Word & w = const_cast< Word& >( pos.it->second );
      if ( ( w &= ~( static_cast<Word>(1) << pos.bit ) )
           == static_cast<Word>(0) )
        return iterator( *this, my_elements.erase( pos.it ) );
      else
        return iterator( *this, my_elements.erase( pos.it, pos.it ), pos.bit );
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::cend(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements, and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_size.

Referenced by DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::erase().

find() [1/2]

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

iterator DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::find ( const Key &  key )

inline

Finds an element with key equivalent to key.

Parameters

key	the value to look-up.

Returns

an iterator pointing to key or end() if the key is not the set.

Definition at line 867 of file UnorderedSetByBlock.h.

    {
      const auto se = my_splitter.split( key );
      const auto it = my_elements.find( se.first );
      if ( it == my_elements.end() ) return end();
      const bool exist = it->second & ( static_cast<Word>(1) << se.second );
      if ( exist ) return iterator( *this, it, se.second );
      else         return end();
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::end(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements, and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_splitter.

Referenced by DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::equal_range(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::erase(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::internal_includes_by_iterator(), and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::internal_trace_includes_by_iterator().

find() [2/2]

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

const_iterator DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::find ( const Key &  key ) const

inline

Finds an element with key equivalent to key.

Parameters

key	the value to look-up.

Returns

a const iterator pointing to key or end() if the key is not the set.

Definition at line 882 of file UnorderedSetByBlock.h.

    {
      const auto se = my_splitter.split( key );
      const auto it = my_elements.find( se.first );
      if ( it == my_elements.cend() ) return cend();
      const bool exist = it->second & ( static_cast<Word>(1) << se.second );
      if ( exist ) return const_iterator( *this, it, se.second );
      else         return cend();
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::cend(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements, and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_splitter.

includes()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

bool DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::includes ( const Self &  other ) const

inline

Parameters

other

any unordered set with same sort of elements

Returns

'true' if and only if this set includes other, and 'false' otherwise.

Note

Much faster that using count or find on each element, since it proceeds block by block.

Definition at line 958 of file UnorderedSetByBlock.h.

    {
      return internal_includes_by_map_iterator( other );
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::internal_includes_by_map_iterator().

insert() [1/2]

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

std::pair<iterator,bool> DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::insert ( const value_type &  value )

inline

Attempts to insert an element into the set.

Parameters

value

Element to be inserted.

Returns

A pair, of which the first element is an iterator that points to the possibly inserted element, and the second is a bool that is true if the element was actually inserted.

This function attempts to insert an element into the set. A set relies on unique keys and thus an element is only inserted if it is not already present in the set.

Insertion requires amortized constant time.

Definition at line 656 of file UnorderedSetByBlock.h.

    {
      const auto se = my_splitter.split( value );
      auto it = my_elements.find( se.first );
      if ( it == my_elements.end() )
        {
          auto   p = my_elements.insert
            ( std::make_pair( se.first,
                              static_cast<Word>(1) << se.second ) );
          my_size += 1;
          return std::make_pair( iterator( *this, p.first, se.second ), true );
        }
      else
        {
          bool exist = it->second & ( static_cast<Word>(1) << se.second );
          if ( ! exist )
            {
              it->second |= static_cast<Word>(1) << se.second;
              my_size    += 1;
            }
          return std::make_pair( iterator( *this, it, se.second ), ! exist );
        }
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements, DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_size, and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_splitter.

Referenced by DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::insert().

insert() [2/2]

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

template<typename InputIterator >

void DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::insert ( InputIterator  first, InputIterator  last  )

inline

Inserts a range of element into the set.

Template Parameters

InputIterator

any model of input iterator

Parameters

[in]	first	an iterator pointing on the first element of the range
[in]	last	an iterator pointing after the last element of the range

This function inserts a range of elements into the set. A set relies on unique keys and thus an element is only inserted if it is not already present in the set.

Each insertion requires amortized constant time.

Definition at line 694 of file UnorderedSetByBlock.h.

    {
      for ( ; first != last; ++first ) insert( *first );
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::insert().

internal_includes_by_iterator()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

bool DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::internal_includes_by_iterator ( const Self &  other ) const

inlineprotected

Performs includes operation using iterators and big steps, slightly slower than internal_includes_by_map_iterator.

Parameters

other

any unordered set with same sort of elements

Returns

'true' if and only if this set includes other, and 'false' otherwise.

Definition at line 1019 of file UnorderedSetByBlock.h.

    {
      auto it_other  = other.cbegin();
      auto itEnd_other = other.cend();
      while ( it_other != itEnd_other )
        {
          const auto it_this = find( *it_other );
          if ( it_this == cend() ) return false;
          auto   itMap_other = it_other.it;
          const Word w_this  = it_this.it->second;
          const Word w_other = itMap_other->second;
          if ( ( w_this & w_other ) != w_other ) return false;
          it_other = const_iterator( other, ++itMap_other );
        }
      return true;
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::cbegin(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::cend(), and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::find().

internal_includes_by_map_iterator()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

bool DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::internal_includes_by_map_iterator ( const Self &  other ) const

inlineprotected

Performs includes operation using underlying container iterator.

Parameters

other

any unordered set with same sort of elements

Returns

'true' if and only if this set includes other, and 'false' otherwise.

Definition at line 968 of file UnorderedSetByBlock.h.

    {
      auto       itMap_other    = other.my_elements.cbegin();
      const auto itEndMap_other = other.my_elements.cend();
      const auto itEndMap_this  = my_elements.cend();
      for ( ; itMap_other != itEndMap_other; ++itMap_other )
        {
          const auto itMap_this = my_elements.find( itMap_other->first );
          if ( itMap_this == itEndMap_this ) return false;
          const Word w_this  = itMap_this->second;
          const Word w_other = itMap_other->second;
          if ( ( w_this & w_other ) != w_other ) return false;
        }
      return true;
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements.

Referenced by DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::includes().

internal_trace_includes_by_iterator()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

bool DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::internal_trace_includes_by_iterator ( const Self &  other ) const

inlineprotected

Performs includes operation using iterators and big steps, slightly slower than internal_includes_by_map_iterator. Verbose version for debug.

Parameters

other

any unordered set with same sort of elements

Returns

'true' if and only if this set includes other, and 'false' otherwise.

Definition at line 1043 of file UnorderedSetByBlock.h.

    {
      trace.info() << "[trace_includes_v2] #this=" << size()
                   << " #other=" << other.size() << std::endl;
      auto it_other  = other.cbegin();
      auto itEnd_other = other.cend();
      while ( it_other != itEnd_other )
        {
          trace.info() << "other: cell=" << it_other.it->first
                << " value=" << std::hex << it_other.it->second << std::endl;
          const auto it_this = find( *it_other );
          if ( it_this != cend() )
            trace.info() << "this : cell=" << it_this.it->first
                  << " value=" << std::hex << it_this.it->second << std::endl;
          else
            trace.info() << "this : end cell" << std::endl;
          if ( it_this == cend() ) return false;
          auto   itMap_other = it_other.it;
          const Word w_this  = it_this.it->second;
          const Word w_other = itMap_other->second;
          if ( ( w_this & w_other ) != w_other ) return false;
          it_other = const_iterator( other, ++itMap_other );
        }
      return true;
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::cbegin(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::cend(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::find(), DGtal::Trace::info(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::size(), and DGtal::trace.

internal_trace_includes_by_map_iterator()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

bool DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::internal_trace_includes_by_map_iterator ( const Self &  other ) const

inlineprotected

Performs includes operation using underlying container iterator. Verbose version for debug.

Parameters

other

any unordered set with same sort of elements

Returns

'true' if and only if this set includes other, and 'false' otherwise.

Definition at line 989 of file UnorderedSetByBlock.h.

    {
      trace.info() << "[trace_includes_v1] #this=" << size()
                   << " #other=" << other.size() << std::endl;
      auto       itMap_other    = other.my_elements.cbegin();
      const auto itEndMap_other = other.my_elements.cend();
      const auto itEndMap_this  = my_elements.cend();
      for ( ; itMap_other != itEndMap_other; ++itMap_other )
        {
          trace.info() << "other: cell=" << itMap_other->first
                << " value=" << std::hex << itMap_other->second << std::endl;
          const auto itMap_this = my_elements.find( itMap_other->first );
          if ( itMap_this != itEndMap_this )
            trace.info() << "this : cell=" << itMap_this->first
                  << " value=" << std::hex << itMap_this->second << std::endl;
          else
            trace.info() << "this : end cell" << std::endl;
          if ( itMap_this == itEndMap_this ) return false;
          const Word w_this  = itMap_this->second;
          const Word w_other = itMap_other->second;
          if ( ( w_this & w_other ) != w_other ) return false;
        }
      return true;
    }

References DGtal::Trace::info(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements, DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::size(), and DGtal::trace.

max_size()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

size_type DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::max_size ( ) const

inlinenoexcept

Returns

the maximum number of elements that can be stored in the container.

Definition at line 578 of file UnorderedSetByBlock.h.

{ return my_elements.max_size(); }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements.

memory_usage()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

size_type DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::memory_usage ( ) const

inlinenoexcept

Note

Specific to this data structure.

Returns

an evaluation of the memory usage of this data structure.

Definition at line 586 of file UnorderedSetByBlock.h.

    {
      size_type mem = (my_elements.bucket_count()+1) * sizeof( void* )
        + 2 * sizeof( size_type );
      mem += blocks() * ( sizeof( void* )       /* next */
                          + sizeof( Key )       /* key */
                          + sizeof( Word )      /* value */
                          + sizeof( size_type ) /* hash  */
                          + sizeof( void* )     /* dyn. alloc. */ );
      return mem;
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::blocks(), and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements.

memory_usage_unordered_set()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

size_type DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::memory_usage_unordered_set ( ) const

inlinenoexcept

Note

Specific to this data structure.

Returns

an evaluation of the memory usage of the same data stored in an unordered set.

Definition at line 601 of file UnorderedSetByBlock.h.

    {
      size_type mem = (my_elements.bucket_count()+1) * sizeof( void* )
        + 2 * sizeof( size_type );
      mem += size() * ( sizeof( void* )       /* next */
                        + sizeof( Key )       /* key */
                        + sizeof( size_type ) /* hash  */
                        + sizeof( void* )     /* dyn. alloc. */ );
      return mem;
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements, and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::size().

operator=() [1/2]

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

Self& DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::operator= ( const Self &  other )

inline

Assignment

Parameters

other

the object to clone

Returns

a reference to this

Definition at line 505 of file UnorderedSetByBlock.h.

    {
      if ( this != &other )
        {
          my_splitter = other.my_splitter;
          my_elements = other.my_elements;
          my_size     = other.my_size;
        }
      return *this;
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements, DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_size, and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_splitter.

operator=() [2/2]

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

Self& DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::operator= ( Self &&  other )

inline

Default move assignment

Parameters

other

the object to clone

Returns

a reference to this

Definition at line 518 of file UnorderedSetByBlock.h.

    {
      my_splitter = std::move( other.my_splitter );
      my_elements = std::move( other.my_elements );
      my_size     = std::move( other.my_size );
      return *this;
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements, DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_size, and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_splitter.

reserve()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

void DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::reserve ( size_type  block_count )

inline

Sets the number of buckets to the number needed to accomodate at least count elements without exceeding maximum load factor and rehashes the container, i.e. puts the elements into appropriate buckets considering that total number of buckets has changed. Effectively calls rehash(std::ceil(count / max_load_factor())).

Parameters

block_count

new capacity of the container (should be thought in terms of number of expected blocks).

Definition at line 1087 of file UnorderedSetByBlock.h.

    {
      my_elements.reserve( block_count );
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements.

size()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

size_type DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::size ( ) const

inlinenoexcept

Returns

the number of elements stored in the container.

Definition at line 576 of file UnorderedSetByBlock.h.

{ return my_size; }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_size.

Referenced by DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::internal_trace_includes_by_iterator(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::internal_trace_includes_by_map_iterator(), and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::memory_usage_unordered_set().

swap()

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

void DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::swap ( Self &  other )

inlinenoexcept

Exchanges the contents of the container with those of other. Does not invoke any move, copy, or swap operations on individual elements.

Parameters

other

the other set to exchange with.

Note

All iterators and references remain valid. The past-the-end iterator is invalidated. The Hash and KeyEqual objects must be Swappable, and they are exchanged using unqualified calls to non-member swap.

Definition at line 636 of file UnorderedSetByBlock.h.

    {
      std::swap( my_splitter, other.my_splitter );
      std::swap( my_elements, other.my_elements );
      std::swap( my_size, other.my_size );
    }

References DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements, DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_size, and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_splitter.

Field Documentation

my_elements

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

Container DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_elements

private

the unordered_set containing the elements

Definition at line 1099 of file UnorderedSetByBlock.h.

Referenced by DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::begin(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::blocks(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::cbegin(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::cend(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::clear(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::const_iterator::const_iterator(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::count(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::emplace(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::empty(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::end(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::erase(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::find(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::const_iterator::increment(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::iterator::increment(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::insert(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::internal_includes_by_map_iterator(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::internal_trace_includes_by_map_iterator(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::iterator::iterator(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::max_size(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::memory_usage(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::memory_usage_unordered_set(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::operator=(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::reserve(), and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::swap().

my_size

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

size_type DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_size

private

the number of elements

Definition at line 1101 of file UnorderedSetByBlock.h.

Referenced by DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::clear(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::emplace(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::erase(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::insert(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::operator=(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::size(), and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::swap().

my_splitter

template<typename Key , typename TSplitter = Splitter< Key >, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class UnorderedMapAllocator = std::allocator< std::pair<const Key, typename TSplitter::Word > >>

Splitter DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::my_splitter

private

The splitter object.

Definition at line 1097 of file UnorderedSetByBlock.h.

Referenced by DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::const_iterator::const_iterator(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::count(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::const_iterator::dereference(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::iterator::dereference(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::emplace(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::find(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::insert(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::iterator::iterator(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::operator=(), and DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::swap().

---

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

• UnorderedSetByBlock.h