rw_hashmultiset< T, Hash, EQ, A > Class Template Reference

Maintains a collection of some type T, in which there may be many equivalent instances of T. More...

#include <rw/stdex/hashmset.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::const_iterator	iterator
typedef impl_type::key_equal	key_equal_type
typedef impl_type::hasher	key_hash_type
typedef impl_type::key_type	key_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_hashmultiset (size_type cap=64, const hasher &h=hasher(), const key_equal_type &eq=key_equal_type())
template<typename InputIterator >
	rw_hashmultiset (InputIterator first, InputIterator last, size_type cap=64, const hasher &h=hasher(), const key_equal_type &eq=key_equal_type())
	rw_hashmultiset (const rw_hashmultiset &other)
	rw_hashmultiset (rw_hashmultiset &&other)
	~rw_hashmultiset ()
iterator	begin ()
const_iterator	begin () const
size_type	capacity () const
const_iterator	cbegin () const
const_iterator	cend () const
void	clear ()
size_type	count (const_reference key) const
bool	empty () const
iterator	end ()
const_iterator	end () const
std::pair< iterator, iterator >	equal_range (const_reference key) const
size_type	erase (const_reference key)
iterator	erase (iterator iter)
iterator	erase (iterator first, iterator last)
float	fill_ratio () const
iterator	find (const_reference key) const
std::pair< iterator, bool >	insert (const_reference val)
iterator	insert (iterator hint, const_reference val)
std::pair< iterator, bool >	insert (value_type &&val)
iterator	insert (iterator hint, value_type &&val)
template<typename InputIterator >
size_type	insert (InputIterator first, InputIterator last)
iterator	lower_bound (const_reference key) const
rw_hashmultiset &	operator= (const rw_hashmultiset &rhs)
rw_hashmultiset &	operator= (rw_hashmultiset &&rhs)
void	resize (size_type cap)
size_type	size () const
void	swap (rw_hashmultiset &other)
iterator	upper_bound (const_reference key) const

Related Functions
(Note that these are not member functions.)
template<class T , class Hash , class EQ , class A >
bool	operator!= (const rw_hashmultiset< T, Hash, EQ, A > &lhs, const rw_hashmultiset< T, Hash, EQ, A > &rhs)
template<class T , class Hash , class EQ , class A >
bool	operator== (const rw_hashmultiset< T, Hash, EQ, A > &lhs, const rw_hashmultiset< T, Hash, EQ, A > &rhs)

Detailed Description

template<class T, class Hash = RWTHash<T>, class EQ = std::equal_to<T>, class A = std::allocator<T>>
class rw_hashmultiset< T, Hash, EQ, A >

Class rw_hashmultiset maintains a collection of T, implemented as a hash table in which there may be many equal instances of T. 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_hashmultiset provides for iterators that reference its elements. Since the contents of rw_hashmultiset are in pseudo-random order, the only iterator ranges that will usually make sense are the results of calling equal_range(), and the entire range from begin() to end().

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

Note

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

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

Synopsis

#include <rw/stdex/hashmset.h>
rw_hashmultiset<T>;

Persistence

None

Member Typedef Documentation

template<class T, class Hash = RWTHash<T>, class EQ = std::equal_to<T>, class A = std::allocator<T>>

typedef impl_type::allocator_type rw_hashmultiset< T, Hash, EQ, A >::allocator_type

A type representing the allocator type for the container.

template<class T, class Hash = RWTHash<T>, class EQ = std::equal_to<T>, class A = std::allocator<T>>

typedef impl_type::const_iterator rw_hashmultiset< T, Hash, EQ, A >::const_iterator

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

template<class T, class Hash = RWTHash<T>, class EQ = std::equal_to<T>, class A = std::allocator<T>>

typedef impl_type::const_pointer rw_hashmultiset< T, Hash, EQ, A >::const_pointer

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

template<class T, class Hash = RWTHash<T>, class EQ = std::equal_to<T>, class A = std::allocator<T>>

typedef impl_type::const_reference rw_hashmultiset< T, Hash, EQ, A >::const_reference

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

template<class T, class Hash = RWTHash<T>, class EQ = std::equal_to<T>, class A = std::allocator<T>>

typedef impl_type::difference_type rw_hashmultiset< T, Hash, EQ, A >::difference_type

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

template<class T, class Hash = RWTHash<T>, class EQ = std::equal_to<T>, class A = std::allocator<T>>

typedef impl_type::hasher rw_hashmultiset< T, Hash, EQ, A >::hasher

A type representing the hash function.

template<class T, class Hash = RWTHash<T>, class EQ = std::equal_to<T>, class A = std::allocator<T>>

typedef impl_type::const_iterator rw_hashmultiset< T, Hash, EQ, A >::iterator

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

template<class T, class Hash = RWTHash<T>, class EQ = std::equal_to<T>, class A = std::allocator<T>>

typedef impl_type::key_equal rw_hashmultiset< T, Hash, EQ, A >::key_equal_type

A type representing the equality function.

template<class T, class Hash = RWTHash<T>, class EQ = std::equal_to<T>, class A = std::allocator<T>>

typedef impl_type::hasher rw_hashmultiset< T, Hash, EQ, A >::key_hash_type

Deprecated:

As of SourcePro 12.5, use hasher instead.

A type representing the hash function.

template<class T, class Hash = RWTHash<T>, class EQ = std::equal_to<T>, class A = std::allocator<T>>

typedef impl_type::key_type rw_hashmultiset< T, Hash, EQ, A >::key_type

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

template<class T, class Hash = RWTHash<T>, class EQ = std::equal_to<T>, class A = std::allocator<T>>

typedef impl_type::pointer rw_hashmultiset< T, Hash, EQ, A >::pointer

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

template<class T, class Hash = RWTHash<T>, class EQ = std::equal_to<T>, class A = std::allocator<T>>

typedef impl_type::reference rw_hashmultiset< T, Hash, EQ, A >::reference

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

template<class T, class Hash = RWTHash<T>, class EQ = std::equal_to<T>, class A = std::allocator<T>>

typedef impl_type::size_type rw_hashmultiset< T, Hash, EQ, A >::size_type

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

template<class T, class Hash = RWTHash<T>, class EQ = std::equal_to<T>, class A = std::allocator<T>>

typedef impl_type::value_type rw_hashmultiset< T, Hash, EQ, A >::value_type

A type representing the value stored in the container.

Constructor & Destructor Documentation

template<class T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::rw_hashmultiset ( size_type  cap = 64, const hasher &  h = hasher(), const key_equal_type &  eq = key_equal_type()  )

inline

Constructs an empty rw_hashmultiset 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 T , class Hash , class EQ , class A >

template<typename InputIterator >

rw_hashmultiset< T, Hash, EQ, A >::rw_hashmultiset ( InputIterator  first, InputIterator  last, size_type  cap = 64, const hasher &  h = hasher(), const key_equal_type &  eq = key_equal_type()  )

inline

Constructs an rw_hashmultiset containing a copy of the elements in the range [first, last). The rw_hashmultiset instance has cap buckets, uses h as its hash function object, and eq as the 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 T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::rw_hashmultiset ( const rw_hashmultiset< T, Hash, EQ, A > &  other )

inline

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

template<class T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::rw_hashmultiset ( rw_hashmultiset< T, Hash, EQ, A > &&  other )

inline

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

Condition:

This method is available only on platforms with rvalue reference support.

template<class T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::~rw_hashmultiset ( )

inline

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

Member Function Documentation

template<class T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::iterator rw_hashmultiset< T, 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 T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::const_iterator rw_hashmultiset< T, 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 T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::size_type rw_hashmultiset< T, Hash, EQ, A >::capacity ( ) const

inline

Returns the number of buckets in the container.

template<class T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::const_iterator rw_hashmultiset< T, 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 T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::const_iterator rw_hashmultiset< T, 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 T , class Hash , class EQ , class A >

void rw_hashmultiset< T, Hash, EQ, A >::clear ( )

inline

Removes all items in the container.

template<class T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::size_type rw_hashmultiset< T, Hash, EQ, A >::count ( const_reference  key ) const

inline

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

template<class T , class Hash , class EQ , class A >

bool rw_hashmultiset< T, Hash, EQ, A >::empty ( ) const

inline

Returns true if there are no items in the container.

template<class T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::iterator rw_hashmultiset< T, 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 T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::const_iterator rw_hashmultiset< T, 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 T , class Hash , class EQ , class A >

std::pair< typename rw_hashmultiset< T, Hash, EQ, A >::iterator, typename rw_hashmultiset< T, Hash, EQ, A >::iterator > rw_hashmultiset< T, Hash, EQ, A >::equal_range ( const_reference  key ) const

inline

Returns the bounds of the subrange representing all values in the container that compare 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 T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::size_type rw_hashmultiset< T, Hash, EQ, A >::erase ( const_reference  key )

inline

Removes each item in the container that compares equal to key according to the equality function object. Returns the number of items that were removed.

template<class T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::iterator rw_hashmultiset< T, 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 T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::iterator rw_hashmultiset< T, Hash, EQ, A >::erase ( iterator  first, iterator  last  )

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 T , class Hash , class EQ , class A >

float rw_hashmultiset< T, 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 T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::iterator rw_hashmultiset< T, Hash, EQ, A >::find ( const_reference  key ) const

inline

Returns the first item in self that 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 T , class Hash , class EQ , class A >

std::pair< typename rw_hashmultiset< T, Hash, EQ, A >::iterator, bool > rw_hashmultiset< T, Hash, EQ, A >::insert ( const_reference  val )

inline

Inserts a copy of val into the container. Returns an iterator to the new item, along with the status true.

template<class T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::iterator rw_hashmultiset< T, Hash, EQ, A >::insert ( iterator  hint, const_reference  val  )

inline

Inserts a copy of val into the container. Returns an iterator to the new item, along with the status true.

The parameter hint is ignored.

template<class T , class Hash , class EQ , class A >

std::pair< typename rw_hashmultiset< T, Hash, EQ, A >::iterator, bool > rw_hashmultiset< T, Hash, EQ, A >::insert ( value_type &&  val )

inline

Inserts val into the container. Returns an iterator to the new item, along with the status true.

Condition:

This method is available only on platforms with rvalue reference support.

template<class T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::iterator rw_hashmultiset< T, Hash, EQ, A >::insert ( iterator  hint, value_type &&  val  )

inline

Inserts val into the container. Returns an iterator to the new item, along with the status true.

The parameter hint is ignored.

Condition:

This method is available only on platforms with rvalue reference support.

template<class T , class Hash , class EQ , class A >

template<typename InputIterator >

rw_hashmultiset< T, Hash, EQ, A >::size_type rw_hashmultiset< T, 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. 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 T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::iterator rw_hashmultiset< T, Hash, EQ, A >::lower_bound ( const_reference  key ) const

inline

Equivalent to equal_range(key).first.

template<class T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A > & rw_hashmultiset< T, Hash, EQ, A >::operator= ( const rw_hashmultiset< T, 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 T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A > & rw_hashmultiset< T, Hash, EQ, A >::operator= ( rw_hashmultiset< T, 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 T , class Hash , class EQ , class A >

void rw_hashmultiset< T, Hash, EQ, A >::resize ( size_type  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 T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::size_type rw_hashmultiset< T, Hash, EQ, A >::size ( ) const

inline

Returns the number of items in the container.

template<class T , class Hash , class EQ , class A >

void rw_hashmultiset< T, Hash, EQ, A >::swap ( rw_hashmultiset< T, 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 T , class Hash , class EQ , class A >

rw_hashmultiset< T, Hash, EQ, A >::iterator rw_hashmultiset< T, Hash, EQ, A >::upper_bound ( const_reference  key ) const

inline

Equivalent to equal_range(key).second.

Friends And Related Function Documentation

template<class T , class Hash , class EQ , class A >

bool operator!= ( const rw_hashmultiset< T, Hash, EQ, A > &  lhs, const rw_hashmultiset< T, Hash, EQ, A > &  rhs  )

related

Equivalent to !(lhs == rhs).

template<class T , class Hash , class EQ , class A >

bool operator== ( const rw_hashmultiset< T, Hash, EQ, A > &  lhs, const rw_hashmultiset< T, 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 which compares equal according to the equality function object.