Loading...
Searching...
No Matches
robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy > Class Template Reference

Internal common class used by robin_map and robin_set. More...

#include <robin_hash.h>

Inherits Hash, KeyEqual, and GrowthPolicy.

Classes

class  robin_iterator
 The 'operator*()' and 'operator->()' methods return a const reference and const pointer respectively to the stored value type. More...
 

Public Types

using key_type = typename KeySelect::key_type
 
using value_type = ValueType
 
using size_type = std::size_t
 
using difference_type = std::ptrdiff_t
 
using hasher = Hash
 
using key_equal = KeyEqual
 
using allocator_type = Allocator
 
using reference = value_type &
 
using const_reference = const value_type &
 
using pointer = value_type *
 
using const_pointer = const value_type *
 
using iterator = robin_iterator< false >
 
using const_iterator = robin_iterator< true >
 

Public Member Functions

 robin_hash (size_type bucket_count, const Hash &hash, const KeyEqual &equal, const Allocator &alloc, float min_load_factor=DEFAULT_MIN_LOAD_FACTOR, float max_load_factor=DEFAULT_MAX_LOAD_FACTOR)
 C++11 doesn't support the creation of a std::vector with a custom allocator and 'count' default-inserted elements.
 
 robin_hash (const robin_hash &other)
 
 robin_hash (robin_hash &&other) noexcept(std::is_nothrow_move_constructible< Hash >::value &&std::is_nothrow_move_constructible< KeyEqual >::value &&std::is_nothrow_move_constructible< GrowthPolicy >::value &&std::is_nothrow_move_constructible< buckets_container_type >::value)
 
robin_hashoperator= (const robin_hash &other)
 
robin_hashoperator= (robin_hash &&other)
 
allocator_type get_allocator () const
 
iterator begin () noexcept
 
const_iterator begin () const noexcept
 
const_iterator cbegin () const noexcept
 
iterator end () noexcept
 
const_iterator end () const noexcept
 
const_iterator cend () const noexcept
 
bool empty () const noexcept
 
size_type size () const noexcept
 
size_type max_size () const noexcept
 
void clear () noexcept
 
template<typename P >
std::pair< iterator, bool > insert (P &&value)
 
template<typename P >
iterator insert_hint (const_iterator hint, P &&value)
 
template<class InputIt >
void insert (InputIt first, InputIt last)
 
template<class K , class M >
std::pair< iterator, bool > insert_or_assign (K &&key, M &&obj)
 
template<class K , class M >
iterator insert_or_assign (const_iterator hint, K &&key, M &&obj)
 
template<class... Args>
std::pair< iterator, bool > emplace (Args &&... args)
 
template<class... Args>
iterator emplace_hint (const_iterator hint, Args &&... args)
 
template<class K , class... Args>
std::pair< iterator, bool > try_emplace (K &&key, Args &&... args)
 
template<class K , class... Args>
iterator try_emplace_hint (const_iterator hint, K &&key, Args &&... args)
 
iterator erase (iterator pos)
 Here to avoid template<class K> size_type erase(const K& key) being used when we use an iterator instead of a const_iterator.
 
iterator erase (const_iterator pos)
 
iterator erase (const_iterator first, const_iterator last)
 
template<class K >
size_type erase (const K &key)
 
template<class K >
size_type erase (const K &key, std::size_t hash)
 
void swap (robin_hash &other)
 
template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr>
U::value_type & at (const K &key)
 
template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr>
U::value_type & at (const K &key, std::size_t hash)
 
template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr>
const U::value_type & at (const K &key) const
 
template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr>
const U::value_type & at (const K &key, std::size_t hash) const
 
template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr>
U::value_type & operator[] (K &&key)
 
template<class K >
size_type count (const K &key) const
 
template<class K >
size_type count (const K &key, std::size_t hash) const
 
template<class K >
iterator find (const K &key)
 
template<class K >
iterator find (const K &key, std::size_t hash)
 
template<class K >
const_iterator find (const K &key) const
 
template<class K >
const_iterator find (const K &key, std::size_t hash) const
 
template<class K >
bool contains (const K &key) const
 
template<class K >
bool contains (const K &key, std::size_t hash) const
 
template<class K >
std::pair< iterator, iteratorequal_range (const K &key)
 
template<class K >
std::pair< iterator, iteratorequal_range (const K &key, std::size_t hash)
 
template<class K >
std::pair< const_iterator, const_iteratorequal_range (const K &key) const
 
template<class K >
std::pair< const_iterator, const_iteratorequal_range (const K &key, std::size_t hash) const
 
size_type bucket_count () const
 
size_type max_bucket_count () const
 
float load_factor () const
 
float min_load_factor () const
 
float max_load_factor () const
 
void min_load_factor (float ml)
 
void max_load_factor (float ml)
 
void rehash (size_type count_)
 
void reserve (size_type count_)
 
hasher hash_function () const
 
key_equal key_eq () const
 
iterator mutable_iterator (const_iterator pos)
 
template<class Serializer >
void serialize (Serializer &serializer) const
 
template<class Deserializer >
void deserialize (Deserializer &deserializer, bool hash_compatible)
 

Static Public Attributes

static const size_type DEFAULT_INIT_BUCKETS_SIZE = 0
 
static constexpr float DEFAULT_MAX_LOAD_FACTOR = 0.5f
 
static constexpr float MINIMUM_MAX_LOAD_FACTOR = 0.2f
 
static constexpr float MAXIMUM_MAX_LOAD_FACTOR = 0.95f
 
static constexpr float DEFAULT_MIN_LOAD_FACTOR = 0.0f
 
static constexpr float MINIMUM_MIN_LOAD_FACTOR = 0.0f
 
static constexpr float MAXIMUM_MIN_LOAD_FACTOR = 0.15f
 

Detailed Description

template<class ValueType, class KeySelect, class ValueSelect, class Hash, class KeyEqual, class Allocator, bool StoreHash, class GrowthPolicy>
class pxr_tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >

Internal common class used by robin_map and robin_set.

ValueType is what will be stored by robin_hash (usually std::pair<Key, T> for map and Key for set).

KeySelect should be a FunctionObject which takes a ValueType in parameter and returns a reference to the key.

ValueSelect should be a FunctionObject which takes a ValueType in parameter and returns a reference to the value. ValueSelect should be void if there is no value (in a set for example).

The strong exception guarantee only holds if the expression std::is_nothrow_swappable<ValueType>::value && std::is_nothrow_move_constructible<ValueType>::value is true.

Behaviour is undefined if the destructor of ValueType throws.

Definition at line 354 of file robin_hash.h.

Member Typedef Documentation

◆ allocator_type

using allocator_type = Allocator

Definition at line 376 of file robin_hash.h.

◆ const_iterator

Definition at line 382 of file robin_hash.h.

◆ const_pointer

using const_pointer = const value_type*

Definition at line 380 of file robin_hash.h.

◆ const_reference

using const_reference = const value_type&

Definition at line 378 of file robin_hash.h.

◆ difference_type

using difference_type = std::ptrdiff_t

Definition at line 373 of file robin_hash.h.

◆ hasher

using hasher = Hash

Definition at line 374 of file robin_hash.h.

◆ iterator

using iterator = robin_iterator<false>

Definition at line 381 of file robin_hash.h.

◆ key_equal

using key_equal = KeyEqual

Definition at line 375 of file robin_hash.h.

◆ key_type

using key_type = typename KeySelect::key_type

Definition at line 370 of file robin_hash.h.

◆ pointer

using pointer = value_type*

Definition at line 379 of file robin_hash.h.

◆ reference

using reference = value_type&

Definition at line 377 of file robin_hash.h.

◆ size_type

using size_type = std::size_t

Definition at line 372 of file robin_hash.h.

◆ value_type

using value_type = ValueType

Definition at line 371 of file robin_hash.h.

Constructor & Destructor Documentation

◆ robin_hash() [1/3]

robin_hash ( size_type  bucket_count,
const Hash &  hash,
const KeyEqual &  equal,
const Allocator &  alloc,
float  min_load_factor = DEFAULT_MIN_LOAD_FACTOR,
float  max_load_factor = DEFAULT_MAX_LOAD_FACTOR 
)
inline

C++11 doesn't support the creation of a std::vector with a custom allocator and 'count' default-inserted elements.

The needed contructor explicit vector(size_type count, const Allocator& alloc = Allocator()); is only available in C++14 and later. We thus must resize after using the vector(const Allocator& alloc) constructor.

We can't use vector(size_type count, const T& value, const Allocator& alloc) as it requires the value T to be copyable.

Definition at line 580 of file robin_hash.h.

◆ robin_hash() [2/3]

robin_hash ( const robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy > &  other)
inline

Definition at line 611 of file robin_hash.h.

◆ robin_hash() [3/3]

robin_hash ( robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy > &&  other)
inlinenoexcept

Definition at line 626 of file robin_hash.h.

Member Function Documentation

◆ at() [1/4]

U::value_type & at ( const K &  key)
inline

Definition at line 946 of file robin_hash.h.

◆ at() [2/4]

const U::value_type & at ( const K &  key) const
inline

Definition at line 959 of file robin_hash.h.

◆ at() [3/4]

U::value_type & at ( const K &  key,
std::size_t  hash 
)
inline

Definition at line 952 of file robin_hash.h.

◆ at() [4/4]

const U::value_type & at ( const K &  key,
std::size_t  hash 
) const
inline

Definition at line 965 of file robin_hash.h.

◆ begin() [1/2]

const_iterator begin ( ) const
inlinenoexcept

Definition at line 693 of file robin_hash.h.

◆ begin() [2/2]

iterator begin ( )
inlinenoexcept

Definition at line 684 of file robin_hash.h.

◆ bucket_count()

size_type bucket_count ( ) const
inline

Definition at line 1050 of file robin_hash.h.

◆ cbegin()

const_iterator cbegin ( ) const
inlinenoexcept

Definition at line 695 of file robin_hash.h.

◆ cend()

const_iterator cend ( ) const
inlinenoexcept

Definition at line 708 of file robin_hash.h.

◆ clear()

void clear ( )
inlinenoexcept

Definition at line 724 of file robin_hash.h.

◆ contains() [1/2]

bool contains ( const K &  key) const
inline

Definition at line 1015 of file robin_hash.h.

◆ contains() [2/2]

bool contains ( const K &  key,
std::size_t  hash 
) const
inline

Definition at line 1020 of file robin_hash.h.

◆ count() [1/2]

size_type count ( const K &  key) const
inline

Definition at line 981 of file robin_hash.h.

◆ count() [2/2]

size_type count ( const K &  key,
std::size_t  hash 
) const
inline

Definition at line 986 of file robin_hash.h.

◆ deserialize()

void deserialize ( Deserializer &  deserializer,
bool  hash_compatible 
)
inline

Definition at line 1113 of file robin_hash.h.

◆ emplace()

std::pair< iterator, bool > emplace ( Args &&...  args)
inline

Definition at line 795 of file robin_hash.h.

◆ emplace_hint()

iterator emplace_hint ( const_iterator  hint,
Args &&...  args 
)
inline

Definition at line 800 of file robin_hash.h.

◆ empty()

bool empty ( ) const
inlinenoexcept

Definition at line 715 of file robin_hash.h.

◆ end() [1/2]

const_iterator end ( ) const
inlinenoexcept

Definition at line 706 of file robin_hash.h.

◆ end() [2/2]

iterator end ( )
inlinenoexcept

Definition at line 704 of file robin_hash.h.

◆ equal_range() [1/4]

std::pair< iterator, iterator > equal_range ( const K &  key)
inline

Definition at line 1025 of file robin_hash.h.

◆ equal_range() [2/4]

std::pair< const_iterator, const_iterator > equal_range ( const K &  key) const
inline

Definition at line 1036 of file robin_hash.h.

◆ equal_range() [3/4]

std::pair< iterator, iterator > equal_range ( const K &  key,
std::size_t  hash 
)
inline

Definition at line 1030 of file robin_hash.h.

◆ equal_range() [4/4]

std::pair< const_iterator, const_iterator > equal_range ( const K &  key,
std::size_t  hash 
) const
inline

Definition at line 1041 of file robin_hash.h.

◆ erase() [1/5]

size_type erase ( const K &  key)
inline

Definition at line 907 of file robin_hash.h.

◆ erase() [2/5]

size_type erase ( const K &  key,
std::size_t  hash 
)
inline

Definition at line 912 of file robin_hash.h.

◆ erase() [3/5]

iterator erase ( const_iterator  first,
const_iterator  last 
)
inline

Definition at line 843 of file robin_hash.h.

◆ erase() [4/5]

iterator erase ( const_iterator  pos)
inline

Definition at line 841 of file robin_hash.h.

◆ erase() [5/5]

iterator erase ( iterator  pos)
inline

Here to avoid template<class K> size_type erase(const K& key) being used when we use an iterator instead of a const_iterator.

Erase bucket used a backward shift after clearing the bucket. Check if there is a new value in the bucket, if not get the next non-empty.

Definition at line 824 of file robin_hash.h.

◆ find() [1/4]

iterator find ( const K &  key)
inline

Definition at line 995 of file robin_hash.h.

◆ find() [2/4]

const_iterator find ( const K &  key) const
inline

Definition at line 1005 of file robin_hash.h.

◆ find() [3/4]

iterator find ( const K &  key,
std::size_t  hash 
)
inline

Definition at line 1000 of file robin_hash.h.

◆ find() [4/4]

const_iterator find ( const K &  key,
std::size_t  hash 
) const
inline

Definition at line 1010 of file robin_hash.h.

◆ get_allocator()

allocator_type get_allocator ( ) const
inline

Definition at line 677 of file robin_hash.h.

◆ hash_function()

hasher hash_function ( ) const
inline

Definition at line 1096 of file robin_hash.h.

◆ insert() [1/2]

void insert ( InputIt  first,
InputIt  last 
)
inline

Definition at line 753 of file robin_hash.h.

◆ insert() [2/2]

std::pair< iterator, bool > insert ( P &&  value)
inline

Definition at line 738 of file robin_hash.h.

◆ insert_hint()

iterator insert_hint ( const_iterator  hint,
P &&  value 
)
inline

Definition at line 743 of file robin_hash.h.

◆ insert_or_assign() [1/2]

iterator insert_or_assign ( const_iterator  hint,
K &&  key,
M &&  obj 
)
inline

Definition at line 783 of file robin_hash.h.

◆ insert_or_assign() [2/2]

std::pair< iterator, bool > insert_or_assign ( K &&  key,
M &&  obj 
)
inline

Definition at line 773 of file robin_hash.h.

◆ key_eq()

key_equal key_eq ( ) const
inline

Definition at line 1098 of file robin_hash.h.

◆ load_factor()

float load_factor ( ) const
inline

Definition at line 1060 of file robin_hash.h.

◆ max_bucket_count()

size_type max_bucket_count ( ) const
inline

Definition at line 1052 of file robin_hash.h.

◆ max_load_factor() [1/2]

float max_load_factor ( ) const
inline

Definition at line 1070 of file robin_hash.h.

◆ max_load_factor() [2/2]

void max_load_factor ( float  ml)
inline

Definition at line 1077 of file robin_hash.h.

◆ max_size()

size_type max_size ( ) const
inlinenoexcept

Definition at line 719 of file robin_hash.h.

◆ min_load_factor() [1/2]

float min_load_factor ( ) const
inline

Definition at line 1068 of file robin_hash.h.

◆ min_load_factor() [2/2]

void min_load_factor ( float  ml)
inline

Definition at line 1072 of file robin_hash.h.

◆ mutable_iterator()

iterator mutable_iterator ( const_iterator  pos)
inline

Definition at line 1103 of file robin_hash.h.

◆ operator=() [1/2]

robin_hash & operator= ( const robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy > &  other)
inline

Definition at line 647 of file robin_hash.h.

◆ operator=() [2/2]

robin_hash & operator= ( robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy > &&  other)
inline

Definition at line 670 of file robin_hash.h.

◆ operator[]()

U::value_type & operator[] ( K &&  key)
inline

Definition at line 976 of file robin_hash.h.

◆ rehash()

void rehash ( size_type  count_)
inline

Definition at line 1083 of file robin_hash.h.

◆ reserve()

void reserve ( size_type  count_)
inline

Definition at line 1089 of file robin_hash.h.

◆ serialize()

void serialize ( Serializer &  serializer) const
inline

Definition at line 1108 of file robin_hash.h.

◆ size()

size_type size ( ) const
inlinenoexcept

Definition at line 717 of file robin_hash.h.

◆ swap()

void swap ( robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy > &  other)
inline

Definition at line 924 of file robin_hash.h.

◆ try_emplace()

std::pair< iterator, bool > try_emplace ( K &&  key,
Args &&...  args 
)
inline

Definition at line 805 of file robin_hash.h.

◆ try_emplace_hint()

iterator try_emplace_hint ( const_iterator  hint,
K &&  key,
Args &&...  args 
)
inline

Definition at line 812 of file robin_hash.h.

Member Data Documentation

◆ DEFAULT_INIT_BUCKETS_SIZE

const size_type DEFAULT_INIT_BUCKETS_SIZE = 0
static

Definition at line 1555 of file robin_hash.h.

◆ DEFAULT_MAX_LOAD_FACTOR

constexpr float DEFAULT_MAX_LOAD_FACTOR = 0.5f
staticconstexpr

Definition at line 1557 of file robin_hash.h.

◆ DEFAULT_MIN_LOAD_FACTOR

constexpr float DEFAULT_MIN_LOAD_FACTOR = 0.0f
staticconstexpr

Definition at line 1561 of file robin_hash.h.

◆ MAXIMUM_MAX_LOAD_FACTOR

constexpr float MAXIMUM_MAX_LOAD_FACTOR = 0.95f
staticconstexpr

Definition at line 1559 of file robin_hash.h.

◆ MAXIMUM_MIN_LOAD_FACTOR

constexpr float MAXIMUM_MIN_LOAD_FACTOR = 0.15f
staticconstexpr

Definition at line 1563 of file robin_hash.h.

◆ MINIMUM_MAX_LOAD_FACTOR

constexpr float MINIMUM_MAX_LOAD_FACTOR = 0.2f
staticconstexpr

Definition at line 1558 of file robin_hash.h.

◆ MINIMUM_MIN_LOAD_FACTOR

constexpr float MINIMUM_MIN_LOAD_FACTOR = 0.0f
staticconstexpr

Definition at line 1562 of file robin_hash.h.


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