Outline
Purpose
Provide an STL-compliant unordered_multimap container.
Classes
Canonical header: bsl_unordered_map.h
- See also
- package bos+stdhdrs in the bos package group
Description
This component defines a single class template, bsl::unordered_multimap, implementing the standard container holding a collection of (possibly equivalent) keys, each mapped to an associated value (with minimal guarantees on ordering).
An instantiation of unordered_multimap is an allocator-aware, value-semantic type whose salient attributes are its size (number of keys) and the set of key-value pairs the unordered_multimap contains, without regard to their order. If unordered_multimap is instantiated with a key type or mapped-value type that is not itself value-semantic, then it will not retain all of its value-semantic qualities. In particular, if ether the key or value type cannot be tested for equality, then an unordered_multimap containing that type cannot be tested for equality. It is even possible to instantiate unordered_multimap with a key or value type that does not have an accessible copy-constructor, in which case the unordered_multimap will not be copyable. Note that the equality operator for each key-value pair is used to determine when two unordered_multimap objects have the same value, and not the object of EQUAL type supplied at construction.
An unordered_multimap meets the requirements of an unordered associative container with forward iterators in the C++11 standard [23.2.5]. The unordered_multimap implemented here adheres to the C++11 standard when compiled with a C++11 compiler, and makes the best approximation when compiled with a C++03 compiler. In particular, for C++03 we emulate move semantics, but limit forwarding (in emplace) to const lvalues, and make no effort to emulate noexcept or initializer-lists.
Requirements on KEY and VALUE
An unordered_multimap is a fully Value-Semantic Type (see bsldoc_glossary ) only if the supplied KEY and VALUE template parameters are themselves fully value-semantic. It is possible to instantiate an unordered_multimap with KEY and VALUE parameter arguments that do not provide a full set of value-semantic operations, but then some methods of the container may not be instantiable. The following terminology, adopted from the C++11 standard, is used in the function documentation of unordered_multimap to describe a function's requirements for the KEY and VALUE template parameters. These terms are also defined in section [17.6.3.1] of the C++11 standard. Note that, in the context of an unordered_multimap instantiation, the requirements apply specifically to the unordered multimap's element type, value_type, which is an alias for pair<const KEY, VALUE>.
Legend
X - denotes an allocator-aware container type (unordered_multimap ) T - value_type associated with X A - type of the allocator used by X m - lvalue of type A (allocator) p, - address (T *) of uninitialized storage for a T within an X rv - rvalue of type (non-const) T v - rvalue or lvalue of type (possibly const) T args - 0 or more arguments
The following terms are used to more precisely specify the requirements on template parameter types in function-level documentation.
default-insertable: T has a default constructor. More precisely, T is default-insertable into X means that the following expression is well-formed:
allocator_traits<A>::construct(m, p)
move-insertable: T provides a constructor that takes an rvalue of type (non-const) T. More precisely, T is move-insertable into X means that the following expression is well-formed:
allocator_traits<A>::construct(m, p, rv)
copy-insertable: T provides a constructor that takes an lvalue or rvalue of type (possibly const) T. More precisely, T is copy-insertable into X means that the following expression is well-formed:
allocator_traits<A>::construct(m, p, v)
move-assignable: T provides an assignment operator that takes an rvalue of type (non-const) T.
copy-assignable: T provides an assignment operator that takes an lvalue or rvalue of type (possibly const) T.
emplace-constructible: T is emplace-constructible into X from args means that the following expression is well-formed:
allocator_traits<A>::construct(m, p, args)
erasable: T provides a destructor. More precisely, T is erasable from X means that the following expression is well-formed:
allocator_traits<A>::destroy(m, p)
equality-comparable: The type provides an equality-comparison operator that defines an equivalence relationship and is both reflexive and transitive.
Requirements on HASH and EQUAL
The (template parameter) types HASH and EQUAL must be copy-constructible function-objects. Note that this requirement is somewhat stronger than the requirement currently in the standard; see the discussion for Issue 2215 (http://cplusplus.github.com/LWG/lwg-active.html#2215);
HASH shall support a function call operator compatible with the following statements:
HASH hash;
KEY key;
std::size_t result = hash(key);
where the definition of the called function meets the requirements of a hash function, as specified in {bslstl_hash |Standard Hash Function}.
EQUAL shall support a function call operator compatible with the following statements:
EQUAL equal;
KEY key1, key2;
bool result = equal(key1, key2);
where the definition of the called function defines an equivalence relationship on keys that is both reflexive and transitive.
HASH and EQUAL function-objects are further constrained such that any two objects whose keys compare equivalent by the comparator shall also produce the same value from the hasher.
Memory Allocation
The type supplied as an unordered multimap's ALLOCATOR template parameter determines how that unordered multimap will allocate memory. The unordered_multimap template supports allocators meeting the requirements of the C++11 standard [17.6.3.5]. In addition, it supports scoped-allocators derived from the bslma::Allocator memory allocation protocol. Clients intending to use bslma-style allocators should use the template's default ALLOCATOR type. The default type for the ALLOCATOR template parameter, bsl::allocator, provides a C++11 standard-compatible adapter for a bslma::Allocator object.
bslma-Style Allocators
If the (template parameter) type ALLOCATOR of an unordered_multimap instantiation is bsl::allocator, then objects of that unordered multimap type will conform to the standard behavior of a bslma-allocator-enabled type. Such an unordered multimap accepts an optional bslma::Allocator argument at construction. If the address of a bslma::Allocator object is explicitly supplied at construction, it is used to supply memory for the unordered multimap throughout its lifetime; otherwise, the unordered multimap will use the default allocator installed at the time of the unordered multimap's construction (see bslma_default ). In addition to directly allocating memory from the indicated bslma::Allocator, an unordered multimap supplies that allocator's address to the constructors of contained objects of the (template parameter) types KEY and VALUE, if respectively, the types define the bslma::UsesBslmaAllocator trait.
Operations
This section describes the run-time complexity of operations on instances of unordered_multimap :
Legend
------
'K' - (template parameter) type 'KEY' of 'unordered_multimap'
'V' - (template parameter) type 'VALUE' of 'unordered_multimap'
'a', 'b' - two distinct objects of type 'unordered_multimap<K, V>'
'rv' - modifiable rvalue of type 'unordered_multimap<K, V>'
'n', 'm' - number of elements in 'a' and 'b', respectively
'w' - number of buckets of 'a'
'value_type' - 'pair<const K, V>'
'hf' - hash function for objects of type 'K'
'eq' - equivalence comparator for objects of type 'K'
'al' - STL-style memory allocator
'k' - an object of type 'K'
'v' - object of type 'V'
'vt' - object of type 'value_type'
'rvt' - modifiable rvalue of type 'value_type'
'idx' - bucket index
'li' - object of type 'initializer_list<value_type>'
'i1', 'i2' - two iterators defining a sequence of 'value_type' objects
'p1', 'p2' - two iterators belonging to 'a'
distance(i1,i2) - the number of elements in the range '[i1 .. i2)'
distance(p1,p2) - the number of elements in the range '[p1 .. p2)'
'z' - floating point value representing a load factor
+----------------------------------------------------+--------------------+
| Operation | Complexity |
+====================================================+====================+
| unordered_multimap<K, V> a; (dflt construction) | O[1] |
| unordered_multimap<K, V> a(al); | |
+----------------------------------------------------+--------------------+
| unordered_multimap<K, V> a(rv);(move construction) | O[1] if 'a' and |
| unordered_multimap<K, V> a(rv, al); | 'rv' use the same |
| | allocator, |
| | O[n] otherwise |
+----------------------------------------------------+--------------------+
| unordered_multimap<K, V> a(b); (copy construction) | Average: O[n] |
| unordered_multimap<K, V> a(b, al); | Worst: O[n^2] |
+----------------------------------------------------+--------------------+
| unordered_multimap<K, V> a(w); | O[n] |
| unordered_multimap<K, V> a(w, al); | |
| unordered_multimap<K, V> a(w, hf); | |
| unordered_multimap<K, V> a(w, hf, al); | |
| unordered_multimap<K, V> a(w, hf, eq); | |
| unordered_multimap<K, V> a(w, hf, eq, al); | |
+----------------------------------------------------+--------------------+
| unordered_multimap<K, V> a(i1, i2); | Average: O[N] |
| unordered_multimap<K, V> a(i1, i2, al); | Worst: O[N^2] |
| unordered_multimap<K, V> a(i1, i2, w); | where N = |
| unordered_multimap<K, V> a(i1, i2, w, al); | distance(i1, i2)] |
| unordered_multimap<K, V> a(i1, i2, w, hf); | |
| unordered_multimap<K, V> a(i1, i2, w, hf, al); | |
| unordered_multimap<K, V> a(i1, i2, w, hf, eq); | |
| unordered_multimap<K, V> a(i1, i2, w, hf, eq, al); | |
+----------------------------------------------------+--------------------+
| unordered_multimap<K, V> a(li); | Average: O[N] |
| unordered_multimap<K, V> a(li, al); | Worst: O[N^2] |
| unordered_multimap<K, V> a(li, w); | where N = |
| unordered_multimap<K, V> a(li, w, al); | 'li.size()'|
| unordered_multimap<K, V> a(li, w, hf); | |
| unordered_multimap<K, V> a(li, w, hf, al); | |
| unordered_multimap<K, V> a(li, w, hf, eq); | |
| unordered_multimap<K, V> a(li, w, hf, eq, al); | |
+----------------------------------------------------+--------------------+
| a.~unordered_multimap<K, V>(); (destruction) | O[n] |
+----------------------------------------------------+--------------------+
| a = rv; (move assignment) | O[1] if 'a' and |
| | 'rv' use the same |
| | allocator, |
| | O[n] otherwise |
+----------------------------------------------------+--------------------+
| a = b; (copy assignment) | Average: O[n] |
| | Worst: O[n^2] |
+----------------------------------------------------+--------------------+
| a = li; | Average: O[N] |
| | Worst: O[N^2] |
| | where N = |
| | 'li.size()'|
+----------------------------------------------------+--------------------+
| a.begin(), a.end(), a.cbegin(), a.cend() | O[1] |
+----------------------------------------------------+--------------------+
| a.begin(idx), a.end(idx), a.cbegin(idx), | O[1] |
| a.cend(idx) | |
+----------------------------------------------------+--------------------+
| a == b, a != b | Best: O[n] |
| | Worst: O[n^2] |
+----------------------------------------------------+--------------------+
| a.swap(b), swap(a, b) | O[1] |
+----------------------------------------------------+--------------------+
| a.key_eq() | O[1] |
+----------------------------------------------------+--------------------+
| a.hash_function() | O[1] |
+----------------------------------------------------+--------------------+
| a.size() | O[1] |
+----------------------------------------------------+--------------------+
| a.max_size() | O[1] |
+----------------------------------------------------+--------------------+
| a.empty() | O[1] |
+----------------------------------------------------+--------------------+
| a.allocator() | O[1] |
+----------------------------------------------------+--------------------+
| a.insert(vt) | Average: O[1] |
| a.insert(rvt) | Worst: O[n] |
| a.emplace(Args&&...) | |
+----------------------------------------------------+--------------------+
| a.insert(p1, vt) | Average: O[1] |
| a.insert(p1, rvt) | Worst: O[n] |
| a.emplace(p1, Args&&...) | |
+----------------------------------------------------+--------------------+
| a.insert(i1, i2) | Average: O[ |
| | distance(i1, i2)]|
| | Worst: O[n * |
| | distance(i1, i2)]|
+----------------------------------------------------+--------------------+
| a.insert(li); | Average: O[N] |
| | Worst: O[n * N] |
| | where N = |
| | 'li.size()'|
+----------------------------------------------------+--------------------+
| a.erase(p1) | Average: O[1] |
| | Worst: O[n] |
+----------------------------------------------------+--------------------+
| a.erase(k) | Average: |
| | O[a.count(k)]|
| | Worst: |
| | O[n] |
+----------------------------------------------------+--------------------+
| a.erase(p1, p2) | Average: O[ |
| | distance(p1, p2)]|
| | Worst: O[n] |
+----------------------------------------------------+--------------------+
| a.clear() | O[n] |
+----------------------------------------------------+--------------------+
| a.contains(k) | Average: O[1] |
| | Worst: O[n] |
+----------------------------------------------------+--------------------+
| a.find(k) | Average: O[1] |
| | Worst: O[n] |
+----------------------------------------------------+--------------------+
| a.count(k) | Average: O[1] |
| | Worst: O[n] |
+----------------------------------------------------+--------------------+
| a.equal_range(k) | Average: O[ |
| | a.count(k)]|
| | Worst: O[n] |
+----------------------------------------------------+--------------------+
| a.bucket_count() | O[1] |
+----------------------------------------------------+--------------------+
| a.max_bucket_count() | O[1] |
+----------------------------------------------------+--------------------+
| a.bucket(k) | O[1] |
+----------------------------------------------------+--------------------+
| a.bucket_size(idx) | O[1] |
+----------------------------------------------------+--------------------+
| a.load_factor() | O[1] |
+----------------------------------------------------+--------------------+
| a.max_load_factor() | O[1] |
| a.max_load_factor(z) | Average: O[1] |
+----------------------------------------------------+--------------------+
| a.rehash(w) | Average: O[n] |
| | Worst: O[n^2] |
+----------------------------------------------------+--------------------+
| a.reserve(w) | Average: O[n] |
| | Worst: O[n^2] |
+----------------------------------------------------+--------------------+
Iterator, Pointer, and Reference Invalidation
No method of unordered_multimap invalidates a pointer or reference to an element in the unordered multimap unless it erases that element, such as any erase overload, clear, or the destructor (which erases all elements). Pointers and references are stable through a rehash.
Iterators to elements in the container are invalidated by any rehash, so iterators may be invalidated by an insert or emplace call if it triggers a rehash (but not otherwise). Iterators to specific elements are also invalidated when those elements are erased. Note that although the end iterator does not refer to any element in the container, it may be invalidated by any non-const method.
Unordered Multimap Configuration
The unordered multimap has interfaces that can provide insight into, and control of, its inner workings. The syntax and semantics of these interfaces for bsl::unordered_multimap are identical to those of bsl::unordered_map. See the discussion in {bslstl_unorderedmap |Unordered Map Configuration} and the illustrative material in {bslstl_unorderedmap |Example 2}.
Practical Requirements on HASH
An important factor in the performance of an unordered multimap (and any of the other unordered containers) is the choice of a hash function. Please see the discussion in {bslstl_unorderedmap |Practical Requirements on HASH}.
Usage
In this section we show intended use of this component.
Example 1: Creating a Concordance
Unordered multimaps are useful in situations when there is no meaningful way to compare key values, when the order of the keys is irrelevant to the problem domain, or (even if there is a meaningful ordering) the benefit of ordering the results is outweighed by the higher performance provided by unordered multimaps (compared to ordered multimaps).
One uses a multimap (ordered or unordered) when there may be more than one mapped value associated with a key value. In this example we will use bslstl_unorderedmultimap to create a concordance (an index of where each unique word appears in the set of documents).
Our source of documents is a set of statically initialized arrays:
static char document0[] =
" IN CONGRESS, July 4, 1776.\n"
"\n"
" The unanimous Declaration of the thirteen united States of America,\n"
"\n"
" When in the Course of human events, it becomes necessary for one\n"
" people to dissolve the political bands which have connected them with\n"
" another, and to assume among the powers of the earth, the separate\n"
" and equal station to which the Laws of Nature and of Nature's God\n"
" entitle them, a decent respect to the opinions of mankind requires\n"
" that they should declare the causes which impel them to the\n"
" separation. We hold these truths to be self-evident, that all men\n"
" are created equal, that they are endowed by their Creator with\n"
" certain unalienable Rights, that among these are Life, Liberty and\n"
" the pursuit of Happiness.--That to secure these rights, Governments\n"
" are instituted among Men, deriving their just powers from the consent\n"
" of the governed, --That whenever any Form of Government becomes\n"
...
" States may of right do. And for the support of this Declaration,\n"
" with a firm reliance on the protection of divine Providence, we\n"
" mutually pledge to each other our Lives, our Fortunes and our sacred\n"
" Honor.\n";
static char document1[] =
"/The Universal Declaration of Human Rights\n"
"/-----------------------------------------\n"
"/Preamble\n"
"/ - - - -\n"
" Whereas recognition of the inherent dignity and of the equal and\n"
" inalienable rights of all members of the human family is the\n"
" foundation of freedom, justice and peace in the world,\n"
...
"/Article 30\n"
"/ - - - - -\n"
" Nothing in this Declaration may be interpreted as implying for any\n"
" State, group or person any right to engage in any activity or to\n"
" perform any act aimed at the destruction of any of the rights and\n"
" freedoms set forth herein.\n";
static char document2[] =
"/CHARTER OF FUNDAMENTAL RIGHTS OF THE EUROPEAN UNION\n"
"/---------------------------------------------------\n"
" PREAMBLE\n"
"\n"
" The peoples of Europe, in creating an ever closer union among them,\n"
" are resolved to share a peaceful future based on common values.\n"
...
"/Article 54\n"
"/- - - -\n"
" Prohibition of abuse of rights\n"
"\n"
" Nothing in this Charter shall be interpreted as implying any right to\n"
" engage in any activity or to perform any act aimed at the destruction\n"
" of any of the rights and freedoms recognized in this Charter or at\n"
" their limitation to a greater extent than is provided for herein.\n";
static char * const documents[] = { document0,
document1,
document2
};
const int numDocuments = sizeof documents / sizeof *documents;
First, we define several aliases to make our code more comprehensible:
Concordance;
typedef Concordance::const_iterator ConcordanceConstItr;
Definition bslstl_pair.h:1210
Definition bslstl_unorderedmultimap.h:707
Next, we create an (empty) unordered multimap to hold our word tallies:
Then, we define the set of characters that define word boundaries:
const char *delimiters = " \n\t,:;.()[]?!/";
Next, we extract the words from our documents. Note that strtok modifies the document arrays (which were not made const).
As each word is located, we create a map value – a pair of the word converted to a bsl::string and a WordLocation object (itself a pair of document code and (word) offset of that word in the document) – and insert the map value into the unordered multimap. Note that (unlike maps and unordered maps) there is no status to check; the insertion succeeds even if the key is already present in the unordered multimap.
for (int idx = 0; idx < numDocuments; ++idx) {
int wordOffset = 0;
for (char *cur = strtok(documents[idx], delimiters);
cur;
cur = strtok(NULL, delimiters)) {
WordLocation location(idx, wordOffset++);
Concordance::value_type value(
bsl::string(cur), location);
concordance.insert(value);
}
}
Definition bslstl_string.h:1281
Then, we can print a complete concordance by iterating through the unordered multimap:
for (ConcordanceConstItr itr = concordance.begin(),
end = concordance.end();
end != itr; ++itr) {
printf("\"%s\", %2d, %4d\n",
itr->first.c_str(),
itr->second.first,
itr->second.second);
}
Standard output shows:
"extent", 2, 3837
"greater", 2, 3836
"abuse", 2, 3791
"constitutions", 2, 3782
"affecting", 2, 3727
...
"he", 1, 1746
"he", 1, 714
"he", 0, 401
"include", 2, 847
Next, if there are some particular words of interest, we seek them out using the equal_range method of the concordance object:
"rights",
"unalienable",
"inalienable"
};
const size_t numWordsOfInterest = sizeof wordsOfInterest
/ sizeof *wordsOfInterest;
for (size_t idx = 0; idx < numWordsOfInterest; ++idx) {
ConcordanceConstItr> found = concordance.equal_range(
wordsOfInterest[idx]);
for (ConcordanceConstItr itr = found.first,
end = found.second;
end != itr; ++itr) {
printf("\"%s\", %2d, %4d\n",
itr->first.c_str(),
itr->second.first,
itr->second.second);
}
printf("\n");
}
Finally, we see on standard output:
"human", 2, 3492
"human", 2, 2192
"human", 2, 534
...
"human", 1, 65
"human", 1, 43
"human", 1, 25
"human", 0, 20
"rights", 2, 3583
"rights", 2, 3553
"rights", 2, 3493
...
"rights", 1, 44
"rights", 1, 19
"rights", 0, 496
"rights", 0, 126
"unalienable", 0, 109
"inalienable", 1, 18
{bslstl_unorderedmap |Example 3} shows how to use the concordance to create an inverse concordance, and how to use the inverse concordance to find the context (surrounding words) of a word of interest.
1.9.8