BDE 4.14.0 Production release
Loading...
Searching...
No Matches
bslstl_unorderedmultiset.h
Go to the documentation of this file.
1/// @file bslstl_unorderedmultiset.h
2///
3/// The content of this file has been pre-processed for Doxygen.
4///
5
6
7// bslstl_unorderedmultiset.h -*-C++-*-
8#ifndef INCLUDED_BSLSTL_UNORDEREDMULTISET
9#define INCLUDED_BSLSTL_UNORDEREDMULTISET
10
11#include <bsls_ident.h>
12BSLS_IDENT("$Id: $")
13
14/// @defgroup bslstl_unorderedmultiset bslstl_unorderedmultiset
15/// @brief Provide an STL-compliant `unordered_multiset` container.
16/// @addtogroup bsl
17/// @{
18/// @addtogroup bslstl
19/// @{
20/// @addtogroup bslstl_unorderedmultiset
21/// @{
22///
23/// <h1> Outline </h1>
24/// * <a href="#bslstl_unorderedmultiset-purpose"> Purpose</a>
25/// * <a href="#bslstl_unorderedmultiset-classes"> Classes </a>
26/// * <a href="#bslstl_unorderedmultiset-description"> Description </a>
27/// * <a href="#bslstl_unorderedmultiset-requirements-on-key"> Requirements on KEY </a>
28/// * <a href="#bslstl_unorderedmultiset-requirements-on-hash-and-equal"> Requirements on HASH and EQUAL </a>
29/// * <a href="#bslstl_unorderedmultiset-memory-allocation"> Memory Allocation </a>
30/// * <a href="#bslstl_unorderedmultiset-bslma-style-allocators"> bslma-Style Allocators </a>
31/// * <a href="#bslstl_unorderedmultiset-operations"> Operations </a>
32/// * <a href="#bslstl_unorderedmultiset-iterator-pointer-and-reference-invalidation"> Iterator, Pointer, and Reference Invalidation </a>
33/// * <a href="#bslstl_unorderedmultiset-unordered-multiset-configuration"> Unordered Multiset Configuration </a>
34/// * <a href="#bslstl_unorderedmultiset-practical-requirements-on-hash"> Practical Requirements on HASH </a>
35/// * <a href="#bslstl_unorderedmultiset-usage"> Usage </a>
36/// * <a href="#bslstl_unorderedmultiset-example-1-categorizing-data"> Example 1: Categorizing Data </a>
37///
38/// # Purpose {#bslstl_unorderedmultiset-purpose}
39/// Provide an STL-compliant @ref unordered_multiset container.
40///
41/// # Classes {#bslstl_unorderedmultiset-classes}
42///
43/// - bsl::unordered_multiset : STL-compliant @ref unordered_multiset container
44///
45/// **Canonical header:** bsl_unordered_set.h
46///
47/// @see package bos+stdhdrs in the bos package group
48///
49/// # Description {#bslstl_unorderedmultiset-description}
50/// This component defines a single class template,
51/// `bsl::unordered_multiset`, implementing the standard container holding a
52/// collection of possibly duplicate keys with no guarantees on ordering (unless
53/// keys have the same value).
54///
55/// An instantiation of @ref unordered_multiset is an allocator-aware,
56/// value-semantic type whose salient attributes are its size (number of keys)
57/// and the set of keys the @ref unordered_multiset contains, without regard to
58/// their order. If @ref unordered_multiset is instantiated with a key type that
59/// is not itself value-semantic, then it will not retain all of its
60/// value-semantic qualities. It is possible to instantiate
61/// @ref unordered_multiset with a key type that does not have an accessible
62/// copy-constructor, in which case the @ref unordered_multiset will not be
63/// copyable. Note that the equality operator for each element is used to
64/// determine when two @ref unordered_multiset objects have the same value, and not
65/// the equality comparator supplied at construction.
66///
67/// An @ref unordered_multiset meets the requirements of an unordered associative
68/// container with forward iterators in the C++11 standard [unord]. The
69/// @ref unordered_multiset implemented here adheres to the C++11 standard, except
70/// that it may rehash when setting the `max_load_factor` in order to preserve
71/// the property that the value is always respected (which is a potentially
72/// throwing operation).
73///
74/// ## Requirements on KEY {#bslstl_unorderedmultiset-requirements-on-key}
75///
76///
77/// An @ref unordered_multiset instantiation is a fully "Value-Semantic Type" (see
78/// @ref bsldoc_glossary ) only if the supplied `KEY` template parameter is fully
79/// value-semantic. It is possible to instantiate an @ref unordered_multiset with
80/// a `KEY` parameter argument that does not provide a full set of
81/// value-semantic operations, but then some methods of the container may not be
82/// instantiable. The following terminology, adopted from the C++11 standard,
83/// is used in the function documentation of @ref unordered_multiset to describe a
84/// function's requirements for the `KEY` template parameter. These terms are
85/// also defined in section [utility.arg.requirements] of the C++11 standard.
86/// Note that, in the context of an @ref unordered_multiset instantiation, the
87/// requirements apply specifically to the @ref unordered_multiset s element type,
88/// `value_type`, which is an alias for `KEY`.
89///
90/// Legend
91/// ------
92/// `X` - denotes an allocator-aware container type (@ref unordered_multiset )
93/// `T` - `value_type` associated with `X`
94/// `A` - type of the allocator used by `X`
95/// `m` - lvalue of type `A` (allocator)
96/// `p` - address (`T *`) of uninitialized storage for a `T` within an `X`
97/// `rv` - rvalue of type (non-`const`) `T`
98/// `v` - rvalue or lvalue of type (possibly `const`) `T`
99/// `args` - 0 or more arguments
100///
101/// The following terms are used to more precisely specify the requirements on
102/// template parameter types in function-level documentation.
103///
104/// *default-insertable*: `T` has a default constructor. More precisely, `T`
105/// is `default-insertable` into `X` means that the following expression is
106/// well-formed:
107///
108/// `allocator_traits<A>::construct(m, p)`
109///
110/// *move-insertable*: `T` provides a constructor that takes an rvalue of type
111/// (non-`const`) `T`. More precisely, `T` is `move-insertable` into `X`
112/// means that the following expression is well-formed:
113///
114/// `allocator_traits<A>::construct(m, p, rv)`
115///
116/// *copy-insertable*: `T` provides a constructor that takes an lvalue or
117/// rvalue of type (possibly `const`) `T`. More precisely, `T` is
118/// `copy-insertable` into `X` means that the following expression is
119/// well-formed:
120///
121/// `allocator_traits<A>::construct(m, p, v)`
122///
123/// *move-assignable*: `T` provides an assignment operator that takes an rvalue
124/// of type (non-`const`) `T`.
125///
126/// *copy-assignable*: `T` provides an assignment operator that takes an lvalue
127/// or rvalue of type (possibly `const`) `T`.
128///
129/// *emplace-constructible*: `T` is `emplace-constructible` into `X` from
130/// `args` means that the following expression is well-formed:
131///
132/// `allocator_traits<A>::construct(m, p, args)`
133///
134/// *erasable*: `T` provides a destructor. More precisely, `T` is `erasable`
135/// from `X` means that the following expression is well-formed:
136///
137/// `allocator_traits<A>::destroy(m, p)`
138///
139/// *equality-comparable*: The type provides an equality-comparison operator
140/// that defines an equivalence relationship and is both reflexive and
141/// transitive.
142///
143/// ## Requirements on HASH and EQUAL {#bslstl_unorderedmultiset-requirements-on-hash-and-equal}
144///
145///
146/// The (template parameter) types `HASH` and `EQUAL` must be copy-constructible
147/// function-objects. Note that this requirement is somewhat stronger than the
148/// requirement currently in the standard; see the discussion for Issue 2215
149/// (http://cplusplus.github.com/LWG/lwg-active.html#2215);
150///
151/// `HASH` shall support a function call operator compatible with the following
152/// statements:
153/// @code
154/// HASH hash;
155/// KEY key;
156/// std::size_t result = hash(key);
157/// @endcode
158/// where the definition of the called function meets the requirements of a
159/// hash function, as specified in {@ref bslstl_hash |Standard Hash Function}.
160///
161/// `EQUAL` shall support the a function call operator compatible with the
162/// following statements:
163/// @code
164/// EQUAL equal;
165/// KEY key1, key2;
166/// bool result = equal(key1, key2);
167/// @endcode
168/// where the definition of the called function defines an equivalence
169/// relationship on keys that is both reflexive and transitive.
170///
171/// `HASH` and `EQUAL` function-objects are further constrained, such for any
172/// two objects whose keys compare equal by the comparator, shall produce the
173/// same value from the hasher.
174///
175/// ## Memory Allocation {#bslstl_unorderedmultiset-memory-allocation}
176///
177///
178/// The type supplied as an unordered multiset's `ALLOCATOR` template parameter
179/// determines how that unordered multiset will allocate memory. The
180/// @ref unordered_multiset template supports allocators meeting the requirements
181/// of the C++11 standard [allocator.requirements], and in addition it supports
182/// scoped-allocators derived from the `bslma::Allocator` memory allocation
183/// protocol. Clients intending to use `bslma`-style allocators should use the
184/// template's default `ALLOCATOR` type. The default type for the `ALLOCATOR`
185/// template parameter, `bsl::allocator`, provides a C++11 standard-compatible
186/// adapter for a `bslma::Allocator` object.
187///
188/// ### bslma-Style Allocators {#bslstl_unorderedmultiset-bslma-style-allocators}
189///
190///
191/// If the parameterized `ALLOCATOR` type of an @ref unordered_multiset
192/// instantiation is `bsl::allocator`, then objects of that unordered multiset
193/// type will conform to the standard behavior of a `bslma`-allocator-enabled
194/// type. Such an unordered multiset accepts an optional `bslma::Allocator`
195/// argument at construction. If the address of a `bslma::Allocator` object is
196/// explicitly supplied at construction, it will be used to supply memory for
197/// the @ref unordered_multiset throughout its lifetime; otherwise, the
198/// @ref unordered_multiset will use the default allocator installed at the time of
199/// the @ref unordered_multiset s construction (see @ref bslma_default ). In addition
200/// to directly allocating memory from the indicated `bslma::Allocator`, an
201/// @ref unordered_multiset supplies that allocator's address to the constructors
202/// of contained objects of the (template parameter) type `KEY` with the
203/// `bslalg::TypeTraitUsesBslmaAllocator` trait.
204///
205/// ## Operations {#bslstl_unorderedmultiset-operations}
206///
207///
208/// This section describes the run-time complexity of operations on instances
209/// of @ref unordered_multiset :
210/// @code
211/// Legend
212/// ------
213/// 'K' - (template parameter) type 'KEY' of the unordered multiset
214/// 'a', 'b' - two distinct objects of type 'unordered_multiset<K>'
215/// 'rv' - modifiable rvalue of type 'unordered_multiset<K>'
216/// 'n', 'm' - number of elements in 'a' and 'b' respectively
217/// 'w' - number of buckets of 'a'
218/// 'value_type' - unordered_multiset<K>::value_type
219/// 'hf' - hash function for objects of type 'K'
220/// 'eq' - equality comparator for objects of type 'K'
221/// 'al' - STL-style memory allocator
222/// 'i1', 'i2' - two iterators defining a sequence of 'value_type' objects
223/// 'li' - object of type 'initializer_list<K>'
224/// 'k' - object of type 'K'
225/// 'rk' - modifiable rvalue of type 'K'
226/// 'v' - object of type 'value_type'
227/// 'p1', 'p2' - two 'const_iterator's belonging to 'a'
228/// distance(i1,i2) - number of elements in the range '[i1 .. i2)'
229/// distance(p1,p2) - number of elements in the range '[p1 .. p2)'
230///
231/// +----------------------------------------------------+--------------------+
232/// | Operation | Complexity |
233/// +====================================================+====================+
234/// | unordered_multiset<K> a; (default construction)| O[1] |
235/// | unordered_multiset<K> a(al); | |
236/// +----------------------------------------------------+--------------------+
237/// | unordered_multiset<K> a(b); (copy construction) | Average: O[n] |
238/// | unordered_multiset<K> a(b, al); | Worst: O[n^2] |
239/// +----------------------------------------------------+--------------------+
240/// | unordered_multiset<K> a(rv); (move construction) | O[1] if 'a' and |
241/// | unordered_multiset<K> a(rv, al); | 'rv' use the same |
242/// | | allocator; |
243/// | | otherwise, |
244/// | | Average: O[n] |
245/// | | Worst: O[n^2] |
246/// +----------------------------------------------------+--------------------+
247/// | unordered_multiset<K> a(li); | Average: O[N] |
248/// | unordered_multiset<K> a(li, al); | Worst: O[N^2] |
249/// | unordered_multiset<K> a(li, w, al); | where N = |
250/// | unordered_multiset<K> a(li, w, hf, al); | 'li.size()'|
251/// | unordered_multiset<K> a(li, w, hf, eq, al); | |
252/// +----------------------------------------------------+--------------------+
253/// | unordered_multiset<K> a(w); | O[n] |
254/// | unordered_multiset<K> a(w, hf); | |
255/// | unordered_multiset<K> a(w, hf, eq); | |
256/// | unordered_multiset<K> a(w, hf, eq, al); | |
257/// +----------------------------------------------------+--------------------+
258/// | unordered_multiset<K> a(i1, i2); | Average: O[ |
259/// | unordered_multiset<K> a(i1, i2, w) | distance(i1, i2)]|
260/// | unordered_multiset<K> a(i1, i2, w, hf); | Worst: O[n^2] |
261/// | unordered_multiset<K> a(i1, i2, w, hf, eq); | |
262/// | unordered_multiset<K> a(i1, i2, w, hf, eq, al); | |
263/// +----------------------------------------------------+--------------------+
264/// | a.~unordered_multiset<K>(); (destruction) | O[n] |
265/// +----------------------------------------------------+--------------------+
266/// | a = b; (copy assignment) | Average: O[n] |
267/// | | Worst: O[n^2] |
268/// +----------------------------------------------------+--------------------+
269/// | a = rv; (move assignment) | O[1] if 'a' and |
270/// | | 'rv' use the same |
271/// | | allocator; |
272/// | | otherwise, |
273/// | | Average: O[n] |
274/// | | Worst: O[n^2] |
275/// +----------------------------------------------------+--------------------+
276/// | a = li; | Average: O[N] |
277/// | | Worst: O[N^2] |
278/// | | where N = |
279/// | | 'li.size()'|
280/// +----------------------------------------------------+--------------------+
281/// | a.begin(), a.end(), a.cbegin(), a.cend(), | O[1] |
282/// +----------------------------------------------------+--------------------+
283/// | a == b, a != b | Best: O[n] |
284/// | | Worst: O[n^2] |
285/// +----------------------------------------------------+--------------------+
286/// | a.swap(b), swap(a, b) | O[1] |
287/// +----------------------------------------------------+--------------------+
288/// | a.key_eq() | O[1] |
289/// +----------------------------------------------------+--------------------+
290/// | a.hash_function() | O[1] |
291/// +----------------------------------------------------+--------------------+
292/// | a.size() | O[1] |
293/// +----------------------------------------------------+--------------------+
294/// | a.max_size() | O[1] |
295/// +----------------------------------------------------+--------------------+
296/// | a.empty() | O[1] |
297/// +----------------------------------------------------+--------------------+
298/// | get_allocator() | O[1] |
299/// +----------------------------------------------------+--------------------+
300/// | a.insert(v) | Average: O[1] |
301/// | a.insert(rk) | Worst: O[n] |
302/// | a.emplace(Args&&...) | |
303/// +----------------------------------------------------+--------------------+
304/// | a.insert(p1, v) | Average: O[1] |
305/// | a.insert(p1, rk) | Worst: O[n] |
306/// | a.emplace_hint(p1, Args&&...) | |
307/// +----------------------------------------------------+--------------------+
308/// | a.insert(i1, i2) | Average O[ |
309/// | | distance(i1, i2)]|
310/// | | Worst: O[ n * |
311/// | | distance(i1, i2)]|
312/// +----------------------------------------------------+--------------------+
313/// | a.insert(li); | Average: O[N] |
314/// | | Worst: O[n * N] |
315/// | | where N = |
316/// | | 'li.size()'|
317/// +----------------------------------------------------+--------------------+
318/// | a.erase(p1) | Average: O[1] |
319/// | | Worst: O[n] |
320/// +----------------------------------------------------+--------------------+
321/// | a.erase(k) | Average: O[ |
322/// | | a.count(k)]|
323/// | | Worst: O[n] |
324/// +----------------------------------------------------+--------------------+
325/// | a.erase(p1, p2) | Average: O[ |
326/// | | distance(p1, p2)]|
327/// | | Worst: O[n] |
328/// +----------------------------------------------------+--------------------+
329/// | a.clear() | O[n] |
330/// +----------------------------------------------------+--------------------+
331/// | a.find(k) | Average: O[1] |
332/// | | Worst: O[n] |
333/// +----------------------------------------------------+--------------------+
334/// | a.contains(k) | Average: O[1] |
335/// | | Worst: O[n] |
336/// +----------------------------------------------------+--------------------+
337/// | a.count(k) | Average: O[1] |
338/// | | Worst: O[n] |
339/// +----------------------------------------------------+--------------------+
340/// | a.equal_range(k) | Average: O[ |
341/// | | a.count(k)]|
342/// | | Worst: O[n] |
343/// +----------------------------------------------------+--------------------+
344/// | a.bucket_count() | O[1] |
345/// +----------------------------------------------------+--------------------+
346/// | a.max_bucket_count() | O[1] |
347/// +----------------------------------------------------+--------------------+
348/// | a.bucket(k) | O[1] |
349/// +----------------------------------------------------+--------------------+
350/// | a.bucket_size(k) | O[a.bucket_size(k)]|
351/// +----------------------------------------------------+--------------------+
352/// | a.load_factor() | O[1] |
353/// +----------------------------------------------------+--------------------+
354/// | a.max_load_factor() | O[1] |
355/// | a.max_load_factor(z) | O[1] |
356/// +----------------------------------------------------+--------------------+
357/// | a.rehash(k) | Average: O[n] |
358/// | | Worst: O[n^2] |
359/// +----------------------------------------------------+--------------------+
360/// | a.reserve(k) | Average: O[n] |
361/// | | Worst: O[n^2] |
362/// +----------------------------------------------------+--------------------+
363/// @endcode
364///
365/// ## Iterator, Pointer, and Reference Invalidation {#bslstl_unorderedmultiset-iterator-pointer-and-reference-invalidation}
366///
367///
368/// No method of @ref unordered_multiset invalidates a pointer or reference to an
369/// element in the unordered multiset, unless it also erases that element, such
370/// as any `erase` overload, `clear`, or the destructor (that erases all
371/// elements). Pointers and references are stable through a rehash.
372///
373/// Iterators to elements in the container are invalidated by any rehash, so
374/// iterators may be invalidated by an `insert` or `emplace` call if it triggers
375/// a rehash (but not otherwise). Iterators to specific elements are also
376/// invalidated when that element is erased. Note that the `end` iterator is
377/// not an iterator referring to any element in the container, so may be
378/// invalidated by any non-`const` method.
379///
380/// ## Unordered Multiset Configuration {#bslstl_unorderedmultiset-unordered-multiset-configuration}
381///
382///
383/// The unordered multiset has interfaces that can provide insight into and
384/// control of its inner workings. The syntax and semantics of these interfaces
385/// for @ref bslstl_unorderedmultiset are identical to those of
386/// @ref bslstl_unorderedmap . See the discussion in
387/// {@ref bslstl_unorderedmap |Unordered Map Configuration} and the illustrative
388/// material in {@ref bslstl_unorderedmap |Example 2}.
389///
390/// ## Practical Requirements on HASH {#bslstl_unorderedmultiset-practical-requirements-on-hash}
391///
392///
393/// An important factor in the performance of an unordered multiset (and any of
394/// the other unordered containers) is the choice of hash function. Please see
395/// the discussion in {@ref bslstl_unorderedmap |Practical Requirements on `HASH`}.
396///
397/// ## Usage {#bslstl_unorderedmultiset-usage}
398///
399///
400/// In this section we show intended use of this component.
401///
402/// ### Example 1: Categorizing Data {#bslstl_unorderedmultiset-example-1-categorizing-data}
403///
404///
405/// Unordered sets are useful in situations when there is no meaningful way to
406/// order key values, when the order of the values is irrelevant to the problem
407/// domain, and (even if there is a meaningful ordering) the value of ordering
408/// the results is outweighed by the higher performance provided by unordered
409/// sets (compared to ordered sets).
410///
411/// One uses a multiset (ordered or unordered) when there may be more than one
412/// instance of an element of a set and when that multiplicity must be
413/// preserved.
414///
415/// Note that the data type described below is an augmentation of that used in
416/// {@ref bslstl_unorderedset |Example 1}. The data itself (randomly generated) is
417/// different.
418///
419/// Suppose one is analyzing data on a set of customers, and each customer is
420/// categorized by several attributes: customer type, geographic area, and
421/// (internal) project code; and that each attribute takes on one of a limited
422/// set of values. Additionally, there is some financial data associated with
423/// each customer: past sales and pending sales.
424///
425/// The several customer attributes are modeled by several enumerations:
426/// @code
427/// typedef enum {
428/// REPEAT
429/// , DISCOUNT
430/// , IMPULSE
431/// , NEED_BASED
432/// , BUSINESS
433/// , NON_PROFIT
434/// , INSTITUTE
435/// // ...
436/// } CustomerCode;
437///
438/// typedef enum {
439/// USA_EAST
440/// , USA_WEST
441/// , CANADA
442/// , MEXICO
443/// , ENGLAND
444/// , SCOTLAND
445/// , FRANCE
446/// , GERMANY
447/// , RUSSIA
448/// // ...
449/// } LocationCode;
450///
451/// typedef enum {
452/// TOAST
453/// , GREEN
454/// , FAST
455/// , TIDY
456/// , PEARL
457/// , SMITH
458/// // ...
459/// } ProjectCode;
460/// @endcode
461/// For printing these values in a human-readable form, we define these helper
462/// functions:
463/// @code
464/// static const char *toAscii(CustomerCode value)
465/// {
466/// switch (value) {
467/// case REPEAT: return "REPEAT";
468/// case DISCOUNT: return "DISCOUNT";
469/// case IMPULSE: return "IMPULSE";
470/// case NEED_BASED: return "NEED_BASED";
471/// case BUSINESS: return "BUSINESS";
472/// case NON_PROFIT: return "NON_PROFIT";
473/// case INSTITUTE: return "INSTITUTE";
474/// // ...
475/// default: return "(* UNKNOWN *)";
476/// }
477/// }
478///
479/// static const char *toAscii(LocationCode value)
480/// {
481/// ...
482/// }
483///
484/// static const char *toAscii(ProjectCode value)
485/// {
486/// ...
487/// }
488/// @endcode
489/// The data set (randomly generated for this example) is provided in a
490/// statically initialized array:
491/// @code
492/// static const struct CustomerDatum {
493/// CustomerCode d_customer;
494/// LocationCode d_location;
495/// ProjectCode d_project;
496/// double d_past;
497/// double d_pending;
498/// } customerData[] = {
499/// { REPEAT , RUSSIA , SMITH, 75674.00, 455.00 },
500/// { REPEAT , ENGLAND , TOAST, 35033.00, 8377.00 },
501/// { BUSINESS , USA_EAST, SMITH, 53942.00, 2782.00 },
502/// ...
503/// { DISCOUNT , MEXICO , GREEN, 99737.00, 3872.00 },
504/// };
505///
506/// const int numCustomerData = sizeof customerData / sizeof *customerData;
507/// @endcode
508/// Suppose, as a step in analysis, we wish to determine the average of the past
509/// sales and the average of the pending sales for each customer for each unique
510/// combination of customer attributes (i.e., for each customer profile in the
511/// data set). To do so, we must aggregate our data items by customer profile
512/// but also retain the unique financial data for each item. The
513/// @ref bslstl_unorderedmultiset provides those semantics.
514///
515/// First, as there are no standard methods for hashing or comparing our user-
516/// defined types, we define `CustomerDatumHash` and `CustomerDatumEqual`
517/// classes, each a stateless functor. Note that there is no meaningful
518/// ordering of the attribute values, they are merely arbitrary code numbers;
519/// nothing is lost by using an unordered multiset instead of an ordered
520/// multiset:
521/// @code
522/// class CustomerDatumHash
523/// {
524/// public:
525/// // CREATORS
526///
527/// /// Create a `CustomerDatumHash` object.
528/// //! CustomerDatumHash() = default;
529///
530/// /// Create a `CustomerDatumHash` object. Note that as
531/// /// `CustomerDatumHash` is an empty (stateless) type, this operation
532/// /// has no observable effect.
533/// //! hash(const CustomerDatumHash& original) = default;
534///
535/// /// Destroy this object.
536/// //! ~CustomerDatumHash() = default;
537///
538/// // ACCESSORS
539///
540/// /// Return a hash value computed using the specified `x`.
541/// std::size_t operator()(CustomerDatum x) const;
542/// };
543///
544/// // ACCESSORS
545/// std::size_t CustomerDatumHash::operator()(CustomerDatum x) const
546/// {
547/// return bsl::hash<int>()(x.d_location * 100 * 100
548/// + x.d_customer * 100
549/// + x.d_project);
550/// }
551///
552/// class CustomerDatumEqual
553/// {
554/// public:
555/// // CREATORS
556///
557/// /// Create a `CustomerDatumEqual` object.
558/// //! CustomerDatumEqual() = default;
559///
560/// /// Create a `CustomerDatumEqual` object. Note that as
561/// /// `CustomerDatumEqual` is an empty (stateless) type, this
562/// /// operation has no observable effect.
563/// //! CustomerDatumEqual(const CustomerDatumEqual& original) = default;
564///
565/// /// Destroy this object.
566/// //! ~CustomerDatumEqual() = default;
567///
568/// // ACCESSORS
569/// bool operator()(const CustomerDatum& lhs,
570/// const CustomerDatum& rhs) const;
571/// };
572///
573/// // ACCESSORS
574/// bool CustomerDatumEqual::operator()(const CustomerDatum& lhs,
575/// const CustomerDatum& rhs) const
576/// {
577/// return lhs.d_location == rhs.d_location
578/// && lhs.d_customer == rhs.d_customer
579/// && lhs.d_project == rhs.d_project;
580/// }
581/// @endcode
582/// Notice that many of the required methods of the hash and comparator types
583/// are compiler generated. (The declaration of those methods are commented out
584/// and suffixed by an `= default` comment.)
585///
586/// Also notice that the boolean operation provided by `CustomerDatumEqual` is
587/// more properly thought of as "equivalence", not "equality". There may be
588/// more than one data item with the same customer profile (i.e., the same for
589/// our purpose here), but they have distinct financial data so the two items
590/// are not equal (unless the financial data also happens to match).
591///
592/// Next, we define the type of the unordered multiset and a convenience
593/// aliases:
594/// @code
595/// typedef bsl::unordered_multiset<CustomerDatum,
596/// CustomerDatumHash,
597/// CustomerDatumEqual> DataByProfile;
598/// typedef DataByProfile::const_iterator DataByProfileConstItr;
599/// @endcode
600/// Now, create a helper function to calculate the average financials for a
601/// category of customer profiles within the unordered multiset.
602/// @code
603/// /// Print to the specified `out` in some human-readable format the
604/// /// averages of the `past` and `pending` attributes of every
605/// /// `CustomerInfoData` object from the specified `start` up to (but not
606/// /// including) the specified `end`. The behavior is undefined unless
607/// /// `end != start`.
608/// void processCategory(DataByProfileConstItr start,
609/// DataByProfileConstItr end,
610/// FILE *out)
611/// {
612/// assert(end != start);
613/// assert(out);
614///
615/// double sumPast = 0.0;
616/// double sumPending = 0.0;
617/// int count = 0;
618///
619/// for (DataByProfileConstItr itr = start; end != itr; ++itr) {
620/// sumPast += itr->d_past;
621/// sumPending += itr->d_pending;
622/// ++count;
623/// }
624/// printf("%-10s %-8s %-5s %10.2f %10.2f\n",
625/// toAscii(start->d_customer),
626/// toAscii(start->d_location),
627/// toAscii(start->d_project),
628/// sumPast/count,
629/// sumPending/count);
630/// }
631/// @endcode
632/// Then, we create an unordered multiset and insert each item of `data`.
633/// @code
634/// DataByProfile dataByProfile;
635///
636/// for (int idx = 0; idx < numCustomerData; ++idx) {
637/// dataByProfile.insert(customerData[idx]);
638/// }
639/// assert(numCustomerData == dataByProfile.size());
640/// @endcode
641/// Finally, to calculate the statistics we need, we must detect the transition
642/// between categories as we iterate through `customerInfoData`.
643/// @code
644/// CustomerDatumEqual areEquivalent;
645/// DataByProfileConstItr end = dataByProfile.end();
646/// DataByProfileConstItr startOfCategory = end;
647///
648/// for (DataByProfileConstItr itr = dataByProfile.begin();
649/// end != itr; ++itr) {
650/// if (end == startOfCategory) {
651/// startOfCategory = itr;
652/// continue;
653/// }
654///
655/// if (!areEquivalent(*startOfCategory, *itr)) {
656/// processCategory(startOfCategory, itr, stdout);
657/// startOfCategory = itr;
658/// }
659/// }
660/// if (end != startOfCategory) {
661/// processCategory(startOfCategory, end, stdout);
662/// }
663/// @endcode
664/// We find on standard output:
665/// @code
666/// BUSINESS GERMANY TIDY 84553.00 3379.00
667/// DISCOUNT ENGLAND TIDY 74110.00 2706.00
668/// NEED_BASED CANADA FAST 97479.00 681.00
669/// ...
670/// NEED_BASED SCOTLAND TOAST 27306.00 5084.50
671/// INSTITUTE CANADA TIDY 83528.00 4722.33
672/// NEED_BASED FRANCE FAST 83741.50 5396.50
673/// REPEAT MEXICO TOAST 7469.00 5958.00
674/// BUSINESS SCOTLAND FAST 24443.00 4247.00
675/// INSTITUTE FRANCE FAST 19349.00 3982.00
676/// NEED_BASED RUSSIA TIDY 50712.00 8647.00
677/// INSTITUTE SCOTLAND TIDY 78240.00 6635.00
678/// BUSINESS RUSSIA PEARL 29386.00 3623.00
679/// INSTITUTE FRANCE PEARL 47747.00 3533.00
680/// @endcode
681/// @}
682/** @} */
683/** @} */
684
685/** @addtogroup bsl
686 * @{
687 */
688/** @addtogroup bslstl
689 * @{
690 */
691/** @addtogroup bslstl_unorderedmultiset
692 * @{
693 */
694
695#include <bslscm_version.h>
696
697#include <bslstl_algorithm.h>
698#include <bslstl_equalto.h>
699#include <bslstl_hash.h>
700#include <bslstl_hashtable.h>
701#include <bslstl_hashtablebucketiterator.h>
702#include <bslstl_hashtableiterator.h>
703#include <bslstl_iteratorutil.h>
704#include <bslstl_pair.h> // result type of 'equal_range' method
705#include <bslstl_unorderedsetkeyconfiguration.h>
706
707#include <bslalg_bidirectionallink.h>
708#include <bslalg_bidirectionalnode.h>
709#include <bslalg_typetraithasstliterators.h>
710
711#include <bslma_allocatortraits.h>
712#include <bslma_isstdallocator.h>
713#include <bslma_bslallocator.h> // Can probably escape with a fwd-decl,
714 // but not very user friendly
715#include <bslma_usesbslmaallocator.h>
716
717#include <bslmf_enableif.h>
718#include <bslmf_isbitwisemoveable.h>
719#include <bslmf_isnothrowswappable.h>
720#include <bslmf_nestedtraitdeclaration.h>
721#include <bslmf_typeidentity.h>
722#include <bslmf_util.h> // 'forward(V)'
723
724#include <bsls_assert.h>
725#include <bsls_compilerfeatures.h>
726#include <bsls_keyword.h>
727#include <bsls_performancehint.h>
728#include <bsls_util.h> // 'forward<T>(V)'
729
730#include <cstddef> // for 'std::size_t'
731
732#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
733# include <initializer_list>
734#endif
735
736#ifdef BSLS_COMPILERFEATURES_SUPPORT_TRAITS_HEADER
737#include <type_traits> // 'std::is_nothrow_move_assignable'
738#endif
739
740#if BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
741// Include version that can be compiled with C++03
742// Generated on Thu Oct 21 10:11:37 2021
743// Command line: sim_cpp11_features.pl bslstl_unorderedmultiset.h
744# define COMPILING_BSLSTL_UNORDEREDMULTISET_H
745# include <bslstl_unorderedmultiset_cpp03.h>
746# undef COMPILING_BSLSTL_UNORDEREDMULTISET_H
747#else
748
749namespace bsl {
750
751 // ========================
752 // class unordered_multiset
753 // ========================
754
755/// This class template implements a value-semantic container type holding
756/// an unordered multiset of values (of template parameter type `KEY`).
757///
758/// This class:
759/// * supports a complete set of *value-semantic* operations
760/// - except for BDEX serialization
761/// * is *exception-neutral* (agnostic except for the `at` method)
762/// * is *alias-safe*
763/// * is `const` *thread-safe*
764/// For terminology see @ref bsldoc_glossary .
765template <class KEY,
766 class HASH = bsl::hash<KEY>,
767 class EQUAL = bsl::equal_to<KEY>,
768 class ALLOCATOR = bsl::allocator<KEY> >
769class unordered_multiset
770{
771
772 private:
773
774 // PRIVATE TYPE
775
776 /// This typedef is an alias for the allocator traits type associated
777 /// with this container.
778 typedef bsl::allocator_traits<ALLOCATOR> AllocatorTraits;
779
780 /// This typedef is an alias for the type of values maintained by this
781 /// unordered multiset.
782 typedef KEY ValueType;
783
784 /// This typedef is an alias for the policy used internally by this
785 /// container to extract the `KEY` value from the values maintained by
786 /// this unordered multiset.
787 typedef ::BloombergLP::bslstl::UnorderedSetKeyConfiguration<ValueType>
788 ListConfiguration;
789
790 /// This typedef is an alias for the template instantiation of the
791 /// underlying `bslstl::HashTable` used to implement this unordered
792 /// multiset.
793 typedef ::BloombergLP::bslstl::HashTable<ListConfiguration,
794 HASH,
795 EQUAL,
796 ALLOCATOR> HashTable;
797
798 /// This typedef is an alias for the type of links maintained by the
799 /// linked list of elements held by the underlying `bslstl::HashTable`.
800 typedef ::BloombergLP::bslalg::BidirectionalLink HashTableLink;
801
802 /// This typedef is a convenient alias for the utility associated with
803 /// movable references.
804 typedef BloombergLP::bslmf::MovableRefUtil MoveUtil;
805
806 // FRIENDS
807 template <class KEY2,
808 class HASH2,
809 class EQUAL2,
810 class ALLOCATOR2>
811 friend bool operator==(
812 const unordered_multiset<KEY2, HASH2, EQUAL2, ALLOCATOR2>&,
813 const unordered_multiset<KEY2, HASH2, EQUAL2, ALLOCATOR2>&);
814
815 public:
816 // PUBLIC TYPES
817 typedef KEY key_type;
818 typedef KEY value_type;
819 typedef HASH hasher;
820 typedef EQUAL key_equal;
821 typedef ALLOCATOR allocator_type;
822 typedef value_type& reference;
823 typedef const value_type& const_reference;
824
825 typedef typename AllocatorTraits::size_type size_type;
826 typedef typename AllocatorTraits::difference_type difference_type;
827 typedef typename AllocatorTraits::pointer pointer;
828 typedef typename AllocatorTraits::const_pointer const_pointer;
829
830 typedef ::BloombergLP::bslstl::HashTableIterator<
831 const value_type, difference_type> iterator;
832
833 typedef ::BloombergLP::bslstl::HashTableBucketIterator<
834 const value_type, difference_type> local_iterator;
835
836 typedef iterator const_iterator;
837 typedef local_iterator const_local_iterator;
838
839 public:
840 // TRAITS
841 BSLMF_NESTED_TRAIT_DECLARATION_IF(
842 unordered_multiset,
843 ::BloombergLP::bslmf::IsBitwiseMoveable,
844 ::BloombergLP::bslmf::IsBitwiseMoveable<HashTable>::value);
845
846 private:
847 // DATA
848 HashTable d_impl;
849
850 public:
851 // CREATORS
852
853 unordered_multiset();
854 explicit unordered_multiset(size_type initialNumBuckets,
855 const HASH& hashFunction = HASH(),
856 const EQUAL& keyEqual = EQUAL(),
857 const ALLOCATOR& basicAllocator = ALLOCATOR());
858 unordered_multiset(size_type initialNumBuckets,
859 const HASH& hashFunction,
860 const ALLOCATOR& basicAllocator);
861 unordered_multiset(size_type initialNumBuckets,
862 const ALLOCATOR& basicAllocator);
863 /// Create an empty unordered multiset. Optionally specify an
864 /// `initialNumBuckets` indicating the initial size of the array of
865 /// buckets of this container. If `initialNumBuckets` is not supplied,
866 /// a single bucket is used. Optionally specify a `hashFunction` used
867 /// to generate the hash values for the keys contained in this unordered
868 /// multiset. If `hashFunction` is not supplied, a default-constructed
869 /// object of the (template parameter) type `HASH` is used. Optionally
870 /// specify a key-equality functor `keyEqual` used to verify that two
871 /// keys are equivalent. If `keyEqual` is not supplied, a
872 /// default-constructed object of the (template parameter) type `EQUAL`
873 /// is used. Optionally specify a `basicAllocator` used to supply
874 /// memory. If `basicAllocator` is not supplied, a default-constructed
875 /// object of the (template parameter) type `ALLOCATOR` is used. If the
876 /// type `ALLOCATOR` is `bsl::allocator` (the default), then
877 /// `basicAllocator`, if supplied, shall be convertible to
878 /// `bslma::Allocator *`. If the type `ALLOCATOR` is `bsl::allocator`
879 /// and `basicAllocator` is not supplied, the currently installed
880 /// default allocator is used.
881 explicit unordered_multiset(const ALLOCATOR& basicAllocator);
882
883 /// Create an unordered multiset having the same value as the specified
884 /// `original` object. Use a copy of `original.hash_function()` to
885 /// generate hash values for the keys contained in this unordered
886 /// multiset. Use a copy of `original.key_eq()` to verify that two keys
887 /// are equivalent. Use the allocator returned by
888 /// `bsl::allocator_traits<ALLOCATOR>::
889 /// select_on_container_copy_construction(original.get_allocator())` to
890 /// allocate memory. This method requires that the (template parameter)
891 /// type `KEY` be `copy-insertable` into this unordered multiset (see
892 /// {Requirements on `KEY`}).
893 unordered_multiset(const unordered_multiset& original);
894
895 /// Create an unordered multiset having the same value as the specified
896 /// `original` object by moving (in constant time) the contents of
897 /// `original` to the new unordered multiset. Use a copy of
898 /// `original.hash_function()` to generate hash values for the keys
899 /// contained in this unordered multiset. Use a copy of
900 /// `original.key_eq()` to verify that two keys are equivalent. The
901 /// allocator associated with `original` is propagated for use in the
902 /// newly-created unordered multiset. `original` is left in a valid but
903 /// unspecified state.
904 unordered_multiset(
905 BloombergLP::bslmf::MovableRef<unordered_multiset> original);
906
907 /// Create an unordered multiset having the same value as the specified
908 /// `original` object that uses the specified `basicAllocator` to supply
909 /// memory. Use a copy of `original.hash_function()` to generate hash
910 /// values for the keys contained in this unordered multiset. Use a
911 /// copy of `original.key_eq()` to verify that two keys are equivalent.
912 /// This method requires that the (template parameter) type `KEY` be
913 /// `copy-insertable` into this unordered multiset (see {Requirements on
914 /// `KEY`}). Note that a `bslma::Allocator *` can be supplied for
915 /// `basicAllocator` if the (template parameter) type `ALLOCATOR` is
916 /// `bsl::allocator` (the default).
917 unordered_multiset(
918 const unordered_multiset& original,
919 const typename type_identity<ALLOCATOR>::type& basicAllocator);
920
921 /// Create an unordered multiset having the same value as the specified
922 /// `original` object that uses the specified `basicAllocator` to supply
923 /// memory. The contents of `original` are moved (in constant time) to
924 /// the new unordered multiset if `basicAllocator ==
925 /// original.get_allocator()`, and are move-inserted (in linear time)
926 /// using `basicAllocator` otherwise. `original` is left in a valid but
927 /// unspecified state. Use a copy of `original.hash_function()` to
928 /// generate hash values for the keys contained in this unordered
929 /// multiset. Use a copy of `original.key_eq()` to verify that two keys
930 /// are equivalent. This method requires that the (template parameter)
931 /// type `KEY` be `move-insertable` into this unordered multiset (see
932 /// {Requirements on `KEY`}). Note that a `bslma::Allocator *` can be
933 /// supplied for `basicAllocator` if the (template parameter) type
934 /// `ALLOCATOR` is `bsl::allocator` (the default).
935 unordered_multiset(
936 BloombergLP::bslmf::MovableRef<unordered_multiset> original,
937 const typename type_identity<ALLOCATOR>::type& basicAllocator);
938
939 /// Create an unordered multiset, and insert each `value_type` object in
940 /// the sequence starting at the specified `first` element, and ending
941 /// immediately before the specified `last` element. Optionally specify
942 /// an `initialNumBuckets` indicating the initial size of the array of
943 /// buckets of this container. If `initialNumBuckets` is not supplied,
944 /// a single bucket is used. Optionally specify a `hashFunction` used
945 /// to generate hash values for the keys contained in this unordered
946 /// multiset. If `hashFunction` is not supplied, a default-constructed
947 /// object of (template parameter) type `HASH` is used. Optionally
948 /// specify a key-equality functor `keyEqual` used to verify that two
949 /// keys are equivalent. If `keyEqual` is not supplied, a
950 /// default-constructed object of (template parameter) type `EQUAL` is
951 /// used. Optionally specify a `basicAllocator` used to supply memory.
952 /// If `basicAllocator` is not supplied, a default-constructed object of
953 /// the (template parameter) type `ALLOCATOR` is used. If the type
954 /// `ALLOCATOR` is `bsl::allocator` and `basicAllocator` is not
955 /// supplied, the currently installed default allocator is used to
956 /// supply memory. The (template parameter) type `INPUT_ITERATOR` shall
957 /// meet the requirements of an input iterator defined in the C++11
958 /// standard [24.2.3] providing access to values of a type convertible
959 /// to `value_type`, and `value_type` must be `emplace-constructible`
960 /// from `*i` into this unordered multiset, where `i` is a
961 /// dereferenceable iterator in the range `[first .. last)` (see
962 /// {Requirements on `KEY`}). The behavior is undefined unless `first`
963 /// and `last` refer to a sequence of valid values where `first` is at a
964 /// position at or before `last`. Note that a `bslma::Allocator *` can
965 /// be supplied for `basicAllocator` if the type `ALLOCATOR` is
966 /// `bsl::allocator` (the default).
967 template <class INPUT_ITERATOR>
968 unordered_multiset(INPUT_ITERATOR first,
969 INPUT_ITERATOR last,
970 size_type initialNumBuckets = 0,
971 const HASH& hashFunction = HASH(),
972 const EQUAL& keyEqual = EQUAL(),
973 const ALLOCATOR& basicAllocator = ALLOCATOR());
974 template <class INPUT_ITERATOR>
975 unordered_multiset(INPUT_ITERATOR first,
976 INPUT_ITERATOR last,
977 size_type initialNumBuckets,
978 const HASH& hashFunction,
979 const ALLOCATOR& basicAllocator);
980 template <class INPUT_ITERATOR>
981 unordered_multiset(INPUT_ITERATOR first,
982 INPUT_ITERATOR last,
983 size_type initialNumBuckets,
984 const ALLOCATOR& basicAllocator);
985 template <class INPUT_ITERATOR>
986 unordered_multiset(INPUT_ITERATOR first,
987 INPUT_ITERATOR last,
988 const ALLOCATOR& basicAllocator);
989
990#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
991# ifdef BSLS_COMPILERFEATURES_SUPPORT_CTAD
992 template <
993 class = bsl::enable_if_t<std::is_invocable_v<HASH, const KEY &>>,
994 class = bsl::enable_if_t<
995 std::is_invocable_v<EQUAL, const KEY &, const KEY &>>,
996 class = bsl::enable_if_t< bsl::IsStdAllocator_v<ALLOCATOR>>
997 >
998# endif
999 unordered_multiset(
1000 std::initializer_list<KEY> values,
1001 size_type initialNumBuckets = 0,
1002 const HASH& hashFunction = HASH(),
1003 const EQUAL& keyEqual = EQUAL(),
1004 const ALLOCATOR& basicAllocator = ALLOCATOR());
1005# ifdef BSLS_COMPILERFEATURES_SUPPORT_CTAD
1006 template <
1007 class = bsl::enable_if_t<std::is_invocable_v<HASH, const KEY &>>,
1008 class = bsl::enable_if_t<bsl::IsStdAllocator<ALLOCATOR>::value>
1009 >
1010# endif
1011 unordered_multiset(std::initializer_list<KEY> values,
1012 size_type initialNumBuckets,
1013 const HASH& hashFunction,
1014 const ALLOCATOR& basicAllocator);
1015# ifdef BSLS_COMPILERFEATURES_SUPPORT_CTAD
1016 template <class = bsl::enable_if_t<bsl::IsStdAllocator<ALLOCATOR>::value>>
1017# endif
1018 unordered_multiset(std::initializer_list<KEY> values,
1019 size_type initialNumBuckets,
1020 const ALLOCATOR& basicAllocator);
1021# ifdef BSLS_COMPILERFEATURES_SUPPORT_CTAD
1022 /// Create an unordered multiset and insert each `value_type` object in
1023 /// the specified `values` initializer list. Optionally specify an
1024 /// `initialNumBuckets` indicating the initial size of the array of
1025 /// buckets of this container. If `initialNumBuckets` is not supplied,
1026 /// a single bucket is used. Optionally specify a `hashFunction` used
1027 /// to generate the hash values for the keys contained in this unordered
1028 /// multiset. If `hashFunction` is not supplied, a default-constructed
1029 /// object of the (template parameter) type `HASH` is used. Optionally
1030 /// specify a key-equality functor `keyEqual` used to verify that two
1031 /// keys are equivalent. If `keyEqual` is not supplied, a
1032 /// default-constructed object of the (template parameter) type `EQUAL`
1033 /// is used. Optionally specify a `basicAllocator` used to supply
1034 /// memory. If `basicAllocator` is not supplied, a default-constructed
1035 /// object of the (template parameter) type `ALLOCATOR` is used. If the
1036 /// type `ALLOCATOR` is `bsl::allocator` and `basicAllocator` is not
1037 /// supplied, the currently installed default allocator is used to
1038 /// supply memory. This method requires that the (template parameter)
1039 /// type `KEY` be `copy-insertable` into this unordered multiset (see
1040 /// {Requirements on `KEY`}). Note that a `bslma::Allocator *` can be
1041 /// supplied for `basicAllocator` if the type `ALLOCATOR` is
1042 /// `bsl::allocator` (the default).
1043 template <class = bsl::enable_if_t<bsl::IsStdAllocator<ALLOCATOR>::value>>
1044# endif
1045 unordered_multiset(std::initializer_list<KEY> values,
1046 const ALLOCATOR& basicAllocator);
1047#endif
1048
1049 /// Destroy this object.
1050 ~unordered_multiset();
1051
1052 // MANIPULATORS
1053
1054 /// Assign to this object the value, hash function, and equality
1055 /// comparator of the specified `rhs` object, propagate to this object
1056 /// the allocator of `rhs` if the `ALLOCATOR` type has trait
1057 /// `propagate_on_container_copy_assignment`, and return a reference
1058 /// providing modifiable access to this object. If an exception is
1059 /// thrown, `*this` is left in a valid but unspecified state. This
1060 /// method requires that the (template parameter) type `KEY` be both
1061 /// `copy-assignable` and `copy-insertable` into this unordered multiset
1062 /// (see {Requirements on `KEY`}).
1063 unordered_multiset& operator=(const unordered_multiset& rhs);
1064
1065 /// Assign to this object the value, hash function, and equality
1066 /// comparator of the specified `rhs` object, propagate to this object
1067 /// the allocator of `rhs` if the `ALLOCATOR` type has trait
1068 /// `propagate_on_container_move_assignment`, and return a reference
1069 /// providing modifiable access to this object. The contents of `rhs`
1070 /// are moved (in constant time) to this unordered multiset if
1071 /// `get_allocator() == rhs.get_allocator()` (after accounting for the
1072 /// aforementioned trait); otherwise, all elements in this unordered
1073 /// multiset are either destroyed or move-assigned to and each
1074 /// additional element in `rhs` is move-inserted into this unordered
1075 /// multiset. `rhs` is left in a valid but unspecified state, and if an
1076 /// exception is thrown, `*this` is left in a valid but unspecified
1077 /// state. This method requires that the (template parameter) type
1078 /// `KEY` be both `move-assignable` and `move-insertable` into this
1079 /// unordered multiset (see {Requirements on `KEY`}).
1080 unordered_multiset&
1081 operator=(BloombergLP::bslmf::MovableRef<unordered_multiset> rhs)
1082 BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(
1083 AllocatorTraits::is_always_equal::value
1084 && std::is_nothrow_move_assignable<HASH>::value
1085 && std::is_nothrow_move_assignable<EQUAL>::value);
1086
1087#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
1088 /// Assign to this object the value resulting from first clearing this
1089 /// unordered multiset and then inserting each `value_type` object in
1090 /// the specified `values` initializer list, and return a reference
1091 /// providing modifiable access to this object. This method requires
1092 /// that the (template parameter) type `KEY` be `copy-insertable` into
1093 /// this unordered multiset (see {Requirements on `KEY`}).
1094 unordered_multiset& operator=(std::initializer_list<KEY> values);
1095#endif
1096
1097 /// Return an iterator providing modifiable access to the first
1098 /// `value_type` object (in the sequence of `value_type` objects)
1099 /// maintained by this unordered multiset, or the `end` iterator if this
1100 /// unordered multiset is empty.
1101 iterator begin() BSLS_KEYWORD_NOEXCEPT;
1102
1103 /// Return an iterator providing modifiable access to the past-the-end
1104 /// element in the sequence of `value_type` objects maintained by this
1105 /// unordered multiset.
1106 iterator end() BSLS_KEYWORD_NOEXCEPT;
1107
1108 /// Return a local iterator providing modifiable access to the first
1109 /// `value_type` object in the sequence of `value_type` objects of the
1110 /// bucket having the specified `index`, in the array of buckets
1111 /// maintained by this unordered multiset, or the `end(index)`
1112 /// otherwise.
1113 local_iterator begin(size_type index);
1114
1115 /// Return a local iterator providing modifiable access to the
1116 /// past-the-end element in the sequence of `value_type` objects of the
1117 /// bucket having the specified `index`, in the array of buckets
1118 /// maintained by this unordered multiset.
1119 local_iterator end(size_type index);
1120
1121 /// Remove all entries from this unordered multiset. Note that the
1122 /// container is empty after this call, but allocated memory may be
1123 /// retained for future use.
1124 void clear() BSLS_KEYWORD_NOEXCEPT;
1125
1126 /// Return a pair of iterators providing modifiable access to the
1127 /// sequence of `value_type` objects in this unordered multiset
1128 /// equivalent to the specified `key`, where the first iterator is
1129 /// positioned at the start of the sequence, and the second is
1130 /// positioned one past the end of the sequence. If this unordered
1131 /// multiset contains no `value_type` objects equivalent to the `key`,
1132 /// then the two returned iterators will have the same value. The
1133 /// behavior is undefined unless `key` is equivalent to the elements of
1134 /// at most one equivalent-key group in this unordered multiset.
1135 template <class LOOKUP_KEY>
1136 typename enable_if<
1137 BloombergLP::bslmf::IsTransparentPredicate<HASH, LOOKUP_KEY>::value
1138 && BloombergLP::bslmf::IsTransparentPredicate<EQUAL,LOOKUP_KEY>::value,
1139 pair<iterator, iterator> >::type
1140 equal_range(const LOOKUP_KEY& key)
1141 {
1142 // Note: implemented inline due to Sun CC compilation error.
1143 typedef bsl::pair<iterator, iterator> ResultType;
1144 HashTableLink *first;
1145 HashTableLink *last;
1146 d_impl.findRange(&first, &last, key);
1147 return ResultType(iterator(first), iterator(last));
1148 }
1149
1150 /// Return a pair of iterators providing modifiable access to the
1151 /// sequence of `value_type` objects in this unordered multiset
1152 /// equivalent to the specified `key`, where the first iterator is
1153 /// positioned at the start of the sequence, and the second is
1154 /// positioned one past the end of the sequence. If this unordered
1155 /// multiset contains no `value_type` objects equivalent to the `key`,
1156 /// then the two returned iterators will have the same value.
1157 pair<iterator, iterator> equal_range(const key_type& key);
1158
1159 /// Remove from this unordered multiset all `value_type` objects that
1160 /// are equivalent to the specified `key`, if they exist, and return the
1161 /// number of object erased; otherwise, if there are no `value_type`
1162 /// objects equivalent to `key`, return 0 with no other effect. This
1163 /// method invalidates only iterators and references to the removed
1164 /// element and previously saved values of the `end()` iterator, and
1165 /// preserves the relative order of the elements not removed.
1166 size_type erase(const key_type& key);
1167
1168 /// Remove from this unordered multiset the `value_type` object at the
1169 /// specified `position`, and return an iterator referring to the
1170 /// element immediately following the removed element, or to the
1171 /// past-the-end position if the removed element was the last element in
1172 /// the sequence of elements maintained by this unordered multiset.
1173 /// This method invalidates only iterators and references to the removed
1174 /// element and previously saved values of the `end()` iterator, and
1175 /// preserves the relative order of the elements not removed. The
1176 /// behavior is undefined unless `position` refers to a `value_type`
1177 /// object in this unordered multiset.
1178 iterator erase(const_iterator position);
1179
1180 /// Remove from unordered multiset the `value_type` objects starting at
1181 /// the specified `first` position up to, but not including the
1182 /// specified `last` position, and return `last`. This method
1183 /// invalidates only iterators and references to the removed element and
1184 /// previously saved values of the `end()` iterator, and preserves the
1185 /// relative order of the elements not removed. The behavior is
1186 /// undefined unless `first` and `last` either refer to elements in this
1187 /// unordered multiset or are the `end` iterator, and the `first`
1188 /// position is at or before the `last` position in the sequence
1189 /// provided by this container.
1190 iterator erase(const_iterator first, const_iterator last);
1191
1192 /// Return an iterator providing modifiable access to the first
1193 /// `value_type` object in the sequence of all the value elements of
1194 /// this unordered multiset equivalent to the specified `key`, if such
1195 /// entries exist, and the past-the-end (`end`) iterator otherwise. The
1196 /// behavior is undefined unless `key` is equivalent to the elements of
1197 /// at most one equivalent-key group in this unordered multiset.
1198 template <class LOOKUP_KEY>
1199 typename enable_if<
1200 BloombergLP::bslmf::IsTransparentPredicate<HASH, LOOKUP_KEY>::value
1201 && BloombergLP::bslmf::IsTransparentPredicate<EQUAL,LOOKUP_KEY>::value,
1202 iterator>::type
1203 find(const LOOKUP_KEY& key)
1204 {
1205 // Note: implemented inline due to Sun CC compilation error.
1206 return iterator(d_impl.find(key));
1207 }
1208
1209 /// Return an iterator providing modifiable access to the first
1210 /// `value_type` object in the sequence of all the value elements of
1211 /// this unordered multiset equivalent to the specified `key`, if such
1212 /// entries exist, and the past-the-end (`end`) iterator otherwise.
1213 iterator find(const key_type& key);
1214
1215 /// Insert the specified `value` into this unordered multiset. If one
1216 /// or more keys equivalent to `value` already exist in this unordered
1217 /// multiset, this method is guaranteed to insert `value` in a position
1218 /// contiguous to one of those equivalent keys. Return an iterator
1219 /// referring to the newly inserted `value_type` object that is
1220 /// equivalent to `value`. Note that this method requires that the
1221 /// (template parameter) type `KEY` be `copy-insertable` into this
1222 /// unordered multiset (see {Requirements on `KEY`}).
1223 iterator insert(const value_type& value);
1224
1225 /// Insert the specified `value` into this unordered multiset. If one
1226 /// or more keys equivalent to `value` already exist in this unordered
1227 /// multiset, this method is guaranteed to insert `value` in a position
1228 /// contiguous to one of those equivalent keys. Return an iterator
1229 /// referring to the newly inserted `value_type` object that is
1230 /// equivalent to `value`. This method requires that the (template
1231 /// parameter) type `KEY` be `move-insertable` into this unordered
1232 /// multiset (see {Requirements on `KEY`}).
1233 iterator insert(BloombergLP::bslmf::MovableRef<value_type> value);
1234
1235 /// Insert the specified `value` into this unordered multiset (in
1236 /// constant time if the specified `hint` refers to an element in this
1237 /// container equivalent to `value`). If one or more keys equivalent to
1238 /// `value` already exist in this unordered multiset, this method is
1239 /// guaranteed to insert `value` in a position contiguous to one of
1240 /// those equivalent keys. Return an iterator referring to the newly
1241 /// inserted `value_type` object that is equivalent to `value`. If
1242 /// `hint` does not refer to an element in this container equivalent to
1243 /// `value`, this operation has worst case `O[N]` and average case
1244 /// constant-time complexity, where `N` is the size of this unordered
1245 /// multiset. This method requires that the (template parameter) type
1246 /// `KEY` be `copy-insertable` into this unordered multiset (see
1247 /// {Requirements on `KEY`}). The behavior is undefined unless `hint`
1248 /// is an iterator in the range `[begin() .. end()]` (both endpoints
1249 /// included).
1250 iterator insert(const_iterator hint, const value_type& value);
1251
1252 /// Insert the specified `value` into this unordered multiset (in
1253 /// constant time if the specified `hint` refers to an element in this
1254 /// container equivalent to `value`). If one or more keys equivalent to
1255 /// `value` already exist in this unordered multiset, this method is
1256 /// guaranteed to insert `value` in a position contiguous to one of
1257 /// those equivalent keys. Return an iterator referring to the newly
1258 /// inserted `value_type` object that is equivalent to `value`. If
1259 /// `hint` does not refer to an element in this container equivalent to
1260 /// `value`, this operation has worst case `O[N]` and average case
1261 /// constant-time complexity, where `N` is the size of this unordered
1262 /// multiset. This method requires that the (template parameter) type
1263 /// `KEY` be `move-insertable` into this unordered multiset (see
1264 /// {Requirements on `KEY`}). The behavior is undefined unless `hint`
1265 /// is an iterator in the range `[begin() .. end()]` (both endpoints
1266 /// included).
1267 iterator insert(const_iterator hint,
1268 BloombergLP::bslmf::MovableRef<value_type> value);
1269
1270 /// Insert into this unordered multiset the value of each `value_type`
1271 /// object in the range starting at the specified `first` iterator and
1272 /// ending immediately before the specified `last` iterator. The
1273 /// (template parameter) type `INPUT_ITERATOR` shall meet the
1274 /// requirements of an input iterator defined in the C++11 standard
1275 /// [24.2.3] providing access to values of a type convertible to
1276 /// `value_type`, and `value_type` must be `emplace-constructible` from
1277 /// `*i` into this unordered multiset, where `i` is a dereferenceable
1278 /// iterator in the range `[first .. last)` (see {Requirements on
1279 /// `KEY`}). The behavior is undefined unless `first` and `last` refer
1280 /// to a sequence of valid values where `first` is at a position at or
1281 /// before `last`.
1282 template <class INPUT_ITERATOR>
1283 void insert(INPUT_ITERATOR first, INPUT_ITERATOR last);
1284
1285#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
1286 /// Insert into this unordered multiset the value of each `value_type`
1287 /// object in the specified `values` initializer list. This method
1288 /// requires that the (template parameter) type `KEY` be
1289 /// `copy-insertable` into this unordered multiset (see {Requirements on
1290 /// `KEY`}).
1291 void insert(std::initializer_list<KEY> values);
1292#endif
1293
1294#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
1295 /// Insert into this unordered multiset a newly created `value_type`
1296 /// object, constructed by forwarding `get_allocator()` (if required)
1297 /// and the specified (variable number of) `args` to the corresponding
1298 /// constructor of `value_type`. Return an iterator referring to the
1299 /// newly created and inserted object in this unordered multiset whose
1300 /// value is equivalent to that of an object constructed from `args`.
1301 /// This method requires that the (template parameter) type `KEY` be
1302 /// `emplace-constructible` into this unordered multiset from `args`
1303 /// (see {Requirements on `KEY`}).
1304 template <class... Args>
1305 iterator emplace(Args&&... args);
1306
1307 /// Insert into this unordered multiset a newly created `value_type`
1308 /// object, constructed by forwarding `get_allocator()` (if required)
1309 /// and the specified (variable number of) `args` to the corresponding
1310 /// constructor of `value_type` (in constant time if the specified
1311 /// `hint` refers to an element in this container equivalent to the
1312 /// newly created `value_type` object). Return an iterator referring to
1313 /// the newly created and inserted object in this unordered multiset
1314 /// whose value is equivalent to that of an object constructed from
1315 /// `args`. If `hint` does not refer to an element in this container
1316 /// equivalent to the newly created `value_type` object, this operation
1317 /// has worst case `O[N]` and average case constant-time complexity,
1318 /// where `N` is the size of this unordered multiset. This method
1319 /// requires that the (template parameter) type `KEY` be
1320 /// `emplace-constructible` into this unordered multiset from `args`
1321 /// (see {Requirements on `KEY`}). The behavior is undefined unless
1322 /// `hint` is an iterator in the range `[begin() .. end()]` (both
1323 /// endpoints included).
1324 template <class... Args>
1325 iterator emplace_hint(const_iterator hint, Args&&... args);
1326
1327#endif
1328
1329 /// Set the maximum load factor of this container to the specified
1330 /// `newLoadFactor`.
1331 void max_load_factor(float newLoadFactor);
1332
1333 /// Change the size of the array of buckets maintained by this container
1334 /// to at least the specified `numBuckets`, and redistribute all the
1335 /// contained elements into the new sequence of buckets, according to
1336 /// their hash values. Note that this operation has no effect if
1337 /// rehashing the elements into `numBuckets` would cause this unordered
1338 /// multiset to exceed its `max_load_factor`.
1339 void rehash(size_type numBuckets);
1340
1341 /// Increase the number of buckets of this unordered multiset to a
1342 /// quantity such that the ratio between the specified `numElements` and
1343 /// this quantity does not exceed `max_load_factor`. Note that this
1344 /// guarantees that, after the reserve, elements can be inserted to grow
1345 /// the container to `size() == numElements` without rehashing. Also
1346 /// note that memory allocations may still occur when growing the
1347 /// container to `size() == numElements`. Also note that this operation
1348 /// has no effect if `numElements <= size()`.
1349 void reserve(size_type numElements);
1350
1351 /// Exchange the value, hasher, key-equality functor, and
1352 /// `max_load_factor` of this object with those of the specified `other`
1353 /// object; also exchange the allocator of this object with that of
1354 /// `other` if the (template parameter) type `ALLOCATOR` has the
1355 /// `propagate_on_container_swap` trait, and do not modify either
1356 /// allocator otherwise. This method provides the no-throw
1357 /// exception-safety guarantee if and only if both the (template
1358 /// parameter) types `HASH` and `EQUAL` provide no-throw swap
1359 /// operations; if an exception is thrown, both objects are left in
1360 /// valid but unspecified states. This operation guarantees `O[1]`
1361 /// complexity. The behavior is undefined unless either this object was
1362 /// created with the same allocator as `other` or `ALLOCATOR` has the
1363 /// `propagate_on_container_swap` trait.
1364 void swap(unordered_multiset& other)
1365 BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(
1366 AllocatorTraits::is_always_equal::value
1367 && bsl::is_nothrow_swappable<HASH>::value
1368 && bsl::is_nothrow_swappable<EQUAL>::value);
1369
1370 // ACCESSORS
1371
1372 /// Return (a copy of) the allocator used for memory allocation by this
1373 /// unordered multiset.
1374 ALLOCATOR get_allocator() const BSLS_KEYWORD_NOEXCEPT;
1375
1376 const_iterator begin() const BSLS_KEYWORD_NOEXCEPT;
1377
1378 /// Return an iterator providing non-modifiable access to the first
1379 /// `value_type` object in the sequence of `value_type` objects
1380 /// maintained by this unordered multiset, or the `end` iterator if this
1381 /// unordered multiset is empty.
1382 const_iterator cbegin() const BSLS_KEYWORD_NOEXCEPT;
1383
1384 const_iterator end() const BSLS_KEYWORD_NOEXCEPT;
1385
1386 /// Return an iterator providing non-modifiable access to the
1387 /// past-the-end element in the sequence of `value_type` objects
1388 /// maintained by this unordered multiset.
1389 const_iterator cend() const BSLS_KEYWORD_NOEXCEPT;
1390
1391 /// Return `true` if this unordered multiset contains an element whose
1392 /// key is equivalent to the specified `key`.
1393 bool contains(const key_type &key) const;
1394
1395 /// Return `true` if this unordered multiset contains an element whose
1396 /// key is equivalent to the specified `key`.
1397 template <class LOOKUP_KEY>
1398 typename enable_if<
1399 BloombergLP::bslmf::IsTransparentPredicate<HASH, LOOKUP_KEY>::value &&
1400 BloombergLP::bslmf::IsTransparentPredicate<EQUAL,
1401 LOOKUP_KEY>::value,
1402 bool>::type
1403 contains(const LOOKUP_KEY& key) const
1404 {
1405 // Note: implemented inline due to Sun CC compilation error
1406 return find(key) != end();
1407 }
1408
1409 /// Return `true` if this unordered multiset contains no elements, and
1410 /// `false` otherwise.
1411 bool empty() const BSLS_KEYWORD_NOEXCEPT;
1412
1413 /// Return the number of elements in this unordered multiset.
1414 size_type size() const BSLS_KEYWORD_NOEXCEPT;
1415
1416 /// Return a theoretical upper bound on the largest number of elements
1417 /// that this unordered multiset could possibly hold. Note that there
1418 /// is no guarantee that the unordered multiset can successfully grow to
1419 /// the returned size, or even close to that size without running out of
1420 /// resources.
1421 size_type max_size() const BSLS_KEYWORD_NOEXCEPT;
1422
1423 /// Return (a copy of) the key-equality binary functor that returns
1424 /// `true` if the value of two `key_type` objects are equivalent, and
1425 /// `false` otherwise.
1426 EQUAL key_eq() const;
1427
1428 /// Return (a copy of) the hash unary functor used by this unordered
1429 /// multiset to generate a hash value (of type `size_t`) for a
1430 /// `key_type` object.
1431 HASH hash_function() const;
1432
1433 /// Return an iterator providing non-modifiable access to the first
1434 /// `value_type` object in the sequence of all the value elements of
1435 /// this unordered multiset equivalent to the specified `key`, if such
1436 /// entries exist, and the past-the-end (`end`) iterator otherwise. The
1437 /// behavior is undefined unless `key` is equivalent to the elements of
1438 /// at most one equivalent-key group in this unordered multiset.
1439 template <class LOOKUP_KEY>
1440 typename enable_if<
1441 BloombergLP::bslmf::IsTransparentPredicate<HASH, LOOKUP_KEY>::value
1442 && BloombergLP::bslmf::IsTransparentPredicate<EQUAL,LOOKUP_KEY>::value,
1443 const_iterator>::type
1444 find(const LOOKUP_KEY& key) const
1445 {
1446 // Note: implemented inline due to Sun CC compilation error.
1447 return const_iterator(d_impl.find(key));
1448 }
1449
1450 /// Return an iterator providing non-modifiable access to the first
1451 /// `value_type` object in the sequence of all the value elements of
1452 /// this unordered multiset equivalent to the specified `key`, if such
1453 /// entries exist, and the past-the-end (`end`) iterator otherwise.
1454 const_iterator find(const key_type& key) const;
1455
1456 /// Return the number of `value_type` objects within this unordered
1457 /// multiset that are equivalent to the specified `key`. The behavior
1458 /// is undefined unless `key` is equivalent to the elements of at most
1459 /// one equivalent-key group in this unordered multiset.
1460 template <class LOOKUP_KEY>
1461 typename enable_if<
1462 BloombergLP::bslmf::IsTransparentPredicate<HASH, LOOKUP_KEY>::value
1463 && BloombergLP::bslmf::IsTransparentPredicate<EQUAL,LOOKUP_KEY>::value,
1464 size_type>::type
1465 count(const LOOKUP_KEY& key) const
1466 {
1467 // Note: implemented inline due to Sun CC compilation error.
1468 typedef ::BloombergLP::bslalg::BidirectionalNode<value_type> BNode;
1469
1470 size_type result = 0;
1471 for (HashTableLink *cursor = d_impl.find(key);
1472 cursor;
1473 ++result, cursor = cursor->nextLink()) {
1474
1475 BNode *cursorNode = static_cast<BNode *>(cursor);
1476 if (!this->key_eq()(
1477 key,
1478 ListConfiguration::extractKey(cursorNode->value()))) {
1479 break;
1480 }
1481 }
1482 return result;
1483 }
1484
1485 /// Return the number of `value_type` objects within this unordered
1486 /// multiset that are equivalent to the specified `key`.
1487 size_type count(const key_type& key) const;
1488
1489 /// Return a pair of iterators providing non-modifiable access to the
1490 /// sequence of `value_type` objects in this unordered multiset
1491 /// equivalent to the specified `key`, where the first iterator is
1492 /// positioned at the start of the sequence, and the second is
1493 /// positioned one past the end of the sequence. If this unordered
1494 /// multiset contains no `value_type` objects equivalent to the `key`,
1495 /// then the two returned iterators will have the same value. The
1496 /// behavior is undefined unless `key` is equivalent to the elements of
1497 /// at most one equivalent-key group in this unordered multiset.
1498 template <class LOOKUP_KEY>
1499 typename enable_if<
1500 BloombergLP::bslmf::IsTransparentPredicate<HASH, LOOKUP_KEY>::value
1501 && BloombergLP::bslmf::IsTransparentPredicate<EQUAL,LOOKUP_KEY>::value,
1502 pair<const_iterator, const_iterator> >::type
1503 equal_range(const LOOKUP_KEY& key) const
1504 {
1505 // Note: implemented inline due to Sun CC compilation error.
1506 typedef bsl::pair<const_iterator, const_iterator> ResultType;
1507 HashTableLink *first;
1508 HashTableLink *last;
1509 d_impl.findRange(&first, &last, key);
1510 return ResultType(const_iterator(first), const_iterator(last));
1511 }
1512
1513
1514 /// Return a pair of iterators providing non-modifiable access to the
1515 /// sequence of `value_type` objects in this unordered multiset
1516 /// equivalent to the specified `key`, where the first iterator is
1517 /// positioned at the start of the sequence, and the second is
1518 /// positioned one past the end of the sequence. If this unordered
1519 /// multiset contains no `value_type` objects equivalent to the `key`,
1520 /// then the two returned iterators will have the same value.
1521 pair<const_iterator, const_iterator> equal_range(
1522 const key_type& key) const;
1523
1524 const_local_iterator begin(size_type index) const;
1525
1526 /// Return a local iterator providing non-modifiable access to the first
1527 /// `value_type` object (in the sequence of `value_type` objects) of the
1528 /// bucket having the specified `index` in the array of buckets
1529 /// maintained by this unordered multiset, or the `end(index)`
1530 /// otherwise. The behavior is undefined unless 'index <
1531 /// bucket_count()'.
1532 const_local_iterator cbegin(size_type index) const;
1533
1534 const_local_iterator end(size_type index) const;
1535
1536 /// Return a local iterator providing non-modifiable access to the
1537 /// past-the-end element (in the sequence of `value_type` objects) of
1538 /// the bucket having the specified `index` in the array of buckets
1539 /// maintained by this unordered multiset. The behavior is undefined
1540 /// unless `index < bucket_count()`.
1541 const_local_iterator cend(size_type index) const;
1542
1543 /// Return the index of the bucket, in the array of buckets of this
1544 /// container, where a value equivalent to the specified `key` would be
1545 /// inserted.
1546 size_type bucket(const key_type& key) const;
1547
1548 /// Return the number of buckets in the array of buckets maintained by
1549 /// this unordered multiset.
1550 size_type bucket_count() const BSLS_KEYWORD_NOEXCEPT;
1551
1552 /// Return a theoretical upper bound on the largest number of buckets
1553 /// that this container could possibly manage. Note that there is no
1554 /// guarantee that the unordered multiset can successfully grow to the
1555 /// returned size, or even close to that size without running out of
1556 /// resources.
1557 size_type max_bucket_count() const BSLS_KEYWORD_NOEXCEPT;
1558
1559 /// Return the number of elements contained in the bucket at the
1560 /// specified `index` in the array of buckets maintained by this
1561 /// container. The behavior is undefined unless 'index <
1562 /// bucket_count()'.
1563 size_type bucket_size(size_type index) const;
1564
1565
1566 /// Return the current ratio between the `size` of this container and
1567 /// the number of buckets. The @ref load_factor is a measure of how full
1568 /// the container is, and a higher load factor leads to an increased
1569 /// number of collisions, thus resulting in a loss performance.
1570 float load_factor() const BSLS_KEYWORD_NOEXCEPT;
1571
1572 /// Return the maximum load factor allowed for this container. If an
1573 /// insert operation would cause @ref load_factor to exceed the
1574 /// `max_load_factor`, that same insert operation will increase the
1575 /// number of buckets and rehash the elements of the container into
1576 /// those buckets the (see rehash).
1577 float max_load_factor() const BSLS_KEYWORD_NOEXCEPT;
1578
1579};
1580
1581#ifdef BSLS_COMPILERFEATURES_SUPPORT_CTAD
1582// CLASS TEMPLATE DEDUCTION GUIDES
1583
1584/// Deduce the template parameter `KEY` from the `value_type` of the
1585/// iterators supplied to the constructor of @ref unordered_multiset . Deduce
1586/// the template parameters `HASH`, `EQUAL` and `ALLOCATOR` from the other
1587/// parameters passed to the constructor. This deduction guide does not
1588/// participate unless: (1) the supplied `HASH` is invocable with a `KEY`,
1589/// (2) the supplied `EQUAL` is invocable with two `KEY`s, and (3) the
1590/// supplied allocator meets the requirements of a standard allocator.
1591template <
1592 class INPUT_ITERATOR,
1593 class KEY = BloombergLP::bslstl::IteratorUtil::IterVal_t<INPUT_ITERATOR>,
1594 class HASH = bsl::hash<KEY>,
1595 class EQUAL = bsl::equal_to<KEY>,
1596 class ALLOCATOR = bsl::allocator<KEY>,
1597 class = bsl::enable_if_t<std::is_invocable_v<HASH, const KEY&>>,
1598 class = bsl::enable_if_t<
1599 std::is_invocable_v<EQUAL, const KEY&, const KEY&>>,
1600 class = bsl::enable_if_t< bsl::IsStdAllocator_v<ALLOCATOR>>
1601 >
1602unordered_multiset(INPUT_ITERATOR,
1603 INPUT_ITERATOR,
1604 typename bsl::allocator_traits<ALLOCATOR>::size_type = 0,
1605 HASH = HASH(),
1606 EQUAL = EQUAL(),
1607 ALLOCATOR = ALLOCATOR())
1608-> unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>;
1609
1610/// Deduce the template parameter `KEY` from the `value_type` of the
1611/// iterators supplied to the constructor of @ref unordered_multiset . Deduce
1612/// the template parameters `HASH` and `EQUAL` from the other parameters
1613/// passed to the constructor. This deduction guide does not participate
1614/// unless the supplied allocator is convertible to `bsl::allocator<KEY>`.
1615template <
1616 class INPUT_ITERATOR,
1617 class KEY = BloombergLP::bslstl::IteratorUtil::IterVal_t<INPUT_ITERATOR>,
1618 class HASH,
1619 class EQUAL,
1620 class ALLOC,
1621 class DEFAULT_ALLOCATOR = bsl::allocator<KEY>,
1622 class = bsl::enable_if_t<bsl::is_convertible_v<ALLOC *, DEFAULT_ALLOCATOR>>
1623 >
1624unordered_multiset(
1625 INPUT_ITERATOR,
1626 INPUT_ITERATOR,
1627 typename bsl::allocator_traits<DEFAULT_ALLOCATOR>::size_type,
1628 HASH,
1629 EQUAL,
1630 ALLOC *)
1631-> unordered_multiset<KEY, HASH, EQUAL>;
1632
1633/// Deduce the template parameter `KEY` from the `value_type` of the
1634/// iterators supplied to the constructor of @ref unordered_multiset . Deduce
1635/// the template parameters `HASH` and `ALLOCATOR` from the other parameters
1636/// passed to the constructor. This deduction guide does not participate
1637/// unless the supplied `HASH` is invocable with a `KEY`, and the supplied
1638/// allocator meets the requirements of a standard allocator.
1639template <
1640 class INPUT_ITERATOR,
1641 class KEY = BloombergLP::bslstl::IteratorUtil::IterVal_t<INPUT_ITERATOR>,
1642 class HASH,
1643 class ALLOCATOR,
1644 class = bsl::enable_if_t<std::is_invocable_v<HASH, const KEY &>>,
1645 class = bsl::enable_if_t< bsl::IsStdAllocator_v<ALLOCATOR>>
1646 >
1647unordered_multiset(INPUT_ITERATOR,
1648 INPUT_ITERATOR,
1649 typename bsl::allocator_traits<ALLOCATOR>::size_type,
1650 HASH,
1651 ALLOCATOR)
1652-> unordered_multiset<KEY, HASH, bsl::equal_to<KEY>, ALLOCATOR>;
1653
1654/// Deduce the template parameter `KEY` from the `value_type` of the
1655/// iterators supplied to the constructor of @ref unordered_multiset . Deduce
1656/// the template parameter `HASH` from the other parameters passed to the
1657/// constructor. This deduction guide does not participate unless the
1658/// supplied allocator is convertible to `bsl::allocator<KEY>`.
1659template <
1660 class INPUT_ITERATOR,
1661 class KEY = BloombergLP::bslstl::IteratorUtil::IterVal_t<INPUT_ITERATOR>,
1662 class HASH,
1663 class ALLOC,
1664 class DEFAULT_ALLOCATOR = bsl::allocator<KEY>,
1665 class = bsl::enable_if_t<bsl::is_convertible_v<ALLOC *, DEFAULT_ALLOCATOR>>
1666 >
1667unordered_multiset(
1668 INPUT_ITERATOR,
1669 INPUT_ITERATOR,
1670 typename bsl::allocator_traits<DEFAULT_ALLOCATOR>::size_type,
1671 HASH,
1672 ALLOC *)
1673-> unordered_multiset<KEY, HASH>;
1674
1675/// Deduce the template parameter `KEY` from the `value_type` of the
1676/// iterators supplied to the constructor of @ref unordered_multiset . This
1677/// deduction guide does not participate unless the supplied allocator meets
1678/// the requirements of a standard allocator.
1679template <
1680 class INPUT_ITERATOR,
1681 class ALLOCATOR,
1682 class KEY = BloombergLP::bslstl::IteratorUtil::IterVal_t<INPUT_ITERATOR>,
1683 class = bsl::enable_if_t<bsl::IsStdAllocator_v<ALLOCATOR>>
1684 >
1685unordered_multiset(INPUT_ITERATOR,
1686 INPUT_ITERATOR,
1687 typename bsl::allocator_traits<ALLOCATOR>::size_type,
1688 ALLOCATOR)
1689-> unordered_multiset<KEY, bsl::hash<KEY>, bsl::equal_to<KEY>, ALLOCATOR>;
1690
1691/// Deduce the template parameter `KEY` from the `value_type` of the
1692/// iterators supplied to the constructor of @ref unordered_multiset . This
1693/// deduction guide does not participate unless the supplied allocator is
1694/// convertible to `bsl::allocator<KEY>`.
1695template <
1696 class INPUT_ITERATOR,
1697 class KEY = BloombergLP::bslstl::IteratorUtil::IterVal_t<INPUT_ITERATOR>,
1698 class ALLOC,
1699 class DEFAULT_ALLOCATOR = bsl::allocator<KEY>,
1700 class = bsl::enable_if_t<bsl::is_convertible_v<ALLOC *, DEFAULT_ALLOCATOR>>
1701 >
1702unordered_multiset(
1703 INPUT_ITERATOR,
1704 INPUT_ITERATOR,
1705 typename bsl::allocator_traits<DEFAULT_ALLOCATOR>::size_type,
1706 ALLOC *)
1707-> unordered_multiset<KEY>;
1708
1709/// Deduce the template parameter `KEY` from the `value_type` of the
1710/// iterators supplied to the constructor of @ref unordered_multiset . This
1711/// deduction guide does not participate unless the supplied allocator meets
1712/// the requirements of a standard allocator.
1713template <
1714 class INPUT_ITERATOR,
1715 class ALLOCATOR,
1716 class KEY = BloombergLP::bslstl::IteratorUtil::IterVal_t<INPUT_ITERATOR>,
1717 class = bsl::enable_if_t<bsl::IsStdAllocator_v<ALLOCATOR>>
1718 >
1719unordered_multiset(INPUT_ITERATOR, INPUT_ITERATOR, ALLOCATOR)
1720-> unordered_multiset<KEY, bsl::hash<KEY>, bsl::equal_to<KEY>, ALLOCATOR>;
1721
1722/// Deduce the template parameter `KEY` from the `value_type` of the
1723/// iterators supplied to the constructor of @ref unordered_multiset . This
1724/// deduction guide does not participate unless the supplied allocator is
1725/// convertible to `bsl::allocator<KEY>`.
1726template <
1727 class INPUT_ITERATOR,
1728 class KEY = BloombergLP::bslstl::IteratorUtil::IterVal_t<INPUT_ITERATOR>,
1729 class ALLOC,
1730 class DEFAULT_ALLOCATOR = bsl::allocator<KEY>,
1731 class = bsl::enable_if_t<bsl::is_convertible_v<ALLOC *, DEFAULT_ALLOCATOR>>
1732 >
1733unordered_multiset(INPUT_ITERATOR, INPUT_ITERATOR, ALLOC *)
1734-> unordered_multiset<KEY>;
1735
1736/// Deduce the template parameter `KEY` from the `value_type` of the
1737/// initializer_list supplied to the constructor of @ref unordered_multiset .
1738/// Deduce the template parameters `HASH`, EQUAL and `ALLOCATOR` from the
1739/// other parameters passed to the constructor. This deduction guide does
1740/// not participate unless: (1) the supplied `HASH` is invocable with a
1741/// `KEY`, (2) the supplied `EQUAL` is invocable with two `KEY`s, and (3)
1742/// the supplied allocator meets the requirements of a standard allocator.
1743template <
1744 class KEY,
1745 class HASH = bsl::hash<KEY>,
1746 class EQUAL = bsl::equal_to<KEY>,
1747 class ALLOCATOR = bsl::allocator<KEY>,
1748 class = bsl::enable_if_t<std::is_invocable_v<HASH, const KEY&>>,
1749 class = bsl::enable_if_t<
1750 std::is_invocable_v<EQUAL, const KEY&, const KEY&>>,
1751 class = bsl::enable_if_t< bsl::IsStdAllocator_v<ALLOCATOR>>
1752 >
1753unordered_multiset(std::initializer_list<KEY>,
1754 typename bsl::allocator_traits<ALLOCATOR>::size_type = 0,
1755 HASH = HASH(),
1756 EQUAL = EQUAL(),
1757 ALLOCATOR = ALLOCATOR())
1758-> unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>;
1759
1760/// Deduce the template parameter `KEY` from the `value_type` of the
1761/// initializer_list supplied to the constructor of @ref unordered_multiset .
1762/// Deduce the template parameters `HASH` and `EQUAL` from the other
1763/// parameters passed to the constructor. This deduction guide does not
1764/// participate unless the supplied allocator is convertible to
1765/// `bsl::allocator<KEY>`.
1766template <
1767 class KEY,
1768 class HASH,
1769 class EQUAL,
1770 class ALLOC,
1771 class DEFAULT_ALLOCATOR = bsl::allocator<KEY>,
1772 class = bsl::enable_if_t<bsl::is_convertible_v<ALLOC *, DEFAULT_ALLOCATOR>>
1773 >
1774unordered_multiset(
1775 std::initializer_list<KEY>,
1776 typename bsl::allocator_traits<DEFAULT_ALLOCATOR>::size_type,
1777 HASH,
1778 EQUAL,
1779 ALLOC *)
1780-> unordered_multiset<KEY, HASH, EQUAL>;
1781
1782/// Deduce the template parameter `KEY` from the `value_type` of the
1783/// initializer_list supplied to the constructor of @ref unordered_multiset .
1784/// Deduce the template parameters `HASH` and `ALLOCATOR` from the other
1785/// parameters passed to the constructor. This deduction guide does not
1786/// participate unless the supplied `HASH` is invocable with a `KEY`, and
1787/// the supplied allocator meets the requirements of a standard allocator.
1788template <
1789 class KEY,
1790 class HASH,
1791 class ALLOCATOR,
1792 class = bsl::enable_if_t<std::is_invocable_v<HASH, const KEY &>>,
1793 class = bsl::enable_if_t< bsl::IsStdAllocator_v<ALLOCATOR>>
1794 >
1795unordered_multiset(std::initializer_list<KEY>,
1796 typename bsl::allocator_traits<ALLOCATOR>::size_type,
1797 HASH,
1798 ALLOCATOR)
1799-> unordered_multiset<KEY, HASH, bsl::equal_to<KEY>, ALLOCATOR>;
1800
1801
1802/// Deduce the template parameter `KEY` from the `value_type` of the
1803/// initializer_list supplied to the constructor of @ref unordered_multiset .
1804/// Deduce the template parameter `HASH` from the other parameters passed to
1805/// the constructor. This deduction guide does not participate unless the
1806/// supplied allocator is convertible to `bsl::allocator<KEY>`.
1807template <
1808 class KEY,
1809 class HASH,
1810 class ALLOC,
1811 class DEFAULT_ALLOCATOR = bsl::allocator<KEY>,
1812 class = bsl::enable_if_t<bsl::is_convertible_v<ALLOC *, DEFAULT_ALLOCATOR>>
1813 >
1814unordered_multiset(
1815 std::initializer_list<KEY>,
1816 typename bsl::allocator_traits<DEFAULT_ALLOCATOR>::size_type,
1817 HASH,
1818 ALLOC *)
1819-> unordered_multiset<KEY, HASH>;
1820
1821/// Deduce the template parameter `KEY` from the `value_type` of the
1822/// initializer_list supplied to the constructor of @ref unordered_multiset .
1823/// This deduction guide does not participate unless the supplied allocator
1824/// meets the requirements of a standard allocator.
1825template <
1826 class KEY,
1827 class ALLOCATOR,
1828 class = bsl::enable_if_t<bsl::IsStdAllocator_v<ALLOCATOR>>
1829 >
1830unordered_multiset(std::initializer_list<KEY>,
1831 typename bsl::allocator_traits<ALLOCATOR>::size_type,
1832 ALLOCATOR)
1833-> unordered_multiset<KEY, bsl::hash<KEY>, bsl::equal_to<KEY>, ALLOCATOR>;
1834
1835/// Deduce the template parameter `KEY` from the `value_type` of the
1836/// initializer_list supplied to the constructor of @ref unordered_multiset .
1837/// This deduction guide does not participate unless the supplied allocator
1838/// is convertible to `bsl::allocator<KEY>`.
1839template <
1840 class KEY,
1841 class ALLOC,
1842 class DEFAULT_ALLOCATOR = bsl::allocator<KEY>,
1843 class = bsl::enable_if_t<bsl::is_convertible_v<ALLOC *, DEFAULT_ALLOCATOR>>
1844 >
1845unordered_multiset(
1846 std::initializer_list<KEY>,
1847 typename bsl::allocator_traits<DEFAULT_ALLOCATOR>::size_type,
1848 ALLOC *)
1849-> unordered_multiset<KEY>;
1850
1851/// Deduce the template parameter `KEY` from the `value_type` of the
1852/// initializer_list supplied to the constructor of @ref unordered_multiset .
1853/// This deduction guide does not participate unless the supplied allocator
1854/// meets the requirements of a standard allocator.
1855template <
1856 class KEY,
1857 class ALLOCATOR,
1858 class = bsl::enable_if_t<bsl::IsStdAllocator_v<ALLOCATOR>>
1859 >
1860unordered_multiset(std::initializer_list<KEY>, ALLOCATOR)
1861-> unordered_multiset<KEY, bsl::hash<KEY>, bsl::equal_to<KEY>, ALLOCATOR>;
1862
1863/// Deduce the template parameter `KEY` from the `value_type` of the
1864/// initializer_list supplied to the constructor of @ref unordered_multiset .
1865/// This deduction guide does not participate unless the supplied allocator
1866/// is convertible to `bsl::allocator<KEY>`.
1867template <
1868 class KEY,
1869 class ALLOC,
1870 class DEFAULT_ALLOCATOR = bsl::allocator<KEY>,
1871 class = bsl::enable_if_t<bsl::is_convertible_v<ALLOC *, DEFAULT_ALLOCATOR>>
1872 >
1873unordered_multiset(std::initializer_list<KEY>, ALLOC *)
1874-> unordered_multiset<KEY>;
1875#endif
1876
1877// FREE OPERATORS
1878
1879/// Return `true` if the specified `lhs` and `rhs` objects have the same
1880/// value, and `false` otherwise. Two @ref unordered_multiset objects have the
1881/// same value if they have the same number of value elements, and for each
1882/// value-element that is contained in `lhs` there is a value-element
1883/// contained in `rhs` having the same value, and vice-versa. Note that
1884/// this method requires that the (template parameter) type `KEY` be
1885/// `equality-comparable` (see {Requirements on `KEY`}).
1886template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
1887bool operator==(const unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>& lhs,
1888 const unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>& rhs);
1889
1890#ifndef BSLS_COMPILERFEATURES_SUPPORT_THREE_WAY_COMPARISON
1891template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
1892bool operator!=(const unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>& lhs,
1893 const unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>& rhs);
1894 // Return 'true' if the specified 'lhs' and 'rhs' objects do not have the
1895 // same value, and 'false' otherwise. Two @ref unordered_multiset objects do
1896 // not have the same value if they do not have the same number of
1897 // value elements, or that for some value-element contained in 'lhs' there
1898 // is not a value-element in 'rhs' having the same value, and vice-versa.
1899 // Note that this method requires that the (template parameter) type 'KEY'
1900 // and be 'equality-comparable' (see {Requirements on 'KEY'}).
1901#endif
1902
1903// FREE FUNCTIONS
1904
1905/// Erase all the elements in the specified unordered_multiset `ms` that
1906/// satisfy the specified predicate `predicate`. Return the number of
1907/// elements erased.
1908template <class KEY, class HASH, class EQUAL, class ALLOCATOR, class PREDICATE>
1909typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::size_type
1910erase_if(unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>& ms,
1911 PREDICATE predicate);
1912
1913template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
1914void swap(unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>& a,
1915 unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>& b)
1916 BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(
1917 BSLS_KEYWORD_NOEXCEPT_OPERATOR(a.swap(b)));
1918 // Exchange the value, hasher, key-equality functor, and 'max_load_factor'
1919 // of the specified 'a' object with those of the specified 'b' object; also
1920 // exchange the allocator of 'a' with that of 'b' if the (template
1921 // parameter) type 'ALLOCATOR' has the 'propagate_on_container_swap' trait,
1922 // and do not modify either allocator otherwise. This function provides
1923 // the no-throw exception-safety guarantee if and only if both the
1924 // (template parameter) types 'HASH' and 'EQUAL' provide no-throw swap
1925 // operations; if an exception is thrown, both objects are left in valid
1926 // but unspecified states. This operation guarantees 'O[1]' complexity.
1927 // The behavior is undefined unless either 'a' was created with the same
1928 // allocator as 'b' or 'ALLOCATOR' has the 'propagate_on_container_swap'
1929 // trait.
1930
1931// ============================================================================
1932// TEMPLATE AND INLINE FUNCTION DEFINITIONS
1933// ============================================================================
1934
1935 //-------------------------
1936 // class unordered_multiset
1937 //-------------------------
1938
1939// CREATORS
1940template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
1941inline
1942unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::unordered_multiset()
1943: d_impl(HASH(), EQUAL(), 0, 1.0f, ALLOCATOR())
1944{
1945}
1946
1947template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
1948inline
1949unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::unordered_multiset(
1950 size_type initialNumBuckets,
1951 const HASH& hashFunction,
1952 const EQUAL& keyEqual,
1953 const ALLOCATOR& basicAllocator)
1954: d_impl(hashFunction, keyEqual, initialNumBuckets, 1.0f, basicAllocator)
1955{
1956}
1957
1958template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
1959inline
1960unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::unordered_multiset(
1961 size_type initialNumBuckets,
1962 const HASH& hashFunction,
1963 const ALLOCATOR& basicAllocator)
1964: d_impl(hashFunction, EQUAL(), initialNumBuckets, 1.0f, basicAllocator)
1965{
1966}
1967
1968template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
1969inline
1970unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::unordered_multiset(
1971 size_type initialNumBuckets,
1972 const ALLOCATOR& basicAllocator)
1973: d_impl(HASH(), EQUAL(), initialNumBuckets, 1.0f, basicAllocator)
1974{
1975}
1976
1977template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
1978inline
1979unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::unordered_multiset(
1980 const ALLOCATOR& basicAllocator)
1981: d_impl(basicAllocator)
1982{
1983}
1984
1985template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
1986inline
1987unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::unordered_multiset(
1988 const unordered_multiset& original)
1989: d_impl(original.d_impl,
1990 AllocatorTraits::select_on_container_copy_construction(
1991 original.get_allocator()))
1992{
1993}
1994
1995template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
1996inline
1997unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::unordered_multiset(
1998 BloombergLP::bslmf::MovableRef<unordered_multiset> original)
1999: d_impl(MoveUtil::move(MoveUtil::access(original).d_impl))
2000{
2001}
2002
2003template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2004inline
2005unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::unordered_multiset(
2006 const unordered_multiset& original,
2007 const typename type_identity<ALLOCATOR>::type& basicAllocator)
2008: d_impl(original.d_impl, basicAllocator)
2009{
2010}
2011
2012template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2013inline
2014unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::unordered_multiset(
2015 BloombergLP::bslmf::MovableRef<unordered_multiset> original,
2016 const typename type_identity<ALLOCATOR>::type& basicAllocator)
2017: d_impl(MoveUtil::move(MoveUtil::access(original).d_impl), basicAllocator)
2018{
2019}
2020
2021template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2022template <class INPUT_ITERATOR>
2023inline
2024unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::unordered_multiset(
2025 INPUT_ITERATOR first,
2026 INPUT_ITERATOR last,
2027 size_type initialNumBuckets,
2028 const HASH& hashFunction,
2029 const EQUAL& keyEqual,
2030 const ALLOCATOR& basicAllocator)
2031: d_impl(hashFunction, keyEqual, initialNumBuckets, 1.0f, basicAllocator)
2032{
2033 this->insert(first, last);
2034}
2035
2036template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2037template <class INPUT_ITERATOR>
2038inline
2039unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::unordered_multiset(
2040 INPUT_ITERATOR first,
2041 INPUT_ITERATOR last,
2042 size_type initialNumBuckets,
2043 const HASH& hashFunction,
2044 const ALLOCATOR& basicAllocator)
2045: d_impl(hashFunction, EQUAL(), initialNumBuckets, 1.0f, basicAllocator)
2046{
2047 this->insert(first, last);
2048}
2049
2050template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2051template <class INPUT_ITERATOR>
2052inline
2053unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::unordered_multiset(
2054 INPUT_ITERATOR first,
2055 INPUT_ITERATOR last,
2056 size_type initialNumBuckets,
2057 const ALLOCATOR& basicAllocator)
2058: d_impl(HASH(), EQUAL(), initialNumBuckets, 1.0f, basicAllocator)
2059{
2060 this->insert(first, last);
2061}
2062
2063template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2064template <class INPUT_ITERATOR>
2065inline
2066unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::unordered_multiset(
2067 INPUT_ITERATOR first,
2068 INPUT_ITERATOR last,
2069 const ALLOCATOR& basicAllocator)
2070: d_impl(HASH(), EQUAL(), 0, 1.0f, basicAllocator)
2071{
2072 this->insert(first, last);
2073}
2074
2075#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
2076template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2077#ifdef BSLS_COMPILERFEATURES_SUPPORT_CTAD
2078template <class, class, class>
2079#endif
2080inline
2081unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::unordered_multiset(
2082 std::initializer_list<KEY> values,
2083 size_type initialNumBuckets,
2084 const hasher& hashFunction,
2085 const key_equal& keyEqual,
2086 const ALLOCATOR& basicAllocator)
2087: unordered_multiset(values.begin(),
2088 values.end(),
2089 initialNumBuckets,
2090 hashFunction,
2091 keyEqual,
2092 basicAllocator)
2093{
2094}
2095
2096template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2097#ifdef BSLS_COMPILERFEATURES_SUPPORT_CTAD
2098template <class, class>
2099#endif
2100inline
2101unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::unordered_multiset(
2102 std::initializer_list<KEY> values,
2103 size_type initialNumBuckets,
2104 const HASH& hashFunction,
2105 const ALLOCATOR& basicAllocator)
2106: unordered_multiset(values.begin(),
2107 values.end(),
2108 initialNumBuckets,
2109 hashFunction,
2110 EQUAL(),
2111 basicAllocator)
2112{
2113}
2114
2115template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2116#ifdef BSLS_COMPILERFEATURES_SUPPORT_CTAD
2117template <class>
2118#endif
2119inline
2120unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::unordered_multiset(
2121 std::initializer_list<KEY> values,
2122 size_type initialNumBuckets,
2123 const ALLOCATOR& basicAllocator)
2124: unordered_multiset(values.begin(),
2125 values.end(),
2126 initialNumBuckets,
2127 HASH(),
2128 EQUAL(),
2129 basicAllocator)
2130{
2131}
2132
2133template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2134#ifdef BSLS_COMPILERFEATURES_SUPPORT_CTAD
2135template <class>
2136#endif
2137inline
2138unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::unordered_multiset(
2139 std::initializer_list<KEY> values,
2140 const ALLOCATOR& basicAllocator)
2141: unordered_multiset(values.begin(),
2142 values.end(),
2143 0,
2144 HASH(),
2145 EQUAL(),
2146 basicAllocator)
2147{
2148}
2149#endif // defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
2150
2151template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2152inline
2153unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::~unordered_multiset()
2154{
2155 // All memory management is handled by the base 'd_impl' member.
2156}
2157
2158// MANIPULATORS
2159template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2160inline
2161unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>&
2162unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::operator=(
2163 const unordered_multiset& rhs)
2164{
2165 // Note that we have delegated responsibility for correct handling of
2166 // allocator propagation to the 'HashTable' implementation.
2167
2168 d_impl = rhs.d_impl;
2169
2170 return *this;
2171}
2172
2173template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2174inline
2175unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>&
2176unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::operator=(
2177 BloombergLP::bslmf::MovableRef<unordered_multiset> rhs)
2178 BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(
2179 AllocatorTraits::is_always_equal::value
2180 && std::is_nothrow_move_assignable<HASH>::value
2181 && std::is_nothrow_move_assignable<EQUAL>::value)
2182{
2183 // Note that we have delegated responsibility for correct handling of
2184 // allocator propagation to the 'HashTable' implementation.
2185
2186 unordered_multiset& lvalue = rhs;
2187
2188 d_impl = MoveUtil::move(lvalue.d_impl);
2189
2190 return *this;
2191}
2192
2193#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
2194template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2195inline
2196unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>&
2197unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::operator=(
2198 std::initializer_list<KEY> values)
2199{
2200 unordered_multiset tmp(values, d_impl.allocator());
2201
2202 d_impl.swap(tmp.d_impl);
2203
2204 return *this;
2205}
2206#endif
2207
2208#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
2209template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2210template <class... Args>
2211inline
2212typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::iterator
2213unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::emplace(Args&&... arguments)
2214{
2215 return iterator(d_impl.emplace(
2216 BSLS_COMPILERFEATURES_FORWARD(Args, arguments)...));
2217
2218}
2219
2220template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2221template <class... Args>
2222inline
2223typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::iterator
2224unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::emplace_hint(
2225 const_iterator hint,
2226 Args&&... arguments)
2227{
2228 return iterator(d_impl.emplaceWithHint(hint.node(),
2229 BSLS_COMPILERFEATURES_FORWARD(Args, arguments)...));
2230}
2231#endif
2232
2233template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2234inline
2235typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::iterator
2240
2241template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2242inline
2243typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::iterator
2248
2249template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2250inline
2251typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::local_iterator
2252unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::begin(size_type index)
2253{
2254 BSLS_ASSERT_SAFE(index < this->bucket_count());
2255
2256 return local_iterator(&d_impl.bucketAtIndex(index));
2257}
2258
2259template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2260inline
2261typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::local_iterator
2262unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::end(size_type index)
2263{
2264 BSLS_ASSERT_SAFE(index < this->bucket_count());
2265
2266 return local_iterator(0, &d_impl.bucketAtIndex(index));
2267}
2268
2269template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2270inline
2271void
2276
2277template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2278typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::iterator
2279unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::find(const key_type& key)
2280{
2281 return iterator(d_impl.find(key));
2282}
2283
2284template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2285inline
2286bsl::pair<typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::iterator,
2287 typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::iterator>
2288unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::equal_range(
2289 const key_type& key)
2290{
2291 HashTableLink *first;
2292 HashTableLink *last;
2293 d_impl.findRange(&first, &last, key);
2294 return bsl::pair<iterator, iterator>(iterator(first), iterator(last));
2295}
2296
2297template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2298inline
2299typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::iterator
2300unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::erase(const_iterator position)
2301{
2302 BSLS_ASSERT(position != this->end());
2303
2304 return iterator(d_impl.remove(position.node()));
2305}
2306
2307template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2308typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::size_type
2309unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::erase(const key_type& key)
2310{
2311 typedef ::BloombergLP::bslalg::BidirectionalNode<value_type> BNode;
2312
2313 HashTableLink *target = d_impl.find(key);
2314 if (target) {
2315 target = d_impl.remove(target);
2316 size_type result = 1;
2317 while (target &&
2318 this->key_eq()(key, ListConfiguration::extractKey(
2319 static_cast<BNode *>(target)->value()))) {
2320 target = d_impl.remove(target);
2321 ++result;
2322 }
2323 return result; // RETURN
2324 }
2325
2326 return 0;
2327}
2328
2329template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2330typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::iterator
2331unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::erase(const_iterator first,
2332 const_iterator last)
2333{
2334
2335#if defined BDE_BUILD_TARGET_SAFE_2
2336 if (first != last) {
2337 iterator it = this->begin();
2338 const iterator end = this->end();
2339 for (; it != first; ++it) {
2340 BSLS_ASSERT(last != it);
2341 BSLS_ASSERT(end != it);
2342 }
2343 for (; it != last; ++it) {
2344 BSLS_ASSERT(end != it);
2345 }
2346 }
2347#endif
2348
2349 while (first != last) {
2350 first = this->erase(first);
2351 }
2352
2353 return iterator(first.node()); // convert from const_iterator
2354}
2355
2356template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2357inline
2358typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::iterator
2359unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::insert(
2360 const value_type& value)
2361{
2362 return iterator(d_impl.insert(value));
2363}
2364
2365template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2366inline
2367typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::iterator
2368unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::insert(
2369 BloombergLP::bslmf::MovableRef<value_type> value)
2370{
2371 return iterator(d_impl.insert(MoveUtil::move(value)));
2372}
2373
2374template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2375inline
2376typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::iterator
2377unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::insert(
2378 const_iterator hint,
2379 const value_type& value)
2380{
2381 return iterator(d_impl.insert(value, hint.node()));
2382}
2383
2384template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2385inline
2386typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::iterator
2387unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::insert(
2388 const_iterator hint,
2389 BloombergLP::bslmf::MovableRef<value_type> value)
2390{
2391 return iterator(d_impl.insert(MoveUtil::move(value), hint.node()));
2392}
2393
2394template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2395template <class INPUT_ITERATOR>
2396void
2397unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::insert(INPUT_ITERATOR first,
2398 INPUT_ITERATOR last)
2399{
2400 difference_type maxInsertions =
2401 ::BloombergLP::bslstl::IteratorUtil::insertDistance(first, last);
2402 if (maxInsertions) {
2403 this->reserve(this->size() + maxInsertions);
2404 }
2405
2406 while (first != last) {
2407 d_impl.insert(*first);
2408 ++first;
2409 }
2410}
2411
2412#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
2413template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2414inline
2415void unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::insert(
2416 std::initializer_list<KEY> values)
2417{
2418 insert(values.begin(), values.end());
2419}
2420#endif
2421
2422template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2423inline
2424void unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::max_load_factor(
2425 float newLoadFactor)
2426{
2427 d_impl.setMaxLoadFactor(newLoadFactor);
2428}
2429
2430template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2431inline
2432void
2433unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::rehash(size_type numBuckets)
2434{
2435 d_impl.rehashForNumBuckets(numBuckets);
2436}
2437
2438template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2439inline
2440void
2441unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::reserve(size_type numElements)
2442{
2443 d_impl.reserveForNumElements(numElements);
2444}
2445
2446template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2447inline
2448void
2449unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::swap(
2450 unordered_multiset& other)
2451 BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(
2452 AllocatorTraits::is_always_equal::value
2453 && bsl::is_nothrow_swappable<HASH>::value
2454 && bsl::is_nothrow_swappable<EQUAL>::value)
2455{
2456 d_impl.swap(other.d_impl);
2457}
2458
2459// ACCESSORS
2460template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2461inline
2462ALLOCATOR
2463unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::get_allocator() const
2464 BSLS_KEYWORD_NOEXCEPT
2465{
2466 return d_impl.allocator();
2467}
2468
2469template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2470inline
2471typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::const_iterator
2472unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::begin() const
2473 BSLS_KEYWORD_NOEXCEPT
2474{
2475 return const_iterator(d_impl.elementListRoot());
2476}
2477
2478template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2479inline
2480typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::const_iterator
2486
2487template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2488inline
2489typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::const_iterator
2490unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::cbegin() const
2491 BSLS_KEYWORD_NOEXCEPT
2492{
2493 return const_iterator(d_impl.elementListRoot());
2494}
2495
2496template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2497inline
2498typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::const_iterator
2504
2505template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2506inline
2507typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::const_local_iterator
2508unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::begin(size_type index) const
2509{
2510 BSLS_ASSERT_SAFE(index < this->bucket_count());
2511
2512 return const_local_iterator(&d_impl.bucketAtIndex(index));
2513}
2514
2515template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2516inline
2517typename
2518 unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::const_local_iterator
2519unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::end(size_type index) const
2520{
2521 BSLS_ASSERT_SAFE(index < this->bucket_count());
2522
2523 return const_local_iterator(0, &d_impl.bucketAtIndex(index));
2524}
2525
2526
2527template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2528inline
2529typename
2530 unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::const_local_iterator
2531unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::cbegin(size_type index) const
2532{
2533 BSLS_ASSERT_SAFE(index < this->bucket_count());
2534
2535 return const_local_iterator(&d_impl.bucketAtIndex(index));
2536}
2537
2538template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2539inline
2540typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::const_local_iterator
2541unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::cend(size_type index) const
2542{
2543 BSLS_ASSERT_SAFE(index < this->bucket_count());
2544
2545 return const_local_iterator(0, &d_impl.bucketAtIndex(index));
2546}
2547
2548template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2549inline
2550typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::size_type
2551unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::bucket(
2552 const key_type& key) const
2553{
2554 return d_impl.bucketIndexForKey(key);
2555}
2556
2557template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2558inline
2559typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::size_type
2560unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::bucket_count() const
2561 BSLS_KEYWORD_NOEXCEPT
2562{
2563 return d_impl.numBuckets();
2564}
2565
2566template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2567inline
2568typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::size_type
2569unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::bucket_size(
2570 size_type index) const
2571{
2572 BSLS_ASSERT_SAFE(index < this->bucket_count());
2573
2574 return d_impl.countElementsInBucket(index);
2575}
2576
2577template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2578typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::size_type
2579unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::count(
2580 const key_type& key) const
2581{
2582 typedef ::BloombergLP::bslalg::BidirectionalNode<value_type> BNode;
2583
2584 size_type result = 0;
2585 for (HashTableLink *cursor = d_impl.find(key);
2586 cursor;
2587 ++result, cursor = cursor->nextLink()) {
2588
2589 BNode *cursorNode = static_cast<BNode *>(cursor);
2590 if (!this->key_eq()(
2591 key,
2592 ListConfiguration::extractKey(cursorNode->value()))) {
2593 break;
2594 }
2595 }
2596 return result;
2597}
2598
2599template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2600inline
2601typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::const_iterator
2602unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::find(
2603 const key_type& key) const
2604{
2605 return const_iterator(d_impl.find(key));
2606}
2607
2608template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2609inline
2610bool unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::contains(
2611 const key_type& key) const
2612{
2613 return find(key) != end();
2614}
2615
2616
2617template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2618inline
2619bool
2620unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::empty() const
2621 BSLS_KEYWORD_NOEXCEPT
2622{
2623 return 0 == d_impl.size();
2624}
2625
2626template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2627inline
2628typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::size_type
2629unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::size() const
2630 BSLS_KEYWORD_NOEXCEPT
2631{
2632 return d_impl.size();
2633}
2634
2635template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2636inline
2637typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::size_type
2638unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::max_size() const
2639 BSLS_KEYWORD_NOEXCEPT
2640{
2641 return AllocatorTraits::max_size(get_allocator());
2642}
2643
2644template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2645inline
2646typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::hasher
2647unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::hash_function() const
2648{
2649 return d_impl.hasher();
2650}
2651
2652template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2653inline
2654typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::key_equal
2655unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::key_eq() const
2656{
2657 return d_impl.comparator();
2658}
2659
2660template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2661inline
2662bsl::pair<
2663 typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::const_iterator,
2664 typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::const_iterator>
2665unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::equal_range(
2666 const key_type& key) const
2667{
2668 HashTableLink *first;
2669 HashTableLink *last;
2670 d_impl.findRange(&first, &last, key);
2671 return bsl::pair<const_iterator, const_iterator>(const_iterator(first),
2672 const_iterator(last));
2673}
2674
2675template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2676inline
2677typename unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::size_type
2678unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::max_bucket_count() const
2679 BSLS_KEYWORD_NOEXCEPT
2680{
2681 return d_impl.maxNumBuckets();
2682}
2683
2684
2685template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2686inline
2687float unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::load_factor() const
2688 BSLS_KEYWORD_NOEXCEPT
2689{
2690 return d_impl.loadFactor();
2691}
2692
2693template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2694inline
2695float unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::max_load_factor() const
2696 BSLS_KEYWORD_NOEXCEPT
2697{
2698 return d_impl.maxLoadFactor();
2699}
2700
2701} // close namespace bsl
2702
2703// FREE OPERATORS
2704template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2705inline
2706bool bsl::operator==(
2707 const bsl::unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>& lhs,
2708 const bsl::unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>& rhs)
2709{
2710 return lhs.d_impl == rhs.d_impl;
2711}
2712
2713#ifndef BSLS_COMPILERFEATURES_SUPPORT_THREE_WAY_COMPARISON
2714template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2715inline
2716bool bsl::operator!=(
2717 const bsl::unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>& lhs,
2718 const bsl::unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>& rhs)
2719{
2720 return !(lhs == rhs);
2721}
2722#endif
2723
2724// FREE FUNCTIONS
2725template <class KEY, class HASH, class EQUAL, class ALLOCATOR, class PREDICATE>
2726inline
2727typename bsl::unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>::size_type
2728bsl::erase_if(unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>& ms,
2729 PREDICATE predicate)
2730{
2731 return BloombergLP::bslstl::AlgorithmUtil::containerEraseIf(ms, predicate);
2732}
2733
2734template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2735inline
2736void
2737bsl::swap(bsl::unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>& a,
2738 bsl::unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR>& b)
2739 BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(
2740 BSLS_KEYWORD_NOEXCEPT_OPERATOR(a.swap(b)))
2741{
2742 a.swap(b);
2743}
2744
2745// ============================================================================
2746// TYPE TRAITS
2747// ============================================================================
2748
2749// Type traits for STL *unordered* *associative* containers:
2750//: o An unordered associative container defines STL iterators.
2751//: o An unordered associative container is bitwise movable if both functors
2752//: and the allocator are bitwise movable.
2753//: o An unordered associative container uses 'bslma' allocators if the
2754//: (template parameter) type 'ALLOCATOR' is convertible from
2755//: 'bslma::Allocator *'.
2756
2757
2758
2759namespace bslalg {
2760
2761template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2762struct HasStlIterators<bsl::unordered_multiset<KEY, HASH, EQUAL, ALLOCATOR> >
2763 : bsl::true_type
2764{};
2765
2766} // close namespace bslalg
2767
2768namespace bslma {
2769
2770template <class KEY, class HASH, class EQUAL, class ALLOCATOR>
2771struct UsesBslmaAllocator<bsl::unordered_multiset<KEY,
2772 HASH,
2773 EQUAL,
2774 ALLOCATOR> >
2775 : bsl::is_convertible<Allocator*, ALLOCATOR>::type
2776{};
2777
2778} // close namespace bslma
2779
2780
2781
2782#endif // End C++11 code
2783
2784#endif
2785
2786// ----------------------------------------------------------------------------
2787// Copyright 2013 Bloomberg Finance L.P.
2788//
2789// Licensed under the Apache License, Version 2.0 (the "License");
2790// you may not use this file except in compliance with the License.
2791// You may obtain a copy of the License at
2792//
2793// http://www.apache.org/licenses/LICENSE-2.0
2794//
2795// Unless required by applicable law or agreed to in writing, software
2796// distributed under the License is distributed on an "AS IS" BASIS,
2797// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
2798// See the License for the specific language governing permissions and
2799// limitations under the License.
2800// ----------------------------- END-OF-FILE ----------------------------------
2801
2802/** @} */
2803/** @} */
2804/** @} */
bslalg_bidirectionallink.h
bslalg_bidirectionalnode.h
bslalg_typetraithasstliterators.h
bslma_allocatortraits.h
bslma_bslallocator.h
bslma_isstdallocator.h
bslma_usesbslmaallocator.h
bslmf_enableif.h
bslmf_isbitwisemoveable.h
bslmf_isnothrowswappable.h
bslmf_nestedtraitdeclaration.h
bslmf_typeidentity.h
bslmf_util.h
bsls_assert.h
bsls_compilerfeatures.h
bsls_ident.h
bsls_keyword.h
bsls_performancehint.h
bsls_util.h
bslstl_algorithm.h
bslstl_equalto.h
bslstl_hash.h
bslstl_hashtable.h
bslstl_hashtablebucketiterator.h
bslstl_hashtableiterator.h
bslstl_iteratorutil.h
bslstl_pair.h
bslstl_unorderedmultiset_cpp03.h
bslstl_unorderedsetkeyconfiguration.h
bsl::allocator
Definition bslma_bslallocator.h:580
bsl::pair
Definition bslstl_pair.h:1210
bsl::unordered_multiset
Definition bslstl_unorderedmultiset.h:770
bsl::unordered_multiset::clear
void clear() BSLS_KEYWORD_NOEXCEPT
Definition bslstl_unorderedmultiset.h:2272
bsl::unordered_multiset::reserve
void reserve(size_type numElements)
Definition bslstl_unorderedmultiset.h:2441
bsl::unordered_multiset::bucket_count
size_type bucket_count() const BSLS_KEYWORD_NOEXCEPT
Definition bslstl_unorderedmultiset.h:2560
bsl::unordered_multiset::const_reference
const value_type & const_reference
Definition bslstl_unorderedmultiset.h:823
bsl::unordered_multiset::operator==
friend bool operator==(const unordered_multiset< KEY2, HASH2, EQUAL2, ALLOCATOR2 > &, const unordered_multiset< KEY2, HASH2, EQUAL2, ALLOCATOR2 > &)
bsl::unordered_multiset::iterator
::BloombergLP::bslstl::HashTableIterator< const value_type, difference_type > iterator
Definition bslstl_unorderedmultiset.h:831
bsl::unordered_multiset::value_type
KEY value_type
Definition bslstl_unorderedmultiset.h:818
bsl::unordered_multiset::const_pointer
AllocatorTraits::const_pointer const_pointer
Definition bslstl_unorderedmultiset.h:828
bsl::unordered_multiset::bucket_size
size_type bucket_size(size_type index) const
Definition bslstl_unorderedmultiset.h:2569
bsl::unordered_multiset::bucket
size_type bucket(const key_type &key) const
Definition bslstl_unorderedmultiset.h:2551
bsl::unordered_multiset::difference_type
AllocatorTraits::difference_type difference_type
Definition bslstl_unorderedmultiset.h:826
bsl::unordered_multiset::max_bucket_count
size_type max_bucket_count() const BSLS_KEYWORD_NOEXCEPT
Definition bslstl_unorderedmultiset.h:2678
bsl::unordered_multiset::const_iterator
iterator const_iterator
Definition bslstl_unorderedmultiset.h:836
bsl::unordered_multiset::const_local_iterator
local_iterator const_local_iterator
Definition bslstl_unorderedmultiset.h:837
bsl::unordered_multiset::key_eq
EQUAL key_eq() const
Definition bslstl_unorderedmultiset.h:2655
bsl::unordered_multiset::hash_function
HASH hash_function() const
Definition bslstl_unorderedmultiset.h:2647
bsl::unordered_multiset::find
enable_if< BloombergLP::bslmf::IsTransparentPredicate< HASH, LOOKUP_KEY >::value &&BloombergLP::bslmf::IsTransparentPredicate< EQUAL, LOOKUP_KEY >::value, iterator >::type find(const LOOKUP_KEY &key)
Definition bslstl_unorderedmultiset.h:1203
bsl::unordered_multiset::end
iterator end() BSLS_KEYWORD_NOEXCEPT
Definition bslstl_unorderedmultiset.h:2244
bsl::unordered_multiset::max_size
size_type max_size() const BSLS_KEYWORD_NOEXCEPT
Definition bslstl_unorderedmultiset.h:2638
bsl::unordered_multiset::begin
unordered_multiset &operator=(BloombergLP::bslmf::MovableRef< unordered_multiset > rhs) BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(AllocatorTraits iterator begin() BSLS_KEYWORD_NOEXCEPT
Definition bslstl_unorderedmultiset.h:2236
bsl::unordered_multiset::empty
bool empty() const BSLS_KEYWORD_NOEXCEPT
Definition bslstl_unorderedmultiset.h:2620
bsl::unordered_multiset::equal_range
enable_if< BloombergLP::bslmf::IsTransparentPredicate< HASH, LOOKUP_KEY >::value &&BloombergLP::bslmf::IsTransparentPredicate< EQUAL, LOOKUP_KEY >::value, pair< iterator, iterator > >::type equal_range(const LOOKUP_KEY &key)
Definition bslstl_unorderedmultiset.h:1140
bsl::unordered_multiset::erase
size_type erase(const key_type &key)
Definition bslstl_unorderedmultiset.h:2309
bsl::unordered_multiset::insert
iterator insert(const value_type &value)
Definition bslstl_unorderedmultiset.h:2359
bsl::unordered_multiset::size_type
AllocatorTraits::size_type size_type
Definition bslstl_unorderedmultiset.h:825
bsl::unordered_multiset::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition bslstl_unorderedmultiset.h:2224
bsl::unordered_multiset::pointer
AllocatorTraits::pointer pointer
Definition bslstl_unorderedmultiset.h:827
bsl::unordered_multiset::rehash
void rehash(size_type numBuckets)
Definition bslstl_unorderedmultiset.h:2433
bsl::unordered_multiset::emplace
iterator emplace(Args &&... args)
Definition bslstl_unorderedmultiset.h:2213
bsl::unordered_multiset::operator=
unordered_multiset & operator=(const unordered_multiset &rhs)
Definition bslstl_unorderedmultiset.h:2162
bsl::unordered_multiset::contains
bool contains(const key_type &key) const
Definition bslstl_unorderedmultiset.h:2610
bsl::unordered_multiset::equal_range
enable_if< BloombergLP::bslmf::IsTransparentPredicate< HASH, LOOKUP_KEY >::value &&BloombergLP::bslmf::IsTransparentPredicate< EQUAL, LOOKUP_KEY >::value, pair< const_iterator, const_iterator > >::type equal_range(const LOOKUP_KEY &key) const
Definition bslstl_unorderedmultiset.h:1503
bsl::unordered_multiset::load_factor
float load_factor() const BSLS_KEYWORD_NOEXCEPT
Definition bslstl_unorderedmultiset.h:2687
bsl::unordered_multiset::reference
value_type & reference
Definition bslstl_unorderedmultiset.h:822
bsl::unordered_multiset::max_load_factor
float max_load_factor() const BSLS_KEYWORD_NOEXCEPT
Definition bslstl_unorderedmultiset.h:2695
bsl::unordered_multiset::hasher
HASH hasher
Definition bslstl_unorderedmultiset.h:819
bsl::unordered_multiset::cend
const_iterator cend() const BSLS_KEYWORD_NOEXCEPT
Definition bslstl_unorderedmultiset.h:2499
bsl::unordered_multiset::local_iterator
::BloombergLP::bslstl::HashTableBucketIterator< const value_type, difference_type > local_iterator
Definition bslstl_unorderedmultiset.h:834
bsl::unordered_multiset::size
size_type size() const BSLS_KEYWORD_NOEXCEPT
Return the number of elements in this unordered multiset.
Definition bslstl_unorderedmultiset.h:2629
bsl::unordered_multiset::key_equal
EQUAL key_equal
Definition bslstl_unorderedmultiset.h:820
bsl::unordered_multiset::~unordered_multiset
~unordered_multiset()
Destroy this object.
Definition bslstl_unorderedmultiset.h:2153
bsl::unordered_multiset::allocator_type
ALLOCATOR allocator_type
Definition bslstl_unorderedmultiset.h:821
bsl::unordered_multiset::BSLMF_NESTED_TRAIT_DECLARATION_IF
BSLMF_NESTED_TRAIT_DECLARATION_IF(unordered_multiset, ::BloombergLP::bslmf::IsBitwiseMoveable, ::BloombergLP::bslmf::IsBitwiseMoveable< HashTable >::value)
bsl::unordered_multiset::get_allocator
void swap(unordered_multiset &other) BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(AllocatorTraits ALLOCATOR get_allocator() const BSLS_KEYWORD_NOEXCEPT
Definition bslstl_unorderedmultiset.h:1374
bsl::unordered_multiset::count
enable_if< BloombergLP::bslmf::IsTransparentPredicate< HASH, LOOKUP_KEY >::value &&BloombergLP::bslmf::IsTransparentPredicate< EQUAL, LOOKUP_KEY >::value, size_type >::type count(const LOOKUP_KEY &key) const
Definition bslstl_unorderedmultiset.h:1465
bsl::unordered_multiset::key_type
KEY key_type
Definition bslstl_unorderedmultiset.h:817
bsl::unordered_multiset::unordered_multiset
unordered_multiset()
Definition bslstl_unorderedmultiset.h:1942
bsl::unordered_multiset::cbegin
const_iterator cbegin() const BSLS_KEYWORD_NOEXCEPT
Definition bslstl_unorderedmultiset.h:2490
BSLS_ASSERT
#define BSLS_ASSERT(X)
Definition bsls_assert.h:1804
BSLS_ASSERT_SAFE
#define BSLS_ASSERT_SAFE(X)
Definition bsls_assert.h:1762
BSLS_COMPILERFEATURES_FORWARD
#define BSLS_COMPILERFEATURES_FORWARD(T, V)
Definition bsls_compilerfeatures.h:2018
BSLS_IDENT
#define BSLS_IDENT(str)
Definition bsls_ident.h:195
BSLS_KEYWORD_NOEXCEPT_OPERATOR
#define BSLS_KEYWORD_NOEXCEPT_OPERATOR(...)
Definition bsls_keyword.h:635
BSLS_KEYWORD_NOEXCEPT
#define BSLS_KEYWORD_NOEXCEPT
Definition bsls_keyword.h:632
BSLS_KEYWORD_NOEXCEPT_SPECIFICATION
#define BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(...)
Definition bsls_keyword.h:634
bsl
Definition bdlb_printmethods.h:283
bsl::swap
void swap(array< VALUE_TYPE, SIZE > &lhs, array< VALUE_TYPE, SIZE > &rhs)
bsl::erase
deque< VALUE_TYPE, ALLOCATOR >::size_type erase(deque< VALUE_TYPE, ALLOCATOR > &deq, const BDE_OTHER_TYPE &value)
Definition bslstl_deque.h:4126
bsl::begin
T::iterator begin(T &container)
Definition bslstl_iterator.h:1495
bsl::size
BSLS_KEYWORD_CONSTEXPR size_t size(const TYPE(&)[DIMENSION]) BSLS_KEYWORD_NOEXCEPT
Return the dimension of the specified array argument.
Definition bslstl_iterator.h:1331
bsl::end
T::iterator end(T &container)
Definition bslstl_iterator.h:1523
bsl::erase_if
deque< VALUE_TYPE, ALLOCATOR >::size_type erase_if(deque< VALUE_TYPE, ALLOCATOR > &deq, PREDICATE predicate)
Definition bslstl_deque.h:4135
bsl::operator!=
bool operator!=(const memory_resource &a, const memory_resource &b)
bslalg
Definition bdlc_flathashmap.h:1805
bslma
Definition balxml_encoderoptions.h:68
bslmf
Definition bdlbb_blob.h:576
std
Definition bdldfp_decimal.h:5188
bsl::allocator_traits
Definition bslma_allocatortraits.h:1061
bsl::allocator_traits< ALLOCATOR >::const_pointer
BloombergLP::bslma::AllocatorTraits_ConstPointerType< ALLOCATOR >::type const_pointer
Definition bslma_allocatortraits.h:1152
bsl::allocator_traits< ALLOCATOR >::size_type
BloombergLP::bslma::AllocatorTraits_SizeType< ALLOCATOR >::type size_type
Definition bslma_allocatortraits.h:1165
bsl::allocator_traits< ALLOCATOR >::pointer
BloombergLP::bslma::AllocatorTraits_PointerType< ALLOCATOR >::type pointer
Definition bslma_allocatortraits.h:1149
bsl::allocator_traits< ALLOCATOR >::difference_type
BloombergLP::bslma::AllocatorTraits_DifferenceType< ALLOCATOR >::type difference_type
Definition bslma_allocatortraits.h:1162
bsl::enable_if
Definition bslmf_enableif.h:525
bsl::equal_to
Definition bslstl_equalto.h:311
bsl::hash
Definition bslstl_hash.h:498
bsl::integral_constant< bool, true >
bsl::is_convertible
Definition bslmf_isconvertible.h:867
bsl::type_identity::type
t_TYPE type
Definition bslmf_typeidentity.h:216
bslalg::HasStlIterators
Definition bslalg_hasstliterators.h:99
bslma::UsesBslmaAllocator
Definition bslma_usesbslmaallocator.h:343