DGtal 1.3.0
Loading...
Searching...
No Matches
UnorderedSetByBlock.h
1
17#pragma once
26#ifndef UNORDEREDSETBYBLOCK_HPP
27#define UNORDEREDSETBYBLOCK_HPP
28
29#include <unordered_map>
30#include <boost/iterator/iterator_facade.hpp>
31#include <climits>
32#include "DGtal/base/Common.h"
33#include "DGtal/base/Bits.h"
34#include "DGtal/kernel/CUnsignedNumber.h"
35#include "DGtal/kernel/CBoundedNumber.h"
36#include "DGtal/kernel/PointVector.h"
37#include "DGtal/kernel/PointHashFunctions.h"
38
39namespace DGtal
40{
41
66 template < typename TElement, typename TWord = uint32_t >
67 struct Splitter {
69 typedef TElement Element;
70 typedef TWord Word;
71 typedef typename Element::Coordinate Coordinate;
72
75
83 static
84 std::pair< Element, Coordinate >
86 {
87 auto block_coords =
88 ( e[ 0 ] & static_cast<Coordinate>( sizeof( Word ) * CHAR_BIT - 1 ) );
89 e[ 0 ] -= block_coords;
90 return { e, block_coords };
91 }
92
99 static
100 Element
102 {
103 e[ 0 ] |= x;
104 return e;
105 }
106
113 static
114 Element
115 join( const std::pair< Element, Coordinate >& p )
116 {
117 Element ge = p.first;
118 ge[ 0 ] |= p.second;
119 return ge;
120 }
121 };
122
123
155 template < typename Key,
156 typename TSplitter = Splitter< Key >,
157 class Hash = std::hash<Key>,
158 class KeyEqual = std::equal_to<Key>,
159 class UnorderedMapAllocator = std::allocator<
160 std::pair<const Key, typename TSplitter::Word >
161 >
162 >
165 typedef TSplitter Splitter;
166 typedef typename Splitter::Word Word;
169 typedef std::unordered_map< Key, Word, Hash, KeyEqual,
170 UnorderedMapAllocator > Container;
171
172 // Standard types
174 typedef Key key_type;
176 typedef Key value_type;
178 typedef typename Container::size_type size_type;
180 typedef typename Container::difference_type difference_type;
182 typedef Hash hasher;
184 typedef KeyEqual key_equal;
186 typedef typename Container::allocator_type allocator_type;
188 typedef Key& reference;
190 typedef const Key& const_reference;
192 typedef Key* pointer;
194 typedef const Key* const_pointer;
195
196 public:
197 // ---------------------- iterators --------------------------------
198
201 : public boost::iterator_facade< const_iterator, Key const,
202 boost::forward_traversal_tag,
203 Key const >
204 {
205 friend struct UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual >;
207 const_iterator() : collection( nullptr ), it(),
208 bit( static_cast<Coordinate>(0) ),
209 current( static_cast<Word>(0) ) {}
210
214 const_iterator( const Self& aSet, typename Container::const_iterator anIt )
215 : collection( &aSet ), it( anIt )
216 {
217 if ( it != collection->my_elements.cend() )
218 {
219 current = it->second;
220 bit = static_cast<Coordinate>( Bits::leastSignificantBit( current ) );
221 }
222 else
223 {
224 current = static_cast<Word>(0);
225 bit = static_cast<Coordinate>(0);
226 }
227 }
228
233 const_iterator( const Self& aSet, typename Container::const_iterator anIt,
234 Coordinate aBit )
235 : collection( &aSet ), it( anIt ), bit( aBit )
236 {
237 if ( it != collection->my_elements.cend() )
238 {
239 current = it->second;
240 current &= ~( ( static_cast<Word>(1) << bit ) - static_cast<Word>(1) );
241 }
242 else
243 current = static_cast<Word>(0);
244 }
245
249 const_iterator( const Self& aSet, const Key& key )
250 : collection( &aSet )
251 {
252 auto se = collection->my_splitter.split( key );
253 it = collection->my_elements.find( se.first );
254 if ( it != collection->my_elements.cend() )
255 {
256 bit = se.second;
257 current = it->second & ~( (static_cast<Word>(1) << bit )
258 - static_cast<Word>(1) );
259 }
260 else
261 {
262 bit = static_cast<Coordinate>(0);
263 current = static_cast<Word>(0);
264 }
265 }
266
267 private:
270 {
271 ASSERT( current != static_cast<Word>(0)
272 && "Invalid increment on const_iterator" );
273 current &= ~( static_cast<Word>(1) << bit );
274 if ( current == static_cast<Word>(0) )
275 {
276 ++it;
277 if ( it != collection->my_elements.cend() )
278 {
279 current = it->second;
281 }
282 else
283 {
284 current = static_cast<Word>(0);
285 bit = static_cast<Coordinate>(0); // NB: LSB(0) is undefined
286 }
287 }
288 else
290 }
291
292 bool equal( const const_iterator & other ) const
293 {
294 ASSERT( collection == other.collection );
295 return it == other.it && bit == other.bit;
296 }
297
298 const Key dereference() const
299 {
300 return collection->my_splitter.join( it->first, bit );
301 }
302
306 typename Container::const_iterator it;
311
312 };
313
315 struct iterator
316 : public boost::iterator_facade< iterator, Key const,
317 boost::forward_traversal_tag,
318 Key const >
319 {
320 friend struct UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual >;
322 iterator() : collection( nullptr ), it(),
323 bit( static_cast<Coordinate>(0) ),
324 current( static_cast<Word>(0) ) {}
325
329 iterator( Self& aSet, typename Container::iterator anIt )
330 : collection( &aSet ), it( anIt )
331 {
332 if ( it != collection->my_elements.end() )
333 {
334 current = it->second;
336 }
337 else
338 {
339 current = static_cast<Word>(0);
340 bit = static_cast<Coordinate>(0);
341 }
342 }
343
348 iterator( Self& aSet, typename Container::iterator anIt, Coordinate aBit )
349 : collection( &aSet ), it( anIt ), bit( aBit )
350 {
351 if ( it != collection->my_elements.end() )
352 {
353 current = it->second;
354 current &= ~( ( static_cast<Word>(1) << bit )
355 - static_cast<Word>(1) );
356 }
357 else
358 current = static_cast<Word>(0);
359 }
360
366 iterator( Self& aSet, const Key& key )
367 : collection( &aSet )
368 {
369 auto se = collection->my_splitter.split( key );
370 it = collection->my_elements.find( se.first );
371 if ( it != collection->my_elements.end() )
372 {
373 bit = se.second;
374 current = it->second & ~( (static_cast<Word>(1) << bit )
375 - static_cast<Word>(1) );
376 }
377 else
378 {
379 bit = static_cast<Coordinate>(0);
380 current = static_cast<Word>(0);
381 }
382 }
383
386 iterator( const const_iterator& other )
387 : collection( other.collection ), it( other.it ),
388 bit( other.bit ), current( other.current )
389 {}
390
394 : collection( std::move( other.collection ) ),
395 it( std::move( other.it ) ),
396 bit( std::move( other.bit ) ),
397 current( std::move( other.current ) )
398 {}
399
402 operator const_iterator() const
403 {
404 return const_iterator( *collection, it, bit );
405 }
406
407 private:
410 {
411 ASSERT( current != static_cast<Word>(0)
412 && "Invalid increment on iterator" );
413 current &= ~( static_cast<Word>(1) << bit );
414 if ( current == static_cast<Word>(0) )
415 {
416 ++it;
417 if ( it != collection->my_elements.end() )
418 {
419 current = it->second;
421 }
422 else
423 {
424 current = static_cast<Word>(0);
425 bit = static_cast<Coordinate>(0); // NB: LSB(0) is undefined
426 }
427 }
428 else
430 }
431
432 bool equal( const iterator & other ) const
433 {
434 ASSERT( collection == other.collection );
435 return it == other.it && bit == other.bit;
436 }
437
438 // The equality comparator with const_iterator must also be
439 // provided to respect the standard that says that iterator and
440 // const_iterator should always be comparable.
441 bool equal( const const_iterator & other ) const
442 {
443 ASSERT( collection == other.collection );
444 return it == other.it && bit == other.bit;
445 }
446
447 const Key dereference() const
448 {
449 return collection->my_splitter.join( it->first, bit );
450 }
451
455 typename Container::iterator it;
460
461 };
462
463 // ------------------------- standard services ----------------------------------
466 public:
467
474 UnorderedSetByBlock( size_type bucket_count = 23,
475 const Splitter & splitter = Splitter(),
476 const Hash& hash = Hash(),
477 const key_equal& equal = key_equal(),
478 const UnorderedMapAllocator& alloc = UnorderedMapAllocator())
479 : my_splitter( splitter ),
480 my_elements( bucket_count, hash, equal, alloc ),
481 my_size( 0 ) {}
482
485
488 UnorderedSetByBlock( const Self& other )
489 : my_splitter( other.my_splitter ),
490 my_elements( other.my_elements ),
491 my_size( other.my_size )
492 {}
493
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 {}
501
505 Self& operator=( const Self& other )
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 }
518 Self& operator=( Self&& other )
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 }
525
527
528 // ---------------------- iterator services -----------------------------
531 public:
532
535 {
536 return iterator( *this, my_elements.begin() );
537 }
540 {
541 return iterator( *this, my_elements.end() );
542 }
543
546 {
547 return const_iterator( *this, my_elements.cbegin() );
548 }
551 {
552 return const_iterator( *this, my_elements.cend() );
553 }
554
557 {
558 return const_iterator( *this, my_elements.cbegin() );
559 }
562 {
563 return const_iterator( *this, my_elements.cend() );
564 }
565
567
568 // ---------------------- capacity services -----------------------------
571 public:
572
574 bool empty() const noexcept { return my_elements.empty(); }
576 size_type size() const noexcept { return my_size; }
578 size_type max_size() const noexcept { return my_elements.max_size(); }
579
582 size_type blocks() const noexcept { return my_elements.size(); }
583
586 size_type memory_usage() const noexcept
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 }
597
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 }
611
613
614 // ---------------------- modifier services -----------------------------
617 public:
618
620 void clear() noexcept
621 {
622 my_elements.clear();
623 my_size = 0;
624 }
625
636 void swap( Self& other ) noexcept
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 }
642
656 std::pair<iterator,bool> insert( const value_type& value )
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 }
679
693 template <typename InputIterator>
694 void insert( InputIterator first, InputIterator last )
695 {
696 for ( ; first != last; ++first ) insert( *first );
697 }
698
712 template<typename... _Args>
713 std::pair<iterator, bool>
714 emplace(_Args&&... __args)
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 }
737
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 }
763
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 }
836
845 {
846 auto it = find( key );
847 if ( it != end() )
848 {
849 erase( it );
850 return 1;
851 }
852 else return 0;
853 }
854
856
857 // ---------------------- lookup services -----------------------------
860 public:
861
867 iterator find( const Key& key )
868 {
869 const auto se = my_splitter.split( key );
870 const auto it = my_elements.find( se.first );
871 if ( it == my_elements.end() ) return end();
872 const bool exist = it->second & ( static_cast<Word>(1) << se.second );
873 if ( exist ) return iterator( *this, it, se.second );
874 else return end();
875 }
876
882 const_iterator find( const Key& key ) const
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 }
891
896 size_type count( const Key& key ) const
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 }
904
913 std::pair<iterator,iterator>
914 equal_range( const Key & key )
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 }
924
933 std::pair<const_iterator,const_iterator>
934 equal_range( const Key & key ) const
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 }
944
946
947 // ---------------------- set services -------------------------
950 public:
951
958 bool includes( const Self& other ) const
959 {
960 return internal_includes_by_map_iterator( other );
961 }
962
963 protected:
968 bool internal_includes_by_map_iterator( const Self& other ) const
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 }
983
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 }
1013
1019 bool internal_includes_by_iterator( const Self& other ) const
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 }
1035
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 }
1068
1070
1071 // ---------------------- hash policy services -----------------------------
1074 public:
1075
1087 void reserve( size_type block_count )
1088 {
1089 my_elements.reserve( block_count );
1090 }
1091
1093
1094 private:
1095 // -------------------------- data ---------------------------------
1102 };
1103
1104
1113 template < typename Key,
1114 typename TSplitter,
1115 class Hash,
1116 class KeyEqual,
1117 class UnorderedMapAllocator >
1118 void swap
1121 noexcept
1122 {
1123 s1.swap( s2 );
1124 }
1125
1126} // namespace DGtal
1127
1128#endif // #ifndef UNORDEREDSETBYBLOCK_HPP
std::ostream & info()
DGtal is the top-level namespace which contains all DGtal functions and types.
void swap(UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator > &s1, UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator > &s2) noexcept
Trace trace
Definition: Common.h:154
STL namespace.
static unsigned int nbSetBits(T val)
Definition: Bits.h:130
static unsigned int leastSignificantBit(DGtal::uint8_t n)
Definition: Bits.h:297
static Element join(Element e, Coordinate x)
BOOST_CONCEPT_ASSERT((concepts::CBoundedNumber< Word >))
Element::Coordinate Coordinate
Splitter< TElement, TWord > Self
static std::pair< Element, Coordinate > split(Element e)
BOOST_CONCEPT_ASSERT((concepts::CUnsignedNumber< Word >))
static Element join(const std::pair< Element, Coordinate > &p)
Read iterator on set elements. Model of ForwardIterator.
bool equal(const const_iterator &other) const
const_iterator(const Self &aSet, typename Container::const_iterator anIt)
const_iterator(const Self &aSet, const Key &key)
Container::const_iterator it
the hidden iterator that traverses the block map.
const Self * collection
the collection that this iterator is traversing.
Coordinate bit
the current position in the block.
const_iterator(const Self &aSet, typename Container::const_iterator anIt, Coordinate aBit)
Word current
the current value of the block, where visited bits have been erased.
Read-write iterator on set elements. Model of ForwardIterator.
Self * collection
the collection that this iterator is traversing.
Coordinate bit
the current position in the block.
iterator(const const_iterator &other)
bool equal(const const_iterator &other) const
Container::iterator it
the hidden iterator that traverses the block map.
iterator(Self &aSet, typename Container::iterator anIt)
iterator(Self &aSet, const Key &key)
bool equal(const iterator &other) const
Word current
the current value of the block, where visited bits have been erased.
iterator(Self &aSet, typename Container::iterator anIt, Coordinate aBit)
void insert(InputIterator first, InputIterator last)
Inserts a range of element into the set.
~UnorderedSetByBlock()=default
Default destructor.
iterator find(const Key &key)
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
std::pair< iterator, bool > insert(const value_type &value)
Attempts to insert an element into the set.
bool internal_trace_includes_by_iterator(const Self &other) const
void swap(Self &other) noexcept
Splitter::Coordinate Coordinate
Self & operator=(Self &&other)
UnorderedSetByBlock(const Self &other)
std::unordered_map< Key, Word, Hash, KeyEqual, UnorderedMapAllocator > Container
The underlying container, an unordered_map.
Key & reference
Reference to value_type/Key.
size_type blocks() const noexcept
size_type erase(const key_type &key)
iterator erase(const_iterator pos) noexcept
size_type max_size() const noexcept
const_iterator cbegin() const
Key * pointer
Pointer to value_type/Key.
bool internal_includes_by_iterator(const Self &other) const
std::pair< iterator, iterator > equal_range(const Key &key)
void reserve(size_type block_count)
Container::difference_type difference_type
Signed integer type (usually std::ptrdiff_t)
const_iterator cend() const
const_iterator begin() const
Self & operator=(const Self &other)
Splitter my_splitter
The splitter object.
size_type size() const noexcept
bool empty() const noexcept
bool internal_includes_by_map_iterator(const Self &other) const
bool includes(const Self &other) const
size_type my_size
the number of elements
std::pair< iterator, bool > emplace(_Args &&... __args)
Attempts to build and insert an element into the set.
const Key * const_pointer
Const Pointer to value_type/Key.
iterator erase(const_iterator first, const_iterator last) noexcept
const_iterator find(const Key &key) const
const_iterator end() const
size_type count(const Key &key) const
const Key & const_reference
Const reference to value_type/Key.
Container::allocator_type allocator_type
Allocator.
Container my_elements
the unordered_set containing the elements
UnorderedSetByBlock(size_type bucket_count=23, const Splitter &splitter=Splitter(), const Hash &hash=Hash(), const key_equal &equal=key_equal(), const UnorderedMapAllocator &alloc=UnorderedMapAllocator())
Container::size_type size_type
Unsigned integer type (usually std::size_t)
UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual > Self
size_type memory_usage_unordered_set() const noexcept
void clear() noexcept
Clears the container.
size_type memory_usage() const noexcept
bool internal_trace_includes_by_map_iterator(const Self &other) const
Aim: The concept CBoundedNumber specifies what are the bounded numbers. Models of this concept should...
Aim: Concept checking for Unsigned numbers. Models of this concept should be listed in NumberTraits c...