SourcePro® API Reference Guide

 
List of all members | Public Types | Public Member Functions | Related Functions
rw_orderedhashmap< K, V, Hash, EQ, A > Class Template Reference

Maintains a collection of mappings between two types K and V, implemented as a hash table of std::pair<const K,V> instances, in which key insertion order is preserved. More...

#include <rw/stdex/orderedhashmap.h>

Public Types

typedef impl_type::allocator_type allocator_type
 
typedef impl_type::const_iterator const_iterator
 
typedef impl_type::const_pointer const_pointer
 
typedef impl_type::const_reference const_reference
 
typedef impl_type::difference_type difference_type
 
typedef impl_type::hasher hasher
 
typedef impl_type::iterator iterator
 
typedef impl_type::key_equal key_equal_type
 
typedef impl_type::key_type key_type
 
typedef impl_type::key_policy::mapped_type mapped_type
 
typedef impl_type::pointer pointer
 
typedef impl_type::reference reference
 
typedef impl_type::size_type size_type
 
typedef impl_type::value_type value_type
 

Public Member Functions

 rw_orderedhashmap (size_type cap=64, const hasher &h=hasher(), const key_equal_type &eq=key_equal_type())
 
 rw_orderedhashmap (const rw_orderedhashmap &other)
 
 rw_orderedhashmap (rw_orderedhashmap &&other)
 
template<typename InputIterator >
 rw_orderedhashmap (InputIterator first, InputIterator last, size_type cap=64, const hasher &h=hasher(), const key_equal_type &eq=key_equal_type())
 
 ~rw_orderedhashmap ()
 
iterator begin ()
 
const_iterator begin () const
 
size_type capacity () const
 
const_iterator cbegin () const
 
const_iterator cend () const
 
void clear ()
 
size_type count (const key_type &key) const
 
bool empty () const
 
iterator end ()
 
const_iterator end () const
 
bool equal_by_keys (const rw_orderedhashmap &rhs) const
 
std::pair< iterator, iteratorequal_range (const key_type &key)
 
std::pair< const_iterator, const_iteratorequal_range (const key_type &key) const
 
size_type erase (const key_type &key)
 
iterator erase (iterator iter)
 
iterator erase (iterator iter, iterator bound)
 
float fill_ratio () const
 
iterator find (const key_type &key)
 
const_iterator find (const key_type &key) const
 
std::pair< iterator, bool > insert (const value_type &val)
 
iterator insert (iterator hint, const value_type &val)
 
std::pair< iterator, bool > insert (value_type &&val)
 
iterator insert (iterator, value_type &&val)
 
template<typename InputIterator >
size_type insert (InputIterator first, InputIterator last)
 
iterator lower_bound (const key_type &key)
 
const_iterator lower_bound (const key_type &key) const
 
rw_orderedhashmapoperator= (const rw_orderedhashmap &rhs)
 
rw_orderedhashmapoperator= (rw_orderedhashmap &&rhs)
 
mapped_typeoperator[] (const key_type &key)
 
void resize (size_t cap)
 
size_type size () const
 
void swap (rw_orderedhashmap &other)
 
iterator upper_bound (const key_type &key)
 
const_iterator upper_bound (const key_type &key) const
 

Related Functions

(Note that these are not member functions.)

template<class K , class V , class Hash , class EQ , class A >
bool operator!= (const rw_orderedhashmap< K, V, Hash, EQ, A > &lhs, const rw_orderedhashmap< K, V, Hash, EQ, A > &rhs)
 
template<class K , class V , class Hash , class EQ , class A >
bool operator== (const rw_orderedhashmap< K, V, Hash, EQ, A > &lhs, const rw_orderedhashmap< K, V, Hash, EQ, A > &rhs)
 

Detailed Description

template<class K, class V, class Hash = RWTHash<K>, class EQ = std::equal_to<K>, class A = std::allocator<std::pair<const K, V> >>
class rw_orderedhashmap< K, V, Hash, EQ, A >

Class rw_orderedhashmap maintains a collection mapping between instances of K (the key) and V (the value), implemented as a hash table of std::pair<const K,V> in which there may not be more than one instance of any given K. Since this is a value-based collection, objects are copied into and out of the collection. As with all classes that meet the ANSI associative container specification, rw_orderedhashmap provides for iterators that reference its elements. rw_orderedhashmap preserves key insertion order.

Hash must provide a const function that takes a single argument convertible to type K and returns a value of type size_t.

Note
Any two keys that are equivalent must hash to the same value.

Key equality is determined by an equality function of type EQ, which takes two arguments convertible to type K and returns a value of type bool.

Note
Any two keys that are equivalent are disallowed for this container.
Synopsis
#include <rw/stdex/orderedhashmap.h>
Persistence
None

Member Typedef Documentation

template<class K, class V, class Hash = RWTHash<K>, class EQ = std::equal_to<K>, class A = std::allocator<std::pair<const K, V> >>
typedef impl_type::allocator_type rw_orderedhashmap< K, V, Hash, EQ, A >::allocator_type

A type representing the allocator type for the container.

template<class K, class V, class Hash = RWTHash<K>, class EQ = std::equal_to<K>, class A = std::allocator<std::pair<const K, V> >>
typedef impl_type::const_iterator rw_orderedhashmap< K, V, Hash, EQ, A >::const_iterator

A type that provides a const forward iterator over the elements in the container.

template<class K, class V, class Hash = RWTHash<K>, class EQ = std::equal_to<K>, class A = std::allocator<std::pair<const K, V> >>
typedef impl_type::const_pointer rw_orderedhashmap< K, V, Hash, EQ, A >::const_pointer

A type that provides a const pointer to an element in the container.

template<class K, class V, class Hash = RWTHash<K>, class EQ = std::equal_to<K>, class A = std::allocator<std::pair<const K, V> >>
typedef impl_type::const_reference rw_orderedhashmap< K, V, Hash, EQ, A >::const_reference

A type that provides a const reference to an element in the container.

template<class K, class V, class Hash = RWTHash<K>, class EQ = std::equal_to<K>, class A = std::allocator<std::pair<const K, V> >>
typedef impl_type::difference_type rw_orderedhashmap< K, V, Hash, EQ, A >::difference_type

A signed integral type used to indicate the distance between two valid iterators on the same container.

template<class K, class V, class Hash = RWTHash<K>, class EQ = std::equal_to<K>, class A = std::allocator<std::pair<const K, V> >>
typedef impl_type::hasher rw_orderedhashmap< K, V, Hash, EQ, A >::hasher

A type representing the hash function.

template<class K, class V, class Hash = RWTHash<K>, class EQ = std::equal_to<K>, class A = std::allocator<std::pair<const K, V> >>
typedef impl_type::iterator rw_orderedhashmap< K, V, Hash, EQ, A >::iterator

A type that provides a forward iterator over the elements in the container.

template<class K, class V, class Hash = RWTHash<K>, class EQ = std::equal_to<K>, class A = std::allocator<std::pair<const K, V> >>
typedef impl_type::key_equal rw_orderedhashmap< K, V, Hash, EQ, A >::key_equal_type

A type representing the key equality function.

template<class K, class V, class Hash = RWTHash<K>, class EQ = std::equal_to<K>, class A = std::allocator<std::pair<const K, V> >>
typedef impl_type::key_type rw_orderedhashmap< K, V, Hash, EQ, A >::key_type

A type representing the type of keys used in the container.

template<class K, class V, class Hash = RWTHash<K>, class EQ = std::equal_to<K>, class A = std::allocator<std::pair<const K, V> >>
typedef impl_type::key_policy::mapped_type rw_orderedhashmap< K, V, Hash, EQ, A >::mapped_type

A type representing the type of mapped values used in the container.

template<class K, class V, class Hash = RWTHash<K>, class EQ = std::equal_to<K>, class A = std::allocator<std::pair<const K, V> >>
typedef impl_type::pointer rw_orderedhashmap< K, V, Hash, EQ, A >::pointer

A type that provides a pointer to an element in the container.

template<class K, class V, class Hash = RWTHash<K>, class EQ = std::equal_to<K>, class A = std::allocator<std::pair<const K, V> >>
typedef impl_type::reference rw_orderedhashmap< K, V, Hash, EQ, A >::reference

A type that provides a reference to an element in the container.

template<class K, class V, class Hash = RWTHash<K>, class EQ = std::equal_to<K>, class A = std::allocator<std::pair<const K, V> >>
typedef impl_type::size_type rw_orderedhashmap< K, V, Hash, EQ, A >::size_type

An unsigned integral type used for counting the number of elements in the container.

template<class K, class V, class Hash = RWTHash<K>, class EQ = std::equal_to<K>, class A = std::allocator<std::pair<const K, V> >>
typedef impl_type::value_type rw_orderedhashmap< K, V, Hash, EQ, A >::value_type

A type representing the value stored in the container.

Constructor & Destructor Documentation

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::rw_orderedhashmap ( size_type  cap = 64,
const hasher h = hasher(),
const key_equal_type eq = key_equal_type() 
)
inline

Constructs an empty rw_orderedhashmap with cap buckets, using h as the hash function object, and eq as the equality function object.

Note
If the value specified for cap is zero, the default number of buckets is used.
template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::rw_orderedhashmap ( const rw_orderedhashmap< K, V, Hash, EQ, A > &  other)
inline

Constructs an rw_orderedhashmap that is a copy of other. Each element from other is copied into self.

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::rw_orderedhashmap ( rw_orderedhashmap< K, V, Hash, EQ, A > &&  other)
inline

Move constructor. The constructed rw_orderedhashmap takes ownership of the data owned by other.

Condition:
This method is available only on platforms with rvalue reference support.
template<class K , class V , class Hash , class EQ , class A >
template<typename InputIterator >
rw_orderedhashmap< K, V, Hash, EQ, A >::rw_orderedhashmap ( InputIterator  first,
InputIterator  last,
size_type  cap = 64,
const hasher h = hasher(),
const key_equal_type eq = key_equal_type() 
)
inline

Constructs an rw_orderedhashmap containing a copy of the pair elements in the range [first, last). The rw_orderedhashmap instance has cap buckets, uses h as its hash function object, and eq as its equality function object.

InputIterator is an input iterator type that points to elements that are convertible to value_type objects.

Note
If the value specified for cap is zero, the default number of buckets is used.
template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::~rw_orderedhashmap ( )
inline

The destructor releases the memory used by the container's implementation.

Member Function Documentation

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::iterator rw_orderedhashmap< K, V, Hash, EQ, A >::begin ( )
inline

Returns an iterator referring to the first element in the container.

If the container is empty, returns end().

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::const_iterator rw_orderedhashmap< K, V, Hash, EQ, A >::begin ( ) const
inline

Returns an iterator referring to the first element in the container.

If the container is empty, returns end().

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::size_type rw_orderedhashmap< K, V, Hash, EQ, A >::capacity ( ) const
inline

Returns the number of buckets in the container.

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::const_iterator rw_orderedhashmap< K, V, Hash, EQ, A >::cbegin ( ) const
inline

Returns an iterator referring to the first element in the container.

If the container is empty, returns end().

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::const_iterator rw_orderedhashmap< K, V, Hash, EQ, A >::cend ( ) const
inline

Returns an iterator referring to the element after the last element in the container.

Dereferencing the iterator returned by this function results in undefined behavior.

template<class K , class V , class Hash , class EQ , class A >
void rw_orderedhashmap< K, V, Hash, EQ, A >::clear ( )
inline

Removes all items in the container.

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::size_type rw_orderedhashmap< K, V, Hash, EQ, A >::count ( const key_type key) const
inline

Returns the number of items in self whose key compares equal to key according to the associated equality function object.

template<class K , class V , class Hash , class EQ , class A >
bool rw_orderedhashmap< K, V, Hash, EQ, A >::empty ( ) const
inline

Returns true if there are no items in the container.

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::iterator rw_orderedhashmap< K, V, Hash, EQ, A >::end ( )
inline

Returns an iterator referring to the element after the last element in the container.

Dereferencing the iterator returned by this function results in undefined behavior.

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::const_iterator rw_orderedhashmap< K, V, Hash, EQ, A >::end ( ) const
inline

Returns an iterator referring to the element after the last element in the container.

Dereferencing the iterator returned by this function results in undefined behavior.

template<class K , class V , class Hash , class EQ , class A >
bool rw_orderedhashmap< K, V, Hash, EQ, A >::equal_by_keys ( const rw_orderedhashmap< K, V, Hash, EQ, A > &  rhs) const
inline

Returns true if the container and rhs have the same number of elements, and for each value_type in lhs, there is a value_type in rhs that has a first part (the key) for which the equality function object returns true. The second part (the value) of the pair is not compared.

template<class K , class V , class Hash , class EQ , class A >
std::pair< typename rw_orderedhashmap< K, V, Hash, EQ, A >::iterator, typename rw_orderedhashmap< K, V, Hash, EQ, A >::iterator > rw_orderedhashmap< K, V, Hash, EQ, A >::equal_range ( const key_type key)
inline

Returns the bounds of the subrange representing all values in the container whose key compares equal to key according to the associated equality function object. If no items in the container compare equal to key, returns end() for both iterators.

template<class K , class V , class Hash , class EQ , class A >
std::pair< typename rw_orderedhashmap< K, V, Hash, EQ, A >::const_iterator, typename rw_orderedhashmap< K, V, Hash, EQ, A >::const_iterator > rw_orderedhashmap< K, V, Hash, EQ, A >::equal_range ( const key_type key) const
inline

Returns the bounds of the subrange representing all values in the container whose key compares equal to key according to the associated equality function object. If no items in the container compare equal to key, returns end() for both iterators.

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::size_type rw_orderedhashmap< K, V, Hash, EQ, A >::erase ( const key_type key)
inline

Removes the item in the container whose key compares equal to key according to the equality function object. Returns 1 if the item was found and removed, 0 otherwise.

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::iterator rw_orderedhashmap< K, V, Hash, EQ, A >::erase ( iterator  iter)
inline

Removes the element referenced by iter and returns an iterator referencing the next element. If iter does not reference an item in self, the result is undefined.

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::iterator rw_orderedhashmap< K, V, Hash, EQ, A >::erase ( iterator  iter,
iterator  bound 
)
inline

Removes each element in the range [first, last). Returns an iterator referencing last. If first does not reference an item in self (and if first and last are not equal), the behavior is undefined.

template<class K , class V , class Hash , class EQ , class A >
float rw_orderedhashmap< K, V, Hash, EQ, A >::fill_ratio ( ) const
inline

Returns the ratio of the number of items in the container to the number of buckets.

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::iterator rw_orderedhashmap< K, V, Hash, EQ, A >::find ( const key_type key)
inline

Returns the first item in self whose key compares equal to key according to the associated equality function object. If no items in the container compare equal to key, returns end().

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::const_iterator rw_orderedhashmap< K, V, Hash, EQ, A >::find ( const key_type key) const
inline

Returns the first item in self whose key compares equal to key according to the associated equality function object. If no items in the container compare equal to key, returns end().

template<class K , class V , class Hash , class EQ , class A >
std::pair< typename rw_orderedhashmap< K, V, Hash, EQ, A >::iterator, bool > rw_orderedhashmap< K, V, Hash, EQ, A >::insert ( const value_type val)
inline

Inserts a copy of val into the container. If an element in the container has the same key as val, an iterator to the existing element in the collection is returned with an associated status of false. Otherwise, the value val is inserted into the collection and an iterator to the new item is returned, along with the status true.

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::iterator rw_orderedhashmap< K, V, Hash, EQ, A >::insert ( iterator  hint,
const value_type val 
)
inline

Inserts a copy of val into the container. If an element in the container has the same key as val, an iterator to the existing element in the collection is returned with an associated status of false. Otherwise, the value val is inserted into the collection and an iterator to the new item is returned, along with the status true.

The parameter hint is ignored.

template<class K , class V , class Hash , class EQ , class A >
std::pair< typename rw_orderedhashmap< K, V, Hash, EQ, A >::iterator, bool > rw_orderedhashmap< K, V, Hash, EQ, A >::insert ( value_type &&  val)
inline

Inserts val into the container. If an element in the container has the same key as val, an iterator to the existing element in the collection is returned with an associated status of false. Otherwise, the value val is inserted into the collection and an iterator to the new item is returned, along with the status true.

Condition:
This method is available only on platforms with rvalue reference support.
template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::iterator rw_orderedhashmap< K, V, Hash, EQ, A >::insert ( iterator  hint,
value_type &&  val 
)
inline

Inserts val into the container. If an element in the container has the same key as val, an iterator to the existing element in the collection is returned with an associated status of false. Otherwise, the value val is inserted into the collection and an iterator to the new item is returned, along with the status true.

The parameter hint is ignored.

Condition:
This method is available only on platforms with rvalue reference support.
template<class K , class V , class Hash , class EQ , class A >
template<typename InputIterator >
rw_orderedhashmap< K, V, Hash, EQ, A >::size_type rw_orderedhashmap< K, V, Hash, EQ, A >::insert ( InputIterator  first,
InputIterator  last 
)
inline

For each value in the range [first, last), inserts a copy of the value into self. If an element in the container has the same key as the value, the value is not inserted. Returns the number of elements inserted.

InputIterator is an input iterator type that points to elements that are convertible to value_type objects.

Note
first and last must not be iterators into self.
template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::iterator rw_orderedhashmap< K, V, Hash, EQ, A >::lower_bound ( const key_type key)
inline

Equivalent to equal_range(key).first.

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::const_iterator rw_orderedhashmap< K, V, Hash, EQ, A >::lower_bound ( const key_type key) const
inline

Equivalent to equal_range(key).first.

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A > & rw_orderedhashmap< K, V, Hash, EQ, A >::operator= ( const rw_orderedhashmap< K, V, Hash, EQ, A > &  rhs)
inline

Replaces the contents of self with copies of the contents of rhs. The capacity, hash function object and equality function object are replaced by the respective objects from rhs.

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A > & rw_orderedhashmap< K, V, Hash, EQ, A >::operator= ( rw_orderedhashmap< K, V, Hash, EQ, A > &&  rhs)
inline

Replaces the contents of self with the contents moved from rhs. The capacity, hash function object and equality function objects are moved from the respective objects in rhs.

Condition:
This method is available only on platforms with rvalue reference support.
template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::mapped_type & rw_orderedhashmap< K, V, Hash, EQ, A >::operator[] ( const key_type key)
inline

Returns a reference to a mapped_type in the container whose key is equal to key according to the associated equality function object. If a key equal to key is not found in the collection, a default constructed mapped_type is created and inserted, and a reference to that instance is returned.

Note
This function requires that mapped_type is default constructible.
template<class K , class V , class Hash , class EQ , class A >
void rw_orderedhashmap< K, V, Hash, EQ, A >::resize ( size_t  cap)
inline

Sets the number of buckets to cap. Each item in the container is rehashed according to the new number of buckets.

Note
If cap is 0, it is ignored.
template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::size_type rw_orderedhashmap< K, V, Hash, EQ, A >::size ( ) const
inline

Returns the number of items in the container.

template<class K , class V , class Hash , class EQ , class A >
void rw_orderedhashmap< K, V, Hash, EQ, A >::swap ( rw_orderedhashmap< K, V, Hash, EQ, A > &  other)
inline

Exchanges the contents of self with other, including the Hash and EQ objects. This method does not copy or destroy any of the items exchanged but exchanges the underlying hash tables.

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::iterator rw_orderedhashmap< K, V, Hash, EQ, A >::upper_bound ( const key_type key)
inline

Equivalent to equal_range(key).second.

template<class K , class V , class Hash , class EQ , class A >
rw_orderedhashmap< K, V, Hash, EQ, A >::const_iterator rw_orderedhashmap< K, V, Hash, EQ, A >::upper_bound ( const key_type key) const
inline

Equivalent to equal_range(key).second.

Friends And Related Function Documentation

template<class K , class V , class Hash , class EQ , class A >
bool operator!= ( const rw_orderedhashmap< K, V, Hash, EQ, A > &  lhs,
const rw_orderedhashmap< K, V, Hash, EQ, A > &  rhs 
)
related

Equivalent to !(lhs == rhs).

template<class K , class V , class Hash , class EQ , class A >
bool operator== ( const rw_orderedhashmap< K, V, Hash, EQ, A > &  lhs,
const rw_orderedhashmap< K, V, Hash, EQ, A > &  rhs 
)
related

Returns true if lhs and rhs have the same number of elements, and for each item in lhs, there is an item in rhs whose first part (the key) compares equal according to the equality function object and whose second part (the value) compares equal according to operator==().

Note
If only the keys of the values need to be compared for equality, use rw_orderedhashmap::equal_by_keys() instead.

Copyright © 2023 Rogue Wave Software, Inc., a Perforce company. All Rights Reserved.