| 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 only four closely related containers: closed_hash_set, closed_hash_map, linked_hash_set and linked_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.
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. However, many C++0x features are not supported; in particular, movable but not copyable elements are not supported.
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_* counterparts are not so fast, but this is dictated by the additional provided feature.
Fast general-purpose hashtable 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:
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):
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 this flag is defined to any non-zero value, all containers will have additional debugging members: valid_iterator(), used_memory(), validate_integrity() and collect_statistics(). See Common Debugging Members reference section for more information.
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, thus avoiding recomputation.
However, this template parameter is only a request and not a requirement. Container may decide to keep hashes even if not asked to or vice versa. Current implementation always keep hashes if key_type is sufficiently large (this is required for it to work).
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.
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.
keep_hashes
If hash function is slow, you can force containers to cache its result for contained elements by setting keep_hashes template parameter to true. Remember, however, that for very fast hash 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
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
Definition:
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. |
|---|
Definition:
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. |
|---|
Definition:
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. |
|---|
Definition:
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. |
|---|
Definition:
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. |
|---|
Destroy all contained elements, free memory and destroy the set itself.
Definition:
size_type max_size () const;
| Returns: | The largest size this set could ever have. |
|---|
Definition:
size_type bucket_count () const;
| Returns: | Current number of bucket used by the container. |
|---|
Definition:
size_type max_bucket_count () const;
| Returns: | The largest number of buckets this set could ever have. |
|---|
Definitions:
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. |
Definition:
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. |
Definitions:
iterator end (); const_iterator end () const;
| Returns: | Past-the-end iterator for the set. |
|---|
Definitions:
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. |
Definition:
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. |
Definitions:
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.
Definition:
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. |
Definition:
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. |
Definition:
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. |
Definition:
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. |
Definition:
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. |
Definition:
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. |
Definition:
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. |
Definition:
float load_factor () const;
| Returns: | Current load factor of the container. |
|---|
Definition:
float max_load_factor () const;
| Returns: | Maximum allowed load factor of the container. |
|---|
Definition:
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. |
|---|
Definition:
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. |
|---|
Definition:
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. |
Definition:
operator!= (const closed_hash_set <...>& set1, const closed_hash_set <...>& set2);
See operator== for details.
Definition:
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
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
Definition:
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. |
|---|
Definition:
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. |
|---|
Definition:
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. |
|---|
Definition:
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. |
|---|
Definition:
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. |
|---|
Destroy all contained elements, free memory and destroy the map itself.
Definition:
size_type max_size () const;
| Returns: | The largest size this map could ever have. |
|---|
Definition:
size_type bucket_count () const;
| Returns: | Current number of bucket used by the container. |
|---|
Definition:
size_type max_bucket_count () const;
| Returns: | The largest number of buckets this map could ever have. |
|---|
Definitions:
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. |
Definition:
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. |
Definitions:
iterator end (); const_iterator end () const;
| Returns: | Past-the-end iterator for the map. |
|---|
Definitions:
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. |
Definition:
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. |
Definitions:
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. |
Definition:
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. |
Definitions:
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.
Definition:
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. |
Definition:
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. |
Definition:
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. |
Definition:
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. |
Definition:
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. |
Definition:
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. |
Definition:
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. |
Definition:
float load_factor () const;
| Returns: | Current load factor of the container. |
|---|
Definition:
float max_load_factor () const;
| Returns: | Maximum allowed load factor of the container. |
|---|
Definition:
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. |
|---|
Definition:
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. |
|---|
Definition:
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. |
Definition:
operator!= (const closed_hash_map <...>& map1, const closed_hash_map <...>& map2);
See operator== for details.
Definition:
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
Definition:
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. |
|---|
Definition:
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. |
|---|
Definition:
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. |
|---|
Definition:
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. |
|---|
Definition:
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. |
|---|
Destroy all contained elements, free memory and destroy the set itself.
Definition:
size_type max_size () const;
| Returns: | The largest size this set could ever have. |
|---|
Definition:
size_type bucket_count () const;
| Returns: | Current number of bucket used by the container. |
|---|
Definition:
size_type max_bucket_count () const;
| Returns: | The largest number of buckets this set could ever have. |
|---|
Definitions:
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. |
|---|
Definition:
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. |
|---|
Definitions:
iterator end (); const_iterator end () const;
| Returns: | Past-the-end iterator for the set. |
|---|
Definitions:
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. |
|---|
Definition:
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. |
|---|
Definitions:
reverse_iterator rend (); const_reverse_iterator rend () const;
| Returns: | Past-the-end reverse iterator for the set. |
|---|
Definition:
const_reverse_iterator crend () const;
| Returns: | Past-the-end reverse iterator for the set. |
|---|
Definitions:
reference front (); const_reference front () const;
| Returns: | The first element in set’s iteration order. |
|---|---|
| Notes: | The set must not be empty. |
Definitions:
reference back (); const_reference back () const;
| Returns: | The last element in set’s iteration order. |
|---|---|
| Notes: | The set must not be empty. |
Definitions:
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. |
Definition:
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. |
Definitions:
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.
Definition:
void 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.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Strong exception safety. |
Definition:
void push_back (const value_type& value);
The same as insert (value) except that nothing is returned.
Definition:
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. |
Definition:
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. |
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.
Definition:
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. |
Definition:
template <typename InputIterator> void insert (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. |
Definition:
void pop_front ();
Erase the first element in the set’s iteration order.
| Notes: | The set must not be empty. Never throws. |
|---|
Definition:
void pop_back ();
Erase the last element in the set’s iteration order.
| Notes: | The set must not be empty. Never throws. |
|---|
Definition:
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. |
Definition:
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. |
Definition:
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. |
Definition:
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.
Definition:
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). |
|---|
Definition:
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.
Definition:
float load_factor () const;
| Returns: | Current load factor of the container. |
|---|
Definition:
float max_load_factor () const;
| Returns: | Maximum allowed load factor of the container. |
|---|
Definition:
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. |
|---|
Definition:
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. |
|---|
Definition:
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. |
Definition:
operator!= (const linked_hash_set <...>& set1, const linked_hash_set <...>& set2);
See operator== for details.
Definition:
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
Definition:
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. |
|---|
Definition:
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. |
|---|
Definition:
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. |
|---|
Definition:
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. |
|---|
Definition:
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. |
|---|
Destroy all contained elements, free memory and destroy the map itself.
Definition:
size_type max_size () const;
| Returns: | The largest size this map could ever have. |
|---|
Definition:
size_type bucket_count () const;
| Returns: | Current number of bucket used by the container. |
|---|
Definition:
size_type max_bucket_count () const;
| Returns: | The largest number of buckets this map could ever have. |
|---|
Definitions:
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. |
|---|
Definition:
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. |
|---|
Definitions:
iterator end (); const_iterator end () const;
| Returns: | Past-the-end iterator for the map. |
|---|
Definitions:
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. |
|---|
Definition:
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. |
|---|
Definitions:
reverse_iterator rend (); const_reverse_iterator rend () const;
| Returns: | Past-the-end reverse iterator for the map. |
|---|
Definition:
const_reverse_iterator crend () const;
| Returns: | Past-the-end reverse iterator for the map. |
|---|
Definitions:
reference front (); const_reference front () const;
| Returns: | The first element in map’s iteration order. |
|---|---|
| Notes: | The map must not be empty. |
Definitions:
reference back (); const_reference back () const;
| Returns: | The last element in map’s iteration order. |
|---|---|
| Notes: | The map must not be empty. |
Definitions:
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. |
Definition:
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. |
Definitions:
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. |
Definition:
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. |
Definitions:
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.
Definition:
void 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.
| Throws: | Exceptions thrown by the hash function, equality predicate or allocator. |
|---|---|
| Notes: | Invalidates iterators. Strong exception safety. |
Definition:
void push_back (const value_type& value);
The same as insert (value) except that nothing is returned.
Definition:
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. |
Definition:
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. |
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.
Definition:
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. |
Definition:
template <typename InputIterator> void insert (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. |
Definition:
void pop_front ();
Erase the first element in the map’s iteration order.
| Notes: | The map must not be empty. Never throws. |
|---|
Definition:
void pop_back ();
Erase the last element in the map’s iteration order.
| Notes: | The map must not be empty. Never throws. |
|---|
Definition:
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. |
Definition:
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. |
Definition:
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. |
Definition:
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.
Definition:
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). |
|---|
Definition:
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.
Definition:
float load_factor () const;
| Returns: | Current load factor of the container. |
|---|
Definition:
float max_load_factor () const;
| Returns: | Maximum allowed load factor of the container. |
|---|
Definition:
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. |
|---|
Definition:
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. |
|---|
Definition:
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. |
Definition:
operator!= (const linked_hash_map <...>& map1, const linked_hash_map <...>& map2);
See operator== for details.
Definition:
void swap (linked_hash_map <...>& map1, linked_hash_map <...>& map2);
Effect is identical to map1.swap (map2). See the method for details.
These methods are only defined if MCT_ENABLE_DEBUGGING is defined and non-zero prior to including any MCT headers. They are valid for all container classes in the library.
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.
Definition:
bool valid_iterator (const_iterator position) const;
| Returns: | true if the iterator is valid for this container. |
|---|---|
| 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. |
Definition:
size_type used_memory () const;
| Returns: | Total amount of memory used by the container, in bytes. |
|---|
Definition:
void validate_integrity () const;
Perform internal structure validation.
| Throws: | An unspecified subclass of std::exception if any errors are detected. Additionally, exceptions thrown by the hash function or equality predicate. |
|---|
Definition:
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. |
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.
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.