DGtal  1.5.beta
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]

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 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, 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.
Aim: Implements basic operations that will be used in Point and Vector classes.
Definition: PointVector.h:593

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 ) {}
Splitter my_splitter
The splitter object.
size_type my_size
the number of elements
Container my_elements
the unordered_set containing the elements

◆ ~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  }

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.

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

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.

582 { 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

◆ 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

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

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

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

715  {
716  const auto se = my_splitter.split( Key( std::forward<_Args>(__args)... ) );
717  auto it = my_elements.find( se.first );
718  if ( it == my_elements.end() )
719  {
720  auto p =
721  my_elements.insert( std::make_pair( se.first,
722  static_cast<Word>(1) << se.second ) );
723  my_size += 1;
724  return std::make_pair( iterator( *this, p.first, se.second ), true );
725  }
726  else
727  {
728  bool exist = it->second & ( static_cast<Word>(1) << se.second );
729  if ( ! exist )
730  {
731  it->second |= static_cast<Word>(1) << se.second;
732  my_size += 1;
733  }
734  return std::make_pair( iterator( *this, it, se.second ), ! exist );
735  }
736  }

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.

574 { 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

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

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

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

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

935  {
936  const_iterator first = find( key );
937  if ( first != end() )
938  {
939  const_iterator last = first;
940  return std::make_pair( first, ++last );
941  }
942  else return std::make_pair( first, first );
943  }

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

845  {
846  auto it = find( key );
847  if ( it != end() )
848  {
849  erase( it );
850  return 1;
851  }
852  else return 0;
853  }
iterator erase(const_iterator pos) noexcept

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

780  {
781  ASSERT( this == first.collection );
782  ASSERT( this == last.collection );
783  if ( first == cend() ) return end();
784  auto itB = first.it;
785  auto itE = last.it;
786  Word mask = static_cast<Word>(0);
787  // Take care of range over one block only
788  if ( itB == itE )
789  {
790  while ( first != last )
791  {
792  mask |= static_cast<Word>(1) << first.bit;
793  my_size -= 1;
794  ++first;
795  }
796  my_elements[ itB->first ] &= ~mask;
797  return iterator( *this,
798  my_elements.find( itE->first ),
799  last.bit ); // must be valid
800  }
801  // Take care of first element.
802  while ( first.it == itB )
803  {
804  mask |= static_cast<Word>(1) << first.bit;
805  my_size -= 1;
806  ++first;
807  }
808  // Erase first block if empty
809  if ( ( my_elements[ itB->first ] &= ~mask )
810  == static_cast<Word>(0) )
811  my_elements.erase( itB );
812  // Count erased elements in main range.
813  for ( itB = first.it; itB != itE; ++itB )
814  my_size -= Bits::nbSetBits( itB->second );
815  // Erase elements in main range
816  my_elements.erase( first.it, itE );
817  // Take care of last element.
818  if ( itE == my_elements.cend() ) return end();
819  itB = itE;
820  first = const_iterator( *this, itB );
821  mask = static_cast<Word>(0);
822  while ( first != last )
823  {
824  mask |= static_cast<Word>(1) << first.bit;
825  my_size -= 1;
826  ++first;
827  }
828  // Erase last block if empty
829  if ( ( my_elements[ itB->first ] &= ~mask )
830  == static_cast<Word>(0) )
831  my_elements.erase( itB );
832  return iterator( *this,
833  my_elements.find( itE->first ),
834  last.bit ); // must be valid or end.
835  }
static unsigned int nbSetBits(T val)
Definition: Bits.h:130
const_iterator cend() const

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

750  {
751  ASSERT( this == pos.collection );
752  ASSERT( pos != cend() );
753  ASSERT( ( pos.it->second & ( static_cast<Word>(1) << pos.bit ) )
754  != static_cast<Word>(0) );
755  my_size -= 1;
756  Word & w = const_cast< Word& >( pos.it->second );
757  if ( ( w &= ~( static_cast<Word>(1) << pos.bit ) )
758  == static_cast<Word>(0) )
759  return iterator( *this, my_elements.erase( pos.it ) );
760  else
761  return iterator( *this, my_elements.erase( pos.it, pos.it ), pos.bit );
762  }

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

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

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

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

959  {
960  return internal_includes_by_map_iterator( other );
961  }
bool internal_includes_by_map_iterator(const Self &other) const

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

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
InputIteratorany model of input iterator
Parameters
[in]firstan iterator pointing on the first element of the range
[in]lastan 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.

695  {
696  for ( ; first != last; ++first ) insert( *first );
697  }
std::pair< iterator, bool > insert(const value_type &value)
Attempts to insert an element into the set.

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

1020  {
1021  auto it_other = other.cbegin();
1022  auto itEnd_other = other.cend();
1023  while ( it_other != itEnd_other )
1024  {
1025  const auto it_this = find( *it_other );
1026  if ( it_this == cend() ) return false;
1027  auto itMap_other = it_other.it;
1028  const Word w_this = it_this.it->second;
1029  const Word w_other = itMap_other->second;
1030  if ( ( w_this & w_other ) != w_other ) return false;
1031  it_other = const_iterator( other, ++itMap_other );
1032  }
1033  return true;
1034  }

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

969  {
970  auto itMap_other = other.my_elements.cbegin();
971  const auto itEndMap_other = other.my_elements.cend();
972  const auto itEndMap_this = my_elements.cend();
973  for ( ; itMap_other != itEndMap_other; ++itMap_other )
974  {
975  const auto itMap_this = my_elements.find( itMap_other->first );
976  if ( itMap_this == itEndMap_this ) return false;
977  const Word w_this = itMap_this->second;
978  const Word w_other = itMap_other->second;
979  if ( ( w_this & w_other ) != w_other ) return false;
980  }
981  return true;
982  }

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

1044  {
1045  trace.info() << "[trace_includes_v2] #this=" << size()
1046  << " #other=" << other.size() << std::endl;
1047  auto it_other = other.cbegin();
1048  auto itEnd_other = other.cend();
1049  while ( it_other != itEnd_other )
1050  {
1051  trace.info() << "other: cell=" << it_other.it->first
1052  << " value=" << std::hex << it_other.it->second << std::endl;
1053  const auto it_this = find( *it_other );
1054  if ( it_this != cend() )
1055  trace.info() << "this : cell=" << it_this.it->first
1056  << " value=" << std::hex << it_this.it->second << std::endl;
1057  else
1058  trace.info() << "this : end cell" << std::endl;
1059  if ( it_this == cend() ) return false;
1060  auto itMap_other = it_other.it;
1061  const Word w_this = it_this.it->second;
1062  const Word w_other = itMap_other->second;
1063  if ( ( w_this & w_other ) != w_other ) return false;
1064  it_other = const_iterator( other, ++itMap_other );
1065  }
1066  return true;
1067  }
std::ostream & info()
Trace trace
Definition: Common.h:153
size_type size() const noexcept

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

990  {
991  trace.info() << "[trace_includes_v1] #this=" << size()
992  << " #other=" << other.size() << std::endl;
993  auto itMap_other = other.my_elements.cbegin();
994  const auto itEndMap_other = other.my_elements.cend();
995  const auto itEndMap_this = my_elements.cend();
996  for ( ; itMap_other != itEndMap_other; ++itMap_other )
997  {
998  trace.info() << "other: cell=" << itMap_other->first
999  << " value=" << std::hex << itMap_other->second << std::endl;
1000  const auto itMap_this = my_elements.find( itMap_other->first );
1001  if ( itMap_this != itEndMap_this )
1002  trace.info() << "this : cell=" << itMap_this->first
1003  << " value=" << std::hex << itMap_this->second << std::endl;
1004  else
1005  trace.info() << "this : end cell" << std::endl;
1006  if ( itMap_this == itEndMap_this ) return false;
1007  const Word w_this = itMap_this->second;
1008  const Word w_other = itMap_other->second;
1009  if ( ( w_this & w_other ) != w_other ) return false;
1010  }
1011  return true;
1012  }

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.

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

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  }
size_type blocks() const noexcept
Container::size_type size_type
Unsigned integer type (usually std::size_t)

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.

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  }

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

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

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

Definition at line 1087 of file UnorderedSetByBlock.h.

1088  {
1089  my_elements.reserve( block_count );
1090  }

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

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

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

◆ my_splitter


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