template class tsl::detail_robin_hash::robin_hash

Overview

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.

#include <robin_hash.h>

template <
    class ValueType,
    class KeySelect,
    class ValueSelect,
    class Hash,
    class KeyEqual,
    class Allocator,
    bool StoreHash,
    class GrowthPolicy
    >
class robin_hash:
    private Hash,
    private KeyEqual,
    private GrowthPolicy
{
public:
    // typedefs

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

    // classes

    template <bool IsConst>
    class robin_iterator;

    // fields

    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;

    // construction

    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
        );

    robin_hash(const robin_hash& other);
    robin_hash(robin_hash&& other);

    // methods

    robin_hash& operator = (const robin_hash& other);
    robin_hash& operator = (robin_hash&& other);
    allocator_type get_allocator() const;
    iterator begin();
    const_iterator begin() const;
    const_iterator cbegin() const;
    iterator end();
    const_iterator end() const;
    const_iterator cend() const;
    bool empty() const;
    size_type size() const;
    size_type max_size() const;
    void clear();

    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);
    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, 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 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
        );
};

Construction

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

Methods

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.