This chapter is a reference guide to the hash support in the Metrowerks standard libraries.
This chapter on Metrowerks implementation of hashes is made up of.
A separate chapter "The <msl_utlity> Header" is also useful when understanding the methdology.
This document reflects issues that are common to hash_set, hash_multiset, hash_map and hash_multimap. Rather than repeat each of these issue for each of the four hash
containers, they are discussed here once and for all.
These classes are analogous to std::set, std::multiset, std::map and std::multimap, but are based on a hash table. The design and implementation of these classes has the following goals:
Not all of these goals can be simultaneously met. For example, optimizations often require a tradeoff between size and speed. "Ease of use" can pull the design in opposite directions from "control over details". And it is not possible to be 100% compatible with two or more other implementations, when they are not compatible among themselves. Nevertheless, thought and concessions have been made toward all of these goals.
These classes are a Metrowerks extension to the standard C++ library. So they have been implemented within the namespace Metrowerks. There are several techniques available for accessing these classes:
One technique is to fully qualify each use of a Metrowerks extension with the full namespace. For example:
#include <hash_set>
int main()
{
Metrowerks::hash_set<int> a;
}
"Metrowerks" is quite a long name and can get tiresome continually typing. But it is not likely to conflict with other library's namespaces. You can easily shorten the Metrowerks namespace while still retaining the protection of namespaces through the use of an alias. For example, here is how to refer to the Metrowerks namespace as "mw":
#include <hash_map>
namespace mw = Metrowerks;
int main()
{
mw::hash_map<int, int> a;
}
The short name "mw" is much more likely to conflict with other's libraries, but as the implementor of your code you can choose your aliases such that there is no conflict.
Using declarations can bring individual names into the current namespace. They can be used either at namespace scope (outside of functions) or at function scope (inside of functions). Here is an example use of a using declaration at namespace scope:
#include <hash_set>
using Metrowerks::hash_multiset;
int main()
{
hash_multiset<int> a;
}
Anywhere below the using declaration, hash_set can be referred to without the use of the Metrowerks qualifier.
Using directives will import every name in one namespace into another. These can be used to essentially "turn off" namespaces so that you don't have to deal with them. They can be used at namespace scope, or to limit their effect, can also be used at function scope. For example:
#include <hash_map>
int main()
{
using namespace Metrowerks;
hash_multimap<int, int> a;
}
In the above example, any name in the Metrowerks namespace can be used in main without qualification.
Most headers with the name <name> have an associated compatibility header <name.h>. These compatibility headers simply issue using declarations for all of the names they contain. Here is an example use:
#include <hash_set.h>
#include <hash_map.h>
int main()
{
hash_set<int> a;
hash_map<int, int> b;
}
Each hash container has a constructor which takes the following arguments, with the following defaults:
size_type num_buckets = 0 const key_hasher& hash = key_hasher()
const key_compare& comp = key_compare()
float load_factor_limit = 2
float growth_factor = 4
const allocator_type& a = allocator_type()
Since all arguments have defaults, the constructor serves as a default constructor. It is also declared explicit to inhibit implicit conversions from the first argument: size_type. The first argument is a way to specify the initial number of buckets. This was chosen as the first parameter in order to remain compatible both with previous versions of Metrowerks hash containers, as well as the SGI hash containers.
The second and third parameters allow client code to initialize the hash and compare function objects if necessary. This will typically only be necessary if ordinary function pointers are being used. When function objects are used, the default constructed function object is often sufficient.
The fourth and fifth parameters allow you to set the initial values of load_factor_limit and growth_factor. Details on how these parameters interact with the size() and bucket_count() of the container can be found in the capacity section.
A second constructor also exists that accepts templated input iterators for constructing a hash container from a range. After the pair of iterators, the 6 parameters from the first constructor follow in the same order, and with the same defaults.
The hash iterators are of the foward type. You can increment them via prefix or postfix ++, but you can not decrement them. This is compatible with our previous implementation of the hash containers, and with the hash containers provided by SGI. But the hash iterators provided by Microsoft are bidirectional. Code that takes advantage of the decrement operators offered by Microsoft will fail at compile time in the Metrowerks implementation.
Forward iterators were chosen over bidirectional iterators to save on memory consumption. Bidirectional iterators would add an additional word of memory to each entry in the hash container. Furthermore a hash container is an unordered collection of elements. This "unorder" can even change as elements are added to the hash container. The ability to iterate an unordered collection in reverse order has a diminished value.
Iterators are invalidated when the number of buckets in the hash container change. This means that iteration over a container while adding elements must be done with extra care (see Capacity for more details). Despite that iterators are invalidated in this fashion, pointers and references into the hash container are never invalidated except when the referenced element is removed from the container.
empty, size and max_size have semantics identical with that described for standard containers.
The load factor of a hash container is the number of elements divided by the number of buckets:
size() load_factor = --------------
bucket_count()
During the life time of a container, the load factor is at all times less than or equal to the load factor limit:
size() -------------- <= load_factor_limit()
bucket_count()
This is a class invariant. When both size() and bucket_count() are zero, the load_factor is interpreted to be zero. size() can not be greater than zero if bucket_count() is zero. Client code can directly or indirectly alter size(), bucket_count() and load_factor_limit(). But at all times, bucket_count() may be adjusted so that the class invariant is not compromised.
The final item in the bulleted list results amounts to a "shrink to fit" statement.
myhash.bucket_count(0); // shrink to fit
The above statement will reduce the bucket count to the point that the load_factor() is just at or below the load_factor_limit().
bucket_count()
returns the current number of buckets in the container.
bucket_count(size_type num_buckets) sets the number of buckets to the first prime number that is equal to or greater than num_buckets, subject to the class invariant described above. It returns the actual number of buckets that were set. This is a relatively expensive operation as all items in the container must be rehashed into the new container. This routine is analogous to vector's reserve. But it does not reserve space for a number of elements. Instead it sets the number of buckets which in turn reserves space for elements, subject to the setting of load_factor_limit().
load_factor() returns size()/bucket_count() as a float.
load_factor_limit()
returns the current load_factor_limit.
load_factor_limit(float lf) sets the load factor limit. If the new load factor limit is less than the current load factor limit, the number of buckets may be increased if the new load factor limit would violate the class invariant as decsribed above. You can completely block the automatic change of bucket_count with:
myhash.load_factor_limit(INFINITY);
This may be important if you are wanting outstanding iterators to not be invalidated while inserting items into the container. The argument to load_factor_limit must be positive, else an exeception of type std::out_of_range is thrown.
The growth_factor functions will read and set the growth_factor. When setting, the new growth factor must be greater than 1 else an exception of type std::out_of_range is thrown.
The collision(const_iterator) method will count the number of items in the same bucket with the referred to item. This may be helpful in diagnosing a poor hash distribution.
hash_set and hash_map have the following insert method:
std::pair<iterator, bool> insert(const value_type& x);
If x does not already exist in the container, it will be inserted. The returned iterator will point to the newly inserted x, and the bool will be true. If x already exists in the container, the container is unchanged. The returned iterator will point to the element that is equal to x, and the bool will be false.
iterator insert(iterator, const value_type& x);
Operates just like the version taking only a value_type. The iterator argument is ignored. It is only present for compatibility with standard containers.
template <class InputIterator> void insert (InputIterator first, InputIterator last);
Inserts those elements in [first, last) that don't already exist in the container.
The functions hash_multiset and hash_multimap have the following insert method:
Prototype:
iterator insert(const value_type& x);
iterator insert(iterator p, const value_type& x);
template <class InputIterator> void insert
(InputIterator first, InputIterator last); In the first insert prototype x is inserted into the container and an iterator pointing to the
newly inserted value is returned. If values equal to x already exist in the container, then the new element is inserted
after all other equal elements. This ordering is stable throughout
the lifetime of the container.
In the second prototype insert first checks to see if *p is equivalent to x according to the compare function. If it is,
then x is inserted before p. If not then x is inserted as if the
insert without an iterator was used. An iterator is returned which
points to the newly inserted element.
The final insert prototype inserts [first, last) into the container. Equal elements
will be ordered according to which was inserted first.
Prototype:
void erase(iterator position);
size_type erase(const key_type& x);
void erase(iterator first, iterator last);
The first erase function erases the item pointed to by position from the container.
The second erases all items in the container that compare equal
to x. and returns the number of elements erased. The third erase erases the range [first, last) from the container.
Prototype:
swap(hash_set& y);
Swaps the contents of *this with y in constant time.
Prototype:
clear();
Erases all elements from the container.
Prototype:
get_allocator() const;
Returns the allocatro the hash container was constructed with.
Prototype:
key_comp() const
Returns the comparison function the hash container was constructed with.
Prototype:
value_comp() const
Returns the comparison function used in the underlying hash table. For hash_set and hash_multiset, this is the same as key_comp().
Prototype:
key_hash()
Returns the hash function the hash container was constructed with.
Prototype:
value_hash()
Returns the hash function used in the underlying hash table. For hash_set and hash_multiset, this is the same as key_hash().
Prototype:
iterator find(const key_type& x) const;
Returns an iterator to the first element in the container that is equal to x, or if x is not in the container, returns end().
Prototype:
count(const key_type& x) const
Return:
Returns the number of elements in the container equal to x.
Prototype:
std::pair<iterator, iterator> equal_range(const key_type& x);
Returns a pair of iterators indicating a range in the container such that all elements in the range are equal to x. If no elements equal to x are in the container, an empty range is returned.
Prototype:
swap(x, y)
Prototype:
operator == (x, y)Return:
Returns true if x and y contain the same elements in the same order. To accomplish this they most likely must have the same number of buckets as well.
Prototype:
operator != (x, y)Return:
The current hash containers are very compatible with previous versions except for a few methods:
You can no longer compare two hash containers with the ordering operators: <, <=, >, >=. Since hash containers are unordered sets of items, such comparisons have little meaning.
lower_bound is no longer supported. Use find instead if you expect the item to be in the container. If not in the container, find will return end(). As there is no ordering, finding the position which an item could be inserted before has no meaning in a hash container.
upper_bound is no longer supported. Again because of the fact that hash containers are unordered, upper_bound has questionable semantics.
Despite the lack of lower_bound and upper_bound, equal_range is supported. In a pinch, equal_range().first sufficies for lower_bound, and equal_range().second suffices for upper_bound.
This header contains two classes:
hash_set is a container that holds an unordered set of items, and no two items in the container can compare equal. hash_multiset permits duplicate entries. Also see the General Hash Issues Introduction.
NOTE This header is non-standard The classes herein are offered as extensions to the C++ standard. They are marked as such by the namespace Metrowerks.
These containers are in the namespace Metrowerks. See Namespace Issues for details and hints about how to best take advantage of this fact.
hash_set and hash_multiset are largely compatible with previous versions of these classes which appeared in namespace std. But see Incompatibility for a short list of incompatibilities.
Previous versions of CodeWarrior placed hash_set and hash_multiset in the headers <hashset.h> and <hashmset.h> respectively. These headers are still available, but should be used only for transition purposes. They will dissappear in a future release. These headers import the contents of <hash_set> into the std namespace (as previous versions of hash_(multi)set were implemented in std.
#include <hashset.h>
int main()
{
std::hash_set<int> a;
}
Both hash_set and hash_multiset have the following template parameters and defaults:
Template Parameters and Defaults:
template <class T, class Hash = hash<T>, class Compare = std::equal_to<T>,class Allocator = std::allocator<T> > class hash_(multi)set;
The first parameter is the type of element the set is to contain. It can be almost any type, but must be copyable.
The second parameter is the hash function used to look up elements. It defaults to the hash function in <hash_fun>. Client code can use hash<T> as is, specialize it, or supply completely different hash function objects or hash function pointers. The hash function must accept a T, and return a size_t.
The third parameter is the comparison function which defaults to std::equal_to<T>. This function should have equality semantics. A specific requirement is that if two keys compare equal according to Compare, then they must also produce the same result when processed by Hash.
The fourth and final parameter is the allocator, which defaults to std::allocator<T>. The same comments and requirements that appear in the standard for allocators apply here as well.
hash_set and hash_multiset define a host of nested types similar to standard containers. Several noteworthy points:
See Iterator Issues that are common to all hash containers.
Iterators of hash_set and hash_multiset are not mutable. They act as const_iterators. One can cast away the const-ness of references returned by iterators, but if the element is modified such that the hash function now has a different value, the behavior is undefined.
See Capacity for details on how to control the number of buckets.
hash_set is a container based on a hash table that supports fast find, insert and erase. The elements in a hash_set are unordered. A hash_set does not allow multiple entries of equivalent elments.
namespace Metrowerks {
template <class T, class Hash = hash<T>, class Compare = std::equal_to<T>,
class Allocator = std::allocator<T> >
class hash_set
{
public:
// types:
typedef T key_type;
typedef T value_type;
typedef Hash key_hasher;
typedef Hash value_hasher;
typedef Allocator allocator_type;
typedef typename Allocator::reference reference;
typedef typename Allocator::const_reference const_reference;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef typename Allocator::pointer pointer;
typedef typename Allocator::const_pointer const_pointer;
typedef Compare key_compare;
typedef Compare value_compare;
typedef typename hash_type::const_iterator iterator;
typedef typename hash_type::const_iterator const_iterator;
// lib.set.cons construct/copy/destroy:
explicit hash_set(size_type num_buckets = 0,
const key_hasher& hash = key_hasher(), const key_compare& comp = key_compare(),
float load_factor_limit = 2, float growth_factor = 2,
const allocator_type& a = allocator_type());
template <class InputIterator>
hash_set(InputIterator first, InputIterator last, size_type num_buckets = 0,
const key_hasher& hash = key_hasher(), const key_compare& comp = key_compare(),
float load_factor_limit = 2, float growth_factor = 2,
const allocator_type& a = allocator_type());
allocator_type get_allocator() const;
// iterators:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
// capacity:
bool empty() const;
size_type size() const;
size_type max_size() const;
size_type bucket_count() const;
size_type bucket_count(size_type num_buckets);
float load_factor() const;
void load_factor_limit(float lf);
float load_factor_limit() const;
void growth_factor(float gf);
float growth_factor() const;
size_type collision(const_iterator i) const;
// modifiers:
std::pair<iterator, bool> insert(const value_type& x);
iterator insert(iterator, const value_type& x);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
void erase(iterator position);
size_type erase(const key_type& x);
void erase(iterator first, iterator last);
void swap(hash_set& y);
void clear();
// observers:
key_compare key_comp() const;
value_compare value_comp() const;
key_hasher key_hash() const;
value_hasher value_hash() const;
// set operations:
iterator find(const key_type& x) const;
size_type count(const key_type& x) const;
std::pair<iterator, iterator> equal_range(const key_type& x) const;
};
template <class T, class Hash, class Compare, class Allocator>
void swap(hash_set<T, Hash, Compare, Allocator>& x,
hash_set<T, Hash, Compare, Allocator>& y);
template <class T, class Hash, class Compare, class Allocator>
bool
operator==(const hash_set<T, Hash, Compare, Allocator>& x,
const hash_set<T, Hash, Compare, Allocator>& y);
template <class T, class Hash, class Compare, class Allocator>
bool
operator!=(const hash_set<T, Hash, Compare, Allocator>& x,
const hash_set<T, Hash, Compare, Allocator>& y);
} // Metrowerks
namespace Metrowerks
template <class T, class Hash = hash<T>, class Compare = std::equal_to<T>,
class Allocator = std::allocator<T> >
class hash_multiset
{
public:
// types:
typedef T key_type;
typedef T value_type;
typedef Hash key_hasher;
typedef Hash value_hasher;
typedef Allocator allocator_type;
typedef typename Allocator::reference reference;
typedef typename Allocator::const_reference const_reference;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef typename Allocator::pointer pointer;
typedef typename Allocator::const_pointer const_pointer;
typedef Compare key_compare;
typedef Compare value_compare;
typedef typename hash_type::const_iterator iterator;
typedef typename hash_type::const_iterator const_iterator;
// lib.set.cons construct/copy/destroy:
explicit hash_multiset(size_type num_buckets = 0,
const key_hasher& hash = key_hasher(), const key_compare& comp = key_compare(),
float load_factor_limit = 2, float growth_factor = 2,
const allocator_type& a = allocator_type());
template <class InputIterator>
hash_multiset(InputIterator first, InputIterator last, size_type num_buckets = 0,
const key_hasher& hash = key_hasher(), const key_compare& comp = key_compare(),
float load_factor_limit = 2, float growth_factor = 2,
const allocator_type& a = allocator_type());
allocator_type get_allocator() const;
// iterators:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
// capacity:
bool empty() const;
size_type size() const;
size_type max_size() const;
size_type bucket_count() const;
size_type bucket_count(size_type num_buckets);
float load_factor() const;
void load_factor_limit(float lf);
float load_factor_limit() const;
void growth_factor(float gf);
float growth_factor() const;
size_type collision(const_iterator i) const;
// modifiers:
iterator insert(const value_type& x);
iterator insert(iterator p, const value_type& x);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
void erase(iterator position);
size_type erase(const key_type& x);
void erase(iterator first, iterator last);
void swap(hash_multiset& y);
void clear();
// observers:
key_compare key_comp() const;
value_compare value_comp() const;
key_hasher key_hash() const;
value_hasher value_hash() const;
// set operations:
iterator find(const key_type& x) const;
size_type count(const key_type& x) const;
std::pair<iterator,iterator> equal_range(const key_type& x) const;
};
template <class T, class Hash, class Compare, class Allocator>
void swap(hash_multiset<T, Hash, Compare, Allocator>& x,
hash_multiset<T, Hash, Compare, Allocator>& y);
template <class T, class Hash, class Compare, class Allocator>
bool
operator==(const hash_multiset<T, Hash, Compare, Allocator>& x,
const hash_multiset<T, Hash, Compare, Allocator>& y);
template <class T, class Hash, class Compare, class Allocator>
bool
operator!=(const hash_multiset<T, Hash, Compare, Allocator>& x,
const hash_multiset<T, Hash, Compare, Allocator>& y);
} // namespace Metrowerks
The hash_map is a container that holds an unordered set of key-value pairs, and no two keys in the container can compare equal. hash_multimap permits duplicate entries. Also see the General Hash Issues Introduction.
This header contains two classes:
NOTE This header is non-standard The classes herein are offered as extensions to the C++ standard. They are marked as such by the namespace Metrowerks.
These containers are in the namespace Metrowerks. See Namespace Issues for details and hints about how to best take advantage of this fact.
hash_map and hash_multimap are largely compatible with previous versions of these classes which appeared in namespace std. But see Incompatibility for a short list of incompatibilities.
Previous versions of CodeWarrior placed hash_map and hash_multimap in the headers <hashmap.h> and <hashmmap.h> respectively. These headers are still available, but should be
used only for transition purposes. They will dissappear in a future
release. These headers import the contents of <hash_map> into the std namespace (as previous versions of hash_(multi)map were implemented in std.
#include <hashmap.h>
int main()
{
std::hash_map<int, int> a;
}
Both hash_map and hash_multimap have the following template parameters and defaults:
template <class Key, class T, class Hash = hash<Key>, class Compare = std::equal_to<Key>, class Allocator = std::allocator<std::pair<const Key, T> > > class hash_(multi)map;
The first parameter is the type of key the map is to contain. It can be almost any type, but must be copyable.
The second parameter is the type of the value that will be assosiated with each key. It can be almost any type, but must be copyable.
The third parameter is the hash function used to look up elements. It defaults to the hash function in <hash_fun>. Client code can use hash<Key> as is, specialize it, or supply completely different hash function objects or hash function pointers. The hash function must accept a Key, and return a size_t.
The fourth parameter is the comparison function which defaults to std::equal_to<Key>. This function should have equality semantics. A specific requirement is that if two keys compare equal according to Compare, then they must also produce the same result when processed by Hash.
The fifth and final parameter is the allocator, which defaults to std::allocator<std::pair<const Key, T> >. The same comments and requirements that appear in the standard for allocators apply here as well.
hash_map and hash_multimap define a host of nested types similar to standard containers. Several noteworthy points:
key_hasher and value_hasher are not the same type. key_hasher is the template parameter Hash.
value_hasher is a nested type which converts key_hasher into a
function which accepts a value_type.
¯ value_hasher has the public typedef's
typedef value_type argument_type; typedef size_type result_type;
This qualifies it as a std::unary_function (as defined in <functional>) and so could be used where other functionals are used.
¯ value_hasher has these public member functions:
size_type operator()(const value_type& x) const; size_type operator()(const key_type& x) const;
These simply return the result of key_hasher, but with the first operator extracting the key_type from the value_type before passing the key_type on to key_hasher.
Key_compare and value_compare are not the same type. key_compare is the template parameter Compare. value_compare is a nested type which converts key_compare into a function which accepts a value_type.
¯ value_compare has the public typedef's
typedef value_type first_argument_type; typedef value_type second_argument_type;
typedef bool result_type;
This qualifies it as a std:: binary_function (as defined in <functional>) and so could be used where other functionals are used.
¯ value_compare has these public member functions:
bool operator()(const value_type& x, const value_type& y) const;
bool operator()(const key_type& x,
const value_type& y) const;
bool operator()(const value_type& x,
const key_type& y) const;
These pass their arguments on to key_compare, extracting the key_type from value_type when necessary.
See Iterator Issues that are common to all hash containers.
See Capacity for details on how to control the number of buckets.
namespace Metrowerks {
template <class Key, class T, class Hash = hash<Key>, class Compare = std::equal_to<Key>,
class Allocator = std::allocator<std::pair<const Key, T> > >
class hash_map
{
public:
// types:
typedef Key key_type;
typedef T mapped_type;
typedef std::pair<const Key, T> value_type;
typedef Hash key_hasher;
typedef Compare key_compare;
typedef Allocator allocator_type;
typedef typename Allocator::reference reference;
typedef typename Allocator::const_reference const_reference;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef typename Allocator::pointer pointer;
typedef typename Allocator::const_pointer const_pointer;
typedef value_hash_imp<is_empty<key_hasher>::value>
value_hasher;
typedef value_compare_imp<is_empty<key_compare>::value>
value_compare;
typedef typename hash_type::iterator iterator;
typedef typename hash_type::const_iterator const_iterator;
// construct/copy/destroy:
explicit hash_map(size_type num_buckets = 0,
const key_hasher& hash = key_hasher(), const key_compare& comp = key_compare(),
float load_factor_limit = 2, float growth_factor = 2,
const allocator_type& a = allocator_type());
template <class InputIterator>
hash_map(InputIterator first, InputIterator last, size_type num_buckets = 0,
const key_hasher& hash = key_hasher(), const key_compare& comp = key_compare(),
float load_factor_limit = 2, float growth_factor = 2,
const allocator_type& a = allocator_type());
allocator_type get_allocator() const;
// iterators:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
// capacity:
bool empty() const;
size_type size() const;
size_type max_size() const;
size_type bucket_count() const;
size_type bucket_count(size_type num_buckets);
float load_factor() const;
void load_factor_limit(float lf);
float load_factor_limit() const;
void growth_factor(float gf);
float growth_factor() const;
size_type collision(const_iterator i) const;
// element access:
mapped_type& operator[](const key_type& x);
// modifiers:
std::pair<iterator, bool> insert(const value_type& x);
iterator insert(iterator, const value_type& x);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
void erase(iterator position);
size_type erase(const key_type& x);
void erase(iterator first, iterator last);
void swap(hash_map& y);
void clear();
// observers:
key_compare key_comp() const;
value_compare value_comp() const;
key_hasher key_hash() const;
value_hasher value_hash() const;
// set operations:
iterator find(const key_type& x);
const_iterator find(const key_type& x) const;
size_type count(const key_type& x) const;
std::pair<iterator, iterator> equal_range(const key_type& x);
std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
};
template <class Key, class T, class Hash, class Compare, class Allocator>
void swap(hash_map<Key, T, Hash, Compare, Allocator>& x,
hash_map<Key, T, Hash, Compare, Allocator>& y);
template <class Key, class T, class Hash, class Compare, class Allocator>
bool
operator==(const hash_map<Key, T, Hash, Compare, Allocator>& x,
const hash_map<Key, T, Hash, Compare, Allocator>& y);
template <class Key, class T, class Hash, class Compare, class Allocator>
bool
operator!=(const hash_map<Key, T, Hash, Compare, Allocator>& x,
const hash_map<Key, T, Hash, Compare, Allocator>& y);
} // Metrowerks
Prototype:
mapped_type& operator[](const key_type& x);
If the key x already exists in the container, returns a reference to the mapped_type associated with that key. If the key x does not already exist in the container, inserts a new entry: (x, mapped_type()), and returns a reference to the newly created, default constructed mapped_type.
namespace Metrowerks {
template <class Key, class T, class Hash = hash<Key>, class Compare = std::equal_to<Key>,
class Allocator = std::allocator<std::pair<const Key, T> > >
class hash_multimap
{
public:
// types:
typedef Key key_type;
typedef T mapped_type;
typedef std::pair<const Key, T> value_type;
typedef Hash key_hasher;
typedef Compare key_compare;
typedef Allocator allocator_type;
typedef typename Allocator::reference reference;
typedef typename Allocator::const_reference const_reference;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef typename Allocator::pointer pointer;
typedef typename Allocator::const_pointer const_pointer;
typedef value_hash_imp<is_empty<key_hasher>::value>
value_hasher;
typedef value_compare_imp<is_empty<key_compare>::value>
value_compare;
typedef typename hash_type::iterator iterator;
typedef typename hash_type::const_iterator const_iterator;
// construct/copy/destroy:
explicit hash_multimap(size_type num_buckets = 0,
const key_hasher& hash = key_hasher(), const key_compare& comp = key_compare(),
float load_factor_limit = 2, float growth_factor = 2,
const allocator_type& a = allocator_type());
template <class InputIterator>
hash_multimap(InputIterator first, InputIterator last, size_type num_buckets = 0,
const key_hasher& hash = key_hasher(), const key_compare& comp = key_compare(),
float load_factor_limit = 2, float growth_factor = 2,
const allocator_type& a = allocator_type());
allocator_type get_allocator() const;
// iterators:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
// capacity:
bool empty() const;
size_type size() const;
size_type max_size() const;
size_type bucket_count() const;
size_type bucket_count(size_type num_buckets);
float load_factor() const;
void load_factor_limit(float lf);
float load_factor_limit() const;
void growth_factor(float gf);
float growth_factor() const;
size_type collision(const_iterator i) const;
// modifiers:
iterator insert(const value_type& x);
iterator insert(iterator p, const value_type& x);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
void erase(iterator position);
size_type erase(const key_type& x);
void erase(iterator first, iterator last);
void swap(hash_multimap& y);
void clear();
// observers:
key_compare key_comp() const;
value_compare value_comp() const;
key_hasher key_hash() const;
value_hasher value_hash() const;
// set operations:
iterator find(const key_type& x);
const_iterator find(const key_type& x) const;
size_type count(const key_type& x) const;
std::pair<iterator, iterator> equal_range(const key_type& x);
std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
};
template <class Key, class T, class Hash, class Compare, class Allocator>
void swap(hash_multimap<Key, T, Hash, Compare, Allocator>& x,
hash_multimap<Key, T, Hash, Compare, Allocator>& y);
template <class Key, class T, class Hash, class Compare, class Allocator>
bool
operator==(const hash_multimap<Key, T, Hash, Compare, Allocator>& x,
const hash_multimap<Key, T, Hash, Compare, Allocator>& y);
template <class Key, class T, class Hash, class Compare, class Allocator>
bool
operator!=(const hash_multimap<Key, T, Hash, Compare, Allocator>& x,
const hash_multimap<Key, T, Hash, Compare, Allocator>& y);
} // namespace Metrowerks
<hash_fun> declares a templated struct which serves as a function object named hash. This is the default hash function for all hash containers. As supplied, hash works for integral types, basic_string types, and char* types (c-strings).
NOTE This header is non-standard The classes herein are offered as extensions to the C++ standard. They are marked as such by the namespace Metrowerks.
Client code can specialize hash to work for other types. For example:
namespace Metrowerks
{
template <>
struct hash<MyType>
: _STD::unary_function<MyType, std::size_t>
{
std::size_t operator()(const MyType& key) const;
};
template <>
std::size_t
hash<MyType>::operator()(const MyType& key) const
{
std::size_t h;
// compute h (the hash of key)
return h;
}
} // Metrowerks
Alternatively, client code can simply supply customized hash functions to the hash containers via the template parameters.
The returned size_t should be as evenly distributed as possible in the range [0, numeric_limits<size_t>::max()]. Logic in the hash containers will take care of folding this output into the range of the current number of buckets.