#include <ordered_hash.h>

Inherits Hash, and KeyEqual.

Classes
class	ordered_iterator

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 = ordered_iterator< false >

using	const_iterator = ordered_iterator< true >

using	reverse_iterator = std::reverse_iterator< iterator >

using	const_reverse_iterator = std::reverse_iterator< const_iterator >

using	values_container_type = ValueTypeContainer

Public Member Functions
	ordered_hash (size_type bucket_count, const Hash &hash, const KeyEqual &equal, const Allocator &alloc, float max_load_factor)

	ordered_hash (const ordered_hash &other)

	ordered_hash (ordered_hash &&other) noexcept(std::is_nothrow_move_constructible< Hash >::value &&std::is_nothrow_move_constructible< KeyEqual >::value &&std::is_nothrow_move_constructible< buckets_container_type >::value &&std::is_nothrow_move_constructible< values_container_type >::value)

ordered_hash &	operator= (const ordered_hash &other)

ordered_hash &	operator= (ordered_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

reverse_iterator	rbegin () noexcept

const_reverse_iterator	rbegin () const noexcept

const_reverse_iterator	rcbegin () const noexcept

reverse_iterator	rend () noexcept

const_reverse_iterator	rend () const noexcept

const_reverse_iterator	rcend () 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 &&value)

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 &&... value_args)

template<class K , class... Args>
iterator	try_emplace_hint (const_iterator hint, K &&key, Args &&... args)

iterator	erase (iterator pos)

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 (ordered_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 >
std::pair< iterator, iterator >	equal_range (const K &key)

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

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

template<class K >
std::pair< const_iterator, const_iterator >	equal_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	max_load_factor () const

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)

iterator	nth (size_type index)

const_iterator	nth (size_type index) const

const_reference	front () const

const_reference	back () const

const values_container_type &	values_container () const noexcept

template<class U = values_container_type, typename std::enable_if< is_vector< U >::value >::type * = nullptr>
const values_container_type::value_type *	data () const noexcept

template<class U = values_container_type, typename std::enable_if< is_vector< U >::value >::type * = nullptr>
size_type	capacity () const noexcept

void	shrink_to_fit ()

template<typename P >
std::pair< iterator, bool >	insert_at_position (const_iterator pos, P &&value)

template<class... Args>
std::pair< iterator, bool >	emplace_at_position (const_iterator pos, Args &&... args)

template<class K , class... Args>
std::pair< iterator, bool >	try_emplace_at_position (const_iterator pos, K &&key, Args &&... value_args)

void	pop_back ()

iterator	unordered_erase (iterator pos)

iterator	unordered_erase (const_iterator pos)

template<class K >
size_type	unordered_erase (const K &key)

template<class K >
size_type	unordered_erase (const K &key, std::size_t hash)

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.75f

Friends
bool	operator== (const ordered_hash &lhs, const ordered_hash &rhs)

bool	operator!= (const ordered_hash &lhs, const ordered_hash &rhs)

bool	operator< (const ordered_hash &lhs, const ordered_hash &rhs)

bool	operator<= (const ordered_hash &lhs, const ordered_hash &rhs)

bool	operator> (const ordered_hash &lhs, const ordered_hash &rhs)

bool	operator>= (const ordered_hash &lhs, const ordered_hash &rhs)

Detailed Description

template<class ValueType, class KeySelect, class ValueSelect, class Hash, class KeyEqual, class Allocator, class ValueTypeContainer, class IndexType>
class tsl::detail_ordered_hash::ordered_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, ValueTypeContainer, IndexType >

Internal common class used by ordered_map and ordered_set.

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

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

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

ValueTypeContainer is the container which will be used to store ValueType values. Usually a std::deque<ValueType, Allocator> or std::vector<ValueType, Allocator>.

The orderd_hash structure is a hash table which preserves the order of insertion of the elements. To do so, it stores the values in the ValueTypeContainer (m_values) using emplace_back at each insertion of a new element. Another structure (m_buckets of type std::vector<bucket_entry>) will serve as buckets array for the hash table part. Each bucket stores an index which corresponds to the index in m_values where the bucket's value is and the (truncated) hash of this value. An index is used instead of a pointer to the value to reduce the size of each bucket entry.

To resolve collisions in the buckets array, the structures use robin hood linear probing with backward shift deletion.