DGtal  1.1.0
Data Structures | Public Types | Private Attributes
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 >:
[legend]
Collaboration diagram for DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >:
[legend]

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)
 
Selfoperator= (const Self &other)
 
Selfoperator= (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... _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, iteratorequal_range (const Key &key)
 
std::pair< const_iterator, const_iteratorequal_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
Keythe type of integral array.
TSplitterthe type for splitting a key into a block and a bit (see Splitter).
Hashthe type that provides a hasher for Key.
KeyEqualthe type that provides an equality comparator for Key.
UnorderedMapAllocatorthe 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_countthe initial number of buckets for the underlying container.
splitterthe splitter object for keys.
hashthe hash object for keys.
equalthe key equality comparator object for keys.
allocthe allocator for the underlying container.

Definition at line 474 of file UnorderedSetByBlock.h.

479  : my_splitter( splitter ),
480  my_elements( bucket_count, hash, equal, alloc ),
481  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
otherthe object to clone

Definition at line 488 of file UnorderedSetByBlock.h.

489  : my_splitter( other.my_splitter ),
490  my_elements( other.my_elements ),
491  my_size( other.my_size )
492  {}

◆ 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
otherthe object to clone

Definition at line 496 of file UnorderedSetByBlock.h.

497  : my_splitter( std::move( other.my_splitter ) ),
498  my_elements( std::move( other.my_elements ) ),
499  my_size( std::move( other.my_size ) )
500  {}

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.

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

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

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

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

582 { return my_elements.size(); }

Referenced by DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::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

◆ 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

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

621  {
622  my_elements.clear();
623  my_size = 0;
624  }

◆ 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
keythe 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 877 of file UnorderedSetByBlock.h.

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

◆ 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
__argsArguments 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 695 of file UnorderedSetByBlock.h.

696  {
697  const auto se = my_splitter.split( Key( std::forward<_Args>(__args)... ) );
698  auto it = my_elements.find( se.first );
699  if ( it == my_elements.end() )
700  {
701  auto p =
702  my_elements.insert( std::make_pair( se.first,
703  static_cast<Word>(1) << se.second ) );
704  my_size += 1;
705  return std::make_pair( iterator( *this, p.first, se.second ), true );
706  }
707  else
708  {
709  bool exist = it->second & ( static_cast<Word>(1) << se.second );
710  if ( ! exist )
711  {
712  it->second |= static_cast<Word>(1) << se.second;
713  my_size += 1;
714  }
715  return std::make_pair( iterator( *this, it, se.second ), ! exist );
716  }
717  }

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

574 { return my_elements.empty(); }

◆ 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

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

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

◆ 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
keythe 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 895 of file UnorderedSetByBlock.h.

896  {
897  iterator first = find( key );
898  if ( first != end() )
899  {
900  iterator last = first;
901  return std::make_pair( first, ++last );
902  }
903  else return std::make_pair( first, first );
904  }

◆ 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
keythe 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 915 of file UnorderedSetByBlock.h.

916  {
917  const_iterator first = find( key );
918  if ( first != end() )
919  {
920  const_iterator last = first;
921  return std::make_pair( first, ++last );
922  }
923  else return std::make_pair( first, first );
924  }

◆ 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
keythe 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 825 of file UnorderedSetByBlock.h.

826  {
827  auto it = find( key );
828  if ( it != end() )
829  {
830  erase( it );
831  return 1;
832  }
833  else return 0;
834  }

◆ 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
firstan iterator such that [first; last) is a valid range in this data structure
lastan 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 760 of file UnorderedSetByBlock.h.

761  {
762  ASSERT( this == first.collection );
763  ASSERT( this == last.collection );
764  if ( first == cend() ) return end();
765  auto itB = first.it;
766  auto itE = last.it;
767  Word mask = static_cast<Word>(0);
768  // Take care of range over one block only
769  if ( itB == itE )
770  {
771  while ( first != last )
772  {
773  mask |= static_cast<Word>(1) << first.bit;
774  my_size -= 1;
775  ++first;
776  }
777  my_elements[ itB->first ] &= ~mask;
778  return iterator( *this,
779  my_elements.find( itE->first ),
780  last.bit ); // must be valid
781  }
782  // Take care of first element.
783  while ( first.it == itB )
784  {
785  mask |= static_cast<Word>(1) << first.bit;
786  my_size -= 1;
787  ++first;
788  }
789  // Erase first block if empty
790  if ( ( my_elements[ itB->first ] &= ~mask )
791  == static_cast<Word>(0) )
792  my_elements.erase( itB );
793  // Count erased elements in main range.
794  for ( itB = first.it; itB != itE; ++itB )
795  my_size -= Bits::nbSetBits( itB->second );
796  // Erase elements in main range
797  my_elements.erase( first.it, itE );
798  // Take care of last element.
799  if ( itE == my_elements.cend() ) return end();
800  itB = itE;
801  first = const_iterator( *this, itB );
802  mask = static_cast<Word>(0);
803  while ( first != last )
804  {
805  mask |= static_cast<Word>(1) << first.bit;
806  my_size -= 1;
807  ++first;
808  }
809  // Erase last block if empty
810  if ( ( my_elements[ itB->first ] &= ~mask )
811  == static_cast<Word>(0) )
812  my_elements.erase( itB );
813  return iterator( *this,
814  my_elements.find( itE->first ),
815  last.bit ); // must be valid or end.
816  }

◆ 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
posa 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 730 of file UnorderedSetByBlock.h.

731  {
732  ASSERT( this == pos.collection );
733  ASSERT( pos != cend() );
734  ASSERT( ( pos.it->second & ( static_cast<Word>(1) << pos.bit ) )
735  != static_cast<Word>(0) );
736  my_size -= 1;
737  Word & w = const_cast< Word& >( pos.it->second );
738  if ( ( w &= ~( static_cast<Word>(1) << pos.bit ) )
739  == static_cast<Word>(0) )
740  return iterator( *this, my_elements.erase( pos.it ) );
741  else
742  return iterator( *this, my_elements.erase( pos.it, pos.it ), pos.bit );
743  }

Referenced by DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::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
keythe value to look-up.
Returns
an iterator pointing to key or end() if the key is not the set.

Definition at line 848 of file UnorderedSetByBlock.h.

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

Referenced by DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::equal_range(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::erase(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::internal_includes_by_iterator(), and DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::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
keythe value to look-up.
Returns
a const iterator pointing to key or end() if the key is not the set.

Definition at line 863 of file UnorderedSetByBlock.h.

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

◆ 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
otherany 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 939 of file UnorderedSetByBlock.h.

940  {
941  return internal_includes_by_map_iterator( other );
942  }

◆ insert()

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

657  {
658  const auto se = my_splitter.split( value );
659  auto it = my_elements.find( se.first );
660  if ( it == my_elements.end() )
661  {
662  auto p = my_elements.insert
663  ( std::make_pair( se.first,
664  static_cast<Word>(1) << se.second ) );
665  my_size += 1;
666  return std::make_pair( iterator( *this, p.first, se.second ), true );
667  }
668  else
669  {
670  bool exist = it->second & ( static_cast<Word>(1) << se.second );
671  if ( ! exist )
672  {
673  it->second |= static_cast<Word>(1) << se.second;
674  my_size += 1;
675  }
676  return std::make_pair( iterator( *this, it, se.second ), ! exist );
677  }
678  }

◆ 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
otherany unordered set with same sort of elements
Returns
'true' if and only if this set includes other, and 'false' otherwise.

Definition at line 1000 of file UnorderedSetByBlock.h.

1001  {
1002  auto it_other = other.cbegin();
1003  auto itEnd_other = other.cend();
1004  while ( it_other != itEnd_other )
1005  {
1006  const auto it_this = find( *it_other );
1007  if ( it_this == cend() ) return false;
1008  auto itMap_other = it_other.it;
1009  const Word w_this = it_this.it->second;
1010  const Word w_other = itMap_other->second;
1011  if ( ( w_this & w_other ) != w_other ) return false;
1012  it_other = const_iterator( other, ++itMap_other );
1013  }
1014  return true;
1015  }

◆ 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
otherany unordered set with same sort of elements
Returns
'true' if and only if this set includes other, and 'false' otherwise.

Definition at line 949 of file UnorderedSetByBlock.h.

950  {
951  auto itMap_other = other.my_elements.cbegin();
952  const auto itEndMap_other = other.my_elements.cend();
953  const auto itEndMap_this = my_elements.cend();
954  for ( ; itMap_other != itEndMap_other; ++itMap_other )
955  {
956  const auto itMap_this = my_elements.find( itMap_other->first );
957  if ( itMap_this == itEndMap_this ) return false;
958  const Word w_this = itMap_this->second;
959  const Word w_other = itMap_other->second;
960  if ( ( w_this & w_other ) != w_other ) return false;
961  }
962  return true;
963  }

Referenced by DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::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
otherany unordered set with same sort of elements
Returns
'true' if and only if this set includes other, and 'false' otherwise.

Definition at line 1024 of file UnorderedSetByBlock.h.

1025  {
1026  trace.info() << "[trace_includes_v2] #this=" << size()
1027  << " #other=" << other.size() << std::endl;
1028  auto it_other = other.cbegin();
1029  auto itEnd_other = other.cend();
1030  while ( it_other != itEnd_other )
1031  {
1032  trace.info() << "other: cell=" << it_other.it->first
1033  << " value=" << std::hex << it_other.it->second << std::endl;
1034  const auto it_this = find( *it_other );
1035  if ( it_this != cend() )
1036  trace.info() << "this : cell=" << it_this.it->first
1037  << " value=" << std::hex << it_this.it->second << std::endl;
1038  else
1039  trace.info() << "this : end cell" << std::endl;
1040  if ( it_this == cend() ) return false;
1041  auto itMap_other = it_other.it;
1042  const Word w_this = it_this.it->second;
1043  const Word w_other = itMap_other->second;
1044  if ( ( w_this & w_other ) != w_other ) return false;
1045  it_other = const_iterator( other, ++itMap_other );
1046  }
1047  return true;
1048  }

◆ 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
otherany unordered set with same sort of elements
Returns
'true' if and only if this set includes other, and 'false' otherwise.

Definition at line 970 of file UnorderedSetByBlock.h.

971  {
972  trace.info() << "[trace_includes_v1] #this=" << size()
973  << " #other=" << other.size() << std::endl;
974  auto itMap_other = other.my_elements.cbegin();
975  const auto itEndMap_other = other.my_elements.cend();
976  const auto itEndMap_this = my_elements.cend();
977  for ( ; itMap_other != itEndMap_other; ++itMap_other )
978  {
979  trace.info() << "other: cell=" << itMap_other->first
980  << " value=" << std::hex << itMap_other->second << std::endl;
981  const auto itMap_this = my_elements.find( itMap_other->first );
982  if ( itMap_this != itEndMap_this )
983  trace.info() << "this : cell=" << itMap_this->first
984  << " value=" << std::hex << itMap_this->second << std::endl;
985  else
986  trace.info() << "this : end cell" << std::endl;
987  if ( itMap_this == itEndMap_this ) return false;
988  const Word w_this = itMap_this->second;
989  const Word w_other = itMap_other->second;
990  if ( ( w_this & w_other ) != w_other ) return false;
991  }
992  return true;
993  }

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

578 { return my_elements.max_size(); }

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

587  {
588  size_type mem = (my_elements.bucket_count()+1) * sizeof( void* )
589  + 2 * sizeof( size_type );
590  mem += blocks() * ( sizeof( void* ) /* next */
591  + sizeof( Key ) /* key */
592  + sizeof( Word ) /* value */
593  + sizeof( size_type ) /* hash */
594  + sizeof( void* ) /* dyn. alloc. */ );
595  return mem;
596  }

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

602  {
603  size_type mem = (my_elements.bucket_count()+1) * sizeof( void* )
604  + 2 * sizeof( size_type );
605  mem += size() * ( sizeof( void* ) /* next */
606  + sizeof( Key ) /* key */
607  + sizeof( size_type ) /* hash */
608  + sizeof( void* ) /* dyn. alloc. */ );
609  return mem;
610  }

◆ 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
otherthe object to clone
Returns
a reference to this

Definition at line 505 of file UnorderedSetByBlock.h.

506  {
507  if ( this != &other )
508  {
509  my_splitter = other.my_splitter;
510  my_elements = other.my_elements;
511  my_size = other.my_size;
512  }
513  return *this;
514  }

◆ 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
otherthe object to clone
Returns
a reference to this

Definition at line 518 of file UnorderedSetByBlock.h.

519  {
520  my_splitter = std::move( other.my_splitter );
521  my_elements = std::move( other.my_elements );
522  my_size = std::move( other.my_size );
523  return *this;
524  }

◆ 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_countnew capacity of the container (should be thought in terms of number of expected blocks).

Definition at line 1068 of file UnorderedSetByBlock.h.

1069  {
1070  my_elements.reserve( block_count );
1071  }

◆ 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

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

637  {
638  std::swap( my_splitter, other.my_splitter );
639  std::swap( my_elements, other.my_elements );
640  std::swap( my_size, other.my_size );
641  }

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 1080 of file UnorderedSetByBlock.h.

Referenced by DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::begin(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::blocks(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::cbegin(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::cend(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::clear(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::const_iterator::const_iterator(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::count(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::emplace(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::empty(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::end(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::erase(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::find(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::const_iterator::increment(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::iterator::increment(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::insert(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::internal_includes_by_map_iterator(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::internal_trace_includes_by_map_iterator(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::iterator::iterator(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::max_size(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::memory_usage(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::memory_usage_unordered_set(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::operator=(), DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::reserve(), and DGtal::UnorderedSetByBlock< PointVector< dim, Integer >, DGtal::Splitter< PointVector< dim, Integer >, uint64_t > >::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

◆ 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 documentation for this struct was generated from the following file:
DGtal::UnorderedSetByBlock::find
iterator find(const Key &key)
Definition: UnorderedSetByBlock.h:848
DGtal::Bits::nbSetBits
static unsigned int nbSetBits(T val)
Definition: Bits.h:130
DGtal::trace
Trace trace
Definition: Common.h:150
DGtal::UnorderedSetByBlock::my_elements
Container my_elements
the unordered_set containing the elements
Definition: UnorderedSetByBlock.h:1080
DGtal::UnorderedSetByBlock::blocks
size_type blocks() const noexcept
Definition: UnorderedSetByBlock.h:582
DGtal::Trace::info
std::ostream & info()
DGtal::UnorderedSetByBlock::cend
const_iterator cend() const
Definition: UnorderedSetByBlock.h:561
DGtal::UnorderedSetByBlock::my_splitter
Splitter my_splitter
The splitter object.
Definition: UnorderedSetByBlock.h:1078
DGtal::UnorderedSetByBlock::size
size_type size() const noexcept
Definition: UnorderedSetByBlock.h:576
DGtal::UnorderedSetByBlock::end
iterator end()
Definition: UnorderedSetByBlock.h:539
DGtal::UnorderedSetByBlock::erase
iterator erase(const_iterator pos) noexcept
Definition: UnorderedSetByBlock.h:730
DGtal::UnorderedSetByBlock::my_size
size_type my_size
the number of elements
Definition: UnorderedSetByBlock.h:1082
DGtal::UnorderedSetByBlock::size_type
Container::size_type size_type
Unsigned integer type (usually std::size_t)
Definition: UnorderedSetByBlock.h:178
DGtal::PointVector
Aim: Implements basic operations that will be used in Point and Vector classes.
Definition: PointVector.h:593
DGtal::UnorderedSetByBlock
Definition: UnorderedSetByBlock.h:163
DGtal::UnorderedSetByBlock::internal_includes_by_map_iterator
bool internal_includes_by_map_iterator(const Self &other) const
Definition: UnorderedSetByBlock.h:949
DGtal::UnorderedSetByBlock::Word
Splitter::Word Word
Definition: UnorderedSetByBlock.h:166