| Author: | Paul Pogonyshev |
|---|---|
| Contact: | pogonyshev@gmail.net |
| Version: | 1.6 |
| Copyright: | © 2009, 2010, 2011, 2012, 2013 Paul Pogonyshev |
Table of Contents
Miscellaneous Container Templates (MCT for short) is an assorted collection of containers designed similarly to those provided by the standard library. Currently, there are six [1] 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 in many cases.
Linked ones have a stable iteration order and some additional functions 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 efficient than linked ones, but support less operations and generally have cumbersome interface.
| [1] | There are also “huge” containers for linked and forward sets and maps, but those can be seen as simply variants of the normal ones. |
Containers in the library are written to meet a set of goals and provide certain guarantees regardless of behavior of contained elements.
Standard library and TR1 compatibility
Where possible, MCT is compatible with the standard library and TR1. MCT classes can usually be used as drop-in replacement for similar standard library or Boost containers.
Thread safety
MCT classes are thread-safe in the face of proper synchronization. Non-mutating (const) functions are always safe, i.e. there is no internal state which would require synchronization. Mutating (non-const) functions 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.
Full allocator support
MCT containers provide good support for any conforming allocator type, including allocators that use non-standard pointers. The latter, in particular, is important for sharing containers between processes using Boost.Interprocess.
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 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 TR1 Containers section.
Advantages of MCT classes:
Disadvantages:
Advantages of MCT classes:
Disadvantages:
| [2] | Results vary with different benchmarks, compilers and CPU architectures. |
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.
In the unlikely case you ever need over 1 billion buckets, read about huge linked hash tables in the reference.
Advantages:
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.
In the unlikely case you ever need over 1 billion buckets, read about huge forward hash tables in the reference.
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.
All MCT containers can be serialized with Boost Serialization library. This is optional in the sense you don’t have to have Boost.Serialization installed in order to use MCT.
But if you do want to define serialization support functions, include headers <mct/hash-set-serialization.hpp> and/or <mct/hash-map-serialization.hpp>, as needed. If Boost.Serialization is not installed, inclusion of either of this header will lead to compilation errors.
MCT can be configured both at installation time and 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.
A reason to configure MCT at inclusion time is to avoid dependencies to what is determined during installation. For example, the library might be installed with disabled C++0x support; if you compile your program using C++0x compiler, define MCT_CXX0X_SUPPORTED to a non-zero value. Another reason is to request debugging assistance from the library.
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 Boost:
#define MCT_HASH_HEADER <boost/functional/hash.hpp> #define MCT_HASH_NAMESPACE boost
For standard library implementation with additional TR1 part:
#define MCT_HASH_HEADER <tr1/functional> #define MCT_HASH_NAMESPACE std::tr1
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 [3]. 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 Boost:
#define MCT_TYPE_TRAITS_HEADER <boost/type_traits.hpp> #define MCT_TYPE_TRAITS_NAMESPACE boost
For standard library implementation with additional TR1 part:
#define MCT_TYPE_TRAITS_HEADER <tr1/type_traits> #define MCT_TYPE_TRAITS_NAMESPACE std::tr1
Like with hash function symbols, you can as well use different values.
| [3] | 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 defined to a non-zero value, compiler supports long long type. This information can be used by MCT for optimizations.
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 actual problems. See Automated Debugging reference section for more details.
Elements
Following common standard library 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() function 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.
Function complexity
When describing complexity, this manual often uses words ‘expected’ and ‘amortized’. The first refers to the common case. E.g. in a hash table many operations have constant complexity if the hash function is good enough and elements are not especially chosen for bad performance. (Even good hash functions have weak spots and will perform poorly on certain specially chosen element sets.)
Amortized complexity refers to average complexity over many calls. For example, insertion has expected constant complexity but only amortized one: occasionally insertion will trigger a non-constant rehashing. Similarly, in a non-linked table operator++ on an iterator has O(bucket_count() / size()) amortized complexity. In this case complexity should be averaged not just over consecutive calls, but over calls on different iterators pointing at all the elements in the table.
MCT classes try to be as compatible as possible with containers from the standard library. Still, there are differences.
This section could also be titled “How to...”.
Advices 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 advices 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 coding 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 use 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.
In certain cases it is possible to speed up closed_hash_set and closed_hash_map even further without incurring any increase in memory footprint. This is no magic — it is possible only if there are “holes” in the stored values that can be used by the containers for internal purposes. So, this can only be done for certain composite user types, and even then is not automatic, as you need to provide some information to MCT about where these “holes” are and how to use them.
Instead of adding yet another template parameter, MCT containers check whether mct::external_use template is specialized for the value type — or, for closed_hash_map, either for key_type or mapped_type. Currently (as of 1.6) the only allowed way to specialize the template is to inherit from mct::extern_use_field.
Suppose you have the following class:
struct Person
{
std::string name;
unsigned short age;
bool gender;
};
Because of alignment rules (at least on modern real-world architectures), this structure can be extended with a char field without increasing its layout size:
... bool gender; char _unused; };
Now we can tell MCT that the field _unused is specifically reserved for the containers and won’t be used by the class itself like this:
namespace mct
{
template <>
struct external_use <Person> : extern_use_field <Person, char, &Person::_unused>
{ };
}
If such a declaration is present, containers like closed_hash_set <Person>, closed_hash_map <int, Person> and so on will use a more efficient representation.
Remember, however, that the class must not use the field at all (except possibly in constructors), not even in its assignment operator. In particular, a type that dedicates a field for external use must not have an implicit assignment operator.
More details and examples can be found in the External Use Specification reference section.
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 facilities 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.
Empty hash tables
When you create a new, empty table, it will not allocate internal bucket array from the start. However, if you insert some elements and subsequently erase all of them, the table is left empty, but with allocated bucket array. This is intentional and prevents frequent reallocations for uses where a table is frequently cleared only to be filled again.
However, if you actually want to clear a hash table and make it release dynamic memory at the same time, simply assign a newly constructed empty table:
map = closed_hash_map <...> ();Additionally, this will have constant complexity provided that map’s value_type has trivial destructor.
You can also tell an empty container to release dynamic memory by using any rehashing operation, e.g. by calling reserve() or rehash().
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 reserve() or rehash() function. 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 reserve() or rehash() function.
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. swap() for class objects) are listed in that class section. There is also a section for Cross-Container Functions.
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
Important
In plain hash tables, increment and decrement operators of the iterators have non-constant O(bucket_count() / size()) amortized complexity. In particular, they can perform poorly in almost empty sets.
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. |
|---|---|
| Complexity: | Constant, but with certain allocation linear in bucket_count() on first element insertion. |
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. |
|---|---|
| Complexity: | Expected O(that.bucket_count()); worst case O(that.bucket_count() * that.size()). If that is empty: constant, but with certain allocation linear in bucket_count() on first element insertion. |
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.
| Complexity: | Constant. |
|---|
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. |
|---|---|
| Complexity: | Same as for copy constructor. |
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. |
|---|---|
| Complexity: | Expected linear in maximum of range size and num_buckets; worst case quadratic in range size. If first == last: constant, but with certain allocation linear in bucket_count() on first element insertion. |
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. |
|---|---|
| Complexity: | Expected linear in maximum of number of values and num_buckets; worst case quadratic in number of values. If the initializer list is empty: constant, but with certain allocation linear in bucket_count() on first element insertion. |
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. |
|---|---|
| Complexity: | Same as for destructor plus copy constructor. |
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.
| Complexity: | Same as for destructor if allocators of this and that sets are equal; otherwise same as for destructor plus copy constructor. |
|---|
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. |
|---|---|
| Complexity: | Expected linear in number of values; worst case quadratic in number of values. |
Destroy all contained elements, free memory and destroy the set itself.
| Complexity: | Constant if value_type has a trivial destructor or the set is empty; linear in bucket_count() otherwise. |
|---|
bool empty () const;
| Returns: | true if the set is empty, i.e. if size () == 0. |
|---|---|
| Complexity: | Constant. |
size_type max_size () const;
| Returns: | The largest size this set could ever have. |
|---|---|
| Complexity: | Constant. |
size_type bucket_count () const;
Determine the number of buckets in the container. For sets with allocated bucket array this is the number of allocated buckets (not including private buckets, if any). For empty containers this is the number the container will allocate when needed. So, the return value is always non-zero.
| Returns: | Current number of buckets. |
|---|---|
| Complexity: | Constant. |
size_type max_bucket_count () const;
| Returns: | The largest number of buckets this set could ever have. |
|---|---|
| Complexity: | Constant. |
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. |
| Complexity: | O(bucket_count() / size()); constant in empty sets. |
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. |
| Complexity: | O(bucket_count() / size()); constant in empty sets. |
iterator end (); const_iterator end () const;
| Returns: | Past-the-end iterator for the set. |
|---|---|
| Complexity: | Constant. |
const_iterator cend () const;
| Returns: | Past-the-end iterator for the set. |
|---|---|
| Complexity: | Constant. |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
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);
Currently hint is simply ignored and effect is the same as insert (value).
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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
Compiler-specific
This function 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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
Compiler-specific
This function 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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
Special note
Purpose of this function in the standard 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 function exists mostly for compatibility reasons.
Compiler-specific
This function is defined only on C++0x compilers
template <typename... Args> std::pair <iterator, bool> emplace (const_iterator hint, Args&&... args);
Currently hint is simply ignored and effect is the same as emplace (args).
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. |
| Complexity: | Expected constant; worst case linear in size(). |
iterator erase (const_iterator position);
Erase the element at given position and return an iterator to the next one.
| Returns: | An iterator pointing to the next element or end() if there’s no next element. |
|---|---|
| Notes: | Never throws. This function has non-constant complexity and can perform poorly in almost empty sets. See also quick_erase() below. |
| Complexity: | O(bucket_count() / size()) amortized. |
Versioned
Since 1.4
void quick_erase (const_iterator position);
Erase the element at given position.
| Notes: | Never throws. |
|---|---|
| Complexity: | Constant. |
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. |
| Complexity: | O(n * bucket_count() / size()) amortized, where n is the distance between first and last. |
void clear ();
Erase all elements in the set.
| Notes: | Never throws. |
|---|---|
| Complexity: | Linear in bucket_count(). Constant for empty sets. |
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 the allocators are equal the function never throws. Otherwise strong exception safety. |
| Complexity: | Constant if the allocators are equal. Otherwise the same as copying the two sets, see the copy constructor. |
float load_factor () const;
| Returns: | Current load factor of the container. |
|---|---|
| Complexity: | Constant. |
float max_load_factor () const;
| Returns: | Maximum allowed load factor of the container. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant if load_factor() < set_to; otherwise same as for rehash(). |
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. |
|---|---|
| Complexity: | Expected linear in bucket_count(); worst case O(bucket_count() * size()). |
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 functions are used. This is exactly identical to:
set.rehash (std::ceil (num_elements / set.max_load_factor ()));
| Notes: | Invalidates iterators. |
|---|---|
| Complexity: | Same as for rehash(). |
hasher hash_function () const;
| Returns: | Set’s hash function object. |
|---|---|
| Complexity: | Constant. |
allocator_type get_allocator () const;
| Returns: | Set’s allocator. |
|---|---|
| Complexity: | Constant. |
operator== (const closed_hash_set <...>& set1, const closed_hash_set <...>& set2);
Compare the elements of the two sets.
See also more generic operator== in Cross-Container Functions section.
| 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. |
| Complexity: | Expected O(bucket_count()); worst case O(bucket_count() * size()). Optimizations: constant for comparing a set with itself or comparing sets of different sizes. |
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 function for details.
Versioned
Since 1.6
A function defined in a separate header <mct/hash-set-serialization.hpp>. Allows to serialize and unserialize closed hash sets using common Boost.Serialization mechanisms.
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
Important
In plain hash tables, increment and decrement operators of the iterators have non-constant O(bucket_count() / size()) amortized complexity. In particular, they can perform poorly in almost empty maps.
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. |
|---|---|
| Complexity: | Constant, but with certain allocation linear in bucket_count() on first element insertion. |
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. |
|---|---|
| Complexity: | Expected O(that.bucket_count()); worst case O(that.bucket_count() * that.size()). If that is empty: constant, but with certain allocation linear in bucket_count() on first element insertion. |
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.
| Complexity: | Constant. |
|---|
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. |
|---|---|
| Complexity: | Same as for copy constructor. |
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. |
|---|---|
| Complexity: | Expected linear in maximum of range size and num_buckets; worst case quadratic in range size. If first == last: constant, but with certain allocation linear in bucket_count() on first element insertion. |
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. |
|---|---|
| Complexity: | Expected linear in maximum of number of values and num_buckets; worst case quadratic in number of values. If the initializer list is empty: constant, but with certain allocation linear in bucket_count() on first element insertion. |
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. |
|---|---|
| Complexity: | Same as for destructor plus copy constructor. |
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.
| Complexity: | Same as for destructor if allocators of this and that maps are equal; otherwise same as for destructor plus copy constructor. |
|---|
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. |
|---|---|
| Complexity: | Expected linear in number of values; worst case quadratic in number of values. |
Destroy all contained elements, free memory and destroy the map itself.
| Complexity: | Constant if value_type has a trivial destructor or the map is empty; linear in bucket_count() otherwise. |
|---|
bool empty () const;
| Returns: | true if the map is empty, i.e. if size () == 0. |
|---|---|
| Complexity: | Constant. |
size_type max_size () const;
| Returns: | The largest size this map could ever have. |
|---|---|
| Complexity: | Constant. |
size_type bucket_count () const;
Determine the number of buckets in the container. For maps with allocated bucket array this is the number of allocated buckets (not including private buckets, if any). For empty containers this is the number the container will allocate when needed. So, the return value is always non-zero.
| Returns: | Current number of buckets. |
|---|---|
| Complexity: | Constant. |
size_type max_bucket_count () const;
| Returns: | The largest number of buckets this map could ever have. |
|---|---|
| Complexity: | Constant. |
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. |
| Complexity: | O(bucket_count() / size()); constant in empty maps. |
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. |
| Complexity: | O(bucket_count() / size()); constant in empty maps. |
iterator end (); const_iterator end () const;
| Returns: | Past-the-end iterator for the map. |
|---|---|
| Complexity: | Constant. |
const_iterator cend () const;
| Returns: | Past-the-end iterator for the map. |
|---|---|
| Complexity: | Constant. |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
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);
Currently hint is simply ignored and effect is the same as insert (value).
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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
Compiler-specific
This function 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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
Compiler-specific
This function 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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
Special note
Purpose of this function in the standard 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 function exists mostly for compatibility reasons.
Compiler-specific
This function is defined only on C++0x compilers
template <typename... Args> std::pair <iterator, bool> emplace (const_iterator hint, Args&&... args);
Currently hint is simply ignored and effect is the same as emplace (args).
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. |
| Complexity: | Expected constant; worst case linear in size(). |
iterator erase (const_iterator position);
Erase the element at given position and return an iterator to the next one.
| Returns: | An iterator pointing to the next element or end() if there’s no next element. |
|---|---|
| Notes: | Never throws. This function has non-constant complexity and can perform poorly in almost empty maps. See also quick_erase() below. |
| Complexity: | O(bucket_count() / size()) amortized. |
Versioned
Since 1.4
void quick_erase (const_iterator position);
Erase the element at given position.
| Notes: | Never throws. |
|---|---|
| Complexity: | Constant. |
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. |
| Complexity: | O(n * bucket_count() / size()) amortized, where n is the distance between first and last. |
void clear ();
Erase all elements in the map.
| Notes: | Never throws. |
|---|---|
| Complexity: | Linear in bucket_count(). Constant for empty maps. |
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 the allocators are equal the function never throws. Otherwise strong exception safety. |
| Complexity: | Constant if the allocators are equal. Otherwise the same as copying the two maps, see the copy constructor. |
float load_factor () const;
| Returns: | Current load factor of the container. |
|---|---|
| Complexity: | Constant. |
float max_load_factor () const;
| Returns: | Maximum allowed load factor of the container. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant if load_factor() < set_to; otherwise same as for rehash(). |
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. |
|---|---|
| Complexity: | Expected linear in bucket_count(); worst case O(bucket_count() * size()). |
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 functions are used. This is exactly identical to:
map.rehash (std::ceil (num_elements / map.max_load_factor ()));
| Notes: | Invalidates iterators. |
|---|---|
| Complexity: | Same as for rehash(). |
hasher hash_function () const;
| Returns: | Map’s hash function object. |
|---|---|
| Complexity: | Constant. |
allocator_type get_allocator () const;
| Returns: | Map’s allocator. |
|---|---|
| Complexity: | Constant. |
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.
See also more generic operator== in Cross-Container Functions section.
| 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. |
| Complexity: | Expected O(bucket_count()); worst case O(bucket_count() * size()). Optimizations: constant for comparing a map with itself or comparing maps of different sizes. |
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 function for details.
Versioned
Since 1.6
A function defined in a separate header <mct/hash-map-serialization.hpp>. Allows to serialize and unserialize closed hash maps using common Boost.Serialization mechanisms.
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 except sort() provide strong exception safety.
Note that linked_hash_set is not a sequence despite having many functions of the latter.
Important
Versioned
Since 1.4
On many platforms maximum number of buckets in a linked_hash_set is substantially less than would fit in memory, though still at least 1 billion. If that’s important to you, read about huge linked hash tables.
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
In linked tables, increment and decrement operators of the iterators have constant complexity.
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. |
|---|---|
| Complexity: | Constant, but with certain allocation linear in bucket_count() on first element insertion. |
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. |
|---|---|
| Complexity: | Expected linear in that.size(); worst case is quadratic in that.size(). If that is empty: constant, but with certain allocation linear in bucket_count() on first element insertion. |
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.
| Complexity: | Constant. |
|---|
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. |
|---|---|
| Complexity: | Same as for copy constructor. |
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. |
|---|---|
| Complexity: | Expected linear in maximum of range size and num_buckets; worst case quadratic in range size. If first == last: constant, but with certain allocation linear in bucket_count() on first element insertion. |
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. |
|---|---|
| Complexity: | Expected linear in maximum of number of values and num_buckets; worst case quadratic in number of values. If the initializer list is empty: constant, but with certain allocation linear in bucket_count() on first element insertion. |
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. |
|---|---|
| Complexity: | Same as for destructor plus copy constructor. |
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.
| Complexity: | Same as for destructor if allocators of this and that sets are equal; otherwise same as for destructor plus copy constructor. |
|---|
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. |
|---|---|
| Complexity: | Expected linear in number of values; worst case quadratic in number of values. |
Destroy all contained elements, free memory and destroy the set itself.
| Complexity: | Constant if value_type has a trivial destructor or the set is empty; linear in size() otherwise. |
|---|
bool empty () const;
| Returns: | true if the set is empty, i.e. if size () == 0. |
|---|---|
| Complexity: | Constant. |
size_type max_size () const;
| Returns: | The largest size this set could ever have. |
|---|---|
| Complexity: | Constant. |
size_type bucket_count () const;
Determine the number of buckets in the container. For sets with allocated bucket array this is the number of allocated buckets (not including private buckets, if any). For empty containers this is the number the container will allocate when needed. So, the return value is always non-zero.
| Returns: | Current number of buckets. |
|---|---|
| Complexity: | Constant. |
size_type max_bucket_count () const;
| Returns: | The largest number of buckets this set could ever have. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
iterator end (); const_iterator end () const;
| Returns: | Past-the-end iterator for the set. |
|---|---|
| Complexity: | Constant. |
const_iterator cend () const;
| Returns: | Past-the-end iterator for the set. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
reverse_iterator rend (); const_reverse_iterator rend () const;
| Returns: | Past-the-end reverse iterator for the set. |
|---|---|
| Complexity: | Constant. |
const_reverse_iterator crend () const;
| Returns: | Past-the-end reverse iterator for the set. |
|---|---|
| Complexity: | Constant. |
reference front (); const_reference front () const;
| Returns: | The first element in set’s iteration order. |
|---|---|
| Notes: | The set must not be empty. |
| Complexity: | Constant. |
reference back (); const_reference back () const;
| Returns: | The last element in set’s iteration order. |
|---|---|
| Notes: | The set must not be empty. |
| Complexity: | Constant. |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
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 function 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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
Compiler-specific
This function 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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
Compiler-specific
This function 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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
Compiler-specific
This function 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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
Special note
Purpose of this function in the standard 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 function exists mostly for compatibility reasons.
Compiler-specific
This function 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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
Special note
Purpose of similar functions in the standard 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 function exists mostly for compatibility reasons.
Compiler-specific
This function is defined only on C++0x compilers
template <typename... Args> std::pair <iterator, bool> emplace (const_iterator hint, Args&&... args);
Currently hint is simply ignored and effect is the same as emplace (args).
void pop_front ();
Erase the first element in the set’s iteration order.
| Notes: | The set must not be empty. Never throws. |
|---|---|
| Complexity: | Constant. |
void pop_back ();
Erase the last element in the set’s iteration order.
| Notes: | The set must not be empty. Never throws. |
|---|---|
| Complexity: | Constant. |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
iterator erase (const_iterator position);
Erase the element at given position and return an iterator to the next one.
| Returns: | An iterator pointing to the next element or end() if there’s no next element. |
|---|---|
| Notes: | Never throws. |
| Complexity: | Constant. |
Versioned
Since 1.4
void quick_erase (const_iterator position);
Erase the element at given position.
| Notes: | Never throws. |
|---|---|
| Complexity: | Constant. |
Special note
This function mainly exists for compatibility with closed_hash_set. In a linked set erase (iterator) function is of constant complexity, so quick_erase() doesn’t have any particular advantage.
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. |
| Complexity: | Linear in distance between first and last. |
void clear ();
Erase all elements in the set.
| Notes: | Never throws. |
|---|---|
| Complexity: | Linear in bucket_count(). Constant for empty sets. |
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 the allocators are equal the function never throws. Otherwise strong exception safety. |
| Complexity: | Constant if the allocators are equal. Otherwise the same as copying the two sets, see the copy constructor. |
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). |
|---|---|
| Complexity: | Constant. |
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.
| Complexity: | Linear in size(). |
|---|
Versioned
Since 1.6
void sort (); template <typename Compare> void sort (Compare compare);
Reorder set elements so that they are iterated in ascending order. In the first version elements are compared using operator<, in the second case — with the compare function object. Sorting is guaranteed to be stable. Comparison doesn’t have to be consistent with set’s equality predicate.
| Throws: | Exceptions thrown by the used comparison function. |
|---|---|
| Notes: | Basic exception safety: if an exception is thrown, order of elements is undefined. Does not invalidate iterators. |
| Complexity: | O(n log n) where n is the set size. |
float load_factor () const;
| Returns: | Current load factor of the container. |
|---|---|
| Complexity: | Constant. |
float max_load_factor () const;
| Returns: | Maximum allowed load factor of the container. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant if load_factor() < set_to; otherwise same as for rehash(). |
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. |
|---|---|
| Complexity: | Expected linear in bucket_count(); worst case quadratic in size(). |
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 functions are used. This is exactly identical to:
set.rehash (std::ceil (num_elements / set.max_load_factor ()));
| Notes: | Invalidates iterators. |
|---|---|
| Complexity: | Same as for rehash(). |
hasher hash_function () const;
| Returns: | Set’s hash function object. |
|---|---|
| Complexity: | Constant. |
allocator_type get_allocator () const;
| Returns: | Set’s allocator. |
|---|---|
| Complexity: | Constant. |
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.
See also more generic operator== in Cross-Container Functions section.
| 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. |
| Complexity: | Expected linear in size(); worst case is quadratic in size(). Optimizations: constant for comparing a set with itself or comparing sets of different sizes. |
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 function for details.
Versioned
Since 1.6
A function defined in a separate header <mct/hash-set-serialization.hpp>. Allows to serialize and unserialize linked hash sets using common Boost.Serialization mechanisms.
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 except sort() provide strong exception safety.
Note that linked_hash_map is not a sequence despite having many functions of the latter.
Important
Versioned
Since 1.4
On many platforms maximum number of buckets in a linked_hash_map is substantially less than would fit in memory, though still at least 1 billion. If that’s important to you, read about huge linked hash tables.
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
In linked tables, increment and decrement operators of the iterators have constant complexity.
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. |
|---|---|
| Complexity: | Constant, but with certain allocation linear in bucket_count() on first element insertion. |
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. |
|---|---|
| Complexity: | Expected linear in that.size(); worst case is quadratic in that.size(). If that is empty: constant, but with certain allocation linear in bucket_count() on first element insertion. |
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.
| Complexity: | Constant. |
|---|
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. |
|---|---|
| Complexity: | Same as for copy constructor. |
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. |
|---|---|
| Complexity: | Expected linear in maximum of range size and num_buckets; worst case quadratic in range size. If first == last: constant, but with certain allocation linear in bucket_count() on first element insertion. |
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. |
|---|---|
| Complexity: | Expected linear in maximum of number of values and num_buckets; worst case quadratic in number of values. If the initializer list is empty: constant, but with certain allocation linear in bucket_count() on first element insertion. |
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. |
|---|---|
| Complexity: | Same as for destructor plus copy constructor. |
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.
| Complexity: | Same as for destructor if allocators of this and that maps are equal; otherwise same as for destructor plus copy constructor. |
|---|
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. |
|---|---|
| Complexity: | Expected linear in number of values; worst case quadratic in number of values. |
Destroy all contained elements, free memory and destroy the map itself.
| Complexity: | Constant if value_type has a trivial destructor or the map is empty; linear in size() otherwise. |
|---|
bool empty () const;
| Returns: | true if the map is empty, i.e. if size () == 0. |
|---|---|
| Complexity: | Constant. |
size_type max_size () const;
| Returns: | The largest size this map could ever have. |
|---|---|
| Complexity: | Constant. |
size_type bucket_count () const;
Determine the number of buckets in the container. For maps with allocated bucket array this is the number of allocated buckets (not including private buckets, if any). For empty containers this is the number the container will allocate when needed. So, the return value is always non-zero.
| Returns: | Current number of buckets. |
|---|---|
| Complexity: | Constant. |
size_type max_bucket_count () const;
| Returns: | The largest number of buckets this map could ever have. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
iterator end (); const_iterator end () const;
| Returns: | Past-the-end iterator for the map. |
|---|---|
| Complexity: | Constant. |
const_iterator cend () const;
| Returns: | Past-the-end iterator for the map. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
reverse_iterator rend (); const_reverse_iterator rend () const;
| Returns: | Past-the-end reverse iterator for the map. |
|---|---|
| Complexity: | Constant. |
const_reverse_iterator crend () const;
| Returns: | Past-the-end reverse iterator for the map. |
|---|---|
| Complexity: | Constant. |
reference front (); const_reference front () const;
| Returns: | The first element in map’s iteration order. |
|---|---|
| Notes: | The map must not be empty. |
| Complexity: | Constant. |
reference back (); const_reference back () const;
| Returns: | The last element in map’s iteration order. |
|---|---|
| Notes: | The map must not be empty. |
| Complexity: | Constant. |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
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 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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
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 function 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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
Compiler-specific
This function 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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
Compiler-specific
This function 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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
Compiler-specific
This function 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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
Special note
Purpose of this function in the standard 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 function exists mostly for compatibility reasons.
Compiler-specific
This function 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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
Special note
Purpose of similar functions in the standard 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 function exists mostly for compatibility reasons.
Compiler-specific
This function is defined only on C++0x compilers
template <typename... Args> std::pair <iterator, bool> emplace (const_iterator hint, Args&&... args);
Currently hint is simply ignored and effect is the same as emplace (args).
void pop_front ();
Erase the first element in the map’s iteration order.
| Notes: | The map must not be empty. Never throws. |
|---|---|
| Complexity: | Constant. |
void pop_back ();
Erase the last element in the map’s iteration order.
| Notes: | The map must not be empty. Never throws. |
|---|---|
| Complexity: | Constant. |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
iterator erase (const_iterator position);
Erase the element at given position and return an iterator to the next one.
| Returns: | An iterator pointing to the next element or end() if there’s no next element. |
|---|---|
| Notes: | Never throws. |
| Complexity: | Constant. |
Versioned
Since 1.4
void quick_erase (const_iterator position);
Erase the element at given position.
| Notes: | Never throws. |
|---|---|
| Complexity: | Constant. |
Special note
This function mainly exists for compatibility with closed_hash_map. In a linked map erase (iterator) function is of constant complexity, so quick_erase() doesn’t have any particular advantage.
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. |
| Complexity: | Linear in distance between first and last. |
void clear ();
Erase all elements in the map.
| Notes: | Never throws. |
|---|---|
| Complexity: | Linear in bucket_count(). Constant for empty maps. |
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 the allocators are equal the function never throws. Otherwise strong exception safety. |
| Complexity: | Constant if the allocators are equal. Otherwise the same as copying the two maps, see the copy constructor. |
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). |
|---|---|
| Complexity: | Constant. |
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.
| Complexity: | Linear in size(). |
|---|
Versioned
Since 1.6
void sort (); template <typename Compare> void sort (Compare compare);
Reorder map elements so that they are iterated in ascending order. In the first version elements are compared using operator< on their keys, in the second case — with the compare function object. Sorting is guaranteed to be stable. Comparison doesn’t have to be consistent with map’s equality predicate; in particular, compare may completely ignore key part and compare the “mapped” part of elements.
| Throws: | Exceptions thrown by the used comparison function. |
|---|---|
| Notes: | Basic exception safety: if an exception is thrown, order of elements is undefined. Does not invalidate iterators. |
| Complexity: | O(n log n) where n is the map size. |
float load_factor () const;
| Returns: | Current load factor of the container. |
|---|---|
| Complexity: | Constant. |
float max_load_factor () const;
| Returns: | Maximum allowed load factor of the container. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant if load_factor() < set_to; otherwise same as for rehash(). |
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. |
|---|---|
| Complexity: | Expected linear in bucket_count(); worst case quadratic in size(). |
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 functions are used. This is exactly identical to:
map.rehash (std::ceil (num_elements / map.max_load_factor ()));
| Notes: | Invalidates iterators. |
|---|---|
| Complexity: | Same as for rehash(). |
hasher hash_function () const;
| Returns: | Map’s hash function object. |
|---|---|
| Complexity: | Constant. |
allocator_type get_allocator () const;
| Returns: | Map’s allocator. |
|---|---|
| Complexity: | Constant. |
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.
See also more generic operator== in Cross-Container Functions section.
| 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. |
| Complexity: | Expected linear in size(); worst case is quadratic in size(). Optimizations: constant for comparing a map with itself or comparing maps of different sizes. |
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 function for details.
Versioned
Since 1.6
A function defined in a separate header <mct/hash-map-serialization.hpp>. Allows to serialize and unserialize linked hash maps using common Boost.Serialization mechanisms.
Versioned
Since 1.2
A fast unordered container with unique values and stable iteration order.
Important
Versioned
Since 1.4
On many platforms maximum number of buckets in a forward_hash_set is substantially less than would fit in memory, though still at least 1 billion. If that’s important to you, read about huge forward hash tables.
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
In forward linked tables, increment operator of the iterators has constant complexity.
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. |
|---|---|
| Complexity: | Constant, but with certain allocation linear in bucket_count() on first element insertion. |
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. |
|---|---|
| Complexity: | Expected linear in that.size(); worst case is quadratic in that.size(). If that is empty: constant, but with certain allocation linear in bucket_count() on first element insertion. |
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.
| Complexity: | Constant. |
|---|
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. |
|---|---|
| Complexity: | Same as for copy constructor. |
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. |
|---|---|
| Complexity: | Expected linear in maximum of range size and num_buckets; worst case quadratic in range size. If first == last: constant, but with certain allocation linear in bucket_count() on first element insertion. |
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. |
|---|---|
| Complexity: | Expected linear in maximum of number of values and num_buckets; worst case quadratic in number of values. If the initializer list is empty: constant, but with certain allocation linear in bucket_count() on first element insertion. |
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. |
|---|---|
| Complexity: | Same as for destructor plus copy constructor. |
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.
| Complexity: | Same as for destructor if allocators of this and that sets are equal; otherwise same as for destructor plus copy constructor. |
|---|
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. |
|---|---|
| Complexity: | Expected linear in number of values; worst case quadratic in number of values. |
Destroy all contained elements, free memory and destroy the set itself.
| Complexity: | Constant if value_type has a trivial destructor or the set is empty; linear in size() otherwise. |
|---|
bool empty () const;
| Returns: | true if the set is empty, i.e. if size () == 0. |
|---|---|
| Complexity: | Constant. |
size_type max_size () const;
| Returns: | The largest size this set could ever have. |
|---|---|
| Complexity: | Constant. |
size_type bucket_count () const;
Determine the number of buckets in the container. For sets with allocated bucket array this is the number of allocated buckets (not including private buckets, if any). For empty containers this is the number the container will allocate when needed. So, the return value is always non-zero.
| Returns: | Current number of buckets. |
|---|---|
| Complexity: | Constant. |
size_type max_bucket_count () const;
| Returns: | The largest number of buckets this set could ever have. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
iterator end (); const_iterator end () const;
| Returns: | Past-the-end iterator for the set. |
|---|---|
| Complexity: | Constant. |
const_iterator cend () const;
| Returns: | Past-the-end iterator for the set. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
const_iterator cbefore_end () const;
| Returns: | A 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. |
|---|---|
| Complexity: | Constant. |
reference front (); const_reference front () const;
| Returns: | The first element in set’s iteration order. |
|---|---|
| Notes: | The set must not be empty. |
| Complexity: | Constant. |
reference back (); const_reference back () const;
| Returns: | The last element in set’s iteration order. |
|---|---|
| Notes: | The set must not be empty. |
| Complexity: | Constant. |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
Compiler-specific
This function 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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
Compiler-specific
This function 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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
Compiler-specific
This function 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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
Special note
Purpose of similar function in the standard 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 function exists mostly for compatibility reasons.
Compiler-specific
This function 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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
Special note
Purpose of similar functions in the standard 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 function exists mostly for compatibility reasons.
void pop_front ();
Erase the first element in the set’s iteration order.
| Notes: | The set must not be empty. Never throws. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
void erase_after (const_iterator position, const_iterator last);
Erase a range of elements.
| Notes: | Never throws. |
|---|---|
| Complexity: | Linear in distance between position and last. |
void clear ();
Erase all elements in the set.
| Notes: | Never throws. |
|---|---|
| Complexity: | Linear in bucket_count(). Constant for empty sets. |
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 map’s) hash function, equality predicates or allocator. |
|---|---|
| Notes: | If the allocators are equal the function never throws. Otherwise strong exception safety. |
| Complexity: | Constant if the allocators are equal. Otherwise the same as copying the two maps, see the copy constructor. |
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. |
|---|---|
| Complexity: | Constant. |
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.
| Complexity: | Linear in size(). |
|---|
Versioned
Since 1.6
void sort (); template <typename Compare> void sort (Compare compare);
Reorder set elements so that they are iterated in ascending order. In the first version elements are compared using operator<, in the second case — with the compare function object. Sorting is guaranteed to be stable. Comparison doesn’t have to be consistent with set’s equality predicate.
| Throws: | Exceptions thrown by the used comparison function. |
|---|---|
| Notes: | Basic exception safety: if an exception is thrown, order of elements is undefined. Does not invalidate iterators. |
| Complexity: | O(n log n) where n is the set size. |
float load_factor () const;
| Returns: | Current load factor of the container. |
|---|---|
| Complexity: | Constant. |
float max_load_factor () const;
| Returns: | Maximum allowed load factor of the container. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant if load_factor() < set_to; otherwise same as for rehash(). |
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. |
|---|---|
| Complexity: | Expected linear in bucket_count(); worst case quadratic in size(). |
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 functions are used. This is exactly identical to:
set.rehash (std::ceil (num_elements / set.max_load_factor ()));
| Notes: | Invalidates iterators. |
|---|---|
| Complexity: | Same as for rehash(). |
hasher hash_function () const;
| Returns: | Set’s hash function object. |
|---|---|
| Complexity: | Constant. |
allocator_type get_allocator () const;
| Returns: | Set’s allocator. |
|---|---|
| Complexity: | Constant. |
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.
See also more generic operator== in Cross-Container Functions section.
| 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. |
| Complexity: | Expected linear in size(); worst case is quadratic in size(). Optimizations: constant for comparing a set with itself or comparing sets of different sizes. |
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 function for details.
Versioned
Since 1.6
A function defined in a separate header <mct/hash-set-serialization.hpp>. Allows to serialize and unserialize forward hash sets using common Boost.Serialization mechanisms.
Versioned
Since 1.2
A fast unordered container mapping unique keys to arbitrary values and providing stable iteration order.
Important
Versioned
Since 1.4
On many platforms maximum number of buckets in a forward_hash_map is substantially less than would fit in memory, though still at least 1 billion. If that’s important to you, read about huge forward hash tables.
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
In forward linked tables, increment operator of the iterators has constant complexity.
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. |
|---|---|
| Complexity: | Constant, but with certain allocation linear in bucket_count() on first element insertion. |
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. |
|---|---|
| Complexity: | Expected linear in that.size(); worst case is quadratic in that.size(). If that is empty: constant, but with certain allocation linear in bucket_count() on first element insertion. |
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.
| Complexity: | Constant. |
|---|
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. |
|---|---|
| Complexity: | Same as for copy constructor. |
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. |
|---|---|
| Complexity: | Expected linear in maximum of range size and num_buckets; worst case quadratic in range size. If first == last: constant, but with certain allocation linear in bucket_count() on first element insertion. |
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. |
|---|---|
| Complexity: | Expected linear in maximum of number of values and num_buckets; worst case quadratic in number of values. If the initializer list is empty: constant, but with certain allocation linear in bucket_count() on first element insertion. |
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. |
|---|---|
| Complexity: | Same as for destructor plus copy constructor. |
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.
| Complexity: | Same as for destructor if allocators of this and that maps are equal; otherwise same as for destructor plus copy constructor. |
|---|
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. |
|---|---|
| Complexity: | Expected linear in number of values; worst case quadratic in number of values. |
Destroy all contained elements, free memory and destroy the map itself.
| Complexity: | Constant if value_type has a trivial destructor or the map is empty; linear in size() otherwise. |
|---|
bool empty () const;
| Returns: | true if the map is empty, i.e. if size () == 0. |
|---|---|
| Complexity: | Constant. |
size_type max_size () const;
| Returns: | The largest size this map could ever have. |
|---|---|
| Complexity: | Constant. |
size_type bucket_count () const;
Determine the number of buckets in the container. For maps with allocated bucket array this is the number of allocated buckets (not including private buckets, if any). For empty containers this is the number the container will allocate when needed. So, the return value is always non-zero.
| Returns: | Current number of buckets. |
|---|---|
| Complexity: | Constant. |
size_type max_bucket_count () const;
| Returns: | The largest number of buckets this map could ever have. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
iterator end (); const_iterator end () const;
| Returns: | Past-the-end iterator for the map. |
|---|---|
| Complexity: | Constant. |
const_iterator cend () const;
| Returns: | Past-the-end iterator for the map. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
const_iterator cbefore_end () const;
| Returns: | A 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. |
|---|---|
| Complexity: | Constant. |
reference front (); const_reference front () const;
| Returns: | The first element in map’s iteration order. |
|---|---|
| Notes: | The map must not be empty. |
| Complexity: | Constant. |
reference back (); const_reference back () const;
| Returns: | The last element in map’s iteration order. |
|---|---|
| Notes: | The map must not be empty. |
| Complexity: | Constant. |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
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. |
| Complexity: | Expected constant; worst case linear in size(). |
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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
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 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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
Compiler-specific
This function 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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
Compiler-specific
This function 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 function 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. |
| Complexity: | Same as calling single-item insert() for each value separately. |
Compiler-specific
This function 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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
Special note
Purpose of similar function in the standard 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 function exists mostly for compatibility reasons.
Compiler-specific
This function 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. |
| Complexity: | Expected constant (amortized); worst case linear in size(). |
Special note
Purpose of similar functions in the standard 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 function exists mostly for compatibility reasons.
void pop_front ();
Erase the first element in the map’s iteration order.
| Notes: | The map must not be empty. Never throws. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant. |
void erase_after (const_iterator position, const_iterator last);
Erase a range of elements.
| Notes: | Never throws. |
|---|---|
| Complexity: | Linear in distance between position and last. |
void clear ();
Erase all elements in the map.
| Notes: | Never throws. |
|---|---|
| Complexity: | Linear in bucket_count(). Constant for empty maps. |
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 the allocators are equal the function never throws. Otherwise strong exception safety. |
| Complexity: | Constant if the allocators are equal. Otherwise the same as copying the two maps, see the copy constructor. |
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. |
|---|---|
| Complexity: | Constant. |
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.
| Complexity: | Linear in size(). |
|---|
Versioned
Since 1.6
void sort (); template <typename Compare> void sort (Compare compare);
Reorder map elements so that they are iterated in ascending order. In the first version elements are compared using operator< on their keys, in the second case — with the compare function object. Sorting is guaranteed to be stable. Comparison doesn’t have to be consistent with map’s equality predicate; in particular, compare may completely ignore key part and compare the “mapped” part of elements.
| Throws: | Exceptions thrown by the used comparison function. |
|---|---|
| Notes: | Basic exception safety: if an exception is thrown, order of elements is undefined. Does not invalidate iterators. |
| Complexity: | O(n log n) where n is the map size. |
float load_factor () const;
| Returns: | Current load factor of the container. |
|---|---|
| Complexity: | Constant. |
float max_load_factor () const;
| Returns: | Maximum allowed load factor of the container. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | Constant if load_factor() < set_to; otherwise same as for rehash(). |
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. |
|---|---|
| Complexity: | Expected linear in bucket_count(); worst case quadratic in size(). |
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 functions are used. This is exactly identical to:
map.rehash (std::ceil (num_elements / map.max_load_factor ()));
| Notes: | Invalidates iterators. |
|---|---|
| Complexity: | Same as for rehash(). |
hasher hash_function () const;
| Returns: | Map’s hash function object. |
|---|---|
| Complexity: | Constant. |
allocator_type get_allocator () const;
| Returns: | Map’s allocator. |
|---|---|
| Complexity: | Constant. |
operator== (const forward_hash_map <...>& map1, const forward_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 (singly) linked, containers are still maps, i.e. iteration order is irrelevant to container equality.
See also more generic operator== in Cross-Container Functions section.
| 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. |
| Complexity: | Expected linear in size(); worst case is quadratic in size(). Optimizations: constant for comparing a map with itself or comparing maps of different sizes. |
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 function for details.
Versioned
Since 1.6
A function defined in a separate header <mct/hash-map-serialization.hpp>. Allows to serialize and unserialize forward hash maps using common Boost.Serialization mechanisms.
Versioned
Since 1.4
In addition to the normal linked and forward sets and maps, there are also “huge” variants. These are completely interface-identical to the “non-huge” version and are therefore not documented in details; simply see the reference section for the corresponding normal container.
The only difference between normal and “huge” containers is that the number of buckets in the former is capped at roughly 1 billion [4] on most platforms, while in “huge” ones it is limited only by available memory. However, on many platforms, most notably widespread x86-64, normal containers use considerably less memory.
Since bucket count limit is extremely unlikely to be a concern and because of the memory footprint advantage, it was decided to provide the somewhat limited containers as the default.
It is also worth noting that on platforms where pointer size doesn’t exceed size of int, for example on x86-32, normal and “huge” containers will be exactly the same, though still different classes.
| [4] | Precisely (std::numeric_limits <int>::max () + 1) / 2, which is e.g. 1,073,741,824 on x86-64 machines. |
It is possible to compare containers of certain distinct types.
Versioned
Since 1.4
operator== (const hash_table_type_1& table1, const hash_table_type_2& table2);
Compare the elements of the two compatible containers. Two containers are compatible when all of the following are true:
To put it differently, containers or their types can differ in:
As an example, you can compare closed_hash_set <int> with forward_hash_set <int>, but not linked_hash_map <int, bool> with linked_hash_map <int, long>.
For maps the second element components (mapped_type) are compared with operator==, while the first (key_type) — with the map equality predicate. Iteration order of either container does not influence comparison result, even for linked containers. I.e. MCT hash tables are sets and maps, which are essentially unordered concepts.
| Returns: | true if the containers are equal, i.e. contain the same elements. |
|---|---|
| Throws: | Exceptions thrown by hash function or equality predicate of either container. |
| Notes: | Result does not depend on either containers’ iteration order. It is undefined if the containers’ equality predicates are not equivalent. |
| Complexity: | If both tables are closed: expected O(bucket_count()); worst case O(bucket_count() * size()). If at least one table is linked or forward: expected linear in size(); worst case is quadratic in size(). Optimizations: constant for comparing a table with itself or comparing tables of different sizes. |
Versioned
Since 1.4
operator!= (const hash_table_type_1& table1, const hash_table_type_2& table2);
See operator== for details.
These member types and functions 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 member functions 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 function is more robust and much faster than comparing to all valid iterators. |
| Complexity: | Constant. |
bool valid_iterator_range (const_iterator first, const_iterator last) const;
For a range to be valid, both its ends 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. |
|---|---|
| Complexity: | Constant if either first or last is invalid and not past-the-end; otherwise linear in distance between first and last or, for invalid ranges, first and end(). |
size_type used_memory () const;
Compute the total amount of memory used by the container. This includes both the size of the container structure (i.e. what you’d get by using sizeof()) and the size of dynamically allocated memory used to store the buckets. If the container is empty and doesn’t have an allocated bucket array, returned value is equal to the size of the container structure even though bucket_count() returns a non-zero value.
| Returns: | Total amount of memory, in bytes. |
|---|---|
| Complexity: | Constant. |
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. |
|---|---|
| Complexity: | At least linear in bucket_count(). |
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. |
| Complexity: | At least linear in bucket_count(). |
Versioned
Since 1.6
MCT provides a few type properties to help with metaprogramming that involves library containers. Using these structures it is impossible to distinguish normal and “huge” containers (for linked and forward tables), but since the types have no important differences, that must not be a problem.
The class is defined in header <mct/hash-set.hpp>. Determines if type is an MCT set container. E.g.:
is_set <closed_hash_set <int> >::value == true
Note, however, that it works only for MCT containers. For example:
is_set <std::set <int> >::value == false
The class is defined in header <mct/hash-map.hpp>. Determines if type is an MCT map container. E.g.:
is_map <linked_hash_map <int, long> >::value == true
Note, however, that it works only for MCT containers. For example:
is_map <std::map <int, long> >::value == false
These are defined if either <mct/hash-set.hpp> or <mct/hash-map.hpp> is included. Determine if type is an MCT closed, linked or forward hash table (either a set or a map) correspondingly. For instance:
is_closed <forward_hash_set <short> >::value == false is_linked <forward_hash_set <short> >::value == false is_forward <forward_hash_set <short> >::value == true
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 currently. See examples below, in the sections describing the mentioned structure.
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 property 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; must be either of an integral type other than bool or support external use in turn 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>
{ };
}
Note that “will not use itself” precondition includes assignment operator too. In the example above, MyClass must have an explicitly defined assignment operator as one implicitly generated by compiler would alter _unused_field.
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>
: extern_use_field <MyCompositeClass, MyClass, &MyCompositeClass::a_field>
{ };
}
Versioned
Since 1.4
A type-trait-like template that can be used to lookup a storage type for given Value when external use is desired. It is not meant to be specialized.
For any Value it is guaranteed that intrusive_storage <Value>::type:
Additionally, it may provide external use specification when Value does not — that’s the whole purpose of the template. For instance, this is the case for std::pair <int, char> at least on modern platforms. Currently this is used by closed_hash_* containers to switch to a more efficient implementation when possible.
In a sense this template serves the same purpose as specializing external_use, but works mostly with types you have no control over, e.g. those in std namespace. It also works automatically, without need to code anything.
template <typename Value> struct intrusive_storage;
Template parameters:
Value: The type for which storage is requested; must be default-constructible
type: Recommended storage type for the Value type; see description above for guarantees and purpose
Deprecated
Deprecation description
Deprecated since 1.4. Use improved extern_use_field instead.
template <typename To,
typename From,
From To::* field>
struct propagate_external_use;
Deriving an external_use specialization from:
propagate_external_use <A, B, &A::x>
gives exactly the same result as from:
extern_use_field <A, B, &A::x>
The structure was meaningful in 1.2, but since 1.4 extern_use_field covers its intended purpose too.
In addition to the general debugging functions 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. (The kind of slowdown this causes can be assessed from MCT’s own test suite as self-validation is part of the reason it takes time to pass.)
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 non-zero 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.
This section lists all public header files in MCT along with types defined in them. This information is also available in other places of the reference, but this section summarizes it.
Defines several set hash table types along with associated type property:
Additionally defined type properties:
Finally, this header is guaranteed to also define all the types provided by intrusiveness.hpp.
Defines several map hash table types along with associated type property:
Additionally defined type properties:
Finally, this header is guaranteed to also define all the types provided by intrusiveness.hpp.
Versioned
Since 1.2
Defines all the types used in external use specification:
This header is guaranteed to be included if either hash-set.hpp or hash-map.hpp or their serialization variants is included.
Versioned
Since 1.6
Doesn’t define any types, but overloads boost::serialization::serialize() for set hash tables. Including this header if Boost.Serialization is not installed will lead to compilation errors. The header includes hash-set.hpp itself, so there is no need to include both.
Versioned
Since 1.6
Doesn’t define any types, but overloads boost::serialization::serialize() for map hash tables. Including this header if Boost.Serialization is not installed will lead to compilation errors. The header includes hash-map.hpp itself, so there is no need to include both.
Semi-internal header defining all the symbols listed in Preprocessor Symbols section. Including any other MCT header is guaranteed to include config.hpp.
This section concisely lists new functionality, backward-incompatible changes and deprecations by stable version.
Copyright © 2009, 2010, 2011, 2012, 2013 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.