| Author: | Paul Pogonyshev |
|---|---|
| Contact: | pogonyshev@gmx.net |
| Copyright: | © 2009, 2010 Paul Pogonyshev |
Table of Contents
Miscellaneous Container Templates (MCT for short) is an assorted collection of STL-like containers. Currently, there are six closely related hash table containers: closed_hash_set, closed_hash_map, linked_hash_set, linked_hash_map, forward_hash_set and forward_hash_map.
The first two are very similar in behavior to TR1 (or Boost) unordered_set and unordered_map. Unlike those, however, they use closed hashing scheme (also known as open addressing). As a result, they tend to be considerably faster.
Linked ones have a stable iteration order and some additional methods to change that. However, they use more memory and are slower than “simple” closed hash tables, so should be used only when specific iteration order is really needed.
Finally, forward hash tables are more performant than linked ones, but support less operations and generally have cumbersome interface.
Containers in the library are written to meet a set of goals and provide certain guarantees regardless of behavior of contained elements.
STL and TR1 compatibility
Where possible, MCT is compatible with STL and TR1. MCT classes can usually be used as drop-in replacement for similar STL or Boost containers.
Thread safety
MCT classes are thread-safe in the face of proper synchronization. Non-mutating (const) method are always safe, i.e. there is no internal state which would require synchronization. Mutating (non-const) methods require that only one thread has access to the modified container; other threads must not “touch” the container while modifications takes place, not even read from it.
Exception safety
Whenever client code throws an exception, containers are always left in a consistent state and there are no memory leaks. This is often referred to as basic exception safety. When possible, MCT also provides strong exception safety. In other words, if an exception is thrown during an operation, it is cancelled and container’s state is exactly the same as if operation never happened.
Eased debugging
Containers come with several debugging functions that allow to find where they become broken (e.g. by using an invalid iterator), which hash function is better and similar things.
Additionally, if permitted by functionality provided by certain container type, the following is also provided by implementation.
High speed
MCT classes are optimized for speed provided that other goals are met.
Rare memory allocations
Memory allocation can be a performance bottleneck of CPU-intensive programs. This is especially true for multithreaded programs as (currently) memory allocation requires synchronization. Such problems can be alleviated by specially tailored allocators, but MCT classes don’t allocate memory often anyway.
In particular, closed_hash_* containers are fast and don’t allocate memory often. In comparison, their linked_hash_* and forward_hash_* counterparts are not so fast, but this is dictated by the additional provided features.
Fast general-purpose hash table containers. The only important functional difference from STL TR1 unordered_set and unordered_map is invalidation of references and pointers to elements.
The following subsections provide a more in-depth comparison. Also refer to Differences With STL TR1 Containers section.
Advantages of MCT classes:
Disadvantages:
Advantages of MCT classes:
Disadvantages:
It is hard to say whether closed_hash_* is faster or slower than dense_hash_* in general as results vary between different benchmarks.
Containers similar to their closed_hash_* counterparts, but with stable iteration order (i.e. one which doesn’t change unpredictably). This is achieved by internally keeping a doubly-linked lists consisting of all the elements.
Advantages (all functional):
Disadvantages (all qualitative):
These containers are somewhat similar to linked hash tables described in the previous section. However, the internally kept list spanning all the elements is only singly-linked. Thus, forward hash tables use less memory and are a little faster, but, on the downside, cannot support considerable part of linked_hash_* functionality.
These containers are inspired by forward_list in C++0x standard library.
Advantages (all qualitative):
Disadvantages (all functional):
MCT lets you to specify mode of external use of a type. This information is completely optional and, in fact, cannot be specified for many types: only those with “holes” in their layout can afford to dedicate a byte or more for external use. However, when specified, it will be leveraged by closed_hash_set and closed_hash_map containers to switch to an (even more) efficient implementation.
MCT can be configured both at installation time and, to a lesser extent, at inclusion time. In other words, regardless of which parameters were chosen during installation, you can still influence how MCT behaves in your program by defining certain symbols before including its headers.
Of course, all configuration parameters below are optional.
Hash functions are not yet part of C++ standard and are only defined in TR1. To make MCT less dependent on C++ compiler and standard library features, these configuration settings can be overriden at inclusion time. If they are not defined, values determined at MCT installation take effect.
Common values are, for C++0x compilers:
#define MCT_HASH_HEADER <functional> #define MCT_HASH_NAMESPACE std
For STL with additional TR1 implementation:
#define MCT_HASH_HEADER <tr1/functional> #define MCT_HASH_NAMESPACE std::tr1
For Boost:
#define MCT_HASH_HEADER <boost/functional/hash.hpp> #define MCT_HASH_NAMESPACE boost
It is not required to use these values. If you use a different (but compatible) implementation of hash function, you can define the settings accordingly.
These are very similar to above symbols for the hash function implementation. Unlike hash functions, type traits are not required for MCT to work, so MCT can be installed even if no provider is found [1]. If they are not present, however, several functions in MCT classes will be considerably slower.
There are probably few cases when default configuration is not good enough. Still, you can override it at inclusion time; e.g. for C++0x compilers:
#define MCT_TYPE_TRAITS_HEADER <type_traits> #define MCT_TYPE_TRAITS_NAMESPACE std
For STL with additional TR1 implementation:
#define MCT_TYPE_TRAITS_HEADER <tr1/type_traits> #define MCT_TYPE_TRAITS_NAMESPACE std::tr1
For Boost:
#define MCT_TYPE_TRAITS_HEADER <boost/type_traits.hpp> #define MCT_TYPE_TRAITS_NAMESPACE boost
Like with hash function symbols, you can as well use different values.
| [1] | This is pretty unlikely since one should just come along with hash provider. |
If defined to a non-zero value, all containers will support various C++0x features. Currently these are:
If this flag is defined to any non-zero value, all containers will have additional debugging members: valid_iterator(), valid_iterator_range(), used_memory(), validate_integrity() and collect_statistics(). See Common Debugging Members reference section for more information.
When set to a non-zero value, functions in MCT will test preconditions and throw unspecified subclass of std::logic_error if they are not met. This is moderately slow, but will detect programming bugs like using an invalidated iterator or popping from an empty linked_hash_map. See Automated Debugging reference section for more information.
Any non-zero value will cause MCT containers to validate internal integrity after each modification. This is extremely slow, so use only for debugging problems. See Automated Debugging reference section for more details.
Elements
Following common STL requirement, MCT requires that element’s destructor doesn’t throw. Behavior with a throwing element destructor is undefined.
Hash function and equality predicate
MCT classes currently require that copy constructors of these function objects do not throw (but calling the object may throw, which is more important). This restriction may be lifted in a future MCT version.
keep_hashes
All container have a keep_hashes template parameter which defaults to false. When it is true, container will store hash values for its elements. Elements with different hash values are never compared against each other, which will often give a speedup if comparator is relatively slow.
Bucket count
Number of buckets as specified as parameter to constructors or rehash() method is always advisory, not mandatory. For instance, current implementation always uses number of buckets that is a power of 2.
Load factor
Load factor of a hash container is ratio of its size to number of buckets. Each container has maximum allowed load factor and if actual load factor exceeds this value, container is rehashed, usually doubling number of buckets. The smaller the maximum load factor is, the faster (on average) the container will be. At the same time, it will also use more memory.
Because each bucket in closed hashing scheme can contain at most one element, load factor of containers in this library never exceeds 1.
MCT classes try to be as compatible as possible with STL. Still, there are differences.
This section could also be titled “How to...”.
Advises in this section are partially based on various benchmarks, partially on educated guesses. Take them with a grain of salt. Since they are quite speculative, you are advised to always benchmark various implementations for your particular case if performance is important enough.
The advises below are mostly concerned with picking hashing principle among the following:
Just pick the best description of your situation below.
I need pointers and references to elements to be always valid
Use open hashing. With closed hashing this cannot be guaranteed.
My hash table will be read-only after some point
In this situation, closed hashing should be generally faster unless elements are really large. Don’t forget to purge erased elements (rehash (0) in MCT classes) when switching to read-only mode.
I have small elements: ints or pointers or small structures of those
Use closed hashing. The smaller the elements are, the more pronounced performance difference with open hashing will be.
The elements are fairly large or “own” largish allocated memory chunks
Use open hashing. Even better, if you can afford the additional inconveniences, intrusive open hashing.
I need to avoid memory allocation on each insert
Presumably because memory allocator requires synchronization between threads. Here you have several options: closed hashing, intrusive open hashing or open hashing with a specially-tailored allocator that avoids locking by e.g. using a memory pool. To choose one of these you probably need to consider other aspects like element size and code difficulty.
Table consists of many fairly small elements and I need to conserve memory
Use Google’s sparse_hash_set or sparse_hash_map. Those are slower, but are superior to other implementations in memory footprint.
One fairly common task is to cache results of some computation. Results are typically cached by arguments to computation function. If domain of those arguments is huge, it is often impossible to keep entire cache in memory, simply because memory is finite. In such cases one needs to limit cache size. There are several different strategies:
This section concerns the third option. “Least useful” is a fairly vague term and can be defined in many different ways, depending on exact needs and/or easiness of implementation. We will further narrow the scope of this section by considering the oldest entry.
To implement a cache with this property, one could use either forward_hash_map or linked_hash_map — not because they uses closed hashing, that’s irrelevant here, but because the containers are linked. Implementation could look like this:
typedef forward_hash_map <key_type, result_type> cache_map;
// or linked_hash_map <...> if you need extra functionality
result_type
compute_result (const key_type& key)
{
cache_map::iterator entry = cache.find (key);
if (entry != cache.end ())
return entry.second;
result_type result = /* some real computation */;
if (cache.size () >= limit)
cache.pop_front ();
cache.insert (make_pair (key, result));
return result;
}
Here cache is a variable of type cache_type and limit is some integral value. Since insert() adds an element at the very end of iteration order, pop_front() can be used to remove the oldest (in insertion terms) element.
If the cache is a linked_hash_map, you can use relink() to alter iteration order. For instance, adding:
cache.relink (cache.end (), entry);
in the found entry case above, will make pop_front() erase the least recently used element, not just the least recently added.
Remember, however, that forward and linked maps use more memory than plain maps, so you should consider whether benefits outweigh this drawback.
Occasionally, it is useful to have queue or stack with fast lookup — for instance, to avoid adding an item which is already added. With traditional array or list implementation, lookup time is proportional to structure size. However, with a hash table-backed implementation you can reduce that to O(1) expected time.
For a queue or stack functionality, a hash table needs to be linked. However, supported operations of forward_hash_set (or forward_hash_map if you need) are just enough in this case and, since these containers are more efficient than linked_hash_*, their use is preferable.
Popping (item removing) in forward_hash_* can only be done at one end, but since pushing (item adding) at both ends is possible, this is enough to implement both queue and stack semantics with the same data structure. To implement a queue, use push_back() and pop_front() functions; for a stack, use push_front() and pop_front().
Don’t forget, however, that hash tables won’t allow duplicate elements. Also remember that the only advantage here is the fast lookup (and no-duplicates restriction if that’s actually desirable in your case). If you don’t need lookup functionality or use it only occasionally, implementation based on array or linked list will almost certainly be more efficient. Additionally, because of associated overhead, hash table implementation will be slower if the queue/stack remains tiny (just a few elements) all the time.
Most tips here just reiterate what is said elsewhere. The section is only meant to give a concise summary of the most performance-sensitive aspects.
Hash function
A good hash function is the most important factor in performance of any hash-based container. You can check if given function works well by using methods described in Common Debugging Members reference section.
Linked containers
While linked containers have functional advantages, this comes at a price, both in performance and memory footprint. Don’t use them unless you actually need stable iteration order.
Forward containers
Forward containers should be used in place of linked ones if the supported functionality is enough for given usecase. They both use less memory and are faster. However, some missing functions (e.g. erase-by-key) are important and can certainly make these containers unsuitable in many cases.
External use information
If you use closed_hash_* containers with a composite element type, consider if it is possible to specialize mct::external_use template for it. If you can do this, the containers for the type will automatically use a more efficient implementation.
keep_hashes
If element comparison function is slow, you can try to reduce number of calls to it by forcing containers to remember contained element hashes: set keep_hashes template parameter to true. If hashes are kept, two elements with different hashes are never compared against each other as they cannot be equal anyway. Remember, however, that for very fast equality function performance impact may be even negative.
Erased elements
MCT classes use closed hashing scheme with quadratic probing. With this scheme it is impossible to (efficiently) mark a bucket as empty. So, an erased bucket still remains occupied, only marked as not containing real data. Such buckets (termed debris) slow down both element lookup and further container modifications.
Containers will automatically get rid of debris if they are too many. However, this operation is quite slow, so it is not done from time to time. If you want, you can force such cleanup by rehashing the container with its current number of buckets. This is especially useful if you are done with modification and from now on the container will be used for lookup only.
Increasing number of buckets
Rehashing is relatively slow operation. So, if you expect many insertions, it is almost always a good idea to preemptively increase number of buckets in a container accordingly by using its rehash() method. Likewise, it pays off to specify initial number of buckets if you can estimate that well enough.
Reducing number of buckets (shrinking container)
While having a low load factor (i.e. many more buckets than elements) usually only benefits performance because there are less hash collisions, the issue is not clear-cut. Sometimes increased memory consumption can make a container slower, because of CPU memory cache misses, or because total program footprint nears physical memory size.
Containers in MCT deliberately never shrink themselves. It seems there is no auto-shrinking strategy that is beneficial often enough yet doesn’t penalize other use cases noticeably. However, you can manually ask a container to shrink by using its rehash() method.
Swapping containers
Swapping two containers with equal allocators is an O(1) operation. However, if allocators are different, the operation is slow: O(n) where n is the total number of buckets. If, for some reason, you use different allocators, keep this in mind.
This section diligently lists and documents every public member of MCT classes. Non-class functions that are closely related to a class (e.g. operator== for class objects) are listed in that class section.
Not all function descriptions explicitly specify exception safety level. If a function documentation doesn’t mention exceptions at all, it can be assumed to never throw anything. If possible exceptions are listed, but safety level is not specified, it can be assumed to be strong safety. Still, in certain “important cases” safety level is specified explicitly even if it matches the default.
A fast unordered container with unique values.
Iterators are invalidated by all insert() variants, setter function max_load_factor (float) and rehash(). All member and associated non-member functions apart from the range insertion provide strong exception safety.
The class is defined in header <mct/hash-set.hpp>:
template <typename Value,
typename Hash = hash <Value>,
typename Equal = std::equal_to <Value>,
typename Allocator = std::allocator <Value>,
bool keep_hashes = false>
class closed_hash_set;
Template parameters:
Value: The set’s value type; must be assignable and copy-constructible Hash: A unary function object type that hashes Value objects and returns an std::size_t hash; copy constructor must not throw, see common note above Equal: A binary function object type used to compare objects of type Value, i.e. equality predicate; copy constructor must not throw, see common note above Allocator: Allocator for type Value keep_hashes: Flag that determines whether the set keeps hashes of individual contained values (i.e. doesn’t recompute them); see flag description above for details
Versioned
Since 1.2
If mct::supports_external_use is true for Value, the container will use a more efficient implementation.
key_type: The set’s value type (i.e. the same as value_type) value_type: The set’s value type hasher: The type of the hash function object key_equal: The type of equality function object allocator_type: The type of allocator object iterator: A bidirectional iterator type capable of navigating the set; value it points to cannot be modified, so this behaves just like const_iterator const_iterator: A constant bidirectional iterator; for sets this behaves exactly as iterator pointer: const_pointer: reference: const_reference: size_type: difference_type: Standard container type members; mostly interesting for meta-programming needs
closed_hash_set (size_type num_buckets = 0,
const hasher& hash = hasher (),
const key_equal& equal = key_equal (),
const allocator_type& allocator = allocator_type ());
Create an empty set.
| Throws: | Exceptions thrown by the allocator. |
|---|
closed_hash_set (const closed_hash_set& that);
Create a new set as a copy of another. Copies contained elements, hash function object, equality predicate, allocator and maximum load factor of the other container.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
Compiler-specific
Only on C++0x compilers:
closed_hash_set (closed_hash_set&& that);
The same as copy constructor, except that the second set is left in undefined state. Unlike the copy constructor, this never throws.
closed_hash_set (const closed_hash_set& that, const allocator_type& allocator);
Similar to the copy constructor, but uses explicitly specified allocator instead of copying it from that container.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
template <typename InputIterator>
closed_hash_set (InputIterator first,
InputIterator last,
size_type num_buckets = 0,
const hasher& hash = hasher (),
const key_equal& equal = key_equal (),
const allocator_type& allocator = allocator_type ());
Create a set containing all elements in the range [first, last). Duplicate elements in the range are effectively ignored.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
Compiler-specific
This constructor is defined only on C++0x compilers
closed_hash_set (std::initializer_list <value_type> initializer,
size_type num_buckets = 0,
const hasher& hash = hasher (),
const key_equal& equal = key_equal (),
const allocator_type& allocator = allocator_type ());
Create a set containing all elements from initializer list. Duplicate elements are effectively ignored.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
closed_hash_set& operator= (const closed_hash_set& that);
Erase current set contents and replace it with contents of another set. This replaces hash function, equality predicate and maximum load factor, but not the allocator.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. Also see common note above. |
|---|
Compiler-specific
Only on C++0x compilers:
closed_hash_set& operator= (closed_hash_set&& that);
The same as copy assignment, except that the second set is left in undefined state. If allocators of the two sets are equal this version doesn’t throw.
Compiler-specific
This assignment is defined only on C++0x compilers
closed_hash_set& operator= (std::initializer_list <value_type> initializer);
Erase current set contents and replace it with values from the initializers. Duplicate elements in the list are effectively ignored.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
Destroy all contained elements, free memory and destroy the set itself.
size_type bucket_count () const;
| Returns: | Current number of bucket used by the container. |
|---|
size_type max_bucket_count () const;
| Returns: | The largest number of buckets this set could ever have. |
|---|
iterator begin (); const_iterator begin () const;
| Returns: | An iterator pointing to the first element in the set, or past-the-end iterator if the set is empty. |
|---|---|
| Notes: | closed_hash_set doesn’t give any guarantees about iteration order. |
const_iterator cbegin () const;
| Returns: | A constant iterator pointing to the first element in the set, or past-the-end iterator if the set is empty. |
|---|---|
| Notes: | closed_hash_set doesn’t give any guarantees about iteration order. |
iterator find (const key_type& key); const_iterator find (const key_type& key) const;
Find an element with given key.
| Returns: | An iterator pointing to matching element or end() if there’s no such element. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
size_type count (const key_type& key) const;
| Returns: | Number of elements with given key. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | For a set return value is always 0 or 1. |
std::pair <iterator, iterator> equal_range (const key_type& key); std::pair <const_iterator, const_iterator> equal_range (const key_type& key) const;
Determine the range consisting of all elements with given key.
| Returns: | A pair P such that [P.first, P.second) is the range consisting all elements with given key. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | For a set such a range always contains 0 or 1 element. |
Note that all insert() variants invalidate iterators while all erase() don’t.
std::pair <iterator, bool> insert (const value_type& value);
Insert the given value into the set unless the set already contains an equal one.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
Only on C++0x compilers:
std::pair <iterator, bool> insert (value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
iterator insert (const_iterator hint, const value_type& value);
Insert the value trying to use given hint about its position.
| Returns: | An iterator pointing to inserted or equal pre-existed element. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Currently hint is simply ignored. Strong exception safety. |
Compiler-specific
Only on C++0x compilers:
iterator insert (const_iterator hint, value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
template <typename InputIterator> void insert (InputIterator first, InputIterator last);
Insert all values in the range [first, last) into the set. Values that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert() on each value in the range, but using this method might be more efficient.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Basic exception safety: if an exception is thrown, the set contents is as before plus maybe part of contents of the range. |
Compiler-specific
This method is defined only on C++0x compilers
void insert (std::initializer_list <value_type> initializer);
Insert given values into the set. Values that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert() on each value in the list, but using this method might be more efficient.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Basic exception safety: if an exception is thrown, the set contents is as before plus maybe part of contents of the initializer list. |
Compiler-specific
This method is defined only on C++0x compilers
template <typename... Args> std::pair <iterator, bool> emplace (Args&&... args);
Insert a value_type object constructed with given arguments into the set unless the set already contains an equal one.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Special note
Purpose of this method in STL unordered_set is to avoid moving or copying the constructed object. Unfortunately, this is impossible to achieve with closed hashing, so in closed_hash_set this is not faster than simple insert(). This method exists mostly for compatibility reasons rather than adding any useful functionality.
Compiler-specific
This method is defined only on C++0x compilers
template <typename... Args> std::pair <iterator, bool> emplace (const_iterator hint, Args&&... args);
Insert a value_type object constructed with given arguments into the set, trying to use given hint about its position.
| Returns: | An iterator pointing to inserted or equal pre-existed element. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Currently hint is simply ignored. Strong exception safety. |
Special note
Purpose of this method in STL unordered_set is to avoid moving or copying the constructed object. Unfortunately, this is impossible to achieve with closed hashing, so in closed_hash_set this is not faster than simple insert(). This method exists mostly for compatibility reasons rather than adding any useful functionality.
size_type erase (const key_type& key);
Erase an element with given key.
| Returns: | Number of erased elements; might be zero. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | For a set return value is always 0 or 1. Strong exception safety. |
iterator erase (const_iterator position);
Erase the element at given position.
| Returns: | An iterator pointing to the next element or end() if there’s no next element. |
|---|---|
| Notes: | Never throws. |
iterator erase (const_iterator first, const_iterator last);
Erase a range of elements.
| Returns: | An iterator pointing to the element following the range — i.e. last. |
|---|---|
| Notes: | Never throws. |
void swap (closed_hash_set& that);
Swap contents (elements), hash function, equality predicates and maximum load factors between two sets. Allocators are not swapped.
| Throws: | Only if allocators are different: exceptions thrown by (either set’s) hash function, equality predicates or allocator. |
|---|---|
| Notes: | If allocators of the two sets are equal the function never throws and is O(1) in complexity. Otherwise strong exception safety is guaranteed and complexity is O(n) where n is the total number of buckets in the sets. Also see common note above. |
float max_load_factor () const;
| Returns: | Maximum allowed load factor of the container. |
|---|
void max_load_factor (float set_to);
Change maximum load factor of the set. If the new maximum is smaller than the current load factor, the set is rehashed to reduce the load.
| Notes: | Invalidates iterators if a rehash is trigerred. |
|---|
void rehash (size_type num_buckets);
Change bucket count to given value, if possible. Implementation can alter num_buckets as needed to have load factor small enough as well as for internal reasons. In particular, it is legal to specify zero as number of buckets: this will be replaced with the smallest number that keeps load below the allowed maximum. Finally, it sometimes makes sense (for performance) to rehash to the same number of buckets as before to “clean” the container after erasing elements.
| Notes: | Invalidates iterators. |
|---|
void reserve (size_type num_elements);
Rehash the table in such a way that it will not be rehashed anymore if size doesn’t exceed given value and no erase()-like methods are used. This is exactly identical to:
set.rehash (std::ceil (num_elements / set.max_load_factor ()));
| Notes: | Invalidates iterators. |
|---|
operator== (const closed_hash_set <...>& set1, const closed_hash_set <...>& set2);
Compare the elements of the two sets.
| Returns: | true if the sets are equal, i.e. contain the same elements. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | Result is undefined if the sets’ equality predicates are not equivalent. |
operator!= (const closed_hash_set <...>& set1, const closed_hash_set <...>& set2);
See operator== for details.
void swap (closed_hash_set <...>& set1, closed_hash_set <...>& set2);
Effect is identical to set1.swap (set2). See the method for details.
A fast unordered container mapping unique keys to arbitrary values.
Iterators are invalidated by all insert() variants, operator[], setter function max_load_factor (float) and rehash(). All member and associated non-member functions apart from the range insertion provide strong exception safety.
The class is defined in header <mct/hash-map.hpp>:
template <typename Key,
typename Mapped,
typename Hash = hash <Key>,
typename Equal = std::equal_to <Key>,
typename Allocator = std::allocator <std::pair <const Key, Mapped> >,
bool keep_hashes = false>
class closed_hash_map;
Template parameters:
Key: The map’s key type; must be assignable and copy-constructible Mapped: The type keys are mapped to; must be copy-constructible Hash: A unary function object type that hashes Key objects and returns an std::size_t hash; copy constructor must not throw, see common note above Equal: A binary function object type used to compare objects of type Key, i.e. equality predicate; copy constructor must not throw, see common note above Allocator: Allocator for type std::pair <const Key, Mapped> keep_hashes: Flag that determines whether the map keeps hashes of individual contained keys (i.e. doesn’t recompute them); see flag description above for details
Versioned
Since 1.2
If mct::supports_external_use is true for Key or Mapped (or both), the container will use a more efficient implementation.
key_type: The map’s key type mapped_type: The type keys are mapped to value_type: The map’s value type; always std::pair <const key_type, mapped_type> hasher: The type of the hash function object key_equal: The type of equality function object allocator_type: The type of allocator object iterator: A bidirectional iterator type capable of navigating the map; note that the iterator is not mutable because first member of the pair it points to cannot be modified const_iterator: A constant bidirectional iterator; similar to iterator except that values it points to are immutable pointer: const_pointer: reference: const_reference: size_type: difference_type: Standard container type members; mostly interesting for meta-programming needs
closed_hash_map (size_type num_buckets = 0,
const hasher& hash = hasher (),
const key_equal& equal = key_equal (),
const allocator_type& allocator = allocator_type ());
Create an empty map.
| Throws: | Exceptions thrown by the allocator. |
|---|
closed_hash_map (const closed_hash_map& that);
Create a new map as a copy of another. Copies contained elements, hash function object, equality predicate, allocator and maximum load factor of the other container.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
Compiler-specific
Only on C++0x compilers:
closed_hash_map (closed_hash_map&& that);
The same as copy constructor, except that the second map is left in undefined state. Unlike the copy constructor, this never throws.
closed_hash_map (const closed_hash_map& that, const allocator_type& allocator);
Similar to the copy constructor, but uses explicitly specified allocator instead of copying it from that container.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
template <typename InputIterator>
closed_hash_map (InputIterator first,
InputIterator last,
size_type num_buckets = 0,
const hasher& hash = hasher (),
const key_equal& equal = key_equal (),
const allocator_type& allocator = allocator_type ());
Create a map containing all elements in the range [first, last). Elements with duplicate keys in the range are effectively ignored: only the first is inserted into the new map.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
Compiler-specific
This constructor is defined only on C++0x compilers
closed_hash_map (std::initializer_list <value_type> initializer,
size_type num_buckets = 0,
const hasher& hash = hasher (),
const key_equal& equal = key_equal (),
const allocator_type& allocator = allocator_type ());
Create a map containing all elements from initializer list. Elements with duplicate keys are effectively ignored.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
closed_hash_map& operator= (const closed_hash_map& that);
Erase current map contents and replace it with contents of another map. This replaces hash function, equality predicate and maximum load factor, but not the allocator.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. Also see common note above. |
|---|
Compiler-specific
Only on C++0x compilers:
closed_hash_map& operator= (closed_hash_map&& that);
The same as copy assignment, except that the second map is left in undefined state. If allocators of the two maps are equal this version doesn’t throw.
Compiler-specific
This assignment is defined only on C++0x compilers
closed_hash_map& operator= (std::initializer_list <value_type> initializer);
Erase current map contents and replace it with values from the initializers. Elements with duplicate keys in the list are effectively ignored.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
Destroy all contained elements, free memory and destroy the map itself.
size_type bucket_count () const;
| Returns: | Current number of bucket used by the container. |
|---|
size_type max_bucket_count () const;
| Returns: | The largest number of buckets this map could ever have. |
|---|
iterator begin (); const_iterator begin () const;
| Returns: | An iterator pointing to the first element in the map, or past-the-end iterator if the map is empty. |
|---|---|
| Notes: | closed_hash_map doesn’t give any guarantees about iteration order. |
const_iterator cbegin () const;
| Returns: | A constant iterator pointing to the first element in the map, or past-the-end iterator if the map is empty. |
|---|---|
| Notes: | closed_hash_map doesn’t give any guarantees about iteration order. |
iterator find (const key_type& key); const_iterator find (const key_type& key) const;
Find an element with given key.
| Returns: | An iterator pointing to matching element or end() if there’s no such element. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
size_type count (const key_type& key) const;
| Returns: | Number of elements with given key. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | For a map return value is always 0 or 1. |
std::pair <iterator, iterator> equal_range (const key_type& key); std::pair <const_iterator, const_iterator> equal_range (const key_type& key) const;
Determine the range consisting of all elements with given key.
| Returns: | A pair P such that [P.first, P.second) is the range consisting all elements with given key. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | For a map such a range always contains 0 or 1 element. |
mapped_type& operator[] (const key_type& key);
Find the object given key is mapped to, or else insert a new association with default-constructed mapped_type.
| Returns: | A reference to a pre-existed or newly inserted object associated with key. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators if a new association is created. Strong exception safety. |
mapped_type& at (const key_type& key); const mapped_type& at (const key_type& key) const;
Find the element with given key and assert its presence.
| Returns: | A reference to the pre-existed object associated with key. |
|---|---|
| Throws: | std::out_of_range if there is no element with given key (the assertion fails). Additionally, exceptions thrown by the hash function or equality predicate. |
Note that all insert() variants invalidate iterators while all erase() don’t.
std::pair <iterator, bool> insert (const value_type& value);
Insert the given value into the map unless the map already contains one with equal key.
| Returns: | A pair of iterator pointing to inserted (or pre-existed with equal key) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
Only on C++0x compilers:
std::pair <iterator, bool> insert (value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
iterator insert (const_iterator hint, const value_type& value);
Insert the value trying to use given hint about its position.
| Returns: | An iterator pointing to inserted or pre-existed element with equal key. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Currently hint is simply ignored. Strong exception safety. |
Compiler-specific
Only on C++0x compilers:
iterator insert (const_iterator hint, value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
template <typename InputIterator> void insert (InputIterator first, InputIterator last);
Insert all values in the range [first, last) into the map. Values with keys that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert() on each value in the range, but using this method might be more efficient.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Basic exception safety: if an exception is thrown, the map contents is as before plus maybe part of contents of the range. |
Compiler-specific
This method is defined only on C++0x compilers
void insert (std::initializer_list <value_type> initializer);
Insert given values into the map. Values with keys that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert() on each value in the list, but using this method might be more efficient.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Basic exception safety: if an exception is thrown, the map contents is as before plus maybe part of contents of the initializer list. |
Compiler-specific
This method is defined only on C++0x compilers
template <typename... Args> std::pair <iterator, bool> emplace (Args&&... args);
Insert a value_type object constructed with given arguments into the map unless the map already contains one with equal key.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Special note
Purpose of this method in STL unordered_map is to avoid moving or copying the constructed object. Unfortunately, this is impossible to achieve with closed hashing, so in closed_hash_map this is not faster than simple insert(). This method exists mostly for compatibility reasons rather than adding any useful functionality.
Compiler-specific
This method is defined only on C++0x compilers
template <typename... Args> std::pair <iterator, bool> emplace (const_iterator hint, Args&&... args);
Insert a value_type object constructed with given arguments into the map, trying to use given hint about its position.
| Returns: | An iterator pointing to inserted or equal pre-existed element. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Currently hint is simply ignored. Strong exception safety. |
Special note
Purpose of this method in STL unordered_map is to avoid moving or copying the constructed object. Unfortunately, this is impossible to achieve with closed hashing, so in closed_hash_map this is not faster than simple insert(). This method exists mostly for compatibility reasons rather than adding any useful functionality.
size_type erase (const key_type& key);
Erase an element with given key.
| Returns: | Number of erased elements; might be zero. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | For a map return value is always 0 or 1. Strong exception safety. |
iterator erase (const_iterator position);
Erase the element at given position.
| Returns: | An iterator pointing to the next element or end() if there’s no next element. |
|---|---|
| Notes: | Never throws. |
iterator erase (const_iterator first, const_iterator last);
Erase a range of elements.
| Returns: | An iterator pointing to the element following the range — i.e. last. |
|---|---|
| Notes: | Never throws. |
void swap (closed_hash_map& that);
Swap contents (elements), hash function, equality predicates and maximum load factors between two maps. Allocators are not swapped.
| Throws: | Only if allocators are different: exceptions thrown by (either map’s) hash function, equality predicates or allocator. |
|---|---|
| Notes: | If allocators of the two map are equal the function never throws and is O(1) in complexity. Otherwise strong exception safety is guaranteed and complexity is O(n) where n is the total number of buckets in the maps. Also see common note above. |
float max_load_factor () const;
| Returns: | Maximum allowed load factor of the container. |
|---|
void max_load_factor (float set_to);
Change maximum load factor of the map. If the new maximum is smaller than the current load factor, the map is rehashed to reduce the load.
| Notes: | Invalidates iterators if a rehash is trigerred. |
|---|
void rehash (size_type num_buckets);
Change bucket count to given value, if possible. Implementation can alter num_buckets as needed to have load factor small enough as well as for internal reasons. In particular, it is legal to specify zero as number of buckets: this will be replaced with the smallest number that keeps load below the allowed maximum. Finally, it sometimes makes sense (for performance) to rehash to the same number of buckets as before to “clean” the container after erasing elements.
| Notes: | Invalidates iterators. |
|---|
void reserve (size_type num_elements);
Rehash the table in such a way that it will not be rehashed anymore if size doesn’t exceed given value and no erase()-like methods are used. This is exactly identical to:
map.rehash (std::ceil (num_elements / map.max_load_factor ()));
| Notes: | Invalidates iterators. |
|---|
operator== (const closed_hash_map <...>& map1, const closed_hash_map <...>& map2);
Compare the elements of the two maps. Second element components (mapped_type) are compared with operator==, while the first (key_type) — with the map equality predicate.
| Returns: | true if the maps are equal, i.e. contain the same elements. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | Result is undefined if the maps’ equality predicates are not equivalent. |
operator!= (const closed_hash_map <...>& map1, const closed_hash_map <...>& map2);
See operator== for details.
void swap (closed_hash_map <...>& map1, closed_hash_map <...>& map2);
Effect is identical to map1.swap (map2). See the method for details.
A fast unordered container with unique values and stable iteration order.
Iterators are invalidated by all insert() variants, setter function max_load_factor (float) and rehash(). All member and associated non-member functions provide strong exception safety.
Note that linked_hash_set is not a sequence despite having many methods of the latter.
The class is defined in header <mct/hash-set.hpp>:
template <typename Value,
typename Hash = hash <Value>,
typename Equal = std::equal_to <Value>,
typename Allocator = std::allocator <Value>,
bool keep_hashes = false>
class linked_hash_set;
Template parameters:
Value: The set’s value type; must be assignable and copy-constructible Hash: A unary function object type that hashes Value objects and returns an std::size_t hash; copy constructor must not throw, see common note above Equal: A binary function object type used to compare objects of type Value, i.e. equality predicate; copy constructor must not throw, see common note above Allocator: Allocator for type Value keep_hashes: Flag that determines whether the set keeps hashes of individual contained values (i.e. doesn’t recompute them); see flag description above for details
key_type: The set’s value type (i.e. the same as value_type) value_type: The set’s value type hasher: The type of the hash function object key_equal: The type of equality function object allocator_type: The type of allocator object iterator: A bidirectional iterator type capable of navigating the set; value it points to cannot be modified, so this behaves just like const_iterator const_iterator: A constant bidirectional iterator; for sets this behaves exactly as iterator reverse_iterator: A bidirectional iterator type that can be used to iterate the set backwards; value it points to cannot be modified. const_reverse_iterator: A constant bidirectional iterator type that can be used to iterate the set backwards. pointer: const_pointer: reference: const_reference: size_type: difference_type: Standard container type members; mostly interesting for meta-programming needs
linked_hash_set (size_type num_buckets = 0,
const hasher& hash = hasher (),
const key_equal& equal = key_equal (),
const allocator_type& allocator = allocator_type ());
Create an empty set.
| Throws: | Exceptions thrown by the allocator. |
|---|
linked_hash_set (const linked_hash_set& that);
Create a new set as a copy of another. Copies contained elements, hash function object, equality predicate, allocator and maximum load factor of the other container. Iteration order in the copy is the same as in that.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
Compiler-specific
Only on C++0x compilers:
linked_hash_set (linked_hash_set&& that);
The same as copy constructor, except that the second set is left in undefined state. Unlike the copy constructor, this never throws.
linked_hash_set (const linked_hash_set& that, const allocator_type& allocator);
Similar to the copy constructor, but uses explicitly specified allocator instead of copying it from that container.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
template <typename InputIterator>
linked_hash_set (InputIterator first,
InputIterator last,
size_type num_buckets = 0,
const hasher& hash = hasher (),
const key_equal& equal = key_equal (),
const allocator_type& allocator = allocator_type ());
Create a set containing all elements in the range [first, last). Duplicate elements in the range are effectively ignored. Iteration order of the set matches [first, last) except for duplicate elements: as only the first copy is added to the set, it is also the only visited during iteration.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
Compiler-specific
This constructor is defined only on C++0x compilers
linked_hash_set (std::initializer_list <value_type> initializer,
size_type num_buckets = 0,
const hasher& hash = hasher (),
const key_equal& equal = key_equal (),
const allocator_type& allocator = allocator_type ());
Create a set containing all elements from initializer list. Duplicate elements are effectively ignored. Iteration order of other elements in the new set is the same as in the list.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
linked_hash_set& operator= (const linked_hash_set& that);
Erase current set contents and replace it with contents of another set. This replaces hash function, equality predicate and maximum load factor, but not the allocator. After assignment, iteration order of the two sets is the same.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. Also see common note above. |
|---|
Compiler-specific
Only on C++0x compilers:
linked_hash_set& operator= (linked_hash_set&& that);
The same as copy assignment, except that the second set is left in undefined state. If allocators of the two sets are equal this version doesn’t throw.
Compiler-specific
This assignment is defined only on C++0x compilers
linked_hash_set& operator= (std::initializer_list <value_type> initializer);
Erase current set contents and replace it with values from the initializers. Duplicate elements in the list are effectively ignored. Iteration order of other elements matches their relative order in the initialization list.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
Destroy all contained elements, free memory and destroy the set itself.
size_type bucket_count () const;
| Returns: | Current number of bucket used by the container. |
|---|
size_type max_bucket_count () const;
| Returns: | The largest number of buckets this set could ever have. |
|---|
iterator begin (); const_iterator begin () const;
| Returns: | An iterator pointing to the first element in the set, or past-the-end iterator if the set is empty. |
|---|
const_iterator cbegin () const;
| Returns: | A constant iterator pointing to the first element in the set, or past-the-end iterator if the set is empty. |
|---|
reverse_iterator rbegin (); const_reverse_iterator rbegin () const;
| Returns: | A reverse iterator pointing to the first element in the reversed set, or past-the-end iterator if the set is empty. |
|---|
const_reverse_iterator crbegin () const;
| Returns: | A constant reverse iterator pointing to the first element in the reversed set, or past-the-end iterator if the set is empty. |
|---|
reverse_iterator rend (); const_reverse_iterator rend () const;
| Returns: | Past-the-end reverse iterator for the set. |
|---|
reference front (); const_reference front () const;
| Returns: | The first element in set’s iteration order. |
|---|---|
| Notes: | The set must not be empty. |
reference back (); const_reference back () const;
| Returns: | The last element in set’s iteration order. |
|---|---|
| Notes: | The set must not be empty. |
iterator find (const key_type& key); const_iterator find (const key_type& key) const;
Find an element with given key.
| Returns: | An iterator pointing to matching element or end() if there’s no such element. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
size_type count (const key_type& key) const;
| Returns: | Number of elements with given key. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | For a set return value is always 0 or 1. |
std::pair <iterator, iterator> equal_range (const key_type& key); std::pair <const_iterator, const_iterator> equal_range (const key_type& key) const;
Determine the range consisting of all elements with given key.
| Returns: | A pair P such that [P.first, P.second) is the range consisting all elements with given key. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | For a set such a range always contains 0 or 1 element. |
Note that all insert() variants (as well as similar push_front() and push_back()) invalidate iterators while all erase() (as well as similar pop_front() and pop_back()) don’t.
std::pair <iterator, bool> push_front (const value_type& value);
Insert the given value into the set unless the set already contains an equal one. If the value is inserted, it will be the first in set’s iteration order.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
Only on C++0x compilers:
std::pair <iterator, bool> push_front (value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
std::pair <iterator, bool> push_back (const value_type& value);
Exactly the same as insert (value).
Compiler-specific
Only on C++0x compilers:
std::pair <iterator, bool> push_back (value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
std::pair <iterator, bool> insert (const value_type& value);
Insert the given value into the set unless the set already contains an equal one. If the value is inserted, it will be the last in set’s iteration order.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
Only on C++0x compilers:
std::pair <iterator, bool> insert (value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
std::pair <iterator, bool> insert (const_iterator before, const value_type& value);
Insert the given value into the set unless the set already contains an equal one. If the value is inserted, it will immediately precede element pointed to by the given iterator in iteration order.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
Only on C++0x compilers:
std::pair <iterator, bool> insert (const_iterator before, value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
Special note
This method has the same arguments as hint-insertion in closed_hash_set, but a different return type and arguably different meaning. This was deemed acceptable, since hint-insertion is hardly useful and is provided mainly for compatibility with unordered_set. Since linked_hash_set is not a direct analogue of that class, compatibility is not a major issue here.
template <typename InputIterator> void insert (InputIterator first, InputIterator last);
Insert all values in the range [first, last) into the set. Values that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert() on each value in the range, but using this method might be more efficient. Inserted elements in the range will be the last in set’s iteration order; their relative precedence will be the same as in [first, last) range.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Strong exception safety. |
template <typename InputIterator> void insert (const_iterator before, InputIterator first, InputIterator last);
Insert all values in the range [first, last) into the set. Values that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert() on each value in the range, but using this method might be more efficient. Inserted elements in the range will immediately precede element pointed to by the given iterator in iteration order; their relative precedence will be the same as in [first, last) range.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
This method is defined only on C++0x compilers
void insert (std::initializer_list <value_type> initializer);
Insert given values into the set. Values that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert() on each value in the list, but using this method might be more efficient. Inserted elements will be the last in set’s iteration order; their relative precedence will be the same as in the list.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
This method is defined only on C++0x compilers
void insert (const_iterator before, std::initializer_list <value_type> initializer);
Insert given values into the set. Values that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert() on each value in the list, but using this method might be more efficient. Inserted elements will immediately precede element pointed to by the given iterator in iteration order; their relative precedence will be the same as in the list.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
This method is defined only on C++0x compilers
template <typename... Args> std::pair <iterator, bool> emplace (Args&&... args);
Insert a value_type object constructed with given arguments into the set unless the set already contains an equal one.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Special note
Purpose of this method in STL unordered_set is to avoid moving or copying the constructed object. Unfortunately, this is impossible to achieve with closed hashing, so in linked_hash_set this is not faster than simple insert(). This method exists mostly for compatibility reasons rather than adding any useful functionality.
Compiler-specific
This method is defined only on C++0x compilers
template <typename... Args> std::pair <iterator, bool> emplace_before (const_iterator before, Args&&... args);
Insert a value_type object constructed with given arguments into the set unless the set already contains an equal one. If the object is inserted, it will immediately precede element pointed to by the given iterator in iteration order.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Special note
Purpose of similar methods in STL unordered_set is to avoid moving or copying the constructed object. Unfortunately, this is impossible to achieve with closed hashing, so in linked_hash_set this is not faster than simple insert(). This method exists mostly for compatibility reasons rather than adding any useful functionality.
Compiler-specific
This method is defined only on C++0x compilers
template <typename... Args> std::pair <iterator, bool> emplace (const_iterator hint, Args&&... args);
Insert a value_type object constructed with given arguments into the set, trying to use given hint about its position.
| Returns: | An iterator pointing to inserted or equal pre-existed element. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Currently hint is simply ignored. Strong exception safety. |
Special note
Purpose of this method in STL unordered_set is to avoid moving or copying the constructed object. Unfortunately, this is impossible to achieve with closed hashing, so in linked_hash_set this is not faster than simple insert(). This method exists mostly for compatibility reasons rather than adding any useful functionality.
void pop_front ();
Erase the first element in the set’s iteration order.
| Notes: | The set must not be empty. Never throws. |
|---|
void pop_back ();
Erase the last element in the set’s iteration order.
| Notes: | The set must not be empty. Never throws. |
|---|
size_type erase (const key_type& key);
Erase an element with given key.
| Returns: | Number of erased elements; might be zero. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | For a set return value is always 0 or 1. Strong exception safety. |
iterator erase (const_iterator position);
Erase the element at given position.
| Returns: | An iterator pointing to the next element or end() if there’s no next element. |
|---|---|
| Notes: | Never throws. |
iterator erase (const_iterator first, const_iterator last);
Erase a range of elements.
| Returns: | An iterator pointing to the element following the range — i.e. last. |
|---|---|
| Notes: | Never throws. |
void swap (linked_hash_set& that);
Swap contents (elements), hash function, equality predicates and maximum load factors between two sets. Allocators are not swapped. Iteration orders are swapped along with elements: after swapping, this set will yield the same sequence of elements as that set did before, and vice versa.
| Throws: | Only if allocators are different: exceptions thrown by (either set’s) hash function, equality predicates or allocator. |
|---|---|
| Notes: | If allocators of the two sets are equal the function never throws and is O(1) in complexity. Otherwise strong exception safety is guaranteed and complexity is O(n) where n is the total number of buckets in the sets. Also see common note above. |
Note that since container is a set, below operations don’t change its equality. I.e. the container after the operation will always be equal (as defined by operator==) to itself before the operation.
These functions never invalidate iterators or throw anything.
void relink (const_iterator before, iterator element);
Make given element (second argument) directly precede before (first argument) in the container’s iteration order.
| Notes: | It is allowed to pass equal iterators, in which case nothing will be done (an element cannot precede itself). |
|---|
void reverse ();
Reverse the order in which container’s elements are iterated. I.e. formerly first element becomes the last, second element becomes second to last and so on.
float max_load_factor () const;
| Returns: | Maximum allowed load factor of the container. |
|---|
void max_load_factor (float set_to);
Change maximum load factor of the set. If the new maximum is smaller than the current load factor, the set is rehashed to reduce the load.
| Notes: | Invalidates iterators if a rehash is trigerred. |
|---|
void rehash (size_type num_buckets);
Change bucket count to given value, if possible. Implementation can alter num_buckets as needed to have load factor small enough as well as for internal reasons. In particular, it is legal to specify zero as number of buckets: this will be replaced with the smallest number that keeps load below the allowed maximum. Finally, it sometimes makes sense (for performance) to rehash to the same number of buckets as before to “clean” the container after erasing elements.
| Notes: | Invalidates iterators. |
|---|
void reserve (size_type num_elements);
Rehash the table in such a way that it will not be rehashed anymore if size doesn’t exceed given value and no erase()-like methods are used. This is exactly identical to:
set.rehash (std::ceil (num_elements / set.max_load_factor ()));
| Notes: | Invalidates iterators. |
|---|
operator== (const linked_hash_set <...>& set1, const linked_hash_set <...>& set2);
Compare the elements of the two sets. Remember that despite being linked, containers are still sets, i.e. iteration order is irrelevant to container equality.
| Returns: | true if the sets are equal, i.e. contain the same elements. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | Result does not depend on either sets’ iteration order. It is undefined if the sets’ equality predicates are not equivalent. |
operator!= (const linked_hash_set <...>& set1, const linked_hash_set <...>& set2);
See operator== for details.
void swap (linked_hash_set <...>& set1, linked_hash_set <...>& set2);
Effect is identical to set1.swap (set2). See the method for details.
A fast unordered container mapping unique keys to arbitrary values and providing stable iteration order.
Iterators are invalidated by all insert() variants, operator[], setter function max_load_factor (float) and rehash(). All member and associated non-member functions provide strong exception safety.
Note that linked_hash_map is not a sequence despite having many methods of the latter.
The class is defined in header <mct/hash-map.hpp>:
template <typename Key,
typename Mapped,
typename Hash = hash <Key>,
typename Equal = std::equal_to <Key>,
typename Allocator = std::allocator <std::pair <const Key, Mapped> >,
bool keep_hashes = false>
class linked_hash_map;
Template parameters:
Key: The map’s key type; must be assignable and copy-constructible Mapped: The type keys are mapped to; must be copy-constructible Hash: A unary function object type that hashes Key objects and returns an std::size_t hash; copy constructor must not throw, see common note above Equal: A binary function object type used to compare objects of type Key, i.e. equality predicate; copy constructor must not throw, see common note above Allocator: Allocator for type std::pair <const Key, Mapped> keep_hashes: Flag that determines whether the map keeps hashes of individual contained keys (i.e. doesn’t recompute them); see flag description above for details
key_type: The map’s key type mapped_type: The type keys are mapped to value_type: The map’s value type; always std::pair <const key_type, mapped_type> hasher: The type of the hash function object key_equal: The type of equality function object allocator_type: The type of allocator object iterator: A bidirectional iterator type capable of navigating the map; note that the iterator is not mutable because first member of the pair it points to cannot be modified const_iterator: A constant bidirectional iterator; similar to iterator except that values it points to are immutable reverse_iterator: A bidirectional iterator type that can be used to iterate the map backwards; first member of the pair it points to cannot be modified. const_reverse_iterator: A constant bidirectional iterator type that can be used to iterate the set backwards. pointer: const_pointer: reference: const_reference: size_type: difference_type: Standard container type members; mostly interesting for meta-programming needs
linked_hash_map (size_type num_buckets = 0,
const hasher& hash = hasher (),
const key_equal& equal = key_equal (),
const allocator_type& allocator = allocator_type ());
Create an empty map.
| Throws: | Exceptions thrown by the allocator. |
|---|
linked_hash_map (const linked_hash_map& that);
Create a new map as a copy of another. Copies contained elements, hash function object, equality predicate, allocator and maximum load factor of the other container. Iteration order in the copy is the same as in that.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
Compiler-specific
Only on C++0x compilers:
linked_hash_map (linked_hash_map&& that);
The same as copy constructor, except that the second map is left in undefined state. Unlike the copy constructor, this never throws.
linked_hash_map (const linked_hash_map& that, const allocator_type& allocator);
Similar to the copy constructor, but uses explicitly specified allocator instead of copying it from that container.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
template <typename InputIterator>
linked_hash_map (InputIterator first,
InputIterator last,
size_type num_buckets = 0,
const hasher& hash = hasher (),
const key_equal& equal = key_equal (),
const allocator_type& allocator = allocator_type ());
Create a map containing all elements in the range [first, last). Elements with duplicate keys in the range are effectively ignored: only the first is inserted into the new map. Iteration order of the map matches [first, last) except for elements with duplicate keys: as only the first copy is added to the map, it is also the only visited during iteration.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
Compiler-specific
This constructor is defined only on C++0x compilers
linked_hash_map (std::initializer_list <value_type> initializer,
size_type num_buckets = 0,
const hasher& hash = hasher (),
const key_equal& equal = key_equal (),
const allocator_type& allocator = allocator_type ());
Create a map containing all elements from initializer list. Elements with duplicate keys are effectively ignored. Iteration order of other elements in the new map is the same as in the list.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
linked_hash_map& operator= (const linked_hash_map& that);
Erase current map contents and replace it with contents of another map. This replaces hash function, equality predicate and maximum load factor, but not the allocator. After assignment, iteration order of the two maps is the same.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. Also see common note above. |
|---|
Compiler-specific
Only on C++0x compilers:
linked_hash_map& operator= (linked_hash_map&& that);
The same as copy assignment, except that the second map is left in undefined state. If allocators of the two maps are equal this version doesn’t throw.
Compiler-specific
This assignment is defined only on C++0x compilers
linked_hash_map& operator= (std::initializer_list <value_type> initializer);
Erase current map contents and replace it with values from the initializers. Elements with duplicate keys in the list are effectively ignored. Iteration order of other elements matches their relative order in the initialization list.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
Destroy all contained elements, free memory and destroy the map itself.
size_type bucket_count () const;
| Returns: | Current number of bucket used by the container. |
|---|
size_type max_bucket_count () const;
| Returns: | The largest number of buckets this map could ever have. |
|---|
iterator begin (); const_iterator begin () const;
| Returns: | An iterator pointing to the first element in the map, or past-the-end iterator if the map is empty. |
|---|
const_iterator cbegin () const;
| Returns: | A constant iterator pointing to the first element in the map, or past-the-end iterator if the map is empty. |
|---|
reverse_iterator rbegin (); const_reverse_iterator rbegin () const;
| Returns: | A reverse iterator pointing to the first element in the reversed map, or past-the-end iterator if the map is empty. |
|---|
const_reverse_iterator crbegin () const;
| Returns: | A constant reverse iterator pointing to the first element in the reversed map, or past-the-end iterator if the map is empty. |
|---|
reverse_iterator rend (); const_reverse_iterator rend () const;
| Returns: | Past-the-end reverse iterator for the map. |
|---|
reference front (); const_reference front () const;
| Returns: | The first element in map’s iteration order. |
|---|---|
| Notes: | The map must not be empty. |
reference back (); const_reference back () const;
| Returns: | The last element in map’s iteration order. |
|---|---|
| Notes: | The map must not be empty. |
iterator find (const key_type& key); const_iterator find (const key_type& key) const;
Find an element with given key.
| Returns: | An iterator pointing to matching element or end() if there’s no such element. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
size_type count (const key_type& key) const;
| Returns: | Number of elements with given key. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | For a map return value is always 0 or 1. |
std::pair <iterator, iterator> equal_range (const key_type& key); std::pair <const_iterator, const_iterator> equal_range (const key_type& key) const;
Determine the range consisting of all elements with given key.
| Returns: | A pair P such that [P.first, P.second) is the range consisting all elements with given key. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | For a map such a range always contains 0 or 1 element. |
mapped_type& operator[] (const key_type& key);
Find the object given key is mapped to, or else insert a new association with default-constructed mapped_type. If insertion happens, new element will be the last in the map’s iteration order.
| Returns: | A reference to a pre-existed or newly inserted object associated with key. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators if a new association is created. Strong exception safety. |
mapped_type& at (const key_type& key); const mapped_type& at (const key_type& key) const;
Find the element with given key and assert its presence.
| Returns: | A reference to the pre-existed object associated with key. |
|---|---|
| Throws: | std::out_of_range if there is no element with given key (the assertion fails). Additionally, exceptions thrown by the hash function or equality predicate. |
Note that all insert() variants (as well as similar push_front() and push_back()) invalidate iterators while all erase() (as well as similar pop_front() and pop_back()) don’t.
std::pair <iterator, bool> push_front (const value_type& value);
Insert the given value into the map unless the map already contains one with equal key. If the value is inserted, it will be the first in map’s iteration order.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
Only on C++0x compilers:
std::pair <iterator, bool> push_front (value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
std::pair <iterator, bool> push_back (const value_type& value);
Exactly the same as insert (value).
Compiler-specific
Only on C++0x compilers:
std::pair <iterator, bool> push_back (value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
std::pair <iterator, bool> insert (const value_type& value);
Insert the given value into the map unless the map already contains one with equal key. If the value is inserted, it will be the last in map’s iteration order.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
Only on C++0x compilers:
std::pair <iterator, bool> insert (value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
std::pair <iterator, bool> insert (const_iterator before, const value_type& value);
Insert the given value into the map unless the map already contains one with equal key. If the value is inserted, it will immediately precede element pointed to by the given iterator in iteration order.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
Only on C++0x compilers:
std::pair <iterator, bool> insert (const_iterator before, value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
Special note
This method has the same arguments as hint-insertion in closed_hash_map, but a different return type and arguably different meaning. This was deemed acceptable, since hint-insertion is hardly useful and is provided mainly for compatibility with unordered_map. Since linked_hash_map is not a direct analogue of that class, compatibility is not a major issue here.
template <typename InputIterator> void insert (InputIterator first, InputIterator last);
Insert all values in the range [first, last) into the map. Values with keys that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert() on each value in the range, but using this method might be more efficient. Inserted elements in the range will be the last in map’s iteration order; their relative precedence will be the same as in [first, last) range.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Strong exception safety. |
template <typename InputIterator> void insert (const_iterator before, InputIterator first, InputIterator last);
Insert all values in the range [first, last) into the map. Values with keys that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert() on each value in the range, but using this method might be more efficient. Inserted elements in the range will immediately precede element pointed to by the given iterator in iteration order; their relative precedence will be the same as in [first, last) range.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
This method is defined only on C++0x compilers
void insert (std::initializer_list <value_type> initializer);
Insert given values into the map. Values with keys that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert() on each value in the list, but using this method might be more efficient. Inserted elements will be the last in map’s iteration order; their relative precedence will be the same as in the list.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
This method is defined only on C++0x compilers
void insert (const_iterator before, std::initializer_list <value_type> initializer);
Insert given values into the map. Values with keys that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert() on each value in the list, but using this method might be more efficient. Inserted elements will immediately precede element pointed to by the given iterator in iteration order; their relative precedence will be the same as in the list.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
This method is defined only on C++0x compilers
template <typename... Args> std::pair <iterator, bool> emplace (Args&&... args);
Insert a value_type object constructed with given arguments into the map unless the map already contains one with equal key.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Special note
Purpose of this method in STL unordered_map is to avoid moving or copying the constructed object. Unfortunately, this is impossible to achieve with closed hashing, so in linked_hash_map this is not faster than simple insert(). This method exists mostly for compatibility reasons rather than adding any useful functionality.
Compiler-specific
This method is defined only on C++0x compilers
template <typename... Args> std::pair <iterator, bool> emplace_before (const_iterator before, Args&&... args);
Insert a value_type object constructed with given arguments into the map unless the map already contains one with equal key. If the object is inserted, it will immediately precede element pointed to by the given iterator in iteration order.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Special note
Purpose of similar methods in STL unordered_map is to avoid moving or copying the constructed object. Unfortunately, this is impossible to achieve with closed hashing, so in linked_hash_map this is not faster than simple insert(). This method exists mostly for compatibility reasons rather than adding any useful functionality.
Compiler-specific
This method is defined only on C++0x compilers
template <typename... Args> std::pair <iterator, bool> emplace (const_iterator hint, Args&&... args);
Insert a value_type object constructed with given arguments into the map, trying to use given hint about its position.
| Returns: | An iterator pointing to inserted or equal pre-existed element. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Currently hint is simply ignored. Strong exception safety. |
Special note
Purpose of this method in STL unordered_map is to avoid moving or copying the constructed object. Unfortunately, this is impossible to achieve with closed hashing, so in linked_hash_map this is not faster than simple insert(). This method exists mostly for compatibility reasons rather than adding any useful functionality.
void pop_front ();
Erase the first element in the map’s iteration order.
| Notes: | The map must not be empty. Never throws. |
|---|
void pop_back ();
Erase the last element in the map’s iteration order.
| Notes: | The map must not be empty. Never throws. |
|---|
size_type erase (const key_type& key);
Erase an element with given key.
| Returns: | Number of erased elements; might be zero. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | For a map return value is always 0 or 1. Strong exception safety. |
iterator erase (const_iterator position);
Erase the element at given position.
| Returns: | An iterator pointing to the next element or end() if there’s no next element. |
|---|---|
| Notes: | Never throws. |
iterator erase (const_iterator first, const_iterator last);
Erase a range of elements.
| Returns: | An iterator pointing to the element following the range — i.e. last. |
|---|---|
| Notes: | Never throws. |
void swap (linked_hash_map& that);
Swap contents (elements), hash function, equality predicates and maximum load factors between two maps. Allocators are not swapped. Iteration orders are swapped along with elements: after swapping, this map will yield the same sequence of elements as that map did before, and vice versa.
| Throws: | Only if allocators are different: exceptions thrown by (either map’s) hash function, equality predicates or allocator. |
|---|---|
| Notes: | If allocators of the two maps are equal the function never throws and is O(1) in complexity. Otherwise strong exception safety is guaranteed and complexity is O(n) where n is the total number of buckets in the maps. Also see common note above. |
Note that since container is a map, below operations don’t change its equality. I.e. the container after the operation will always be equal (as defined by operator==) to itself before the operation.
These functions never invalidate iterators or throw anything.
void relink (const_iterator before, iterator element);
Make given element (second argument) directly precede before (first argument) in the container’s iteration order.
| Notes: | It is allowed to pass equal iterators, in which case nothing will be done (an element cannot precede itself). |
|---|
void reverse ();
Reverse the order in which container’s elements are iterated. I.e. formerly first element becomes the last, second element becomes second to last and so on.
float max_load_factor () const;
| Returns: | Maximum allowed load factor of the container. |
|---|
void max_load_factor (float set_to);
Change maximum load factor of the map. If the new maximum is smaller than the current load factor, the map is rehashed to reduce the load.
| Notes: | Invalidates iterators if a rehash is trigerred. |
|---|
void rehash (size_type num_buckets);
Change bucket count to given value, if possible. Implementation can alter num_buckets as needed to have load factor small enough as well as for internal reasons. In particular, it is legal to specify zero as number of buckets: this will be replaced with the smallest number that keeps load below the allowed maximum. Finally, it sometimes makes sense (for performance) to rehash to the same number of buckets as before to “clean” the container after erasing elements.
| Notes: | Invalidates iterators. |
|---|
void reserve (size_type num_elements);
Rehash the table in such a way that it will not be rehashed anymore if size doesn’t exceed given value and no erase()-like methods are used. This is exactly identical to:
map.rehash (std::ceil (num_elements / map.max_load_factor ()));
| Notes: | Invalidates iterators. |
|---|
operator== (const linked_hash_map <...>& map1, const linked_hash_map <...>& map2);
Compare the elements of the two maps. Second element components (mapped_type) are compared with operator==, while the first (key_type) — with the map equality predicate. Remember that despite being linked, containers are still maps, i.e. iteration order is irrelevant to container equality.
| Returns: | true if the maps are equal, i.e. contain the same elements. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | Result does not depend on either maps’ iteration order. It is undefined if the maps’ equality predicates are not equivalent. |
operator!= (const linked_hash_map <...>& map1, const linked_hash_map <...>& map2);
See operator== for details.
void swap (linked_hash_map <...>& map1, linked_hash_map <...>& map2);
Effect is identical to map1.swap (map2). See the method for details.
Versioned
Since 1.2
A fast unordered container with unique values and stable iteration order.
The class is defined in header <mct/hash-set.hpp>:
template <typename Value,
typename Hash = hash <Value>,
typename Equal = std::equal_to <Value>,
typename Allocator = std::allocator <Value>,
bool keep_hashes = false>
class forward_hash_set;
Template parameters:
Value: The set’s value type; must be assignable and copy-constructible Hash: A unary function object type that hashes Value objects and returns an std::size_t hash; copy constructor must not throw, see common note above Equal: A binary function object type used to compare objects of type Value, i.e. equality predicate; copy constructor must not throw, see common note above Allocator: Allocator for type Value keep_hashes: Flag that determines whether the set keeps hashes of individual contained values (i.e. doesn’t recompute them); see flag description above for details
key_type: The set’s value type (i.e. the same as value_type) value_type: The set’s value type hasher: The type of the hash function object key_equal: The type of equality function object allocator_type: The type of allocator object iterator: A forward iterator type capable of navigating the set; value it points to cannot be modified, so this behaves just like const_iterator const_iterator: A constant forward iterator; for sets this behaves exactly as iterator pointer: const_pointer: reference: const_reference: size_type: difference_type: Standard container type members; mostly interesting for meta-programming needs
forward_hash_set (size_type num_buckets = 0,
const hasher& hash = hasher (),
const key_equal& equal = key_equal (),
const allocator_type& allocator = allocator_type ());
Create an empty set.
| Throws: | Exceptions thrown by the allocator. |
|---|
forward_hash_set (const forward_hash_set& that);
Create a new set as a copy of another. Copies contained elements, hash function object, equality predicate, allocator and maximum load factor of the other container. Iteration order in the copy is the same as in that.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
Compiler-specific
Only on C++0x compilers:
forward_hash_set (forward_hash_set&& that);
The same as copy constructor, except that the second set is left in undefined state. Unlike the copy constructor, this never throws.
forward_hash_set (const forward_hash_set& that, const allocator_type& allocator);
Similar to the copy constructor, but uses explicitly specified allocator instead of copying it from that container.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
template <typename InputIterator>
forward_hash_set (InputIterator first,
InputIterator last,
size_type num_buckets = 0,
const hasher& hash = hasher (),
const key_equal& equal = key_equal (),
const allocator_type& allocator = allocator_type ());
Create a set containing all elements in the range [first, last). Duplicate elements in the range are effectively ignored. Iteration order of the set matches [first, last) except for duplicate elements: as only the first copy is added to the set, it is also the only visited during iteration.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
Compiler-specific
This constructor is defined only on C++0x compilers
forward_hash_set (std::initializer_list <value_type> initializer,
size_type num_buckets = 0,
const hasher& hash = hasher (),
const key_equal& equal = key_equal (),
const allocator_type& allocator = allocator_type ());
Create a set containing all elements from initializer list. Duplicate elements are effectively ignored. Iteration order of other elements in the new set is the same as in the list.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
forward_hash_set& operator= (const forward_hash_set& that);
Erase current set contents and replace it with contents of another set. This replaces hash function, equality predicate and maximum load factor, but not the allocator. After assignment, iteration order of the two sets is the same.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. Also see common note above. |
|---|
Compiler-specific
Only on C++0x compilers:
forward_hash_set& operator= (forward_hash_set&& that);
The same as copy assignment, except that the second set is left in undefined state. If allocators of the two sets are equal this version doesn’t throw.
Compiler-specific
This assignment is defined only on C++0x compilers
forward_hash_set& operator= (std::initializer_list <value_type> initializer);
Erase current set contents and replace it with values from the initializers. Duplicate elements in the list are effectively ignored. Iteration order of other elements matches their relative order in the initialization list.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
Destroy all contained elements, free memory and destroy the set itself.
size_type bucket_count () const;
| Returns: | Current number of bucket used by the container. |
|---|
size_type max_bucket_count () const;
| Returns: | The largest number of buckets this set could ever have. |
|---|
iterator begin (); const_iterator begin () const;
| Returns: | An iterator pointing to the first element in the set, or past-the-end iterator if the set is empty. |
|---|
const_iterator cbegin () const;
| Returns: | A constant iterator pointing to the first element in the set, or past-the-end iterator if the set is empty. |
|---|
iterator before_begin (); const_iterator before_begin () const;
| Returns: | A non-dereferencable iterator that, when incremented, is equal to begin(). This is useful as an argument to various *_after() functions. |
|---|
const_iterator cbefore_begin () const;
| Returns: | A constant non-dereferencable iterator that, when incremented, is equal to cbegin(). This is useful as an argument to various *_after() functions. |
|---|
iterator before_end (); const_iterator before_end () const;
| Returns: | An iterator that, when incremented, is equal to end(). If the set is not empty, this is an iterator pointing to the last element. It is useful as an argument to various *_after() functions. |
|---|
const_iterator cbefore_end () const;
| Returns: | An constant iterator that, when incremented, is equal to cend(). If the set is not empty, this is an iterator pointing to the last element. It is useful as an argument to various *_after() functions. |
|---|
reference front (); const_reference front () const;
| Returns: | The first element in set’s iteration order. |
|---|---|
| Notes: | The set must not be empty. |
reference back (); const_reference back () const;
| Returns: | The last element in set’s iteration order. |
|---|---|
| Notes: | The set must not be empty. |
iterator find (const key_type& key); const_iterator find (const key_type& key) const;
Find an element with given key.
| Returns: | An iterator pointing to matching element or end() if there’s no such element. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
size_type count (const key_type& key) const;
| Returns: | Number of elements with given key. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | For a set return value is always 0 or 1. |
std::pair <iterator, iterator> equal_range (const key_type& key); std::pair <const_iterator, const_iterator> equal_range (const key_type& key) const;
Determine the range consisting of all elements with given key.
| Returns: | A pair P such that [P.first, P.second) is the range consisting all elements with given key. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | For a set such a range always contains 0 or 1 element. |
Note that all insert() variants (as well as similar push_front() and push_back()) invalidate iterators while all erase() (as well as similar pop_front()) don’t.
std::pair <iterator, bool> push_front (const value_type& value);
Insert the given value into the set unless the set already contains an equal one. If the value is inserted, it will be the first in set’s iteration order.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
Only on C++0x compilers:
std::pair <iterator, bool> push_front (value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
std::pair <iterator, bool> push_back (const value_type& value);
Exactly the same as insert (value).
Compiler-specific
Only on C++0x compilers:
std::pair <iterator, bool> push_back (value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
std::pair <iterator, bool> insert (const value_type& value);
Insert the given value into the set unless the set already contains an equal one. If the value is inserted, it will be the last in set’s iteration order.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
Only on C++0x compilers:
std::pair <iterator, bool> insert (value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
std::pair <iterator, bool> insert_after (const_iterator after, const value_type& value);
Insert the given value into the set unless the set already contains an equal one. If the value is inserted, it will immediately follow element pointed to by the given iterator in iteration order. Iterators returned by before_begin() and before_end() are commonly used for after, but in addition any valid iterator for the set is allowed.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
Only on C++0x compilers:
std::pair <iterator, bool> insert_after (const_iterator after, value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
template <typename InputIterator> void insert (InputIterator first, InputIterator last);
Insert all values in the range [first, last) into the set. Values that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert() on each value in the range, but using this method might be more efficient. Inserted elements in the range will be the last in set’s iteration order; their relative precedence will be the same as in [first, last) range.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Basic exception safety: if an exception is thrown, the set contents is as before plus maybe part of contents of the range. |
template <typename InputIterator> void insert_after (const_iterator after, InputIterator first, InputIterator last);
Insert all values in the range [first, last) into the set. Values that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert_after() on each value in the range, but using this method might be more efficient. Inserted elements in the range will immediately follow element pointed to by the given iterator in iteration order; their relative precedence will be the same as in [first, last) range. Iterators returned by before_begin() and before_end() are commonly used for after, but in addition any valid iterator for the set is allowed.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Basic exception safety: if an exception is thrown, the set contents is as before plus maybe part of contents of the range. |
Compiler-specific
This method is defined only on C++0x compilers
void insert (std::initializer_list <value_type> initializer);
Insert given values into the set. Values that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert() on each value in the list, but using this method might be more efficient. Inserted elements will be the last in set’s iteration order; their relative precedence will be the same as in the list.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Basic exception safety: if an exception is thrown, the set contents is as before plus maybe part of contents of the initializer list. |
Compiler-specific
This method is defined only on C++0x compilers
void insert_after (const_iterator after, std::initializer_list <value_type> initializer);
Insert given values into the set. Values that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert_after() on each value in the list, but using this method might be more efficient. Inserted elements will immediately follow element pointed to by the given iterator in iteration order; their relative precedence will be the same as in the list. Iterators returned by before_begin() and before_end() are commonly used for after, but in addition any valid iterator for the set is allowed.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Basic exception safety: if an exception is thrown, the set contents is as before plus maybe part of contents of the initializer list. |
Compiler-specific
This method is defined only on C++0x compilers
template <typename... Args> std::pair <iterator, bool> emplace (Args&&... args);
Insert a value_type object constructed with given arguments into the set unless the set already contains an equal one.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Special note
Purpose of similar method in STL unordered_set is to avoid moving or copying the constructed object. Unfortunately, this is impossible to achieve with closed hashing, so in forward_hash_set this is not faster than simple insert(). This method exists mostly for compatibility reasons rather than adding any useful functionality.
Compiler-specific
This method is defined only on C++0x compilers
template <typename... Args> std::pair <iterator, bool> emplace_after (const_iterator after, Args&&... args);
Insert a value_type object constructed with given arguments into the set unless the set already contains an equal one. If the object is inserted, it will immediately follow element pointed to by the given iterator in iteration order. Iterators returned by before_begin() and before_end() are commonly used for after, but in addition any valid iterator for the set is allowed.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Special note
Purpose of similar methods in STL unordered_set is to avoid moving or copying the constructed object. Unfortunately, this is impossible to achieve with closed hashing, so in forward_hash_set this is not faster than simple insert(). This method exists mostly for compatibility reasons rather than adding any useful functionality.
void pop_front ();
Erase the first element in the set’s iteration order.
| Notes: | The set must not be empty. Never throws. |
|---|
void erase_after (const_iterator position);
Erase the element following given position. Note that in forward hash tables it is not possible to erase elements by having an iterator pointing to them: you need an iterator pointing to the previous element.
| Notes: | Never throws. |
|---|
void erase_after (const_iterator position, const_iterator last);
Erase a range of elements.
| Notes: | Never throws. |
|---|
void swap (forward_hash_set& that);
Swap contents (elements), hash function, equality predicates and maximum load factors between two sets. Allocators are not swapped. Iteration orders are swapped along with elements: after swapping, this set will yield the same sequence of elements as that set did before, and vice versa.
| Throws: | Only if allocators are different: exceptions thrown by (either set’s) hash function, equality predicates or allocator. |
|---|---|
| Notes: | If allocators of the two sets are equal the function never throws and is O(1) in complexity. Otherwise strong exception safety is guaranteed and complexity is O(n) where n is the total number of buckets in the sets. Also see common note above. |
Note that since container is a set, below operations don’t change its equality. I.e. the container after the operation will always be equal (as defined by operator==) to itself before the operation.
These functions never invalidate iterators or throw anything.
void relink_after (const_iterator to_after, iterator from_after);
Relink the element immediately following the second argument iterator after the first argument iterator. Both arguments may be before_begin() or some valid iterators, except that from_after must not be equal to before_end().
| Notes: | It is allowed to pass equal iterators or try to relink an element after itself; in both these cases nothing will be done. |
|---|
void reverse ();
Reverse the order in which container’s elements are iterated. I.e. formerly first element becomes the last, second element becomes second to last and so on.
float max_load_factor () const;
| Returns: | Maximum allowed load factor of the container. |
|---|
void max_load_factor (float set_to);
Change maximum load factor of the set. If the new maximum is smaller than the current load factor, the set is rehashed to reduce the load.
| Notes: | Invalidates iterators if a rehash is trigerred. |
|---|
void rehash (size_type num_buckets);
Change bucket count to given value, if possible. Implementation can alter num_buckets as needed to have load factor small enough as well as for internal reasons. In particular, it is legal to specify zero as number of buckets: this will be replaced with the smallest number that keeps load below the allowed maximum. Finally, it sometimes makes sense (for performance) to rehash to the same number of buckets as before to “clean” the container after erasing elements.
| Notes: | Invalidates iterators. |
|---|
void reserve (size_type num_elements);
Rehash the table in such a way that it will not be rehashed anymore if size doesn’t exceed given value and no erase()-like methods are used. This is exactly identical to:
set.rehash (std::ceil (num_elements / set.max_load_factor ()));
| Notes: | Invalidates iterators. |
|---|
operator== (const forward_hash_set <...>& set1, const forward_hash_set <...>& set2);
Compare the elements of the two sets. Remember that despite being (singly) linked, containers are still sets, i.e. iteration order is irrelevant to container equality.
| Returns: | true if the sets are equal, i.e. contain the same elements. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | Result does not depend on either sets’ iteration order. It is undefined if the sets’ equality predicates are not equivalent. |
operator!= (const forward_hash_set <...>& set1, const forward_hash_set <...>& set2);
See operator== for details.
void swap (forward_hash_set <...>& set1, forward_hash_set <...>& set2);
Effect is identical to set1.swap (set2). See the method for details.
Versioned
Since 1.2
A fast unordered container mapping unique keys to arbitrary values and providing stable iteration order.
The class is defined in header <mct/hash-map.hpp>:
template <typename Key,
typename Mapped,
typename Hash = hash <Key>,
typename Equal = std::equal_to <Key>,
typename Allocator = std::allocator <std::pair <const Key, Mapped> >,
bool keep_hashes = false>
class forward_hash_map;
Template parameters:
Key: The map’s key type; must be assignable and copy-constructible Mapped: The type keys are mapped to; must be copy-constructible Hash: A unary function object type that hashes Key objects and returns an std::size_t hash; copy constructor must not throw, see common note above Equal: A binary function object type used to compare objects of type Key, i.e. equality predicate; copy constructor must not throw, see common note above Allocator: Allocator for type std::pair <const Key, Mapped> keep_hashes: Flag that determines whether the map keeps hashes of individual contained keys (i.e. doesn’t recompute them); see flag description above for details
key_type: The map’s key type mapped_type: The type keys are mapped to value_type: The map’s value type; always std::pair <const key_type, mapped_type> hasher: The type of the hash function object key_equal: The type of equality function object allocator_type: The type of allocator object iterator: A forward iterator type capable of navigating the map; note that the iterator is not mutable because first member of the pair it points to cannot be modified const_iterator: A constant forward iterator; similar to iterator except that values it points to are immutable pointer: const_pointer: reference: const_reference: size_type: difference_type: Standard container type members; mostly interesting for meta-programming needs
forward_hash_map (size_type num_buckets = 0,
const hasher& hash = hasher (),
const key_equal& equal = key_equal (),
const allocator_type& allocator = allocator_type ());
Create an empty map.
| Throws: | Exceptions thrown by the allocator. |
|---|
forward_hash_map (const forward_hash_map& that);
Create a new map as a copy of another. Copies contained elements, hash function object, equality predicate, allocator and maximum load factor of the other container. Iteration order in the copy is the same as in that.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
Compiler-specific
Only on C++0x compilers:
forward_hash_map (forward_hash_map&& that);
The same as copy constructor, except that the second map is left in undefined state. Unlike the copy constructor, this never throws.
forward_hash_map (const forward_hash_map& that, const allocator_type& allocator);
Similar to the copy constructor, but uses explicitly specified allocator instead of copying it from that container.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
template <typename InputIterator>
forward_hash_map (InputIterator first,
InputIterator last,
size_type num_buckets = 0,
const hasher& hash = hasher (),
const key_equal& equal = key_equal (),
const allocator_type& allocator = allocator_type ());
Create a map containing all elements in the range [first, last). Elements with duplicate keys in the range are effectively ignored: only the first is inserted into the new map. Iteration order of the map matches [first, last) except for elements with duplicate keys: as only the first copy is added to the map, it is also the only visited during iteration.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
Compiler-specific
This constructor is defined only on C++0x compilers
forward_hash_map (std::initializer_list <value_type> initializer,
size_type num_buckets = 0,
const hasher& hash = hasher (),
const key_equal& equal = key_equal (),
const allocator_type& allocator = allocator_type ());
Create a map containing all elements from initializer list. Elements with duplicate keys are effectively ignored. Iteration order of other elements in the new map is the same as in the list.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
forward_hash_map& operator= (const forward_hash_map& that);
Erase current map contents and replace it with contents of another map. This replaces hash function, equality predicate and maximum load factor, but not the allocator. After assignment, iteration order of the two maps is the same.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. Also see common note above. |
|---|
Compiler-specific
Only on C++0x compilers:
forward_hash_map& operator= (forward_hash_map&& that);
The same as copy assignment, except that the second map is left in undefined state. If allocators of the two maps are equal this version doesn’t throw.
Compiler-specific
This assignment is defined only on C++0x compilers
forward_hash_map& operator= (std::initializer_list <value_type> initializer);
Erase current map contents and replace it with values from the initializers. Elements with duplicate keys in the list are effectively ignored. Iteration order of other elements matches their relative order in the initialization list.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|
Destroy all contained elements, free memory and destroy the map itself.
size_type bucket_count () const;
| Returns: | Current number of bucket used by the container. |
|---|
size_type max_bucket_count () const;
| Returns: | The largest number of buckets this map could ever have. |
|---|
iterator begin (); const_iterator begin () const;
| Returns: | An iterator pointing to the first element in the map, or past-the-end iterator if the map is empty. |
|---|
const_iterator cbegin () const;
| Returns: | A constant iterator pointing to the first element in the map, or past-the-end iterator if the map is empty. |
|---|
iterator before_begin (); const_iterator before_begin () const;
| Returns: | A non-dereferencable iterator that, when incremented, is equal to begin(). This is useful as an argument to various *_after() functions. |
|---|
const_iterator cbefore_begin () const;
| Returns: | A constant non-dereferencable iterator that, when incremented, is equal to cbegin(). This is useful as an argument to various *_after() functions. |
|---|
iterator before_end (); const_iterator before_end () const;
| Returns: | An iterator that, when incremented, is equal to end(). If the map is not empty, this is an iterator pointing to the last element. It is useful as an argument to various *_after() functions. |
|---|
const_iterator cbefore_end () const;
| Returns: | An constant iterator that, when incremented, is equal to cend(). If the map is not empty, this is an iterator pointing to the last element. It is useful as an argument to various *_after() functions. |
|---|
reference front (); const_reference front () const;
| Returns: | The first element in map’s iteration order. |
|---|---|
| Notes: | The map must not be empty. |
reference back (); const_reference back () const;
| Returns: | The last element in map’s iteration order. |
|---|---|
| Notes: | The map must not be empty. |
iterator find (const key_type& key); const_iterator find (const key_type& key) const;
Find an element with given key.
| Returns: | An iterator pointing to matching element or end() if there’s no such element. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
size_type count (const key_type& key) const;
| Returns: | Number of elements with given key. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | For a map return value is always 0 or 1. |
std::pair <iterator, iterator> equal_range (const key_type& key); std::pair <const_iterator, const_iterator> equal_range (const key_type& key) const;
Determine the range consisting of all elements with given key.
| Returns: | A pair P such that [P.first, P.second) is the range consisting all elements with given key. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | For a map such a range always contains 0 or 1 element. |
mapped_type& operator[] (const key_type& key);
Find the object given key is mapped to, or else insert a new association with default-constructed mapped_type. If insertion happens, new element will be the last in the map’s iteration order.
| Returns: | A reference to a pre-existed or newly inserted object associated with key. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators if a new association is created. Strong exception safety. |
mapped_type& at (const key_type& key); const mapped_type& at (const key_type& key) const;
Find the element with given key and assert its presence.
| Returns: | A reference to the pre-existed object associated with key. |
|---|---|
| Throws: | std::out_of_range if there is no element with given key (the assertion fails). Additionally, exceptions thrown by the hash function or equality predicate. |
Note that all insert() variants (as well as similar push_front() and push_back()) invalidate iterators while all erase() (as well as similar pop_front()) don’t.
std::pair <iterator, bool> push_front (const value_type& value);
Insert the given value into the map unless the map already contains one with equal key. If the value is inserted, it will be the first in map’s iteration order.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
Only on C++0x compilers:
std::pair <iterator, bool> push_front (value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
std::pair <iterator, bool> push_back (const value_type& value);
Exactly the same as insert (value).
Compiler-specific
Only on C++0x compilers:
std::pair <iterator, bool> push_back (value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
std::pair <iterator, bool> insert (const value_type& value);
Insert the given value into the map unless the map already contains one with equal key. If the value is inserted, it will be the last in map’s iteration order.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
Only on C++0x compilers:
std::pair <iterator, bool> insert (value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
std::pair <iterator, bool> insert_after (const_iterator after, const value_type& value);
Insert the given value into the map unless the map already contains one with equal key. If the value is inserted, it will immediately follow element pointed to by the given iterator in iteration order. Iterators returned by before_begin() and before_end() are commonly used for after, but in addition any valid iterator for the map is allowed.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Compiler-specific
Only on C++0x compilers:
std::pair <iterator, bool> insert_after (const_iterator after, value_type&& value);
Insert the value by using value_type’s move constructor. Otherwise the same as above.
template <typename InputIterator> void insert (InputIterator first, InputIterator last);
Insert all values in the range [first, last) into the map. Values with keys that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert() on each value in the range, but using this method might be more efficient. Inserted elements in the range will be the last in map’s iteration order; their relative precedence will be the same as in [first, last) range.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Basic exception safety: if an exception is thrown, the map contents is as before plus maybe part of contents of the range. |
template <typename InputIterator> void insert_after (const_iterator after, InputIterator first, InputIterator last);
Insert all values in the range [first, last) into the map. Values with keys that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert_after() on each value in the range, but using this method might be more efficient. Inserted elements in the range will immediately follow element pointed to by the given iterator in iteration order; their relative precedence will be the same as in [first, last) range. Iterators returned by before_begin() and before_end() are commonly used for after, but in addition any valid iterator for the map is allowed.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Basic exception safety: if an exception is thrown, the map contents is as before plus maybe part of contents of the range. |
Compiler-specific
This method is defined only on C++0x compilers
void insert (std::initializer_list <value_type> initializer);
Insert given values into the map. Values with keys that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert() on each value in the list, but using this method might be more efficient. Inserted elements will be the last in map’s iteration order; their relative precedence will be the same as in the list.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Basic exception safety: if an exception is thrown, the map contents is as before plus maybe part of contents of the initializer list. |
Compiler-specific
This method is defined only on C++0x compilers
void insert_after (const_iterator after, std::initializer_list <value_type> initializer);
Insert given values into the map. Values with keys that are equal to any already contained are effectively ignored. This is equivalent to calling single-item insert_after() on each value in the list, but using this method might be more efficient. Inserted elements will be the last in map’s iteration order; their relative precedence will be the same as in the list. Iterators returned by before_begin() and before_end() are commonly used for after, but in addition any valid iterator for the map is allowed.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Basic exception safety: if an exception is thrown, the map contents is as before plus maybe part of contents of the initializer list. |
Compiler-specific
This method is defined only on C++0x compilers
template <typename... Args> std::pair <iterator, bool> emplace (Args&&... args);
Insert a value_type object constructed with given arguments into the map unless the map already contains one with equal key.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Special note
Purpose of similar method in STL unordered_map is to avoid moving or copying the constructed object. Unfortunately, this is impossible to achieve with closed hashing, so in forward_hash_map this is not faster than simple insert(). This method exists mostly for compatibility reasons rather than adding any useful functionality.
Compiler-specific
This method is defined only on C++0x compilers
template <typename... Args> std::pair <iterator, bool> emplace_after (const_iterator after, Args&&... args);
Insert a value_type object constructed with given arguments into the map unless the map already contains one with equal key. If the object is inserted, it will immediately follow element pointed to by the given iterator in iteration order. Iterators returned by before_begin() and before_end() are commonly used for after, but in addition any valid iterator for the map is allowed.
| Returns: | A pair of iterator pointing to inserted (or equal pre-existed) element and a flag indicating whether insertion took place. |
|---|---|
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
| Notes: | Invalidates iterators. Strong exception safety. |
Special note
Purpose of similar methods in STL unordered_map is to avoid moving or copying the constructed object. Unfortunately, this is impossible to achieve with closed hashing, so in forward_hash_map this is not faster than simple insert(). This method exists mostly for compatibility reasons rather than adding any useful functionality.
void pop_front ();
Erase the first element in the map’s iteration order.
| Notes: | The map must not be empty. Never throws. |
|---|
void erase_after (const_iterator position);
Erase the element following given position. Note that in forward hash tables it is not possible to erase elements by having an iterator pointing to them: you need an iterator pointing to the previous element.
| Notes: | Never throws. |
|---|
void erase_after (const_iterator position, const_iterator last);
Erase a range of elements.
| Notes: | Never throws. |
|---|
void swap (forward_hash_map& that);
Swap contents (elements), hash function, equality predicates and maximum load factors between two maps. Allocators are not swapped. Iteration orders are swapped along with elements: after swapping, this map will yield the same sequence of elements as that map did before, and vice versa.
| Throws: | Only if allocators are different: exceptions thrown by (either map’s) hash function, equality predicates or allocator. |
|---|---|
| Notes: | If allocators of the two maps are equal the function never throws and is O(1) in complexity. Otherwise strong exception safety is guaranteed and complexity is O(n) where n is the total number of buckets in the maps. Also see common note above. |
Note that since container is a map, below operations don’t change its equality. I.e. the container after the operation will always be equal (as defined by operator==) to itself before the operation.
These functions never invalidate iterators or throw anything.
void relink_after (const_iterator to_after, iterator from_after);
Relink the element immediately following the second argument iterator after the first argument iterator. Both arguments may be before_begin() or some valid iterators, except that from_after must not be equal to before_end().
| Notes: | It is allowed to pass equal iterators or try to relink an element after itself; in both these cases nothing will be done. |
|---|
void reverse ();
Reverse the order in which container’s elements are iterated. I.e. formerly first element becomes the last, second element becomes second to last and so on.
float max_load_factor () const;
| Returns: | Maximum allowed load factor of the container. |
|---|
void max_load_factor (float set_to);
Change maximum load factor of the map. If the new maximum is smaller than the current load factor, the map is rehashed to reduce the load.
| Notes: | Invalidates iterators if a rehash is trigerred. |
|---|
void rehash (size_type num_buckets);
Change bucket count to given value, if possible. Implementation can alter num_buckets as needed to have load factor small enough as well as for internal reasons. In particular, it is legal to specify zero as number of buckets: this will be replaced with the smallest number that keeps load below the allowed maximum. Finally, it sometimes makes sense (for performance) to rehash to the same number of buckets as before to “clean” the container after erasing elements.
| Notes: | Invalidates iterators. |
|---|
void reserve (size_type num_elements);
Rehash the table in such a way that it will not be rehashed anymore if size doesn’t exceed given value and no erase()-like methods are used. This is exactly identical to:
map.rehash (std::ceil (num_elements / map.max_load_factor ()));
| Notes: | Invalidates iterators. |
|---|
operator== (const forward_hash_map <...>& map1, const forward_hash_map <...>& map2);
Compare the elements of the two maps. Remember that despite being (singly) linked, containers are still maps, i.e. iteration order is irrelevant to container equality.
| Returns: | true if the maps are equal, i.e. contain the same elements. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | Result does not depend on either maps’ iteration order. It is undefined if the maps’ equality predicates are not equivalent. |
operator!= (const forward_hash_map <...>& map1, const forward_hash_map <...>& map2);
See operator== for details.
void swap (forward_hash_map <...>& map1, forward_hash_map <...>& map2);
Effect is identical to map1.swap (map2). See the method for details.
These methods are defined only if any of MCT_ENABLE_DEBUGGING, MCT_CHECK_PRECONDITIONS or MCT_SELF_VALIDATION is defined and non-zero prior to including any MCT headers. Whether they are defined can be tested with MCT_DEBUGGING_MEMBERS. The members are valid for all container classes in the library.
Remember that MCT_ENABLE_DEBUGGING only causes these members to be defined; they won’t be called automatically. If you need the latter refer to Automated Debugging section.
A simple structure without any methods and the following fields:
- double debris_ratio
- Ratio of number of debris buckets to total number of occupied buckets. See implementation description for details.
- double avg_present_lookup
- Average cost of looking up an element contained in the container. Values considerably higher than 1.0 indicate frequent hash collisions and possibly bad choice of hash function.
- size_type max_present_lookup
- Maximum cost of looking up a contained element.
- double avg_absent_lookup
- Average cost of looking up an element not contained in the container. This assumes uniform hash distribution. Usually strongly correlates with ratio of number of occupied buckets to total number of buckets, but bad hash function can increase this further.
- size_type max_absent_lookup
- Maximum cost of looking up a non-contained element.
bool valid_iterator (const_iterator position) const;
| Returns: | true if the iterator is valid for this container; past-the-end iterator is not considered valid. |
|---|---|
| Notes: | For optimization reasons, a valid and an invalid iterator can be deemed equal. This method is more robust and much faster than comparing to all valid iterators. |
bool valid_iterator_range (const_iterator first, const_iterator last) const;
For a range to be valid, both its end must be valid or past-the-end iterators and first must precede or be equal to last.
| Returns: | true if [first, last) is a valid iterator range. |
|---|
size_type used_memory () const;
| Returns: | Total amount of memory used by the container, in bytes. |
|---|
void validate_integrity () const;
Perform internal structure validation.
| Throws: | An unspecified subclass of std::logic_error if any errors are detected. Additionally, exceptions thrown by the hash function or equality predicate. |
|---|
statistics collect_statistics () const;
Collect various information about current use and potential performance of the container. Useful to determine why a container underperforms.
| Returns: | Statistics reflecting current container composure and performance. |
|---|---|
| Throws: | Exceptions thrown by the hash function or equality predicate. |
| Notes: | These statistics don’t represent any past state of the container. |
Versioned
Since 1.2
MCT provides a generic mechanism for specifying information about external use of types. This is done by specializing external_use structure in mct namespace. Other structures described in this section can be seen as auxiliary.
All structures are defined in header <mct/intrusiveness.hpp>. However, including either of <mct/hash-set.hpp> or <mct/hash-map.hpp> is guaranteed to define them as well.
Templated structure that specifies external use information for a type. By default it is empty and is intended to be specialized by users of MCT.
Warning
Exact contents of specializations is not fixed yet and might change in later versions. The only correct way to specialize is to inherit from extern_use_field or propagate_external_use currently. See examples below, in the sections describing the mentioned structures.
Because of currently undefined contents, this structure is of little use (other than specializing) outside MCT. Inside the library, closed_hash_set and closed_hash_map can leverage external use information to provide better performance.
template <typename Type,
typename Enable = void>
struct external_use;
Template parameters:
Type: The type to which external use information applies Enable: “Hidden” template parameter, for the purpose of using constructs like std::enable_if or boost::enable_if
The structure is already specialized for std::pair <First, Second> where supports_external_use is true for First or Second or both. In other words, if you provide external use information for MyType, such information will also apply for std::pair <MyType, *> and std::pair <*, MyType>. And, recursively, to std::pair <std::pair <MyType, *>, *> and so forth.
There are no specializations for concrete types.
Type trait structure, simply determining whether external_use for a type is properly specialized. The only member is variable value of type bool. E.g.:
supports_external_use <int>::value == false
A type that can be (and currently should be, see warning above) used as a base class when specializing external_use.
template <typename Type,
typename Value,
Value Type::* field>
struct extern_use_field;
Template parameters:
Type: The type which contains a field dedicated for external use Value: The type of the field; currently must be an integral type other than bool field: Pointer-to-member for the field dedicated for external use
This assumes that MyClass has a public field named _unused_field of type char, which it will not use itself and dedicates for external use:
namespace mct
{
template <>
struct external_use <MyClass>
: extern_use_field <MyClass, char, &MyClass::_unused_field>
{ };
}
A type that can be (and currently should be, see warning above) used as a base class when propagating external use information from a field type.
template <typename To,
typename From,
From To::* field>
struct propagate_external_use;
Template parameters:
To: The type for which external use information is specified From: A type for which external_use is already specialized; To must have a field of type From field: Pointer-to-member for the field of type From in type To
This is a followup to the example in the previous section and assumes that external_use has been specialized for MyClass. Now, suppose MyCompositeClass has a public field named a_field of type MyClass. We can reuse external use information already registered for MyClass like this:
namespace mct
{
template <>
struct external_use <MyCompositeClass>
: propagate_external_use <MyCompositeClass, MyClass, &MyCompositeClass::a_field>
{ };
}
In addition to the general debugging methods described earlier, MCT provides tools for automated debugging of problems.
MCT functions are capable of automatically checking their preconditions to some extent. To activate this mode, define MCT_CHECK_PRECONDITIONS to a non-zero value before including any MCT header. If a precondition test fails, function will throw std::logic_error (or some unspecified subclass of that); this is not mentioned in other reference sections.
This mode is a good way to detect many programming bugs like using an invalidated iterator or popping from an empty linked_hash_map. However, don’t expect it to alert of all possible problems.
Automatic precondition testing can be moderately slow, so consider that before enabling the mode. Additionally, later versions of MCT can add more precondition tests thus increasing performance hit.
Setting MCT_CHECK_PRECONDITIONS to a non-zero value causes definition of the common debugging members.
It is possible to force MCT into a self-validating mode by defining MCT_SELF_VALIDATION to a non-zero value. This allows to spot bugs (usually caused by memory corruption or invalid parameters supplied to container functions) quickly. However, this leads to extremely poor performance, and thus should be used only when you suspect there is a problem.
Setting MCT_SELF_VALIDATION to a non-zero value causes definition of the common debugging members.
This section lists some preprocessor symbols (macros) that are useful to clients of the package. There are some other symbols starting with prefix MCT_, but they should be considered private to the package and are not guaranteed to retain current meaning or even stay in the package.
MCT_MAJOR_VERSION: MCT_MINOR_VERSION: MCT_PATCH_VERSION: Three numbers of the package version. MCT follows old Linux versioning scheme where odd minor version means a development release. MCT_VERSION_STRING: The version as a string, mainly if needed for presentation purposes.
MCT_HASH_HEADER: MCT_HASH_NAMESPACE: MCT_TYPE_TRAITS_HEADER: MCT_TYPE_TRAITS_NAMESPACE: Header and namespace for hash function and type traits definitions. These symbols either come from configuration determined at installation, or can be redefined at inclusion time (see section Inclusion-Time Configuration). MCT_HAVE_TYPE_TRAITS: Defined to nonzero if MCT uses type traits.
Some symbols are defined by MCT itself based on configuration:
MCT_DEBUGGING_MEMBERS: 1 or 0 depending on whether containers provide common debugging members.
Copyright © 2010 Paul Pogonyshev.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.