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