[ unordered associative containers ]

TR1 provides hash tables in the form of unordered associative containers template class: unordered_map, unordered_multimap, unordered_set and unordered_multiset. Such containers does support compile and runtime tuning.

Synopsis: Template Class and Nested Types: map/multimap

#include <tr1/unordered_map>

template <class Key, class Ty, 
    class Hash = hash<key>,
    class Pred = equal_to<key>,
    class Alloc = allocator< pair<const Key, Ty> > > 
class unordered_map  : public HashTable<...>
{
    // basic container nested types...

    typedef std:::pair<const Key, Ty> value_type;     
    typedef ... reference;
    typedef ... const_reference;
    typedef ... iterator;
    typedef ... const_iterator;
    typedef ... difference_type;       
    typedef ... size_type;       

    // specific unordered container nested types...

    typedef ... key_type;              // the type of key
    typedef ... key_equal;             // the type of predicate equal 
    typedef ... hasher;                // the type of hash functor
    typedef ... local_iterator;
    typedef ... const_local_iterator;

Synopsis: Template Class and Nested Types: set/multiset


#include <tr1/unordered_set>

template <class Ty, 
    class Hash = hash<key>,
    class Pred = equal_to<key>,
    class Alloc = allocator< pair<const Key, Ty> > > 
class unordered_set  : public HashTable<...>
{
    // basic container nested types...

    typedef Ty  value_type;
    typedef ... reference;
    typedef ... const_reference;
    typedef ... iterator;
    typedef ... const_iterator;
    typedef ... difference_type;       
    typedef ... size_type;       

    // specific unordered container nested types...

    typedef ... key_type;              // the type of key
    typedef ... key_equal;             // the type of predicate equal 
    typedef ... hasher;                // the type of hash functor
    typedef ... local_iterator;
    typedef ... const_local_iterator;


Hash Functor Type


template <typename Ty> struct myhash : public std::unary_function<Ty, size_t>
{
    size_t operator()(Ty value) const    
    {
        ...
    
    }
};

EqualKey Functor Type


template <typename Key> struct equal_to : public std::binary_function<Key, Key, bool>
{
    bool operator()(const Key &lhs, const Key &rhs) const
    {
        ...
    }
};

Constructors

Unordered associative containers can be construct in three ways:

unordered_map<Key, Ty>::unordered_map();                                     // default constructor
unordered_map<Key, Ty>::unordered_map(const unordered_map &);                // copy constructor

template <typename InputIterator> 
unordered_map<Key, Ty>::unordered_map(InputIterator beg, InputIterator end); // range initialization

Each of the three constructors can be provided with additional arguments (that have default values otherwise). Such optional arguments are in the order:

size_type                 // initial number of buckets
const hasher &            // an instance of hasher function
const key_equal &         // an instance of equality predicate if it needs initialization
const allocator_type &    // an instance of allocator

Insert member function


Insert a key_type or the pair<key_type, value_type> in the container:

iterator unordered_set<Key...>::insert(const key_type &);
iterator unordered_map<Key...>::insert(std::pair<key_type, value_type> &);

iterator unordered_set<Key...>::insert(iterator, const key_type &);
iterator unordered_map<Key...>::insert(iterator, std::pair<key_type, value_type> &);

template <typename InputIterator>
void unordered_set<Key...>::insert(InputIterator beg, InputIterator end); // Iterator to Ty 

template <typename InputIterator>
void unordered_map<Key...>::insert(InputIterator beg, InputIterator end); // Iterator to std::pair<Key, Ty>


erase, clear member function


erase(k) removes all elements whose key compares equal to k and returns the number of elements removed:

size_type unordered_map<...>::erase(const key_type &k);

erase(it) removes the element pointed at by it and returns an iterator(const_iterator) to the following element:

iterator unordered_map<...>::erase(iterator);
const_iterator unordered_map<...>::erase(const_iterator);

erase(beg,end) removes the elements pointed at by iterators in the range [beg,end) and returns an iterator(const_iterator) that points at the element that followed the range:

iterator unordered_map<...>::erase(iterator beg, iterator end);
const_iterator unordered_map<...>::erase(const_iterator beg, const_iterator end);

clear() removes all elements from the container:

void unordered_map<...>::clear();

find, count and equal_range member functions


find() returns an iterator (or const_iterator) to an object whose key compares equal to k:

iterator unordered_map<...>::find(const key_type &k);
const_iterator unordered_map<...>::find(const key_type &k)const;

count(k) returns the number of objects whose key compares equal to k:

size_type unordered_map<...>::count(const key_type &k)const;

equal_range(k) returns a pair of iterators(const_iterators) that defines a range that contains all the objects whose key compares equal to k:

std::pair<iterator,iterator> unordered_map<...>::equal_range(const key_type &k);
std::pair<const_iterator, const_iterator> unordered_map<...>::equal_range(const key_type &k)const;

hash_function, key_eq member functions


hash_function() returns a copy of the hash object:

Hash unordered_map<...>::hash_function() const;

key_eq() returns a copy of the equality predicate:

Pred unordered_map<...>::key_eq() const;


bucket_count, max_bucket_count, bucket and bucket_size member functions


bucket_count() returns the number of buckets:

size_type unordered_map<...>::bucket_count() const;

max_bucket_count() returns the max number of buckets the container can handle:

size_type unordered_map<...>::max_bucket_count() const;

bucket(k) returns the index of bucket that would contain objects whose key is equal to k:

size_type unordered_map<...>::bucket(const key_type &k) const;

bucket_size(n) returns the number of objects in the bucket at index n:

size_type unordered_map<...>::bucket_size(size_type n) const;

begin, end, begin(n) end(n) iterators


begin() return an iterator that points to the first element of unordered map:

iterator unordered_map<...>::begin();
const_iterator unordered_map<...>::begin() const;

end() return an iterator that points beyond the end of the unordered map:

iterator unordered_map<...>::end();
const_iterator unordered_map<...>::end() const;

begin(n) return a local iterator that points to the first element in the nth bucket:
        
local_iterator unordered_map<...>::begin(size_type n);
const_local_iterator unordered_map<...>::begin(size_type n) const;

end(n) return a local iterator that points beyond the last element in the nth bucket:

local_iterator unordered_map<...>::end(size_t n);
const_local_iterator unordered_map<...>::end(size_t n) const;


The hash table load factor is the average number of objects per bucket. The target load factor is the threshold that if exceeded triggers a rehash.

load_factor, max_load_factor, rehash member functions


load_factor() return the current load factor:

float unordered_map<...>::load_factor() const;

max_load_factor() return the target load factor:

float unordered_map<...>::max_load_factor() const;

max_load_factor(z) set the target load factor:

void unordered_map<...>::max_load_factor(float z);

rehash(n) set the number of buckets to at least n (ensuring that load factor is less than the target load factor) and rehash the table:

void unordered_map<...>::rehash(size_type n);

Comments