BDE 4.39.x Production Release
Loading...
Searching...
No Matches
bslstl_map.h
Go to the documentation of this file.
1/// @file bslstl_map.h
2///
3/// The content of this file has been pre-processed for Doxygen.
4///
5
6
7// bslstl_map.h -*-C++-*-
8#ifndef INCLUDED_BSLSTL_MAP
9#define INCLUDED_BSLSTL_MAP
10
11#include <bsls_ident.h>
12BSLS_IDENT("$Id: $")
13
14/// @defgroup bslstl_map bslstl_map
15/// @brief Provide an STL-compliant map class.
16/// @addtogroup bsl
17/// @{
18/// @addtogroup bslstl
19/// @{
20/// @addtogroup bslstl_map
21/// @{
22///
23/// <h1> Outline </h1>
24/// * <a href="#bslstl_map-purpose"> Purpose</a>
25/// * <a href="#bslstl_map-classes"> Classes </a>
26/// * <a href="#bslstl_map-canonical-header"> Canonical Header </a>
27/// * <a href="#bslstl_map-description"> Description </a>
28/// * <a href="#bslstl_map-requirements-on-key-and-value"> Requirements on KEY and VALUE </a>
29/// * <a href="#bslstl_map-glossary"> Glossary </a>
30/// * <a href="#bslstl_map-key-comparison"> Key Comparison </a>
31/// * <a href="#bslstl_map-memory-allocation"> Memory Allocation </a>
32/// * <a href="#bslstl_map-bslma-style-allocators"> bslma-Style Allocators </a>
33/// * <a href="#bslstl_map-operations"> Operations </a>
34/// * <a href="#bslstl_map-usage"> Usage </a>
35/// * <a href="#bslstl_map-example-1-creating-a-trade-matching-system"> Example 1: Creating a Trade Matching System </a>
36///
37/// # Purpose {#bslstl_map-purpose}
38/// Provide an STL-compliant map class.
39///
40/// # Classes {#bslstl_map-classes}
41///
42/// - bsl::map: STL-compliant map template
43///
44/// # Canonical Header {#bslstl_map-canonical-header}
45/// bsl_map.h
46///
47/// @see bslstl_multimap, bslstl_set
48///
49/// # Description {#bslstl_map-description}
50/// This component defines a single class template `bsl::map`,
51/// implementing the standard container holding an ordered sequence of key-value
52/// pairs (having unique keys), and presenting a mapping from the keys (of a
53/// template parameter type, `KEY`) to their associated values (of another
54/// template parameter type, `VALUE`).
55///
56/// An instantiation of `map` is an allocator-aware, value-semantic type whose
57/// salient attributes are its size (number of key-value pairs) and the ordered
58/// sequence of key-value pairs the map contains. If `map` is instantiated with
59/// either a key type or mapped-value type that is not itself value-semantic,
60/// then it will not retain all of its value-semantic qualities. In particular,
61/// if either the key or value type cannot be tested for equality, then a `map`
62/// containing that type cannot be tested for equality. It is even possible to
63/// instantiate `map` with a key or mapped-value type that does not have a copy
64/// constructor, in which case the `map` will not be copyable.
65///
66/// A map meets the requirements of an associative container with bidirectional
67/// iterators in the C++ standard [associative.reqmts]. The `map` implemented
68/// here adheres to the C++11 standard when compiled with a C++11 compiler, and
69/// makes the best approximation when compiled with a C++03 compiler. In
70/// particular, for C++03 we emulate move semantics, but limit forwarding (in
71/// `emplace`) to `const` lvalues, and make no effort to emulate `noexcept` or
72/// initializer-lists.
73///
74/// ## Requirements on KEY and VALUE {#bslstl_map-requirements-on-key-and-value}
75///
76///
77/// A `map` is a fully Value-Semantic Type (see @ref bsldoc_glossary ) only if the
78/// supplied `KEY` and `VALUE` template parameters are themselves fully
79/// value-semantic. It is possible to instantiate a `map` with `KEY` and
80/// `VALUE` parameter arguments that do not provide a full set of value-semantic
81/// operations, but then some methods of the container may not be instantiable.
82/// The following terminology, adopted from the C++11 standard, is used in the
83/// function documentation of `map` to describe a function's requirements for
84/// the `KEY` and `VALUE` template parameters. These terms are also defined in
85/// sections [utility.arg.requirements] and [container.requirements.general] of
86/// the C++11 standard. Note that, in the context of a `map` instantiation, the
87/// requirements apply specifically to the map's entry type, `value_type`, which
88/// is an alias for `bsl::pair<const KEY, VALUE>`.
89///
90/// ## Glossary {#bslstl_map-glossary}
91///
92///
93/// @code
94/// Legend
95/// ------
96/// 'X' - denotes an allocator-aware container type (e.g., 'map')
97/// 'T' - 'value_type' associated with 'X'
98/// 'A' - type of the allocator used by 'X'
99/// 'm' - lvalue of type 'A' (allocator)
100/// 'p', - address ('T *') of uninitialized storage for a 'T' within an 'X'
101/// 'rv' - rvalue of type (non-'const') 'T'
102/// 'v' - rvalue or lvalue of type (possibly 'const') 'T'
103/// 'args' - 0 or more arguments
104/// @endcode
105/// The following terms are used to more precisely specify the requirements on
106/// template parameter types in function-level documentation.
107///
108/// *default-insertable*: `T` has a default constructor. More precisely, `T`
109/// is `default-insertable` into `X` means that the following expression is
110/// well-formed:
111/// `allocator_traits<A>::construct(m, p)`
112///
113/// *move-insertable*: `T` provides a constructor that takes an rvalue of type
114/// (non-`const`) `T`. More precisely, `T` is `move-insertable` into `X`
115/// means that the following expression is well-formed:
116/// `allocator_traits<A>::construct(m, p, rv)`
117///
118/// *copy-insertable*: `T` provides a constructor that takes an lvalue or
119/// rvalue of type (possibly `const`) `T`. More precisely, `T` is
120/// `copy-insertable` into `X` means that the following expression is
121/// well-formed:
122/// `allocator_traits<A>::construct(m, p, v)`
123///
124/// *move-assignable*: `T` provides an assignment operator that takes an rvalue
125/// of type (non-`const`) `T`.
126///
127/// *copy-assignable*: `T` provides an assignment operator that takes an lvalue
128/// or rvalue of type (possibly `const`) `T`.
129///
130/// *emplace-constructible*: `T` is `emplace-constructible` into `X` from
131/// `args` means that the following expression is well-formed:
132/// `allocator_traits<A>::construct(m, p, args)`
133///
134/// *erasable*: `T` provides a destructor. More precisely, `T` is `erasable`
135/// from `X` means that the following expression is well-formed:
136/// `allocator_traits<A>::destroy(m, p)`
137///
138/// *equality-comparable*: The type provides an equality-comparison operator
139/// that defines an equivalence relationship and is both reflexive and
140/// transitive.
141///
142/// ## Key Comparison {#bslstl_map-key-comparison}
143///
144///
145/// The type supplied as a map's `COMPARATOR` template parameter determines how
146/// that map will order elements. In particular, the `COMPARATOR` type must
147/// induce a strict weak ordering on objects of type `KEY`. The `COMPARATOR`
148/// parameter defaults to `std::less<KEY>` when not supplied in an instantiation
149/// of `map`. Note that the `COMPARATOR` type must be copy-constructible.
150///
151/// The C++11 standard does not require that the function-call operator provided
152/// by `COMPARATOR` functors be `const`-qualified. However, there is a
153/// suggestion for C++17 that this is an oversight in the standard, and that
154/// `const`-qualification will be required in the future. Keep this in mind
155/// when opting to use an alternative to the default `COMPARATOR`.
156///
157/// ## Memory Allocation {#bslstl_map-memory-allocation}
158///
159///
160/// The type supplied as a map's `ALLOCATOR` template parameter determines how
161/// that map will allocate memory. The `map` template supports allocators
162/// meeting the requirements of the C++11 standard [allocator.requirements].
163/// In addition, `map` supports scoped-allocators derived from the
164/// `bslma::Allocator` memory allocation protocol. Clients intending to use
165/// `bslma`-style allocators should use the template's default `ALLOCATOR`
166/// type: The default type for the `ALLOCATOR` template parameter,
167/// `bsl::allocator`, provides a C++11 standard-compatible adapter for a
168/// `bslma::Allocator` object.
169///
170/// ### bslma-Style Allocators {#bslstl_map-bslma-style-allocators}
171///
172///
173/// If the (template parameter) type `ALLOCATOR` of a `map` instantiation' is
174/// `bsl::allocator`, then objects of that map type will conform to the standard
175/// behavior of a `bslma`-allocator-enabled type. Such a map accepts an
176/// optional `bslma::Allocator` argument at construction. If the address of a
177/// `bslma::Allocator` object is explicitly supplied at construction, it is used
178/// to supply memory for the map throughout its lifetime; otherwise, the map
179/// will use the default allocator installed at the time of the map's
180/// construction (see @ref bslma_default ). In addition to directly allocating
181/// memory from the indicated `bslma::Allocator`, a map supplies that
182/// allocator's address to the constructors of contained objects of the
183/// (template parameter) type `KEY` and `VALUE`, if respectively, the types
184/// define the `bslma::UsesBslmaAllocator` trait.
185///
186/// ## Operations {#bslstl_map-operations}
187///
188///
189/// This section describes the run-time complexity of operations on instances
190/// of `map`:
191/// @code
192/// Legend
193/// ------
194/// 'K' - (template parameter) type 'KEY' of the map
195/// 'V' - (template parameter) type 'VALUE' of the map
196/// 'a', 'b' - two distinct objects of type 'map<K, V>'
197/// 'rv' - modifiable rvalue of type 'map<K, V>'
198/// 'n', 'm' - number of elements in 'a' and 'b', respectively
199/// 'value_type' - 'pair<const K, V>'
200/// 'c' - comparator providing an ordering for objects of type 'K'
201/// 'al - STL-style memory allocator
202/// 'rg' - range of objects convertible to 'V'
203/// 'i1', 'i2' - two iterators defining a sequence of 'value_type' objects
204/// 'k' - object of type 'K'
205/// 'v' - object of type 'V'
206/// 'vt' - object of type 'value_type'
207/// 'rvt' - modifiable rvalue of type 'value_type'
208/// 'p1', 'p2' - two 'const_iterator's belonging to 'a'
209/// distance(i1,i2) - number of elements in the range '[i1 .. i2)'
210///
211/// +----------------------------------------------------+--------------------+
212/// | Operation | Complexity |
213/// +====================================================+====================+
214/// | map<K, V> a; (default construction) | O[1] |
215/// | map<K, V> a(al); | |
216/// | map<K, V> a(c, al); | |
217/// +----------------------------------------------------+--------------------+
218/// | map<K, V> a(rv); (move construction) | O[1] if 'a' and |
219/// | map<K, V> a(rv, al); | 'rv' use the same |
220/// | | allocator, |
221/// | | O[n] otherwise |
222/// +----------------------------------------------------+--------------------+
223/// | map<K, V> a(b); (copy construction) | O[n] |
224/// | map<K, V> a(b, al); | |
225/// +----------------------------------------------------+--------------------+
226/// | map<K, V> a(i1, i2); | O[N] if [i1 .. i2) |
227/// | map<K, V> a(i1, i2, al); | is sorted with |
228/// | map<K, V> a(i1, i2, c, al); | 'a.value_comp()', |
229/// | | O[N * log(N)] |
230/// | | otherwise, where N |
231/// | | is distance(i1,i2) |
232/// +----------------------------------------------------+--------------------+
233/// | map<K, V> a(from_range, rg); | O[N] if 'rg' is |
234/// | map<K, V> a(from_range, rg, al); | sorted with |
235/// | map<K, V> a(from_range, rg, c, al); | 'a.value_comp()', |
236/// | | O[N * log(N)] |
237/// | | otherwise, where N |
238/// | | is ranges:: |
239/// | | distance(rg) |
240/// +----------------------------------------------------+--------------------+
241/// | a.~map<K, V>(); (destruction) | O[n] |
242/// +----------------------------------------------------+--------------------+
243/// | a = rv; (move assignment) | O[1] if 'a' and |
244/// | | 'rv' use the same |
245/// | | allocator, |
246/// | | O[n] otherwise |
247/// +----------------------------------------------------+--------------------+
248/// | a = b; (copy assignment) | O[n] |
249/// +----------------------------------------------------+--------------------+
250/// | a.begin(), a.end(), a.cbegin(), a.cend(), | O[1] |
251/// | a.rbegin(), a.rend(), a.crbegin(), a.crend() | |
252/// +----------------------------------------------------+--------------------+
253/// | a == b, a != b | O[n] |
254/// +----------------------------------------------------+--------------------+
255/// | a < b, a <= b, a > b, a >= b | O[n] |
256/// +----------------------------------------------------+--------------------+
257/// | a.swap(b), swap(a, b) | O[1] if 'a' and |
258/// | | 'b' use the same |
259/// | | allocator, |
260/// | | O[n + m] otherwise |
261/// +----------------------------------------------------+--------------------+
262/// | a.size() | O[1] |
263/// +----------------------------------------------------+--------------------+
264/// | a.max_size() | O[1] |
265/// +----------------------------------------------------+--------------------+
266/// | a.empty() | O[1] |
267/// +----------------------------------------------------+--------------------+
268/// | get_allocator() | O[1] |
269/// +----------------------------------------------------+--------------------+
270/// | a[k] | O[log(n)] |
271/// +----------------------------------------------------+--------------------+
272/// | a.at(k) | O[log(n)] |
273/// +----------------------------------------------------+--------------------+
274/// | a.insert(vt) | O[log(n)] |
275/// | a.insert(rvt) | |
276/// | a.emplace(Args&&...) | |
277/// +----------------------------------------------------+--------------------+
278/// | a.insert(p1, vt) | amortized constant |
279/// | a.insert(p1, rvt) | if the value is |
280/// | a.emplace(p1, Args&&...) | inserted right |
281/// | | before p1, |
282/// | | O[log(n)] |
283/// | | otherwise |
284/// +----------------------------------------------------+--------------------+
285/// | a.insert(i1, i2) | O[log(N) * |
286/// | | distance(i1,i2)] |
287/// | | |
288/// | | where N is |
289/// | | n + distance(i1,i2)|
290/// +----------------------------------------------------+--------------------+
291/// | a.insert_range(rg) | O[log(N) * |
292/// | | ranges:: |
293/// | | distance(rg)] |
294/// | | |
295/// | | where N is n + |
296/// | | ranges:: |
297/// | | distance(rg)] |
298/// +----------------------------------------------------+--------------------+
299/// | a.erase(p1) | amortized constant |
300/// +----------------------------------------------------+--------------------+
301/// | a.erase(k) | O[log(n) + |
302/// | | a.count(k)] |
303/// +----------------------------------------------------+--------------------+
304/// | a.erase(p1, p2) | O[log(n) + |
305/// | | distance(p1, p2)] |
306/// +----------------------------------------------------+--------------------+
307/// | a.erase(p1, p2) | O[log(n) + |
308/// | | distance(p1, p2)] |
309/// +----------------------------------------------------+--------------------+
310/// | a.clear() | O[n] |
311/// +----------------------------------------------------+--------------------+
312/// | a.contains(k) | O[log(n)] |
313/// +----------------------------------------------------+--------------------+
314/// | a.key_comp() | O[1] |
315/// +----------------------------------------------------+--------------------+
316/// | a.value_comp() | O[1] |
317/// +----------------------------------------------------+--------------------+
318/// | a.find(k) | O[log(n)] |
319/// +----------------------------------------------------+--------------------+
320/// | a.count(k) | O[log(n) + |
321/// | | a.count(k)] |
322/// +----------------------------------------------------+--------------------+
323/// | a.lower_bound(k) | O[log(n)] |
324/// +----------------------------------------------------+--------------------+
325/// | a.upper_bound(k) | O[log(n)] |
326/// +----------------------------------------------------+--------------------+
327/// | a.equal_range(k) | O[log(n)] |
328/// +----------------------------------------------------+--------------------+
329/// @endcode
330///
331/// ## Usage {#bslstl_map-usage}
332///
333///
334/// In this section we show intended use of this component.
335///
336/// ### Example 1: Creating a Trade Matching System {#bslstl_map-example-1-creating-a-trade-matching-system}
337///
338///
339/// In this example, we will utilize `bsl::map` to define and implement a class,
340/// `TradeMatcher`, that provides a simple trade matching system for a single
341/// stock. The manipulators of `TradeMatcher` will allow clients to place buy
342/// orders and sell orders, and the accessors of `TradeMatcher` will allow
343/// clients to retrieve active orders and past executions.
344///
345/// First, we define the public interface for `TradeMatcher`:
346/// @code
347/// /// This class provides a mechanism that characterizes a simple trade
348/// /// matching system for one stock. An object of this class allows
349/// /// clients to place orders and view the active orders.
350/// class TradeMatcher {
351/// @endcode
352/// Here, we create two type aliases, `SellOrdersMap` and `BuyOrdersMap`, for
353/// two `bsl::map` instantiations that maps the price of an order (type
354/// `double`) to the quantity of the order (type `int`). `SellOrdersMap` uses
355/// the default `bsl::less` comparator to store the sequence of sell orders in
356/// ascending price order. `BuyOrdersMap` uses the `bsl::greater` comparator to
357/// store the sequence of buy orders in descending price order. Also note that
358/// we use the default `ALLOCATOR` template parameter for both aliases as we
359/// intend to provide memory with `bslma`-style allocators:
360/// @code
361/// // PRIVATE TYPES
362/// typedef bsl::map<double, int> SellOrdersMap;
363/// // This `typedef` is an alias for a mapping between the price and
364/// // quantity of an order in ascending price order.
365///
366/// typedef bsl::map<double, int, std::greater<double> > BuyOrdersMap;
367/// // This `typedef` is an alias for a mapping between the price and
368/// // quantity of an order in descending price order.
369///
370///
371/// // DATA
372/// SellOrdersMap d_sellOrders; // current sell orders
373/// BuyOrdersMap d_buyOrders; // current buy orders
374///
375/// private:
376/// // NOT IMPLEMENTED
377/// TradeMatcher& operator=(const TradeMatcher&);
378/// TradeMatcher(const TradeMatcher&);
379///
380/// public:
381/// // PUBLIC TYPES
382/// typedef SellOrdersMap::const_iterator SellOrdersConstIterator;
383/// // This `typedef` provides an alias for the type of an iterator
384/// // providing non-modifiable access to sell orders in a
385/// // `TradeMatcher`.
386///
387/// typedef BuyOrdersMap::const_iterator BuyOrdersConstIterator;
388/// // This `typedef` provides an alias for the type of an iterator
389/// // providing non-modifiable access to buy orders in a
390/// // `TradeMatcher`.
391///
392/// // CREATORS
393/// TradeMatcher(bslma::Allocator *basicAllocator = 0);
394/// // Create an empty `TradeMatcher` object. Optionally specify a
395/// // `basicAllocator` used to supply memory. If `basicAllocator` is
396/// // 0, the currently installed default allocator is used.
397///
398/// //! ~TradeMatcher() = default;
399/// // Destroy this object.
400///
401/// // MANIPULATORS
402/// void placeBuyOrder(double price, int numShares);
403/// // Place an order to buy the specified `numShares` at the specified
404/// // `price`. The placed buy order will (possibly partially) execute
405/// // when active sale orders exist in the system at or below `price`.
406/// // The behavior is undefined unless `0 < price` and `0 <
407/// // numShares`.
408///
409/// void placeSellOrder(double price, int numShares);
410/// // Place an order to sell the specified `numShares` at the
411/// // specified `price`. The placed sell order will (possibly
412/// // partially) execute when active buy orders exist in the system at
413/// // or above `price`. The behavior is undefined unless `0 < price`
414/// // and `0 < numShares`.
415///
416/// // ACCESSORS
417/// SellOrdersConstIterator beginSellOrders() const;
418/// // Return an iterator providing non-modifiable access to the active
419/// // sell order at the lowest price in the ordered sequence (from low
420/// // price to high price) of sell orders maintained by this object.
421///
422/// SellOrdersConstIterator endSellOrders() const;
423/// // Return an iterator providing non-modifiable access to the
424/// // past-the-end sell order in the ordered sequence (from low price
425/// // to high price) of sell orders maintained by this object.
426///
427/// BuyOrdersConstIterator beginBuyOrders() const;
428/// // Return an iterator providing non-modifiable access to the active
429/// // buy order at the highest price in the ordered sequence (from
430/// // high price to low price) of buy orders maintained by this
431/// // object.
432///
433/// BuyOrdersConstIterator endBuyOrders() const;
434/// // Return an iterator providing non-modifiable access to the
435/// // past-the-end buy order in the ordered sequence (from high price
436/// // to low price) of buy orders maintained by this object.
437/// };
438/// @endcode
439/// Now, we define the implementations methods of the `TradeMatcher` class:
440/// @code
441/// // CREATORS
442/// TradeMatcher::TradeMatcher(bslma::Allocator *basicAllocator)
443/// : d_sellOrders(basicAllocator)
444/// , d_buyOrders(basicAllocator)
445/// {
446/// }
447/// @endcode
448/// Notice that, on construction, we pass the contained `bsl::map` objects the
449/// `bsl::Allocator` supplied at construction'.
450/// @code
451/// // MANIPULATORS
452/// void TradeMatcher::placeBuyOrder(double price, int numShares)
453/// {
454/// BSLS_ASSERT(0 < price);
455/// BSLS_ASSERT(0 < numShares);
456///
457/// // Buy shares from sellers from the one with the lowest price up to but
458/// // not including the first seller with a price greater than the
459/// // specified `price`.
460///
461/// SellOrdersMap::iterator itr = d_sellOrders.begin();
462///
463/// while (numShares && itr != d_sellOrders.upper_bound(price)) {
464/// if (itr->second > numShares) {
465/// itr->second -= numShares;
466/// numShares = 0;
467/// break;
468/// }
469///
470/// itr = d_sellOrders.erase(itr);
471/// numShares -= itr->second;
472/// }
473///
474/// if (numShares > 0) {
475/// d_buyOrders[price] += numShares;
476/// }
477/// }
478///
479/// void TradeMatcher::placeSellOrder(double price, int numShares)
480/// {
481/// BSLS_ASSERT(0 < price);
482/// BSLS_ASSERT(0 < numShares);
483///
484/// // Sell shares to buyers from the one with the highest price up to but
485/// // not including the first buyer with a price smaller than the
486/// // specified `price`.
487///
488/// BuyOrdersMap::iterator itr = d_buyOrders.begin();
489///
490/// while (numShares && itr != d_buyOrders.upper_bound(price)) {
491/// if (itr->second > numShares) {
492/// itr->second -= numShares;
493/// numShares = 0;
494/// break;
495/// }
496///
497/// itr = d_buyOrders.erase(itr);
498/// numShares -= itr->second;
499/// }
500///
501/// if (numShares > 0) {
502/// d_sellOrders[price] += numShares;
503/// }
504/// }
505///
506/// // ACCESSORS
507/// TradeMatcher::SellOrdersConstIterator TradeMatcher::beginSellOrders() const
508/// {
509/// return d_sellOrders.begin();
510/// }
511///
512/// TradeMatcher::SellOrdersConstIterator TradeMatcher::endSellOrders() const
513/// {
514/// return d_sellOrders.end();
515/// }
516///
517/// TradeMatcher::BuyOrdersConstIterator TradeMatcher::beginBuyOrders() const
518/// {
519/// return d_buyOrders.begin();
520/// }
521///
522/// TradeMatcher::BuyOrdersConstIterator TradeMatcher::endBuyOrders() const
523/// {
524/// return d_buyOrders.end();
525/// }
526/// @endcode
527/// @}
528/** @} */
529/** @} */
530
531/** @addtogroup bsl
532 * @{
533 */
534/** @addtogroup bslstl
535 * @{
536 */
537/** @addtogroup bslstl_map
538 * @{
539 */
540
541#include <bslscm_version.h>
542
543#include <bslstl_algorithm.h>
544#include <bslstl_iterator.h>
545#include <bslstl_iteratorutil.h>
546#include <bslstl_mapcomparator.h>
547#include <bslstl_pair.h>
548#include <bslstl_ranges.h>
549#include <bslstl_stdexceptutil.h>
550#include <bslstl_treeiterator.h>
551#include <bslstl_treenode.h>
552#include <bslstl_treenodepool.h>
553
554#include <bslalg_rangecompare.h>
555#include <bslalg_rbtreeanchor.h>
556#include <bslalg_rbtreenode.h>
557#include <bslalg_rbtreeutil.h>
558#include <bslalg_synththreewayutil.h>
559#include <bslalg_typetraithasstliterators.h>
560
561#include <bslma_constructionutil.h>
562#include <bslma_isstdallocator.h>
563#include <bslma_default.h>
564#include <bslma_destructorguard.h>
565#include <bslma_bslallocator.h>
566#include <bslma_usesbslmaallocator.h>
567
568#include <bslmf_addlvaluereference.h>
569#include <bslmf_containercompatiblerange.h>
570#include <bslmf_enableif.h>
571#include <bslmf_isconvertible.h>
572#include <bslmf_istransparentpredicate.h>
573#include <bslmf_movableref.h>
574#include <bslmf_typeidentity.h>
575#include <bslmf_util.h> // 'forward(V)'
576
577#include <bsls_assert.h>
578#include <bsls_compilerfeatures.h>
579#include <bsls_keyword.h>
580#include <bsls_libraryfeatures.h>
581#include <bsls_objectbuffer.h>
582#include <bsls_performancehint.h>
583#include <bsls_platform.h>
584#include <bsls_util.h> // 'forward<T>(V)'
585
586#include <functional>
587
588#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
589# include <initializer_list>
590#endif
591
592#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
593#include <tuple> // for forward_as_tuple (C++11)
594#include <utility> // for piecewise_construct (C++11)
595#endif
596
597#ifndef BDE_DONT_ALLOW_TRANSITIVE_INCLUDES
598#include <bsls_nativestd.h>
599#endif // BDE_DONT_ALLOW_TRANSITIVE_INCLUDES
600
601#ifdef BSLS_COMPILERFEATURES_SUPPORT_TRAITS_HEADER
602#include <type_traits>
603 #ifndef BSLS_COMPILERFEATURES_SUPPORT_RVALUE_REFERENCES
604 #error Rvalue references curiously absent despite native 'type_traits'.
605 #endif
606#endif
607
608#if defined(BSLS_LIBRARYFEATURES_HAS_CPP20_CONCEPTS) \
609 && defined(BSLS_LIBRARYFEATURES_HAS_CPP20_RANGES)
610# define BSLSTL_MAP_REQUIRES_CONTAINER_COMPATIBLE_RANGE(R, T) \
611 requires ::BloombergLP::bslmf::ContainerCompatibleRange<R, T>
612#else
613# define BSLSTL_MAP_REQUIRES_CONTAINER_COMPATIBLE_RANGE(R, T)
614#endif
615
616#if BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
617// clang-format off
618// Include version that can be compiled with C++03
619// Generated on Mon Nov 3 18:52:43 2025
620// Command line: sim_cpp11_features.pl bslstl_map.h
621
622# define COMPILING_BSLSTL_MAP_H
623# include <bslstl_map_cpp03.h>
624# undef COMPILING_BSLSTL_MAP_H
625
626// clang-format on
627#else
628
629namespace bsl {
630
631 // =========
632 // class map
633 // =========
634
635/// This class template implements a value-semantic container type holding
636/// an ordered sequence of key-value pairs having unique keys that provide a
637/// mapping from keys (of the template parameter type, `KEY`) to their
638/// associated values (of another template parameter type, `VALUE`).
639///
640/// This class:
641/// * supports a complete set of *value-semantic* operations
642/// - except for BDEX serialization
643/// * is *exception-neutral*
644/// * is *alias-safe*
645/// * is `const` *thread-safe*
646/// For terminology see @ref bsldoc_glossary .
647///
648/// See @ref bslstl_map
649template <class KEY,
650 class VALUE,
651 class COMPARATOR = std::less<KEY>,
652 class ALLOCATOR = allocator<pair<const KEY, VALUE> > >
653class map {
654
655 // PRIVATE TYPES
656
657 /// This typedef is an alias for the type of key-value pair objects
658 /// maintained by this map.
659 typedef pair<const KEY, VALUE> ValueType;
660
661 /// This typedef is an alias for the comparator used internally by this
662 /// map.
663 typedef BloombergLP::bslstl::MapComparator<KEY, VALUE, COMPARATOR>
664 Comparator;
665
666 /// This typedef is an alias for the type of nodes held by the tree (of
667 /// nodes) used to implement this map.
668 typedef BloombergLP::bslstl::TreeNode<ValueType> Node;
669
670 /// This typedef is an alias for the factory type used to create and
671 /// destroy `Node` objects.
672 typedef BloombergLP::bslstl::TreeNodePool<ValueType, ALLOCATOR>
673 NodeFactory;
674
675 /// This typedef is an alias for the allocator traits type associated
676 /// with this container.
677 typedef typename bsl::allocator_traits<ALLOCATOR> AllocatorTraits;
678
679 /// This typedef is a convenient alias for the utility associated with
680 /// movable references.
681 typedef BloombergLP::bslmf::MovableRefUtil MoveUtil;
682
683 /// This struct is wrapper around the comparator and allocator data
684 /// members. It takes advantage of the empty-base optimization (EBO) so
685 /// that if the comparator is stateless, it takes up no space.
686 ///
687 /// TBD: This class should eventually be replaced by the use of a
688 /// general EBO-enabled component that provides a `pair`-like interface
689 /// or a `tuple`.
690 ///
691 /// See @ref bslstl_map
692 class DataWrapper : public Comparator {
693
694 // DATA
695 NodeFactory d_pool; // pool of 'Node' objects
696
697 private:
698 // NOT IMPLEMENTED
699 DataWrapper(const DataWrapper&);
700 DataWrapper& operator=(const DataWrapper&);
701
702 public:
703 // CREATORS
704
705 /// Create a data wrapper using a copy of the specified `comparator`
706 /// to order key-value pairs and a copy of the specified
707 /// `basicAllocator` to supply memory.
708 DataWrapper(const COMPARATOR& comparator,
709 const ALLOCATOR& basicAllocator);
710
711 /// Create a data wrapper initialized to the contents of the `pool`
712 /// associated with the specified `original` data wrapper. The
713 /// comparator and allocator associated with `original` are
714 /// propagated to the new data wrapper. `original` is left in a
715 /// valid but unspecified state.
716 DataWrapper(
717 BloombergLP::bslmf::MovableRef<DataWrapper> original);// IMPLICIT
718
719 // MANIPULATORS
720
721 /// Return a reference providing modifiable access to the node
722 /// factory associated with this data wrapper.
723 NodeFactory& nodeFactory();
724
725 // ACCESSORS
726
727 /// Return a reference providing non-modifiable access to the node
728 /// factory associated with this data wrapper.
729 const NodeFactory& nodeFactory() const;
730 };
731
732 // DATA
733 DataWrapper d_compAndAlloc;
734 // comparator and pool of 'Node'
735 // objects
736
737 BloombergLP::bslalg::RbTreeAnchor d_tree; // balanced tree of 'Node'
738 // objects
739
740 public:
741 // PUBLIC TYPES
742 typedef KEY key_type;
743 typedef VALUE mapped_type;
744 typedef pair<const KEY, VALUE> value_type;
745 typedef COMPARATOR key_compare;
746 typedef ALLOCATOR allocator_type;
747 typedef value_type& reference;
748 typedef const value_type& const_reference;
749
750 typedef typename AllocatorTraits::size_type size_type;
751 typedef typename AllocatorTraits::difference_type difference_type;
752 typedef typename AllocatorTraits::pointer pointer;
753 typedef typename AllocatorTraits::const_pointer const_pointer;
754
755 typedef BloombergLP::bslstl::TreeIterator<
756 value_type, Node, difference_type> iterator;
757 typedef BloombergLP::bslstl::TreeIterator<
758 const value_type, Node, difference_type> const_iterator;
759 typedef bsl::reverse_iterator<iterator> reverse_iterator;
760 typedef bsl::reverse_iterator<const_iterator> const_reverse_iterator;
761
762 /// This nested class defines a mechanism for comparing two objects of
763 /// `value_type` by adapting an object of (template parameter) type
764 /// `COMPARATOR`, which compares two objects of (template parameter) type `KEY` .
765 ///
766 /// \note Note that this class exactly matches its definition in
767 /// the C++11 standard [map.overview]; otherwise, we would have
768 /// implemented it as a separate component-local class.
769 ///
770 /// See @ref bslstl_map
771 class value_compare {
772
773 // FRIENDS
774 friend class map;
775
776 protected:
777 // PROTECTED DATA
778 COMPARATOR comp; // we would not have elected to make this data
779 // member 'protected'
780
781 // PROTECTED CREATORS
782
783 /// Create a @ref value_compare object that uses the specified
784 /// `comparator`.
785 value_compare(COMPARATOR comparator); // IMPLICIT
786
787 public:
788 // PUBLIC TYPES
789
790 /// This `typedef` is an alias for the result type of a call to the
791 /// overload of `operator()` (the comparison function) provided by a
792 /// `map::value_compare` object.
793 typedef bool result_type;
794
795 /// This `typedef` is an alias for the type of the first parameter
796 /// of the overload of `operator()` (the comparison function)
797 /// provided by a `map::value_compare` object.
798 typedef value_type first_argument_type;
799
800 /// This `typedef` is an alias for the type of the second parameter
801 /// of the overload of `operator()` (the comparison function)
802 /// provided by a `map::value_compare` object.
803 typedef value_type second_argument_type;
804
805 // CREATORS
806 value_compare(const value_compare& original) = default;
807 // Create a @ref value_compare object having the same value as the
808 // specified 'original' object.
809
810 ~value_compare() = default;
811 // Destroy this object.
812
813 // MANIPULATORS
814 value_compare& operator=(const value_compare& rhs) = default;
815 // Assign to this object the value of the specified 'rhs' object,
816 // and return a reference providing modifiable access to this
817 // object.
818
819 // ACCESSORS
820
821 /// Return `true` if the specified `x` object is ordered before the
822 /// specified `y` object, as determined by the comparator supplied
823 /// at construction, and `false` otherwise.
824 bool operator()(const value_type& x, const value_type& y) const;
825 };
826
827 private:
828 // PRIVATE CLASS METHODS
829
830 /// Return an address providing modifiable access to the specified `node`.
831 ///
832 /// \pre The behavior is undefined unless `node` is the address of a
833 /// `Node` object.
834 static Node *toNode(BloombergLP::bslalg::RbTreeNode *node);
835
836 /// Return an address providing non-modifiable access to the specified `node`.
837 ///
838 /// \pre The behavior is undefined unless `node` is the address of a
839 /// `Node` object.
840 static const Node *toNode(const BloombergLP::bslalg::RbTreeNode *node);
841
842 // PRIVATE MANIPULATORS
843
844 /// Return a reference providing modifiable access to the node allocator
845 /// for this map.
846 NodeFactory& nodeFactory();
847
848 /// Return a reference providing modifiable access to the comparator for
849 /// this map.
850 Comparator& comparator();
851
852 /// Efficiently exchange the value, comparator, and allocator of this
853 /// object with the value, comparator, and allocator of the specified
854 /// `other` object. This method provides the no-throw exception-safety
855 /// guarantee, *unless* swapping the (user-supplied) comparator or
856 /// allocator objects can throw.
857 void quickSwapExchangeAllocators(map& other);
858
859 /// Efficiently exchange the value and comparator of this object with
860 /// the value and comparator of the specified `other` object. This
861 /// method provides the no-throw exception-safety guarantee, *unless*
862 /// swapping the (user-supplied) comparator objects can throw.
863 ///
864 /// \pre The behavior is undefined unless this object was created with the same
865 /// allocator as `other`.
866 void quickSwapRetainAllocators(map& other);
867
868 /// Insert the values between the specified `first` and `last` into an
869 /// initially empty map. If sorted, directly place each value in its
870 /// proper position. If an out of order value is detected, revert to
871 /// normal insertion.
872 template <class INPUT_ITERATOR, class SENTINEL>
873 void constructFromRange(INPUT_ITERATOR first, SENTINEL last);
874
875#if defined(BSLS_LIBRARYFEATURES_HAS_CPP20_CONCEPTS) \
876 && defined(BSLS_LIBRARYFEATURES_HAS_CPP20_RANGES)
877
878 /// Insert the values between the specified `first` and `last` into an
879 /// initially empty map. The specified 'numElements` is used to improve
880 /// performance. If sorted, directly place each value in its proper
881 /// position. If an out of order value is detected, revert to normal insertion.
882 ///
883 /// \pre The behavior is undefined if the iterators support
884 /// the calculation of distance and `numElements` is not the distance
885 /// from `first` to `last`.
886 template <class INPUT_ITERATOR, class SENTINEL>
887 void constructFromRange(INPUT_ITERATOR first,
888 SENTINEL last,
889 size_t numElements);
890#endif
891
892 // Insert the values between `first` and `last` into this map.
893 template <class INPUT_ITERATOR, class SENTINEL>
894 void insertFromRange(INPUT_ITERATOR first,
895 SENTINEL last);
896
897#if defined(BSLS_LIBRARYFEATURES_HAS_CPP20_CONCEPTS) \
898 && defined(BSLS_LIBRARYFEATURES_HAS_CPP20_RANGES)
899
900 /// Insert the values between the specified `first` and `last` into this
901 /// map. The specified `numElements` is used to improve performance.
902 ///
903 /// \pre The behavior is undefined if the iterators support the calculation
904 /// of distance and `numElements` is not the distance from `first` to
905 /// `last`.
906 template <class INPUT_ITERATOR, class SENTINEL>
907 void insertFromRange(INPUT_ITERATOR first,
908 SENTINEL last,
909 size_t numElements);
910#endif
911
912 // PRIVATE ACCESSORS
913
914 /// Return a reference providing non-modifiable access to the node
915 /// allocator for this map.
916 const NodeFactory& nodeFactory() const;
917
918 /// Return a reference providing non-modifiable access to the comparator
919 /// for this map.
920 const Comparator& comparator() const;
921
922 public:
923 // CREATORS
924
925 /// Create an empty map. Optionally specify a `comparator` used to
926 /// order key-value pairs contained in this object. If `comparator` is
927 /// not supplied, a default-constructed object of the (template
928 /// parameter) type `COMPARATOR` is used. Optionally specify a
929 /// `basicAllocator` used to supply memory. If `basicAllocator` is not
930 /// supplied, a default-constructed object of the (template parameter)
931 /// type `ALLOCATOR` is used. If the type `ALLOCATOR` is
932 /// `bsl::allocator` (the default), then `basicAllocator`, if supplied,
933 /// shall be convertible to `bslma::Allocator *`. If the type
934 /// `ALLOCATOR` is `bsl::allocator` and `basicAllocator` is not
935 /// supplied, the currently installed default allocator is used.
936 map();
937 explicit map(const COMPARATOR& comparator,
938 const ALLOCATOR& basicAllocator = ALLOCATOR())
939 : d_compAndAlloc(comparator, basicAllocator)
940 , d_tree()
941 {
942 // The implementation is placed here in the class definition to work
943 // around an AIX compiler bug, where the constructor can fail to
944 // compile because it is unable to find the definition of the default
945 // argument. This occurs when a parameterized class wraps around the
946 // container and the comparator is defined after the new class.
947 }
948
949 /// Create an empty map that uses the specified `basicAllocator` to
950 /// supply memory. Use a default-constructed object of the (template
951 /// parameter) type `COMPARATOR` to order the key-value pairs contained in this map.
952 ///
953 /// \note Note that a `bslma::Allocator *` can be supplied for
954 /// `basicAllocator` if the (template parameter) `ALLOCATOR` is
955 /// `bsl::allocator` (the default).
956 explicit map(const ALLOCATOR& basicAllocator);
957
958 /// Create a map having the same value as the specified `original`
959 /// object. Use a copy of `original.key_comp()` to order the key-value
960 /// pairs contained in this map. Use the allocator returned by
961 /// 'bsl::allocator_traits<ALLOCATOR>::
962 /// select_on_container_copy_construction(original.get_allocator())' to
963 /// allocate memory. If the (template parameter) type `ALLOCATOR` is
964 /// `bsl::allocator` (the default), the currently installed default
965 /// allocator is used. This method requires that the (template
966 /// parameter) types `KEY` and `VALUE` both be `copy-insertable` into
967 /// this map (see {Requirements on `KEY` and `VALUE`}).
968 map(const map& original);
969
970 /// Create a map having the same value as the specified `original`
971 /// object by moving (in constant time) the contents of `original` to
972 /// the new map. Use a copy of `original.key_comp()` to order the
973 /// key-value pairs contained in this map. The allocator associated
974 /// with `original` is propagated for use in the newly-created map.
975 /// `original` is left in a valid but unspecified state.
976 map(BloombergLP::bslmf::MovableRef<map> original); // IMPLICIT
977
978 /// Create a map having the same value as the specified `original`
979 /// object that uses the specified `basicAllocator` to supply memory.
980 /// Use a copy of `original.key_comp()` to order the key-value pairs
981 /// contained in this map. This method requires that the (template
982 /// parameter) types `KEY` and `VALUE` both be `copy-insertable` into this map (see {Requirements on `KEY` and `VALUE`}).
983 ///
984 /// \note Note that a
985 /// `bslma::Allocator *` can be supplied for `basicAllocator` if the
986 /// (template parameter) `ALLOCATOR` is `bsl::allocator` (the default).
987 map(const map& original,
988 const typename type_identity<ALLOCATOR>::type& basicAllocator);
989
990 /// Create a map having the same value as the specified `original`
991 /// object that uses the specified `basicAllocator` to supply memory.
992 /// The contents of `original` are moved (in constant time) to the new
993 /// map if `basicAllocator == original.get_allocator()`, and are move-
994 /// inserted (in linear time) using `basicAllocator` otherwise.
995 /// `original` is left in a valid but unspecified state. Use a copy of
996 /// `original.key_comp()` to order the key-value pairs contained in this
997 /// map. This method requires that the (template parameter) types `KEY`
998 /// and `VALUE` both be `move-insertable` into this map (see {Requirements on `KEY` and `VALUE`}).
999 ///
1000 /// \note Note that a
1001 /// `bslma::Allocator *` can be supplied for `basicAllocator` if the
1002 /// (template parameter) `ALLOCATOR` is `bsl::allocator` (the default).
1003 map(BloombergLP::bslmf::MovableRef<map> original,
1004 const typename type_identity<ALLOCATOR>::type& basicAllocator);
1005
1006 /// Create a map, and insert each `value_type` object in the sequence
1007 /// starting at the specified `first` element, and ending immediately
1008 /// before the specified `last` element, ignoring those objects having a
1009 /// key equivalent to that which appears earlier in the sequence.
1010 /// Optionally specify a `comparator` used to order key-value pairs
1011 /// contained in this object. If `comparator` is not supplied, a
1012 /// default-constructed object of the (template parameter) type
1013 /// `COMPARATOR` is used. Optionally specify a `basicAllocator` used to
1014 /// supply memory. If `basicAllocator` is not supplied, a
1015 /// default-constructed object of the (template parameter) type
1016 /// `ALLOCATOR` is used. If the type `ALLOCATOR` is `bsl::allocator`
1017 /// (the default), then `basicAllocator`, if supplied, shall be
1018 /// convertible to `bslma::Allocator *`. If the type `ALLOCATOR` is
1019 /// `bsl::allocator` and `basicAllocator` is not supplied, the currently
1020 /// installed default allocator is used. If the sequence `first` to
1021 /// `last` is ordered according to `comparator`, then this operation has
1022 /// `O[N]` complexity, where `N` is the number of elements between
1023 /// `first` and `last`; otherwise, this operation has `O[N * log(N)]`
1024 /// complexity.
1025 ///
1026 /// The (template parameter) type `INPUT_ITERATOR` shall
1027 /// meet the requirements of an input iterator defined in the C++11
1028 /// standard [input.iterators] providing access to values of a type
1029 /// convertible to `value_type`, and `value_type` must be
1030 /// `emplace-constructible` from `*i` into this map, where `i` is a
1031 /// dereferenceable iterator in the range `[first .. last)` (see
1032 /// {Requirements on `KEY` and `VALUE`}).
1033 ///
1034 /// \pre The behavior is undefined unless `first` and `last` refer to a sequence of valid values where
1035 /// `first` is at a position at or before `last`.
1036 template <class INPUT_ITERATOR>
1037 map(INPUT_ITERATOR first,
1038 INPUT_ITERATOR last,
1039 const COMPARATOR& comparator = COMPARATOR(),
1040 const ALLOCATOR& basicAllocator = ALLOCATOR());
1041 template <class INPUT_ITERATOR>
1042 map(INPUT_ITERATOR first,
1043 INPUT_ITERATOR last,
1044 const ALLOCATOR& basicAllocator);
1045
1046 /// Create a map having the (`value_type`) values obtained from the
1047 /// specified `range`. Ignore those those objects having a key equivalent
1048 /// to that which appears earlier in the sequence. Optionally specify a
1049 /// `comparator` used to order key-value pairs contained in this object.
1050 /// If `comparator` is not supplied, a default-constructed object of the
1051 /// (template parameter) type `COMPARATOR` is used. Optionally specify a
1052 /// `basicAllocator` used to supply memory. If `basicAllocator` is not
1053 /// supplied, a default-constructed object of the (template parameter) type
1054 /// `ALLOCATOR` is used. If the type `ALLOCATOR` is `bsl::allocator`
1055 /// (the default), then `basicAllocator`, if supplied, shall be
1056 /// convertible to `bslma::Allocator *`. If the type `ALLOCATOR` is
1057 /// `bsl::allocator` and `basicAllocator` is not supplied, the currently
1058 /// installed default allocator is used. If values obtained from `range
1059 /// are ordered according to `comparator`, then this operation has `O[N]`
1060 /// complexity, where `N` is the number of values in the `range`;
1061 /// otherwise, this operation has `O[N * log(N)]` complexity.
1062 ///
1063 /// \note Note that `RANGE` must meet the requirements of an input range and the values
1064 /// from `range` must have a type matching or convertible to `value_type`.
1065 template <class RANGE>
1066 BSLSTL_MAP_REQUIRES_CONTAINER_COMPATIBLE_RANGE(RANGE, value_type)
1067 map(bsl::from_range_t ,
1068 BSLS_COMPILERFEATURES_FORWARD_REF(RANGE) range,
1069 const COMPARATOR& comparator = COMPARATOR(),
1070 const ALLOCATOR& basicAllocator = ALLOCATOR())
1071 : d_compAndAlloc(comparator, basicAllocator)
1072 , d_tree()
1073 {
1074 // Defined inline to avoid Windows errors.
1075
1076#if defined(BSLS_LIBRARYFEATURES_HAS_CPP20_CONCEPTS) \
1077 && defined(BSLS_LIBRARYFEATURES_HAS_CPP20_RANGES)
1078 if constexpr (ranges::sized_range<RANGE>) {
1079 constructFromRange(bsl::ranges::begin(range),
1080 bsl::ranges::end (range),
1081 bsl::ranges::size (range));
1082 } else // ...
1083#endif
1084 {
1085 constructFromRange(bsl::ranges::begin(range),
1086 bsl::ranges::end (range));
1087 }
1088 }
1089
1090 template <class RANGE>
1091 BSLSTL_MAP_REQUIRES_CONTAINER_COMPATIBLE_RANGE(RANGE, value_type)
1092 map(from_range_t ,
1093 BSLS_COMPILERFEATURES_FORWARD_REF(RANGE) range,
1094 const ALLOCATOR& basicAllocator)
1095 : d_compAndAlloc(COMPARATOR(), basicAllocator)
1096 , d_tree()
1097 {
1098 // Defined inline to avoid Windows errors.
1099
1100 map other(bsl::from_range,
1101 range,
1102 COMPARATOR(),
1103 nodeFactory().allocator());
1104 quickSwapRetainAllocators(other);
1105 }
1106
1107#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
1108 /// Create a map and insert each `value_type` object in the specified
1109 /// `values` initializer list, ignoring those objects having a key
1110 /// equivalent to that which appears earlier in the list. Optionally
1111 /// specify a `comparator` used to order keys contained in this object.
1112 /// If `comparator` is not supplied, a default-constructed object of the
1113 /// (template parameter) type `COMPARATOR` is used. Optionally specify
1114 /// a `basicAllocator` used to supply memory. If `basicAllocator` is
1115 /// not supplied, a default-constructed object of the (template
1116 /// parameter) type `ALLOCATOR` is used. If the type `ALLOCATOR` is
1117 /// `bsl::allocator` (the default), then `basicAllocator`, if supplied,
1118 /// shall be convertible to `bslma::Allocator *`. If the type
1119 /// `ALLOCATOR` is `bsl::allocator` and `basicAllocator` is not
1120 /// supplied, the currently installed default allocator is used. If
1121 /// `values` is ordered according to `comparator`, then this operation
1122 /// has `O[N]` complexity, where `N` is the number of elements in
1123 /// `values`; otherwise, this operation has `O[N * log(N)]` complexity.
1124 /// This method requires that the (template parameter) types `KEY` and
1125 /// `VALUE` both be `copy-insertable` into this map (see {Requirements
1126 /// on `KEY` and `VALUE`}).
1127 map(std::initializer_list<value_type> values,
1128 const COMPARATOR& comparator = COMPARATOR(),
1129 const ALLOCATOR& basicAllocator = ALLOCATOR());
1130 map(std::initializer_list<value_type> values,
1131 const ALLOCATOR& basicAllocator);
1132#endif
1133
1134 /// Destroy this object.
1135 ~map();
1136
1137 // MANIPULATORS
1138
1139 /// Assign to this object the value and comparator of the specified
1140 /// `rhs` object, propagate to this object the allocator of `rhs` if the
1141 /// `ALLOCATOR` type has trait @ref propagate_on_container_copy_assignment ,
1142 /// and return a reference providing modifiable access to this object.
1143 /// If an exception is thrown, `*this` is left in a valid but
1144 /// unspecified state. This method requires that the (template
1145 /// parameter) types `KEY` and `VALUE` both be `copy-assignable` and
1146 /// `copy-insertable` into this map (see {Requirements on `KEY` and
1147 /// `VALUE`}).
1148 map& operator=(const map& rhs);
1149
1150 map& operator=(BloombergLP::bslmf::MovableRef<map> rhs)
1151 BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(
1152 AllocatorTraits::is_always_equal::value &&
1153 std::is_nothrow_move_assignable<COMPARATOR>::value);
1154 // Assign to this object the value and comparator of the specified
1155 // 'rhs' object, propagate to this object the allocator of 'rhs' if the
1156 // 'ALLOCATOR' type has trait @ref propagate_on_container_move_assignment ,
1157 // and return a reference providing modifiable access to this object.
1158 // The contents of 'rhs' are moved (in constant time) to this map if
1159 // 'get_allocator() == rhs.get_allocator()' (after accounting for the
1160 // aforementioned trait); otherwise, all elements in this map are
1161 // either destroyed or move-assigned to and each additional element in
1162 // 'rhs' is move-inserted into this map. 'rhs' is left in a valid but
1163 // unspecified state, and if an exception is thrown, '*this' is left
1164 // in a valid but unspecified state. This method requires that the
1165 // (template parameter) types 'KEY' and 'VALUE' both be
1166 // 'move-assignable' and 'move-insertable' into this map (see
1167 // {Requirements on 'KEY' and 'VALUE'}).
1168
1169#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
1170 /// Assign to this object the value resulting from first clearing this
1171 /// map and then inserting each `value_type` object in the specified
1172 /// `values` initializer list, ignoring those objects having a key
1173 /// equivalent to that which appears earlier in the list; return a
1174 /// reference providing modifiable access to this object. This method
1175 /// requires that the (template parameter) types `KEY` and `VALUE` both
1176 /// be `copy-insertable` into this map (see {Requirements on `KEY` and
1177 /// `VALUE`}).
1178 map& operator=(std::initializer_list<value_type> values);
1179#endif
1180
1181 /// Return a reference providing modifiable access to the mapped-value
1182 /// associated with the specified `key`; if this `map` does not already
1183 /// contain a `value_type` object having an equivalent key, first insert
1184 /// a new `value_type` object having `key` and a default-constructed
1185 /// `VALUE` object, and return a reference to the newly mapped (default)
1186 /// value. This method requires that the (template parameter) type
1187 /// `KEY` be `copy-insertable` into this map and the (template
1188 /// parameter) type `VALUE` be `default-insertable` into this map (see
1189 /// {Requirements on `KEY` and `VALUE`}).
1190 typename add_lvalue_reference<VALUE>::type operator[](const key_type& key);
1191
1192 /// Return a reference providing modifiable access to the mapped-value
1193 /// associated with the specified `key`; if this `map` does not already
1194 /// contain a `value_type` object having an equivalent key, first insert
1195 /// a new `value_type` object having the move-inserted `key` and a
1196 /// default-constructed `VALUE` object, and return a reference to the
1197 /// newly mapped (default) value. This method requires that the
1198 /// (template parameter) type `KEY` be `move-insertable` into this map
1199 /// and the (template parameter) type `VALUE` be `default-insertable`
1200 /// into this map (see {Requirements on `KEY` and `VALUE`}).
1201 typename add_lvalue_reference<VALUE>::type operator[](
1202 BloombergLP::bslmf::MovableRef<key_type> key);
1203
1204#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
1205 /// Return a reference providing modifiable access to the mapped-value
1206 /// associated with a key that is equivalent with the specified `key`; if
1207 /// this `map` does not already contain a `value_type` object having an
1208 /// equivalent key, first insert a new `value_type` object having the
1209 /// move-inserted `key` and a default-constructed `VALUE` object, and
1210 /// return a reference to the newly mapped (default) value. This method
1211 /// requires that the (template parameter) type `KEY` be `move-insertable`
1212 /// into this map and the (template parameter) type `VALUE` be
1213 /// `default-insertable` into this map (see {Requirements on `KEY` and
1214 /// `VALUE`}).
1215 template <class LOOKUP_KEY>
1216 typename bsl::enable_if<
1217 BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,
1218 LOOKUP_KEY>::value,
1219 typename add_lvalue_reference<VALUE>::type>::type
1220 operator [](LOOKUP_KEY&& key)
1221 {
1222 // Note: implemented inline due to Sun CC compilation error.
1223
1224 return try_emplace(
1225 BSLS_COMPILERFEATURES_FORWARD(LOOKUP_KEY, key)).first->second;
1226 }
1227#endif
1228
1229 /// Return a reference providing modifiable access to the mapped-value
1230 /// associated with the specified `key`, if such an entry exists; otherwise, throw a `std::out_of_range` exception.
1231 ///
1232 /// \note Note that this
1233 /// method may also throw a different kind of exception if the
1234 /// (user-supplied) comparator throws.
1235 typename add_lvalue_reference<VALUE>::type at(const key_type& key);
1236
1237 /// Return a reference providing modifiable access to the
1238 /// mapped-value associated with a key that is equivalent to the
1239 /// specified `key`, if such an entry exists; otherwise, throw a `std::out_of_range` exception.
1240 ///
1241 /// \note Note that this method may also throw
1242 /// a different kind of exception if the (user-supplied) comparator
1243 /// throws.
1244 template <class LOOKUP_KEY>
1245 typename bsl::enable_if<
1246 BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,
1247 LOOKUP_KEY>::value,
1248 typename add_lvalue_reference<VALUE>::type>::type
1249 at(const LOOKUP_KEY& key) {
1250 // Note: implemented inline due to Sun CC compilation error.
1251
1252 iterator iter = find(key);
1253 if (iter == end()) {
1254 BloombergLP::bslstl::StdExceptUtil::throwOutOfRange(
1255 "map<...>::at(LOOKUP_KEY): invalid key value");
1256 }
1257 return iter->second;
1258 }
1259
1260 /// Return an iterator providing modifiable access to the first
1261 /// `value_type` object in the ordered sequence of `value_type` objects
1262 /// maintained by this map, or the `end` iterator if this map is empty.
1263 iterator begin() BSLS_KEYWORD_NOEXCEPT;
1264
1265 /// Return an iterator providing modifiable access to the past-the-end
1266 /// element in the ordered sequence of `value_type` objects maintained
1267 /// by this map.
1268 iterator end() BSLS_KEYWORD_NOEXCEPT;
1269
1270 /// Return a reverse iterator providing modifiable access to the last
1271 /// `value_type` object in the ordered sequence of `value_type` objects
1272 /// maintained by this map, or `rend` if this map is empty.
1273 reverse_iterator rbegin() BSLS_KEYWORD_NOEXCEPT;
1274
1275 /// Return a reverse iterator providing modifiable access to the
1276 /// prior-to-the-beginning element in the ordered sequence of
1277 /// `value_type` objects maintained by this map.
1278 reverse_iterator rend() BSLS_KEYWORD_NOEXCEPT;
1279
1280 /// Insert the specified `value` into this map if a key (the `first`
1281 /// element) equivalent to that of `value` does not already exist in
1282 /// this map; otherwise, if a `value_type` object whose key is
1283 /// equivalent to that of `value` already exists in this map, this
1284 /// method has no effect. Return a pair whose `first` member is an
1285 /// iterator referring to the (possibly newly inserted) `value_type`
1286 /// object in this map whose key is equivalent to that of `value`, and
1287 /// whose `second` member is `true` if a new value was inserted, and
1288 /// `false` if the key was already present. This method requires that
1289 /// the (template parameter) types `KEY` and `VALUE` both be
1290 /// `copy-insertable` into this map (see {Requirements on `KEY` and
1291 /// `VALUE`}).
1292 pair<iterator, bool> insert(const value_type& value);
1293
1294 /// Insert into this map the specified `value` if a key (the `first`
1295 /// element) equivalent to that of `value` does not already exist in
1296 /// this map; otherwise, this method has no effect. Return a pair whose
1297 /// `first` member is an iterator referring to the (possibly newly
1298 /// inserted) `value_type` object in this map whose key is equivalent to
1299 /// that of `value`, and whose `second` member is `true` if a new value
1300 /// was inserted and `false` if the key was already present. This
1301 /// method requires that the (template parameter) types `KEY` and
1302 /// `VALUE` both be `move-insertable` into this map (see {Requirements
1303 /// on `KEY` and `VALUE`}).
1304 pair<iterator, bool> insert(
1305 BloombergLP::bslmf::MovableRef<value_type> value);
1306
1307#if defined(BSLS_PLATFORM_CMP_SUN) && BSLS_PLATFORM_CMP_VERSION < 0x5130
1308 template <class ALT_VALUE_TYPE>
1309 pair<iterator, bool>
1310#elif !defined(BSLS_COMPILERFEATURES_SUPPORT_TRAITS_HEADER)
1311 template <class ALT_VALUE_TYPE>
1312 typename enable_if<is_convertible<ALT_VALUE_TYPE, value_type>::value,
1313 pair<iterator, bool> >::type
1314#else
1315 /// Insert into this map a `value_type` object created from the
1316 /// specified `value` if a key (the `first` element) equivalent to that
1317 /// of such an object does not already exist in this map; otherwise,
1318 /// this method has no effect (other than possibly creating a temporary
1319 /// `value_type` object). Return a pair whose `first` member is an
1320 /// iterator referring to the (possibly newly inserted) `value_type`
1321 /// object in this map whose key is equivalent to that of the object
1322 /// created from `value`, and whose `second` member is `true` if a new
1323 /// value was inserted and `false` if the key was already present. This
1324 /// method requires that the (template parameter) types `KEY` and
1325 /// `VALUE` both be `move-insertable` into this map (see {Requirements
1326 /// on `KEY` and `VALUE`}), and the `value_type` be constructible from
1327 /// the (template parameter) `ALT_VALUE_TYPE`.
1328 template <class ALT_VALUE_TYPE>
1329 typename enable_if<std::is_constructible<value_type,
1330 ALT_VALUE_TYPE&&>::value,
1331 pair<iterator, bool> >::type
1332#endif
1333 insert(BSLS_COMPILERFEATURES_FORWARD_REF(ALT_VALUE_TYPE) value)
1334 {
1335 // This function has to be implemented inline, in violation of BDE
1336 // convention, as the MSVC compiler cannot match the out-of-class
1337 // definition of the declaration in the class.
1338
1339 return emplace(BSLS_COMPILERFEATURES_FORWARD(ALT_VALUE_TYPE, value));
1340 }
1341
1342 /// Insert the specified `value` into this map (in amortized constant
1343 /// time if the specified `hint` is a valid immediate successor to the
1344 /// key of `value`) if a key (the `first` element) equivalent to that of
1345 /// `value` does not already exist in this map; otherwise, if a
1346 /// `value_type` object whose key is equivalent to that of `value`
1347 /// already exists in this map, this method has no effect. Return an
1348 /// iterator referring to the (possibly newly inserted) `value_type`
1349 /// object in this map whose key is equivalent to that of `value`. If
1350 /// `hint` is not a valid immediate successor to the key of `value`,
1351 /// this operation has `O[log(N)]` complexity, where `N` is the size of
1352 /// this map. This method requires that the (template parameter) types
1353 /// `KEY` and `VALUE` both be `copy-insertable` into this map (see
1354 /// {Requirements on `KEY` and `VALUE`}).
1355 ///
1356 /// \pre The behavior is undefined unless `hint` is an iterator in the range `[begin() .. end()]` (both
1357 /// endpoints included).
1358 iterator insert(const_iterator hint, const value_type& value);
1359
1360 /// Insert into this map the specified `value` (in amortized constant
1361 /// time if the specified `hint` is a valid immediate successor to
1362 /// `value`) if a key (the `first` element) equivalent to that of
1363 /// `value` does not already exist in this map; otherwise, this method
1364 /// has no effect. Return an iterator referring to the (possibly newly
1365 /// inserted) `value_type` object in this map whose key is equivalent to
1366 /// that of `value`. If `hint` is not a valid immediate successor to
1367 /// `value`, this operation has `O[log(N)]` complexity, where `N` is the
1368 /// size of this map. This method requires that the (template
1369 /// parameter) types `KEY` and `VALUE` both be `move-insertable` into
1370 /// this map (see {Requirements on `KEY` and `VALUE`}).
1371 ///
1372 /// \pre The behavior is undefined unless `hint` is an iterator in the range
1373 /// `[begin() .. end()]` (both endpoints included).
1374 iterator insert(const_iterator hint,
1375 BloombergLP::bslmf::MovableRef<value_type> value);
1376
1377#if defined(BSLS_PLATFORM_CMP_SUN) && BSLS_PLATFORM_CMP_VERSION < 0x5130
1378 template <class ALT_VALUE_TYPE>
1379 iterator
1380#elif !defined(BSLS_COMPILERFEATURES_SUPPORT_TRAITS_HEADER)
1381 template <class ALT_VALUE_TYPE>
1382 typename enable_if<is_convertible<ALT_VALUE_TYPE, value_type>::value,
1383 iterator>::type
1384#else
1385 /// Insert into this map a `value_type` object created from the
1386 /// specified `value` (in amortized constant time if the specified
1387 /// `hint` is a valid immediate successor to the object created from
1388 /// `value`) if a key (the `first` element) equivalent to such an object
1389 /// does not already exist in this map; otherwise, this method has no
1390 /// effect (other than possibly creating a temporary `value_type`
1391 /// object). Return an iterator referring to the (possibly newly
1392 /// inserted) `value_type` object in this map whose key is equivalent to
1393 /// that of the object created from `value`. If `hint` is not a valid
1394 /// immediate successor to the object created from `value`, this
1395 /// operation has `O[log(N)]` complexity, where `N` is the size of this
1396 /// map. This method requires that the (template parameter) types `KEY`
1397 /// and `VALUE` both be `move-insertable` into this map (see
1398 /// {Requirements on `KEY` and `VALUE`}), and the `value_type` be
1399 /// constructible from the (template parameter) `ALT_VALUE_TYPE`.
1400 ///
1401 /// \pre The behavior is undefined unless `hint` is an iterator in the range
1402 /// `[begin() .. end()]` (both endpoints included).
1403 template <class ALT_VALUE_TYPE>
1404 typename enable_if<std::is_constructible<value_type,
1405 ALT_VALUE_TYPE&&>::value,
1406 iterator>::type
1407#endif
1408 insert(const_iterator hint,
1409 BSLS_COMPILERFEATURES_FORWARD_REF(ALT_VALUE_TYPE) value)
1410 {
1411 // This function has to be implemented inline, in violation of BDE
1412 // convention, as the MSVC compiler cannot match the out-of-class
1413 // definition of the declaration in the class.
1414
1415 return emplace_hint(
1416 hint,
1417 BSLS_COMPILERFEATURES_FORWARD(ALT_VALUE_TYPE, value));
1418 }
1419
1420 /// Insert into this map the value of each `value_type` object in the
1421 /// range starting at the specified `first` iterator and ending
1422 /// immediately before the specified `last` iterator, if a key
1423 /// equivalent to that of the object is not already contained in this
1424 /// map. The (template parameter) type `INPUT_ITERATOR` shall meet the
1425 /// requirements of an input iterator defined in the C++11 standard
1426 /// [input.iterators] providing access to values of a type convertible
1427 /// to `value_type`, and `value_type` must be `emplace-constructible`
1428 /// from `*i` into this map, where `i` is a dereferenceable iterator in
1429 /// the range `[first .. last)` (see {Requirements on `KEY` and `VALUE`}).
1430 ///
1431 /// \pre The behavior is undefined unless `first` and `last`
1432 /// refer to a sequence of valid values where `first` is at a position
1433 /// at or before `last`.
1434 template <class INPUT_ITERATOR>
1435 void insert(INPUT_ITERATOR first, INPUT_ITERATOR last);
1436
1437 /// Insert into this map the value of each `value_type` object in the
1438 /// specified `range` if the key equivalent of that object is not
1439 /// already contained in this map. The (template parameter) type `RANGE`
1440 /// must meet the requirements the C++20 standard [ranges] providing access
1441 /// to values of a type convertible to `value_type`, and `value_type` must
1442 /// be `emplace-constructible` from `*i` into this map, where `i` is a
1443 /// dereferenceable iterator obtained from `range` (see {Requirements on `KEY` and `VALUE`}).
1444 ///
1445 /// \pre The behavior is undefined if `range` overlaps
1446 /// this map.
1447 template <class RANGE>
1448 BSLSTL_MAP_REQUIRES_CONTAINER_COMPATIBLE_RANGE(RANGE, value_type)
1449 void insert_range(BSLS_COMPILERFEATURES_FORWARD_REF(RANGE) range)
1450 {
1451 // Defined inline to avoid Windows errors.
1452
1453#if defined(BSLS_LIBRARYFEATURES_HAS_CPP20_CONCEPTS) \
1454 && defined(BSLS_LIBRARYFEATURES_HAS_CPP20_RANGES)
1455 if constexpr (ranges::sized_range<RANGE>) {
1456 insertFromRange(bsl::ranges::begin(range),
1457 bsl::ranges::end (range),
1458 bsl::ranges::size (range));
1459 } else // ...
1460#endif
1461 {
1462 insertFromRange(bsl::ranges::begin(range),
1463 bsl::ranges::end (range));
1464 }
1465 }
1466
1467#if defined(BSLS_PLATFORM_CMP_SUN) && BSLS_PLATFORM_CMP_VERSION < 0x5130
1468 void insert(const_iterator first, const_iterator last);
1469 // This method is provided only on Sun to work around a bug in the Sun
1470 // Studio 12.3 compiler, which prevents us from disabling (at compile
1471 // time) the overload of 'insert' taking a 'const_iterator' and a
1472 // forwarding reference if the second argument is not convertible to
1473 // the value type associated with the map. Without such a check, in
1474 // certain cases, the same compiler complains of ambiguity between
1475 // the 'insert' method taking two input iterators and the 'insert'
1476 // method taking a 'const_iterator' and a forwarding reference; such
1477 // an ambiguity is resolved by providing this method, which is
1478 // equivalent to the 'insert' method (above) taking two input iterators
1479 // of template parameter type.
1480#endif
1481
1482#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
1483 /// Insert into this map the value of each `value_type` object in the
1484 /// specified `values` initializer list if a key equivalent to that of
1485 /// the object is not already contained in this map. This method
1486 /// requires that the (template parameter) types `KEY` and `VALUE` both
1487 /// be `copy-insertable` into this map (see {Requirements on `KEY` and
1488 /// `VALUE`}).
1489 void insert(std::initializer_list<value_type> values);
1490#endif
1491
1492#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
1493 /// If a key equivalent to the specified `key` already exists in this
1494 /// map, assign the specified `obj` to the value associated with that
1495 /// key, and return a pair containing an iterator referring to the
1496 /// existing item and `false`. Otherwise, insert into this map a
1497 /// newly-created `value_type` object, constructed from
1498 /// `(key, std::forward<BDE_OTHER_TYPE>(obj)...))`, and return a pair
1499 /// containing an iterator referring to the newly-created entry and
1500 /// `true`.
1501 template <class BDE_OTHER_TYPE>
1502 pair<iterator, bool> insert_or_assign(const KEY& key,
1503 BDE_OTHER_TYPE&& obj);
1504
1505 template <class BDE_OTHER_TYPE>
1506 pair<iterator, bool> insert_or_assign(
1507 BloombergLP::bslmf::MovableRef<KEY> key,
1508 BDE_OTHER_TYPE&& obj);
1509
1510 /// If a key equivalent to the specified `key` already exists in this
1511 /// map, assign the specified `obj` to the value associated with that
1512 /// key, and return a pair containing an iterator referring to the
1513 /// existing item and `false`. Otherwise, insert into this map a
1514 /// newly-created `value_type` object, constructed from
1515 /// `(std::forward<KEY>(key), std::forward<BDE_OTHER_TYPE>(obj)...))`,
1516 /// and return a pair containing an iterator referring to the
1517 /// newly-created entry and `true`.
1518 template<class LOOKUP_KEY, class BDE_OTHER_TYPE>
1519 typename bsl::enable_if<
1520 BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,
1521 LOOKUP_KEY>::value,
1522 pair<iterator, bool> >::type
1523 insert_or_assign(LOOKUP_KEY&& key, BDE_OTHER_TYPE&& obj)
1524 {
1525 // Note: implemented inline due to Sun CC compilation error.
1526
1527 typedef pair<iterator, bool> Result;
1528
1529 int comparisonResult;
1530 BloombergLP::bslalg::RbTreeNode *insertLocation =
1531 BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation(
1532 &comparisonResult,
1533 &d_tree,
1534 this->comparator(),
1535 key);
1536
1537 if (!comparisonResult) { // ASSIGN
1538 iterator(insertLocation)->second =
1539 BSLS_COMPILERFEATURES_FORWARD(BDE_OTHER_TYPE, obj);
1540 return Result(iterator(insertLocation), false); // RETURN
1541 }
1542
1543 // INSERT
1544 BloombergLP::bslalg::RbTreeNode *node =
1545 nodeFactory().emplaceIntoNewNode(
1546 BSLS_COMPILERFEATURES_FORWARD(LOOKUP_KEY, key),
1547 BSLS_COMPILERFEATURES_FORWARD(BDE_OTHER_TYPE, obj));
1548
1549 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
1550 insertLocation,
1551 comparisonResult < 0,
1552 node);
1553
1554 return Result(iterator(node), true);
1555 }
1556
1557 /// If a key equivalent to the specified `key` already exists in this
1558 /// map, assign the specified `obj` to the value associated with that
1559 /// key, and return an iterator referring to the existing item.
1560 /// Otherwise, insert into this map a newly-created `value_type` object,
1561 /// constructed from `(key, std::forward<BDE_OTHER_TYPE>(obj)...))`, and
1562 /// return an iterator referring to the newly-created entry. Use the
1563 /// specified `hint` as a starting point for checking to see if the key
1564 /// is already in the map.
1565 template <class BDE_OTHER_TYPE>
1566 iterator insert_or_assign(const_iterator hint,
1567 const KEY& key,
1568 BDE_OTHER_TYPE&& obj);
1569
1570 /// If a key equivalent to the specified `key` already exists in this
1571 /// _map, assign the specified `obj` to the value associated with that
1572 /// key, and return an iterator referring to the existing item.
1573 /// Otherwise, insert into this map a newly-created `value_type` object
1574 /// constructed from
1575 /// `(std::forward<KEY>(key), std::forward<BDE_OTHER_TYPE>(obj)...))`,
1576 /// and return an iterator referring to the newly-created entry. Use
1577 /// the specified `hint` as a starting point for checking to see if the
1578 /// key already in the map.
1579 template <class BDE_OTHER_TYPE>
1580 iterator insert_or_assign(const_iterator hint,
1581 BloombergLP::bslmf::MovableRef<KEY> key,
1582 BDE_OTHER_TYPE&& obj);
1583
1584 /// If a key equivalent to the specified `key` already exists in this
1585 /// _map, assign the specified `obj` to the value associated with that
1586 /// key, and return an iterator referring to the existing item.
1587 /// Otherwise, insert into this map a newly-created `value_type` object
1588 /// constructed from
1589 /// `(std::forward<KEY>(key), std::forward<BDE_OTHER_TYPE>(obj)...))`,
1590 /// and return an iterator referring to the newly-created entry. Use
1591 /// the specified `hint` as a starting point for checking to see if the
1592 /// key already in the map.
1593 template<class LOOKUP_KEY, class BDE_OTHER_TYPE>
1594 typename bsl::enable_if<
1595 BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,
1596 LOOKUP_KEY>::value,
1597 iterator>::type
1598 insert_or_assign(const_iterator hint,
1599 LOOKUP_KEY&& key,
1600 BDE_OTHER_TYPE&& obj)
1601 {
1602 // Note: implemented inline due to Sun CC compilation error.
1603
1604 BloombergLP::bslalg::RbTreeNode *hintNode =
1605 const_cast<BloombergLP::bslalg::RbTreeNode *>(hint.node());
1606
1607 int comparisonResult;
1608 BloombergLP::bslalg::RbTreeNode *insertLocation =
1609 BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation(
1610 &comparisonResult,
1611 &d_tree,
1612 this->comparator(),
1613 key,
1614 hintNode);
1615
1616 if (!comparisonResult) { // ASSIGN
1617 iterator(insertLocation)->second =
1618 BSLS_COMPILERFEATURES_FORWARD(BDE_OTHER_TYPE, obj);
1619 return iterator(insertLocation); // RETURN
1620 }
1621
1622 // INSERT
1623 BloombergLP::bslalg::RbTreeNode *node =
1624 nodeFactory().emplaceIntoNewNode(
1625 BSLS_COMPILERFEATURES_FORWARD(LOOKUP_KEY, key),
1626 BSLS_COMPILERFEATURES_FORWARD(BDE_OTHER_TYPE, obj));
1627
1628 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
1629 insertLocation,
1630 comparisonResult < 0,
1631 node);
1632
1633 return iterator(node);
1634 }
1635#endif
1636
1637#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
1638 /// Insert into this map a newly-created `value_type` object,
1639 /// constructed by forwarding `get_allocator()` (if required) and the
1640 /// specified (variable number of) `args` to the corresponding
1641 /// constructor of `value_type`, if a key equivalent to such a value
1642 /// does not already exist in this map; otherwise, this method has no
1643 /// effect (other than possibly creating a temporary `value_type`
1644 /// object). Return a pair whose `first` member is an iterator
1645 /// referring to the (possibly newly created and inserted) object in
1646 /// this map whose key is equivalent to that of an object constructed
1647 /// from `args`, and whose `second` member is `true` if a new value was
1648 /// inserted, and `false` if an equivalent key was already present.
1649 /// This method requires that the (template parameter) types `KEY` and
1650 /// `VALUE` both be `emplace-constructible` from `args` (see
1651 /// {Requirements on `KEY` and `VALUE`}).
1652 template <class... Args>
1653 pair<iterator, bool> emplace(Args&&... args);
1654
1655 /// Insert into this map a newly-created `value_type` object,
1656 /// constructed by forwarding `get_allocator()` (if required) and the
1657 /// specified (variable number of) `args` to the corresponding
1658 /// constructor of `value_type` (in amortized constant time if the
1659 /// specified `hint` is a valid immediate successor to the `value_type`
1660 /// object constructed from `args`), if a key equivalent to such a value
1661 /// does not already exist in this map; otherwise, this method has no
1662 /// effect (other than possibly creating a temporary `value_type`
1663 /// object). Return an iterator referring to the (possibly newly
1664 /// created and inserted) object in this map whose key is equivalent to
1665 /// that of an object constructed from `args`. If `hint` is not a valid
1666 /// immediate successor to the `value_type` object implied by `args`,
1667 /// this operation has `O[log(N)]` complexity where `N` is the size of
1668 /// this map. This method requires that the (template parameter) types
1669 /// `KEY` and `VALUE` both be `emplace-constructible` from `args` (see
1670 /// {Requirements on `KEY` and `VALUE`}).
1671 ///
1672 /// \pre The behavior is undefined unless `hint` is an iterator in the range `[begin() .. end()]` (both
1673 /// endpoints included).
1674 template <class... Args>
1675 iterator emplace_hint(const_iterator hint, Args&&... args);
1676#endif
1677
1678 /// Remove from this map the `value_type` object at the specified
1679 /// `position`, and return an iterator referring to the element
1680 /// immediately following the removed element, or to the past-the-end
1681 /// position if the removed element was the last element in the sequence
1682 /// of elements maintained by this map. This method invalidates only
1683 /// iterators and references to the removed element and previously saved values of the `end()` iterator.
1684 ///
1685 /// \pre The behavior is undefined unless
1686 /// `position` refers to a `value_type` object in this map.
1687 iterator erase(const_iterator position);
1688 iterator erase(iterator position);
1689
1690 /// Remove from this map the `value_type` object whose key is equivalent
1691 /// the specified `key`, if such an entry exists, and return 1;
1692 /// otherwise, if there is no `value_type` object having an equivalent
1693 /// key, return 0 with no other effect. This method invalidates only
1694 /// iterators and references to the removed element and previously saved
1695 /// values of the `end()` iterator.
1696 size_type erase(const key_type& key);
1697 template <class t_KEY>
1698 typename enable_if<
1699 BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,
1700 t_KEY>::value &&
1701 !is_convertible<BSLS_COMPILERFEATURES_FORWARD_REF(t_KEY),
1702 iterator>::value &&
1703 !is_convertible<BSLS_COMPILERFEATURES_FORWARD_REF(t_KEY),
1704 const_iterator>::value,
1705 size_type>::type erase(BSLS_COMPILERFEATURES_FORWARD_REF(t_KEY) key)
1706 {
1707 // Implemented inline due to Sun CC compilation error.
1708 iterator it = this->find(key);
1709 if (it == end()) {
1710 return 0; // RETURN
1711 }
1712 erase(it);
1713 return 1;
1714 }
1715
1716 /// Remove from this map the `value_type` objects starting at the
1717 /// specified `first` position up to, but including the specified `last`
1718 /// position, and return `last`. This method invalidates only
1719 /// iterators and references to the removed element and previously saved values of the `end()` iterator.
1720 ///
1721 /// \pre The behavior is undefined unless
1722 /// `first` and `last` either refer to elements in this map or are the
1723 /// `end` iterator, and the `first` position is at or before the `last`
1724 /// position in the ordered sequence provided by this container.
1725 iterator erase(const_iterator first, const_iterator last);
1726
1727 void swap(map& other) BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(
1728 AllocatorTraits::is_always_equal::value &&
1729 bsl::is_nothrow_swappable<COMPARATOR>::value);
1730 // Exchange the value and comparator of this object with those of the
1731 // specified 'other' object; also exchange the allocator of this object
1732 // with that of 'other' if the (template parameter) type 'ALLOCATOR'
1733 // has the @ref propagate_on_container_swap trait, and do not modify
1734 // either allocator otherwise. This method provides the no-throw
1735 // exception-safety guarantee if and only if the (template parameter)
1736 // type 'COMPARATOR' provides a no-throw swap operation, and provides
1737 // the basic exception-safety guarantee otherwise; if an exception is
1738 // thrown, both objects are left in valid but unspecified states. This
1739 // operation has 'O[1]' complexity if either this object was created
1740 // with the same allocator as 'other' or 'ALLOCATOR' has the
1741 // @ref propagate_on_container_swap trait; otherwise, it has 'O[n + m]'
1742 // complexity, where 'n' and 'm' are the number of elements in this
1743 // object and 'other', respectively. Note that this method's support
1744 // for swapping objects created with different allocators when
1745 // 'ALLOCATOR' does not have the @ref propagate_on_container_swap trait is
1746 // a departure from the C++ Standard.
1747
1748#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
1749 /// If a key equivalent to the specified `key` already exists in this
1750 /// map, return a pair containing an iterator referring to the existing
1751 /// item and `false`. Otherwise, insert into this map a newly-created
1752 /// entry constructed from `key` and the specified `args`, and return a
1753 /// pair containing an iterator referring to the newly-created entry and
1754 /// `true`. This method requires that the (template parameter) types
1755 /// `KEY` and `VALUE` are `emplace-constructible` from `key` and `args`
1756 /// respectively. For C++03, `VALUE` must also be `copy-constructible`.
1757 template <class... Args>
1758 pair<iterator, bool> try_emplace(const KEY& key, Args&&... args);
1759 template <class... Args>
1760 pair<iterator, bool> try_emplace(BloombergLP::bslmf::MovableRef<KEY> key,
1761 Args&&... args);
1762 template<class LOOKUP_KEY, class... Args>
1763 typename bsl::enable_if<
1764 BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,
1765 LOOKUP_KEY>::value &&
1766 !bsl::is_convertible<LOOKUP_KEY&&, const_iterator>::value &&
1767 !bsl::is_convertible<LOOKUP_KEY&&, iterator>::value,
1768 pair<iterator, bool> >::type
1769 try_emplace(LOOKUP_KEY&& key, Args&&... args)
1770 {
1771 // Note: implemented inline due to Sun CC compilation error.
1772
1773 const LOOKUP_KEY& lvalue = key;
1774
1775 int comparisonResult;
1776 BloombergLP::bslalg::RbTreeNode *insertLocation =
1777 BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation(
1778 &comparisonResult,
1779 &d_tree,
1780 this->comparator(),
1781 lvalue);
1782 if (!comparisonResult) {
1783 return pair<iterator, bool>(
1784 iterator(insertLocation), false); // RETURN
1785 }
1786
1787 #if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
1788 BloombergLP::bslalg::RbTreeNode *node =
1789 nodeFactory().emplaceIntoNewNode(
1790 std::piecewise_construct,
1791 std::forward_as_tuple(std::forward<LOOKUP_KEY>(key)),
1792 std::forward_as_tuple(std::forward<Args>(args)...));
1793 #else
1794 BloombergLP::bslalg::RbTreeNode *node =
1795 nodeFactory().emplaceIntoNewNode(
1796 std::forward<LOOKUP_KEY>(key),
1797 mapped_type(std::forward<Args>(args)...));
1798 #endif
1799
1800 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
1801 insertLocation,
1802 comparisonResult < 0,
1803 node);
1804
1805 return pair<iterator, bool>(iterator(node), true);
1806 }
1807
1808 /// If a key equivalent to the specified `key` already exists in this
1809 /// map, return an iterator referring to the existing item. Otherwise,
1810 /// insert into this map a newly-created `value_type` object,
1811 /// constructed from from `key` and the specified `args`, and return an
1812 /// iterator referring to the newly-created entry. Use the specified
1813 /// `hint` as a starting point for checking to see if the key already in
1814 /// the map. This method requires that the (template parameter) types
1815 /// `KEY` and `VALUE` are `emplace-constructible` from `key` and `args`
1816 /// respectively. For C++03, `VALUE` must also be `copy-constructible`.
1817 template<class... Args>
1818 iterator try_emplace(const_iterator hint, const KEY& key, Args&&... args);
1819 template <class... Args>
1820 iterator try_emplace(const_iterator hint,
1821 BloombergLP::bslmf::MovableRef<KEY> key,
1822 Args&&... args);
1823 template<class LOOKUP_KEY, class... Args>
1824 typename bsl::enable_if<
1825 BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,
1826 LOOKUP_KEY>::value,
1827 iterator>::type
1828 try_emplace(const_iterator hint, LOOKUP_KEY&& key, Args&&... args)
1829 {
1830 // Note: implemented inline due to Sun CC compilation error.
1831
1832 const LOOKUP_KEY& lvalue = key;
1833
1834 BloombergLP::bslalg::RbTreeNode *hintNode =
1835 const_cast<BloombergLP::bslalg::RbTreeNode *>(hint.node());
1836
1837 int comparisonResult;
1838 BloombergLP::bslalg::RbTreeNode *insertLocation =
1839 BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation(
1840 &comparisonResult,
1841 &d_tree,
1842 this->comparator(),
1843 lvalue,
1844 hintNode);
1845
1846 if (!comparisonResult) {
1847 return iterator(insertLocation); // RETURN
1848 }
1849
1850 #if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
1851 BloombergLP::bslalg::RbTreeNode *node =
1852 nodeFactory().emplaceIntoNewNode(
1853 std::piecewise_construct,
1854 std::forward_as_tuple(std::forward<LOOKUP_KEY>(key)),
1855 std::forward_as_tuple(std::forward<Args>(args)...));
1856 #else
1857 BloombergLP::bslalg::RbTreeNode *node =
1858 nodeFactory().emplaceIntoNewNode(
1859 std::forward<LOOKUP_KEY>(key),
1860 mapped_type(std::forward<Args>(args)...));
1861 #endif
1862
1863 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
1864 insertLocation,
1865 comparisonResult < 0,
1866 node);
1867
1868 return iterator(node);
1869 }
1870#endif
1871
1872 /// Remove all entries from this map.
1873 /// \note Note that the map is empty after
1874 /// this call, but allocated memory may be retained for future use.
1875 void clear() BSLS_KEYWORD_NOEXCEPT;
1876
1877 // Turn off complaints about necessarily class-defined methods.
1878 // BDE_VERIFY pragma: push
1879 // BDE_VERIFY pragma: -CD01
1880
1881 /// Return an iterator providing modifiable access to the `value_type`
1882 /// object in this map whose key is equivalent to the specified `key`,
1883 /// if such an entry exists, and the past-the-end (`end`) iterator
1884 /// otherwise.
1885 iterator find(const key_type& key)
1886 {
1887 // Note: implemented inline due to Sun CC compilation error.
1888
1889 return iterator(BloombergLP::bslalg::RbTreeUtil::find(
1890 d_tree, this->comparator(), key));
1891 }
1892
1893 /// Return an iterator providing modifiable access to the `value_type`
1894 /// object in this map whose key is equivalent to the specified `key`,
1895 /// if such an entry exists, and the past-the-end (`end`) iterator
1896 /// otherwise.
1897 template <class LOOKUP_KEY>
1898 typename bsl::enable_if<
1899 BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,
1900 LOOKUP_KEY>::value,
1901 iterator>::type
1902 find(const LOOKUP_KEY& key)
1903 {
1904 // Note: implemented inline due to Sun CC compilation error.
1905
1906 return iterator(BloombergLP::bslalg::RbTreeUtil::find(
1907 d_tree, this->comparator(), key));
1908 }
1909
1910 /// Return an iterator providing modifiable access to the first (i.e.,
1911 /// ordered least) `value_type` object in this map whose key is
1912 /// greater-than or equal-to the specified `key`, and the past-the-end
1913 /// iterator if this map does not contain a `value_type` object whose key is greater-than or equal-to `key`.
1914 ///
1915 /// \note Note that this function
1916 /// returns the *first* position before which a `value_type` object
1917 /// having an equivalent key could be inserted into the ordered sequence
1918 /// maintained by this map, while preserving its ordering.
1919 iterator lower_bound(const key_type& key)
1920 {
1921 // Note: implemented inline due to Sun CC compilation error.
1922
1923 return iterator(BloombergLP::bslalg::RbTreeUtil::lowerBound(
1924 d_tree, this->comparator(), key));
1925 }
1926
1927 /// Return an iterator providing modifiable access to the first (i.e.,
1928 /// ordered least) `value_type` object in this map whose key is
1929 /// greater-than or equal-to the specified `key`, and the past-the-end
1930 /// iterator if this map does not contain a `value_type` object whose key is greater-than or equal-to `key`.
1931 ///
1932 /// \note Note that this function
1933 /// returns the *first* position before which a `value_type` object
1934 /// having an equivalent key could be inserted into the ordered sequence
1935 /// maintained by this map, while preserving its ordering.
1936 template <class LOOKUP_KEY>
1937 typename bsl::enable_if<
1938 BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,
1939 LOOKUP_KEY>::value,
1940 iterator>::type
1941 lower_bound(const LOOKUP_KEY& key)
1942 {
1943 // Note: implemented inline due to Sun CC compilation error.
1944
1945 return iterator(BloombergLP::bslalg::RbTreeUtil::lowerBound(
1946 d_tree, this->comparator(), key));
1947 }
1948
1949 /// Return an iterator providing modifiable access to the first (i.e.,
1950 /// ordered least) `value_type` object in this map whose key is greater
1951 /// than the specified `key`, and the past-the-end iterator if this map
1952 /// does not contain a `value_type` object whose key is greater-than `key`.
1953 ///
1954 /// \note Note that this function returns the *last* position before
1955 /// which a `value_type` object having an equivalent key could be
1956 /// inserted into the ordered sequence maintained by this map, while
1957 /// preserving its ordering.
1958 iterator upper_bound(const key_type& key)
1959 {
1960 // Note: implemented inline due to Sun CC compilation error.
1961
1962 return iterator(BloombergLP::bslalg::RbTreeUtil::upperBound(
1963 d_tree, this->comparator(), key));
1964 }
1965
1966 /// Return an iterator providing modifiable access to the first (i.e.,
1967 /// ordered least) `value_type` object in this map whose key is greater
1968 /// than the specified `key`, and the past-the-end iterator if this map
1969 /// does not contain a `value_type` object whose key is greater-than `key`.
1970 ///
1971 /// \note Note that this function returns the *last* position before
1972 /// which a `value_type` object having an equivalent key could be
1973 /// inserted into the ordered sequence maintained by this map, while
1974 /// preserving its ordering.
1975 template <class LOOKUP_KEY>
1976 typename bsl::enable_if<
1977 BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,
1978 LOOKUP_KEY>::value,
1979 iterator>::type
1980 upper_bound(const LOOKUP_KEY& key)
1981 {
1982 // Note: implemented inline due to Sun CC compilation error.
1983
1984 return iterator(BloombergLP::bslalg::RbTreeUtil::upperBound(
1985 d_tree, this->comparator(), key));
1986 }
1987
1988 /// Return a pair of iterators providing modifiable access to the
1989 /// sequence of `value_type` objects in this map whose keys are
1990 /// equivalent to the specified `key`, where the first iterator is
1991 /// positioned at the start of the sequence and the second is positioned
1992 /// one past the end of the sequence. The first returned iterator will
1993 /// be `lower_bound(key)`, the second returned iterator will be
1994 /// `upper_bound(key)`, and, if this map contains no `value_type`
1995 /// objects with an equivalent key, then the two returned iterators will have the same value.
1996 ///
1997 /// \note Note that since a map maintains unique keys,
1998 /// the range will contain at most one element.
1999 pair<iterator, iterator> equal_range(const key_type& key)
2000 {
2001 // Note: implemented inline due to Sun CC compilation error.
2002
2003 iterator startIt = lower_bound(key);
2004 iterator endIt = startIt;
2005 if (endIt != end() && !comparator()(key, *endIt.node())) {
2006 ++endIt;
2007 }
2008 return pair<iterator, iterator>(startIt, endIt);
2009 }
2010
2011 /// Return a pair of iterators providing modifiable access to the
2012 /// sequence of `value_type` objects in this map whose keys are
2013 /// equivalent to the specified `key`, where the first iterator is
2014 /// positioned at the start of the sequence and the second is positioned
2015 /// one past the end of the sequence. The first returned iterator will
2016 /// be `lower_bound(key)`, the second returned iterator will be
2017 /// `upper_bound(key)`, and, if this map contains no `value_type`
2018 /// objects with an equivalent key, then the two returned iterators will have the same value.
2019 ///
2020 /// \note Note that although a map maintains unique
2021 /// keys, the range may contain more than one element, because a
2022 /// transparent comparator may have been supplied that provides a
2023 /// different (but compatible) partitioning of keys for `LOOKUP_KEY` as
2024 /// the comparisons used to order the keys in the map.
2025 template <class LOOKUP_KEY>
2026 typename bsl::enable_if<
2027 BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,
2028 LOOKUP_KEY>::value,
2029 pair<iterator, iterator> >::type
2030 equal_range(const LOOKUP_KEY& key)
2031 {
2032 // Note: implemented inline due to Sun CC compilation error.
2033
2034 iterator startIt = lower_bound(key);
2035 iterator endIt = startIt;
2036 if (endIt != end() && !comparator()(key, *endIt.node())) {
2037 ++endIt;
2038
2039 // Typically, even with a transparent comparator, we expect to find
2040 // either 0 or 1 matching keys. We test for those two common cases
2041 // before performing a logarithmic search via @ref upper_bound to
2042 // determine the end of the range.
2043
2044 if (endIt != end() && !comparator()(key, *endIt.node())) {
2045 endIt = upper_bound(key);
2046 }
2047 }
2048 return pair<iterator, iterator>(startIt, endIt);
2049 }
2050
2051 // BDE_VERIFY pragma: pop
2052
2053 // ACCESSORS
2054
2055 /// Return (a copy of) the allocator used for memory allocation by this
2056 /// map.
2057 allocator_type get_allocator() const BSLS_KEYWORD_NOEXCEPT;
2058
2059 /// Return an iterator providing non-modifiable access to the first
2060 /// `value_type` object in the ordered sequence of `value_type` objects
2061 /// maintained by this map, or the `end` iterator if this map is empty.
2062 const_iterator begin() const BSLS_KEYWORD_NOEXCEPT;
2063
2064 /// Return an iterator providing non-modifiable access to the
2065 /// past-the-end element in the ordered sequence of `value_type`
2066 /// objects maintained by this map.
2067 const_iterator end() const BSLS_KEYWORD_NOEXCEPT;
2068
2069 /// Return a reverse iterator providing non-modifiable access to the
2070 /// last `value_type` object in the ordered sequence of `value_type`
2071 /// objects maintained by this map, or `rend` if this map is empty.
2072 const_reverse_iterator rbegin() const BSLS_KEYWORD_NOEXCEPT;
2073
2074 /// Return a reverse iterator providing non-modifiable access to the
2075 /// prior-to-the-beginning element in the ordered sequence of
2076 /// `value_type` objects maintained by this map.
2077 const_reverse_iterator rend() const BSLS_KEYWORD_NOEXCEPT;
2078
2079 /// Return an iterator providing non-modifiable access to the first
2080 /// `value_type` object in the ordered sequence of `value_type` objects
2081 /// maintained by this map, or the `cend` iterator if this map is empty.
2082 const_iterator cbegin() const BSLS_KEYWORD_NOEXCEPT;
2083
2084 /// Return an iterator providing non-modifiable access to the
2085 /// past-the-end element in the ordered sequence of `value_type` objects
2086 /// maintained by this map.
2087 const_iterator cend() const BSLS_KEYWORD_NOEXCEPT;
2088
2089 /// Return a reverse iterator providing non-modifiable access to the
2090 /// last `value_type` object in the ordered sequence of `value_type`
2091 /// objects maintained by this map, or `crend` if this map is empty.
2092 const_reverse_iterator crbegin() const BSLS_KEYWORD_NOEXCEPT;
2093
2094 /// Return a reverse iterator providing non-modifiable access to the
2095 /// prior-to-the-beginning element in the ordered sequence of
2096 /// `value_type` objects maintained by this map.
2097 const_reverse_iterator crend() const BSLS_KEYWORD_NOEXCEPT;
2098
2099 /// Return `true` if this map contains an element whose key is
2100 /// equivalent to the specified `key`.
2101 bool contains(const key_type &key) const;
2102
2103 /// Return `true` if this map contains an element whose key is
2104 /// equivalent to the specified `key`.
2105 template <class LOOKUP_KEY>
2106 typename bsl::enable_if<
2107 BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,
2108 LOOKUP_KEY>::value,
2109 bool>::type
2110 contains(const LOOKUP_KEY& key) const
2111 {
2112 // Note: implemented inline due to Sun CC compilation error.
2113
2114 return find(key) != end();
2115 }
2116
2117 /// Return `true` if this map contains no elements, and `false`
2118 /// otherwise.
2119 bool empty() const BSLS_KEYWORD_NOEXCEPT;
2120
2121 /// Return the number of elements in this map.
2122 size_type size() const BSLS_KEYWORD_NOEXCEPT;
2123
2124 /// Return a theoretical upper bound on the largest number of elements that this map could possibly hold.
2125 ///
2126 /// \note Note that there is no guarantee
2127 /// that the map can successfully grow to the returned size, or even
2128 /// close to that size without running out of resources.
2129 size_type max_size() const BSLS_KEYWORD_NOEXCEPT;
2130
2131 /// Return a reference providing non-modifiable access to the
2132 /// mapped-value associated with a key that is equivalent to the
2133 /// specified `key`, if such an entry exists; otherwise, throw a `std::out_of_range` exception.
2134 ///
2135 /// \note Note that this method may also throw
2136 /// a different kind of exception if the (user-supplied) comparator
2137 /// throws.
2138 typename add_lvalue_reference<const VALUE>::type at(const key_type& key)
2139 const;
2140
2141 /// Return a reference providing non-modifiable access to the
2142 /// mapped-value associated with a key that is equivalent to the
2143 /// specified `key`, if such an entry exists; otherwise, throw a `std::out_of_range` exception.
2144 ///
2145 /// \note Note that this method may also throw
2146 /// a different kind of exception if the (user-supplied) comparator
2147 /// throws.
2148 template <class LOOKUP_KEY>
2149 typename bsl::enable_if<
2150 BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,
2151 LOOKUP_KEY>::value,
2152 typename add_lvalue_reference<const VALUE>::type>::type
2153 at(const LOOKUP_KEY& key) const {
2154 // Note: implemented inline due to Sun CC compilation error.
2155
2156 const_iterator iter = find(key);
2157 if (iter == end()) {
2158 BloombergLP::bslstl::StdExceptUtil::throwOutOfRange(
2159 "map<...>::at(LOOKUP_KEY) const: invalid key value");
2160 }
2161 return iter->second;
2162 }
2163
2164 /// Return the key-comparison functor (or function pointer) used by this
2165 /// map; if a comparator was supplied at construction, return its value;
2166 /// otherwise, return a default constructed @ref key_compare object.
2167 ///
2168 /// \note Note that this comparator compares objects of type `KEY`, which is the
2169 /// key part of the `value_type` objects contained in this map.
2170 key_compare key_comp() const;
2171
2172 /// Return a functor for comparing two `value_type` objects by comparing their respective keys using `key_comp()`.
2173 ///
2174 /// \note Note that this
2175 /// comparator compares objects of type `value_type` (i.e.,
2176 /// `bsl::pair<const KEY, VALUE>`).
2177 value_compare value_comp() const;
2178
2179 // Turn off complaints about necessarily class-defined methods.
2180 // BDE_VERIFY pragma: push
2181 // BDE_VERIFY pragma: -CD01
2182
2183 /// Return an iterator providing non-modifiable access to the
2184 /// `value_type` object in this map whose key is equivalent to the
2185 /// specified `key`, if such an entry exists, and the past-the-end
2186 /// (`end`) iterator otherwise.
2187 const_iterator find(const key_type& key) const
2188 {
2189 // Note: implemented inline due to Sun CC compilation error.
2190
2191 return const_iterator(BloombergLP::bslalg::RbTreeUtil::find(
2192 d_tree, this->comparator(), key));
2193 }
2194
2195 /// Return an iterator providing non-modifiable access to the
2196 /// `value_type` object in this map whose key is equivalent to the
2197 /// specified `key`, if such an entry exists, and the past-the-end
2198 /// (`end`) iterator otherwise.
2199 template <class LOOKUP_KEY>
2200 typename bsl::enable_if<
2201 BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,
2202 LOOKUP_KEY>::value,
2203 const_iterator>::type
2204 find(const LOOKUP_KEY& key) const
2205 {
2206 // Note: implemented inline due to Sun CC compilation error.
2207
2208 return const_iterator(BloombergLP::bslalg::RbTreeUtil::find(
2209 d_tree, this->comparator(), key));
2210 }
2211
2212 /// Return the number of `value_type` objects within this map whose keys are equivalent to the specified `key`.
2213 ///
2214 /// \note Note that since a map
2215 /// maintains unique keys, the returned value will be either 0 or 1.
2216 size_type count(const key_type& key) const
2217 {
2218 // Note: implemented inline due to Sun CC compilation error.
2219
2220 return (find(key) != end()) ? 1 : 0;
2221 }
2222
2223 /// Return the number of `value_type` objects within this map whose keys are equivalent to the specified `key`.
2224 ///
2225 /// \note Note that although a map
2226 /// maintains unique keys, the returned value can be other than 0 or 1,
2227 /// because a transparent comparator may have been supplied that
2228 /// provides a different (but compatible) partitioning of keys for
2229 /// `LOOKUP_KEY` as the comparisons used to order the keys in the map.
2230 template <class LOOKUP_KEY>
2231 typename bsl::enable_if<
2232 BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,
2233 LOOKUP_KEY>::value,
2234 size_type>::type
2235 count(const LOOKUP_KEY& key) const
2236 {
2237 // Note: implemented inline due to Sun CC compilation error.
2238
2239 int count = 0;
2240 const_iterator it = lower_bound(key);
2241
2242 while (it != end() && !comparator()(key, *it.node())) {
2243 ++it;
2244 ++count;
2245 }
2246 return count;
2247 }
2248
2249 /// Return an iterator providing non-modifiable access to the first
2250 /// (i.e., ordered least) `value_type` object in this map whose key is
2251 /// greater-than or equal-to the specified `key`, and the past-the-end
2252 /// iterator if this map does not contain a `value_type` object whose key is greater-than or equal-to `key`.
2253 ///
2254 /// \note Note that this function
2255 /// returns the *first* position before which a `value_type` object
2256 /// having an equivalent key could be inserted into the ordered sequence
2257 /// maintained by this map, while preserving its ordering.
2258 const_iterator lower_bound(const key_type& key) const
2259 {
2260 // Note: implemented inline due to Sun CC compilation error.
2261
2262 return iterator(BloombergLP::bslalg::RbTreeUtil::lowerBound(
2263 d_tree, this->comparator(), key));
2264 }
2265
2266 /// Return an iterator providing non-modifiable access to the first
2267 /// (i.e., ordered least) `value_type` object in this map whose key is
2268 /// greater-than or equal-to the specified `key`, and the past-the-end
2269 /// iterator if this map does not contain a `value_type` object whose key is greater-than or equal-to `key`.
2270 ///
2271 /// \note Note that this function
2272 /// returns the *first* position before which a `value_type` object
2273 /// having an equivalent key could be inserted into the ordered sequence
2274 /// maintained by this map, while preserving its ordering.
2275 template <class LOOKUP_KEY>
2276 typename bsl::enable_if<
2277 BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,
2278 LOOKUP_KEY>::value,
2279 const_iterator>::type
2280 lower_bound(const LOOKUP_KEY& key) const
2281 {
2282 // Note: implemented inline due to Sun CC compilation error.
2283
2284 return const_iterator(
2285 BloombergLP::bslalg::RbTreeUtil::lowerBound(d_tree,
2286 this->comparator(),
2287 key));
2288 }
2289
2290 /// Return an iterator providing non-modifiable access to the first
2291 /// (i.e., ordered least) `value_type` object in this map whose key is
2292 /// greater than the specified `key`, and the past-the-end iterator if
2293 /// this map does not contain a `value_type` object whose key is greater-than `key`.
2294 ///
2295 /// \note Note that this function returns the *last*
2296 /// position before which a `value_type` object having an equivalent key
2297 /// could be inserted into the ordered sequence maintained by this map,
2298 /// while preserving its ordering.
2299 const_iterator upper_bound(const key_type& key) const
2300 {
2301 // Note: implemented inline due to Sun CC compilation error.
2302
2303 return const_iterator(BloombergLP::bslalg::RbTreeUtil::upperBound(
2304 d_tree, this->comparator(), key));
2305 }
2306
2307 /// Return an iterator providing non-modifiable access to the first
2308 /// (i.e., ordered least) `value_type` object in this map whose key is
2309 /// greater than the specified `key`, and the past-the-end iterator if
2310 /// this map does not contain a `value_type` object whose key is greater-than `key`.
2311 ///
2312 /// \note Note that this function returns the *last*
2313 /// position before which a `value_type` object having an equivalent key
2314 /// could be inserted into the ordered sequence maintained by this map,
2315 /// while preserving its ordering.
2316 template <class LOOKUP_KEY>
2317 typename bsl::enable_if<
2318 BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,
2319 LOOKUP_KEY>::value,
2320 const_iterator>::type
2321 upper_bound(const LOOKUP_KEY& key) const
2322 {
2323 // Note: implemented inline due to Sun CC compilation error.
2324
2325 return const_iterator(BloombergLP::bslalg::RbTreeUtil::upperBound(
2326 d_tree, this->comparator(), key));
2327 }
2328
2329 /// Return a pair of iterators providing non-modifiable access to the
2330 /// sequence of `value_type` objects in this map whose keys are
2331 /// equivalent to the specified `key`, where the first iterator is
2332 /// positioned at the start of the sequence and the second iterator is
2333 /// positioned one past the end of the sequence. The first returned
2334 /// iterator will be `lower_bound(key)`, the second returned iterator
2335 /// will be `upper_bound(key)`, and, if this map contains no
2336 /// `value_type` objects having keys equivalent to `key`, then the two returned iterators will have the same value.
2337 ///
2338 /// \note Note that since a map
2339 /// maintains unique keys, the range will contain at most one element.
2340 pair<const_iterator, const_iterator> equal_range(const key_type& key) const
2341 {
2342 // Note: implemented inline due to Sun CC compilation error.
2343
2344 const_iterator startIt = lower_bound(key);
2345 const_iterator endIt = startIt;
2346 if (endIt != end() && !comparator()(key, *endIt.node())) {
2347 ++endIt;
2348 }
2349 return pair<const_iterator, const_iterator>(startIt, endIt);
2350 }
2351
2352 /// Return a pair of iterators providing non-modifiable access to the
2353 /// sequence of `value_type` objects in this map whose keys are
2354 /// equivalent to the specified `key`, where the first iterator is
2355 /// positioned at the start of the sequence and the second iterator is
2356 /// positioned one past the end of the sequence. The first returned
2357 /// iterator will be `lower_bound(key)`, the second returned iterator
2358 /// will be `upper_bound(key)`, and, if this map contains no
2359 /// `value_type` objects having keys equivalent to `key`, then the two returned iterators will have the same value.
2360 ///
2361 /// \note Note that although a
2362 /// map maintains unique keys, the range may contain more than one
2363 /// element, because a transparent comparator may have been supplied
2364 /// that provides a different (but compatible) partitioning of keys for
2365 /// `LOOKUP_KEY` as the comparisons used to order the keys in the map.
2366 template <class LOOKUP_KEY>
2367 typename bsl::enable_if<
2368 BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,
2369 LOOKUP_KEY>::value,
2370 pair<const_iterator, const_iterator> >::type
2371 equal_range(const LOOKUP_KEY& key) const
2372 {
2373 // Note: implemented inline due to Sun CC compilation error.
2374
2375 const_iterator startIt = lower_bound(key);
2376 const_iterator endIt = startIt;
2377 if (endIt != end() && !comparator()(key, *endIt.node())) {
2378 ++endIt;
2379
2380 // Typically, even with a transparent comparator, we expect to find
2381 // either 0 or 1 matching keys. We test for those two common cases
2382 // before performing a logarithmic search via @ref upper_bound to
2383 // determine the end of the range.
2384
2385 if (endIt != end() && !comparator()(key, *endIt.node())) {
2386 endIt = upper_bound(key);
2387 }
2388 }
2389 return pair<const_iterator, const_iterator>(startIt, endIt);
2390 }
2391
2392 // BDE_VERIFY pragma: pop
2393};
2394
2395#ifdef BSLS_COMPILERFEATURES_SUPPORT_CTAD
2396// CLASS TEMPLATE DEDUCTION GUIDES
2397
2398/// Deduce the template parameters `KEY` and `VALUE` from the `value_type`
2399/// of the iterators supplied to the constructor of `map`. Deduce the
2400/// template parameters `COMPARATOR` and `ALLOCATOR` from the other
2401/// parameters passed to the constructor. This deduction guide does not
2402/// participate unless the supplied allocator meets the requirements of a
2403/// standard allocator.
2404template <
2405 class INPUT_ITERATOR,
2406 class KEY = BloombergLP::bslstl::IteratorUtil::IterKey_t<INPUT_ITERATOR>,
2407 class VALUE =
2408 BloombergLP::bslstl::IteratorUtil::IterMapped_t<INPUT_ITERATOR>,
2409 class COMPARATOR = std::less<KEY>,
2410 class ALLOCATOR = bsl::allocator<
2411 BloombergLP::bslstl::IteratorUtil::IterToAlloc_t<INPUT_ITERATOR>>,
2412 class = bsl::enable_if_t<!bsl::IsStdAllocator_v<COMPARATOR>>,
2413 class = bsl::enable_if_t<bsl::IsStdAllocator_v<ALLOCATOR>>
2414 >
2415map(INPUT_ITERATOR,
2416 INPUT_ITERATOR,
2417 COMPARATOR = COMPARATOR(),
2418 ALLOCATOR = ALLOCATOR())
2419-> map<KEY, VALUE, COMPARATOR, ALLOCATOR>;
2420
2421/// Deduce the template parameters `KEY` and `VALUE` from the `value_type`
2422/// of the iterators supplied to the constructor of `map`. Deduce the
2423/// template parameter `COMPARATOR` from the other parameter passed to the
2424/// constructor. This deduction guide does not participate unless the
2425/// supplied allocator is convertible to
2426/// `bsl::allocator<bsl::pair<const KEY, VALUE>>`.
2427template <
2428 class INPUT_ITERATOR,
2429 class COMPARATOR,
2430 class ALLOC,
2431 class KEY = BloombergLP::bslstl::IteratorUtil::IterKey_t<INPUT_ITERATOR>,
2432 class VALUE =
2433 BloombergLP::bslstl::IteratorUtil::IterMapped_t<INPUT_ITERATOR>,
2434 class DEFAULT_ALLOCATOR = bsl::allocator<pair<const KEY, VALUE>>,
2435 class = bsl::enable_if_t<bsl::is_convertible_v<ALLOC *, DEFAULT_ALLOCATOR>>
2436 >
2437map(INPUT_ITERATOR, INPUT_ITERATOR, COMPARATOR, ALLOC *)
2438-> map<KEY, VALUE, COMPARATOR>;
2439
2440/// Deduce the template parameters `KEY` and `VALUE` from the `value_type`
2441/// of the iterators supplied to the constructor of `map`. This deduction
2442/// guide does not participate unless the supplied allocator meets the
2443/// requirements of a standard allocator.
2444template <
2445 class INPUT_ITERATOR,
2446 class ALLOCATOR,
2447 class KEY = BloombergLP::bslstl::IteratorUtil::IterKey_t<INPUT_ITERATOR>,
2448 class VALUE =
2449 BloombergLP::bslstl::IteratorUtil::IterMapped_t<INPUT_ITERATOR>,
2450 class = bsl::enable_if_t<bsl::IsStdAllocator_v<ALLOCATOR>>
2451 >
2452map(INPUT_ITERATOR, INPUT_ITERATOR, ALLOCATOR)
2453-> map<KEY, VALUE, std::less<KEY>, ALLOCATOR>;
2454
2455/// Deduce the template parameters `KEY` and `VALUE` from the `value_type`
2456/// of the iterators supplied to the constructor of `map`. This deduction
2457/// guide does not participate unless the supplied allocator is convertible
2458/// to `bsl::allocator<bsl::pair<const KEY, VALUE>>`.
2459template <
2460 class INPUT_ITERATOR,
2461 class ALLOC,
2462 class KEY = BloombergLP::bslstl::IteratorUtil::IterKey_t<INPUT_ITERATOR>,
2463 class VALUE =
2464 BloombergLP::bslstl::IteratorUtil::IterMapped_t<INPUT_ITERATOR>,
2465 class DEFAULT_ALLOCATOR = bsl::allocator<pair<const KEY, VALUE>>,
2466 class = bsl::enable_if_t<bsl::is_convertible_v<ALLOC *, DEFAULT_ALLOCATOR>>
2467 >
2468map(INPUT_ITERATOR, INPUT_ITERATOR, ALLOC *)
2469-> map<KEY, VALUE>;
2470
2471/// Deduce the template parameters `KEY` and `VALUE` from the `value_type`
2472/// of the initializer_list supplied to the constructor of `map`. Deduce
2473/// the template parameters `COMPARATOR` and `ALLOCATOR` from the other
2474/// parameters passed to the constructor. This deduction guide does not
2475/// participate unless the supplied allocator meets the requirements of a
2476/// standard allocator.
2477template <
2478 class KEY,
2479 class VALUE,
2480 class COMPARATOR = std::less<KEY>,
2481 class ALLOCATOR = bsl::allocator<bsl::pair<const KEY, VALUE>>,
2482 class = bsl::enable_if_t<!bsl::IsStdAllocator_v<COMPARATOR>>,
2483 class = bsl::enable_if_t<bsl::IsStdAllocator_v<ALLOCATOR>>
2484 >
2485map(std::initializer_list<pair<const KEY, VALUE>>,
2486 COMPARATOR = COMPARATOR(),
2487 ALLOCATOR = ALLOCATOR())
2488-> map<KEY, VALUE, COMPARATOR, ALLOCATOR>;
2489
2490/// Deduce the template parameters `KEY` and `VALUE` from the `value_type`
2491/// of the initializer_list supplied to the constructor of `map`. Deduce
2492/// the template parameter `COMPARATOR` from the other parameters passed to
2493/// the constructor. This deduction guide does not participate unless the
2494/// supplied allocator is convertible to
2495/// `bsl::allocator<bsl::pair<const KEY, VALUE>>`.
2496template <
2497 class KEY,
2498 class VALUE,
2499 class COMPARATOR,
2500 class ALLOC,
2501 class DEFAULT_ALLOCATOR = bsl::allocator<bsl::pair<const KEY, VALUE>>,
2502 class = bsl::enable_if_t<bsl::is_convertible_v<ALLOC *, DEFAULT_ALLOCATOR>>
2503 >
2504map(std::initializer_list<pair<const KEY, VALUE>>, COMPARATOR, ALLOC *)
2505-> map<KEY, VALUE, COMPARATOR>;
2506
2507/// Deduce the template parameters `KEY` and `VALUE` from the `value_type`
2508/// of the initializer_list supplied to the constructor of `map`. Deduce
2509/// the template parameter `ALLOCATOR` from the other parameter passed to
2510/// the constructor. This deduction guide does not participate unless the
2511/// supplied allocator meets the requirements of a standard allocator.
2512template <
2513 class KEY,
2514 class VALUE,
2515 class ALLOCATOR,
2516 class = bsl::enable_if_t<bsl::IsStdAllocator_v<ALLOCATOR>>
2517 >
2518map(std::initializer_list<pair<const KEY, VALUE>>, ALLOCATOR)
2519-> map<KEY, VALUE, std::less<KEY>, ALLOCATOR>;
2520
2521/// Deduce the template parameters `KEY` and `VALUE` from the `value_type`
2522/// of the initializer_list supplied to the constructor of `map`. This
2523/// deduction guide does not participate unless the supplied allocator is
2524/// convertible to `bsl::allocator<bsl::pair<const KEY, VALUE>>`.
2525template <
2526 class KEY,
2527 class VALUE,
2528 class ALLOC,
2529 class DEFAULT_ALLOCATOR = bsl::allocator<bsl::pair<const KEY, VALUE>>,
2530 class = bsl::enable_if_t<bsl::is_convertible_v<ALLOC *, DEFAULT_ALLOCATOR>>
2531 >
2532map(std::initializer_list<pair<const KEY, VALUE>>, ALLOC *)
2533-> map<KEY, VALUE>;
2534#endif
2535
2536// FREE OPERATORS
2537
2538/// Return `true` if the specified `lhs` and `rhs` objects have the same
2539/// value, and `false` otherwise. Two `map` objects `lhs` and `rhs` have
2540/// the same value if they have the same number of key-value pairs, and each
2541/// element in the ordered sequence of key-value pairs of `lhs` has the same
2542/// value as the corresponding element in the ordered sequence of key-value
2543/// pairs of `rhs`. This method requires that the (template parameter)
2544/// types `KEY` and `VALUE` both be `equality-comparable` (see {Requirements
2545/// on `KEY` and `VALUE`}).
2546template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2547bool operator==(const map<KEY, VALUE, COMPARATOR, ALLOCATOR>& lhs,
2548 const map<KEY, VALUE, COMPARATOR, ALLOCATOR>& rhs);
2549
2550#ifndef BSLS_COMPILERFEATURES_SUPPORT_THREE_WAY_COMPARISON
2551template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2552bool operator!=(const map<KEY, VALUE, COMPARATOR, ALLOCATOR>& lhs,
2553 const map<KEY, VALUE, COMPARATOR, ALLOCATOR>& rhs);
2554 // Return 'true' if the specified 'lhs' and 'rhs' objects do not have the
2555 // same value, and 'false' otherwise. Two 'map' objects 'lhs' and 'rhs' do
2556 // not have the same value if they do not have the same number of key-value
2557 // pairs, or some element in the ordered sequence of key-value pairs of
2558 // 'lhs' does not have the same value as the corresponding element in the
2559 // ordered sequence of key-value pairs of 'rhs'. This method requires that
2560 // the (template parameter) types 'KEY' and 'VALUE' both be
2561 // 'equality-comparable' (see {Requirements on 'KEY' and 'VALUE'}).
2562#endif
2563
2564#ifdef BSLALG_SYNTHTHREEWAYUTIL_AVAILABLE
2565
2566/// Perform a lexicographic three-way comparison of the specified `lhs` and
2567/// the specified `rhs` maps by using the comparison operators of
2568/// `bsl::pair<const KEY, VALUE>` on each element; return the result of that
2569/// comparison.
2570template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2571BloombergLP::bslalg::SynthThreeWayUtil::Result<pair<const KEY, VALUE>>
2572operator<=>(const map<KEY, VALUE, COMPARATOR, ALLOCATOR>& lhs,
2573 const map<KEY, VALUE, COMPARATOR, ALLOCATOR>& rhs);
2574
2575#else
2576
2577template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2578bool operator<(const map<KEY, VALUE, COMPARATOR, ALLOCATOR>& lhs,
2579 const map<KEY, VALUE, COMPARATOR, ALLOCATOR>& rhs);
2580 // Return 'true' if the value of the specified 'lhs' map is
2581 // lexicographically less than that of the specified 'rhs' map, and 'false'
2582 // otherwise. Given iterators 'i' and 'j' over the respective sequences
2583 // '[lhs.begin() .. lhs.end())' and '[rhs.begin() .. rhs.end())', the value
2584 // of map 'lhs' is lexicographically less than that of map 'rhs' if
2585 // 'true == *i < *j' for the first pair of corresponding iterator positions
2586 // where '*i < *j' and '*j < *i' are not both 'false'. If no such
2587 // corresponding iterator position exists, the value of 'lhs' is
2588 // lexicographically less than that of 'rhs' if 'lhs.size() < rhs.size()'.
2589 // This method requires that 'operator<', inducing a total order, be
2590 // defined for 'value_type'.
2591
2592template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2593bool operator>(const map<KEY, VALUE, COMPARATOR, ALLOCATOR>& lhs,
2594 const map<KEY, VALUE, COMPARATOR, ALLOCATOR>& rhs);
2595 // Return 'true' if the value of the specified 'lhs' map is
2596 // lexicographically greater than that of the specified 'rhs' map, and
2597 // 'false' otherwise. The value of map 'lhs' is lexicographically greater
2598 // than that of map 'rhs' if 'rhs' is lexicographically less than 'lhs'
2599 // (see 'operator<'). This method requires that 'operator<', inducing a
2600 // total order, be defined for 'value_type'. Note that this operator
2601 // returns 'rhs < lhs'.
2602
2603template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2604bool operator<=(const map<KEY, VALUE, COMPARATOR, ALLOCATOR>& lhs,
2605 const map<KEY, VALUE, COMPARATOR, ALLOCATOR>& rhs);
2606 // Return 'true' if the value of the specified 'lhs' map is
2607 // lexicographically less than or equal to that of the specified 'rhs' map,
2608 // and 'false' otherwise. The value of map 'lhs' is lexicographically less
2609 // than or equal to that of map 'rhs' if 'rhs' is not lexicographically
2610 // less than 'lhs' (see 'operator<'). This method requires that
2611 // 'operator<', inducing a total order, be defined for 'value_type'. Note
2612 // that this operator returns '!(rhs < lhs)'.
2613
2614template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2615bool operator>=(const map<KEY, VALUE, COMPARATOR, ALLOCATOR>& lhs,
2616 const map<KEY, VALUE, COMPARATOR, ALLOCATOR>& rhs);
2617 // Return 'true' if the value of the specified 'lhs' map is
2618 // lexicographically greater than or equal to that of the specified 'rhs'
2619 // map, and 'false' otherwise. The value of map 'lhs' is lexicographically
2620 // greater than or equal to that of map 'rhs' if 'lhs' is not
2621 // lexicographically less than 'rhs' (see 'operator<'). This method
2622 // requires that 'operator<', inducing a total order, be defined for
2623 // 'value_type'. Note that this operator returns '!(lhs < rhs)'.
2624
2625#endif // BSLALG_SYNTHTHREEWAYUTIL_AVAILABLE
2626
2627// FREE FUNCTIONS
2628
2629/// Erase all the elements in the specified map `m` that satisfy the
2630/// specified predicate `predicate`. Return the number of elements erased.
2631template <class KEY,
2632 class VALUE,
2633 class COMPARATOR,
2634 class ALLOCATOR,
2635 class PREDICATE>
2636typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::size_type
2637erase_if(map<KEY, VALUE, COMPARATOR, ALLOCATOR>& m, PREDICATE predicate);
2638
2639/// Exchange the value and comparator of the specified `a` object with those
2640/// of the specified `b` object; also exchange the allocator of `a` with
2641/// that of `b` if the (template parameter) type `ALLOCATOR` has the
2642/// @ref propagate_on_container_swap trait, and do not modify either allocator
2643/// otherwise. This function provides the no-throw exception-safety
2644/// guarantee if and only if the (template parameter) type `COMPARATOR`
2645/// provides a no-throw swap operation, and provides the basic
2646/// exception-safety guarantee otherwise; if an exception is thrown, both
2647/// objects are left in valid but unspecified states. This operation has
2648/// `O[1]` complexity if either `a` was created with the same allocator as
2649/// `b` or `ALLOCATOR` has the @ref propagate_on_container_swap trait;
2650/// otherwise, it has `O[n + m]` complexity, where `n` and `m` are the number of elements in `a` and `b`, respectively.
2651///
2652/// \note Note that this
2653/// function's support for swapping objects created with different
2654/// allocators when `ALLOCATOR` does not have the
2655/// @ref propagate_on_container_swap trait is a departure from the C++
2656/// Standard.
2657template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2658void swap(map<KEY, VALUE, COMPARATOR, ALLOCATOR>& a,
2659 map<KEY, VALUE, COMPARATOR, ALLOCATOR>& b)
2660 BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(false);
2661
2662// ============================================================================
2663// INLINE FUNCTION DEFINITIONS
2664// ============================================================================
2665
2666 // -----------------
2667 // class DataWrapper
2668 // -----------------
2669
2670// CREATORS
2671template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2672inline
2673map<KEY, VALUE, COMPARATOR, ALLOCATOR>::DataWrapper::DataWrapper(
2674 const COMPARATOR& comparator,
2675 const ALLOCATOR& basicAllocator)
2676: ::bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR>::Comparator(comparator)
2677, d_pool(basicAllocator)
2678{
2679}
2680
2681template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2682inline
2683map<KEY, VALUE, COMPARATOR, ALLOCATOR>::DataWrapper::DataWrapper(
2684 BloombergLP::bslmf::MovableRef<DataWrapper> original)
2685: ::bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR>::Comparator(
2686 MoveUtil::access(original).keyComparator())
2687, d_pool(MoveUtil::move(MoveUtil::access(original).d_pool))
2688{
2689}
2690
2691template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2692inline
2693typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::NodeFactory&
2694map<KEY, VALUE, COMPARATOR, ALLOCATOR>::DataWrapper::nodeFactory()
2695{
2696 return d_pool;
2697}
2698
2699// ACCESSORS
2700template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2701inline
2702const typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::NodeFactory&
2703map<KEY, VALUE, COMPARATOR, ALLOCATOR>::DataWrapper::nodeFactory() const
2704{
2705 return d_pool;
2706}
2707
2708 // ------------------------
2709 // class map::value_compare
2710 // ------------------------
2711
2712// CREATORS
2713template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2714inline
2715map<KEY, VALUE, COMPARATOR, ALLOCATOR>::value_compare::value_compare(
2716 COMPARATOR comparator)
2717: comp(comparator)
2718{
2719}
2720
2721// ACCESSORS
2722template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2723inline
2724bool map<KEY, VALUE, COMPARATOR, ALLOCATOR>::value_compare::operator()(
2725 const value_type& x,
2726 const value_type& y) const
2727{
2728 return comp(x.first, y.first);
2729}
2730
2731 // ---------
2732 // class map
2733 // ---------
2734
2735// PRIVATE CLASS METHODS
2736template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2737inline
2738typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::Node *
2739map<KEY, VALUE, COMPARATOR, ALLOCATOR>::toNode(
2740 BloombergLP::bslalg::RbTreeNode *node)
2741{
2742 return static_cast<Node *>(node);
2743}
2744
2745template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2746inline
2747const typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::Node *
2748map<KEY, VALUE, COMPARATOR, ALLOCATOR>::toNode(
2749 const BloombergLP::bslalg::RbTreeNode *node)
2750{
2751 return static_cast<const Node *>(node);
2752}
2753
2754// PRIVATE MANIPULATORS
2755template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2756inline
2757typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::NodeFactory&
2758map<KEY, VALUE, COMPARATOR, ALLOCATOR>::nodeFactory()
2759{
2760 return d_compAndAlloc.nodeFactory();
2761}
2762
2763template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2764inline
2765typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::Comparator&
2766map<KEY, VALUE, COMPARATOR, ALLOCATOR>::comparator()
2767{
2768 return d_compAndAlloc;
2769}
2770
2771template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2772inline
2773void map<KEY, VALUE, COMPARATOR, ALLOCATOR>::quickSwapExchangeAllocators(
2774 map& other)
2775{
2776 BloombergLP::bslalg::RbTreeUtil::swap(&d_tree, &other.d_tree);
2777 nodeFactory().swapExchangeAllocators(other.nodeFactory());
2778
2779 // 'DataWrapper' contains a 'NodeFactory' object and inherits from
2780 // 'Comparator'. If the empty-base-class optimization has been applied to
2781 // 'Comparator', then we must not call 'swap' on it because
2782 // 'sizeof(Comparator) > 0' and, therefore, we will incorrectly swap bytes
2783 // of the 'NodeFactory' members!
2784
2785 if (sizeof(NodeFactory) != sizeof(DataWrapper)) {
2786 comparator().swap(other.comparator());
2787 }
2788}
2789
2790template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2791inline
2792void map<KEY, VALUE, COMPARATOR, ALLOCATOR>::quickSwapRetainAllocators(
2793 map& other)
2794{
2795 BloombergLP::bslalg::RbTreeUtil::swap(&d_tree, &other.d_tree);
2796 nodeFactory().swapRetainAllocators(other.nodeFactory());
2797
2798 // See 'quickSwapExchangeAllocators' (above).
2799
2800 if (sizeof(NodeFactory) != sizeof(DataWrapper)) {
2801 comparator().swap(other.comparator());
2802 }
2803}
2804
2805template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2806template <class INPUT_ITERATOR, class SENTINEL>
2807inline
2808void
2809map<KEY, VALUE, COMPARATOR, ALLOCATOR>::constructFromRange(
2810 INPUT_ITERATOR first,
2811 SENTINEL last)
2812{
2813 if (first == last) {
2814 return; // RETURN
2815 }
2816
2817 if BSLS_KEYWORD_CONSTEXPR_CPP17 (
2818 BloombergLP::bslstl::IteratorUtil::
2819 canCalculateInsertDistance<INPUT_ITERATOR, SENTINEL>()) {
2820 const size_type numElements = static_cast<size_type>(
2821 BloombergLP::bslstl::IteratorUtil::insertDistance(first, last));
2822 nodeFactory().reserveNodes(numElements);
2823 }
2824
2825 BloombergLP::bslalg::RbTreeUtilTreeProctor<NodeFactory> proctor(
2826 &d_tree,
2827 &nodeFactory());
2828
2829 // The following loop guarantees amortized linear time to insert an ordered
2830 // sequence of values (as required by the standard). If the values are
2831 // in sorted order, we are guaranteed the next node can be inserted as the
2832 // right child of the previous node, and can call 'insertAt' without
2833 // 'findUniqueInsertLocation'.
2834
2835 insert(*first);
2836 BloombergLP::bslalg::RbTreeNode *prevNode = d_tree.rootNode();
2837
2838 while (++first != last) {
2839
2840 const value_type& value = *first;
2841 if (this->comparator()(value.first, *prevNode)) {
2842 // The values are not in order, so insert them normally.
2843 insert(value);
2844 insertFromRange(++first, last);
2845 break;
2846 }
2847
2848 if (this->comparator()(*prevNode, value.first)) {
2849 BloombergLP::bslalg::RbTreeNode *node =
2850 nodeFactory().emplaceIntoNewNode(value);
2851 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
2852 prevNode,
2853 false,
2854 node);
2855 prevNode = node;
2856 }
2857 }
2858
2859 proctor.release();
2860}
2861
2862#if defined(BSLS_LIBRARYFEATURES_HAS_CPP20_CONCEPTS) \
2863 && defined(BSLS_LIBRARYFEATURES_HAS_CPP20_RANGES)
2864
2865template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2866template <class INPUT_ITERATOR, class SENTINEL>
2867inline
2868void
2869map<KEY, VALUE, COMPARATOR, ALLOCATOR>::constructFromRange(
2870 INPUT_ITERATOR first,
2871 SENTINEL last,
2872 size_t numElements)
2873
2874{
2875 BSLS_ASSERT_SAFE((
2876 !BloombergLP::bslstl::IteratorUtil
2877 ::canCalculateInsertDistance<INPUT_ITERATOR, SENTINEL>()
2878 || numElements == static_cast<size_type>(
2879 BloombergLP::bslstl::IteratorUtil::insertDistance(first, last))));
2880
2881 if (first == last) {
2882 return; // RETURN
2883 }
2884
2885 if (0 < numElements) {
2886 nodeFactory().reserveNodes(numElements);
2887 }
2888
2889 BloombergLP::bslalg::RbTreeUtilTreeProctor<NodeFactory> proctor(
2890 &d_tree,
2891 &nodeFactory());
2892
2893 // The following loop guarantees amortized linear time to insert an ordered
2894 // sequence of values (as required by the standard). If the values are
2895 // in sorted order, we are guaranteed the next node can be inserted as the
2896 // right child of the previous node, and can call 'insertAt' without
2897 // 'findUniqueInsertLocation'.
2898
2899 insert(*first); --numElements;
2900 BloombergLP::bslalg::RbTreeNode *prevNode = d_tree.rootNode();
2901
2902 while (++first != last) {
2903
2904 const value_type& value = *first;
2905 if (this->comparator()(value.first, *prevNode)) {
2906 // The values are not in order, so insert them normally.
2907 insert(value); --numElements;
2908 insertFromRange(++first, last, numElements);
2909 break;
2910 }
2911
2912 if (this->comparator()(*prevNode, value.first)) {
2913 BloombergLP::bslalg::RbTreeNode *node =
2914 nodeFactory().emplaceIntoNewNode(value);
2915 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
2916 prevNode,
2917 false,
2918 node);
2919 --numElements;
2920 prevNode = node;
2921 }
2922 }
2923
2924 proctor.release();
2925}
2926
2927#endif
2928
2929template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2930template <class INPUT_ITERATOR, class SENTINEL>
2931inline
2932void map<KEY, VALUE, COMPARATOR, ALLOCATOR>::insertFromRange(
2933 INPUT_ITERATOR first,
2934 SENTINEL last)
2935{
2936 ///Implementation Notes
2937 ///--------------------
2938 // First, consume currently held free nodes. Free nodes may be available
2939 // from previous insertions that where skipped due to collisions with
2940 // keys already in the map or from nodes reserved in `constructFromRange`.
2941 //
2942 // If those nodes are insufficient *and* one can calculate the remaining
2943 // number of elements, then reserve exactly that many free nodes. There is
2944 // no more than one call to 'reserveNodes' per invocation of this method,
2945 // hence the use of 'BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY'.
2946 //
2947 // When reserving nodes, we assume the elements remaining to be inserted
2948 // have unique keys that do not duplicate any keys already in the container
2949 // If there are any duplicates, this container will have free nodes on
2950 // return from this method.
2951
2952 while (first != last) {
2953
2954 if (BloombergLP::bslstl::IteratorUtil
2955 ::canCalculateInsertDistance<INPUT_ITERATOR, SENTINEL>()
2956 && BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(
2957 !nodeFactory().hasFreeNodes())) {
2958 const size_type numElements = static_cast<size_type>(
2959 BloombergLP::bslstl::IteratorUtil::insertDistance(first, last));
2960
2961 nodeFactory().reserveNodes(numElements);
2962 }
2963
2964 insert(*first);
2965 ++first;
2966 }
2967}
2968
2969#if defined(BSLS_LIBRARYFEATURES_HAS_CPP20_CONCEPTS) \
2970 && defined(BSLS_LIBRARYFEATURES_HAS_CPP20_RANGES)
2971
2972template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
2973template <class INPUT_ITERATOR, class SENTINEL>
2974inline
2975void map<KEY, VALUE, COMPARATOR, ALLOCATOR>::insertFromRange(
2976 INPUT_ITERATOR first,
2977 SENTINEL last,
2978 size_t numElements)
2979{
2980 BSLS_ASSERT_SAFE((
2981 !BloombergLP::bslstl::IteratorUtil
2982 ::canCalculateInsertDistance<INPUT_ITERATOR, SENTINEL>()
2983 || numElements == static_cast<size_type>(
2984 BloombergLP::bslstl::IteratorUtil::insertDistance(first, last))));
2985
2986 while (first != last) {
2987
2988 if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(
2989 !nodeFactory().hasFreeNodes())) {
2990 nodeFactory().reserveNodes(numElements);
2991 }
2992
2993 insert(*first);
2994 --numElements;
2995 ++first;
2996 }
2997}
2998
2999#endif
3000
3001// PRIVATE ACCESSORS
3002template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3003inline
3004const typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::NodeFactory&
3005map<KEY, VALUE, COMPARATOR, ALLOCATOR>::nodeFactory() const
3006{
3007 return d_compAndAlloc.nodeFactory();
3008}
3009
3010template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3011inline
3012const typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::Comparator&
3013map<KEY, VALUE, COMPARATOR, ALLOCATOR>::comparator() const
3014{
3015 return d_compAndAlloc;
3016}
3017
3018// CREATORS
3019template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3020inline
3021map<KEY, VALUE, COMPARATOR, ALLOCATOR>::map()
3022: d_compAndAlloc(COMPARATOR(), ALLOCATOR())
3023, d_tree()
3024{
3025}
3026
3027template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3028inline
3029map<KEY, VALUE, COMPARATOR, ALLOCATOR>::map(const ALLOCATOR& basicAllocator)
3030: d_compAndAlloc(COMPARATOR(), basicAllocator)
3031, d_tree()
3032{
3033}
3034
3035template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3036inline
3037map<KEY, VALUE, COMPARATOR, ALLOCATOR>::map(const map& original)
3038: d_compAndAlloc(original.comparator().keyComparator(),
3039 AllocatorTraits::select_on_container_copy_construction(
3040 original.nodeFactory().allocator()))
3041, d_tree()
3042{
3043 if (0 < original.size()) {
3044 nodeFactory().reserveNodes(original.size());
3045 BloombergLP::bslalg::RbTreeUtil::copyTree(&d_tree,
3046 original.d_tree,
3047 &nodeFactory());
3048 }
3049}
3050
3051template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3052inline
3053map<KEY, VALUE, COMPARATOR, ALLOCATOR>::map(
3054 BloombergLP::bslmf::MovableRef<map> original)
3055: d_compAndAlloc(MoveUtil::move(MoveUtil::access(original).d_compAndAlloc))
3056, d_tree()
3057{
3058 map& lvalue = original;
3059 BloombergLP::bslalg::RbTreeUtil::swap(&d_tree, &lvalue.d_tree);
3060}
3061
3062template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3063inline
3064map<KEY, VALUE, COMPARATOR, ALLOCATOR>::map(const map& original,
3065 const typename type_identity<ALLOCATOR>::type& basicAllocator)
3066: d_compAndAlloc(original.comparator().keyComparator(), basicAllocator)
3067, d_tree()
3068{
3069 if (0 < original.size()) {
3070 nodeFactory().reserveNodes(original.size());
3071 BloombergLP::bslalg::RbTreeUtil::copyTree(&d_tree,
3072 original.d_tree,
3073 &nodeFactory());
3074 }
3075}
3076
3077template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3078inline
3079map<KEY, VALUE, COMPARATOR, ALLOCATOR>::map(
3080 BloombergLP::bslmf::MovableRef<map> original,
3081 const typename type_identity<ALLOCATOR>::type& basicAllocator)
3082: d_compAndAlloc(MoveUtil::access(original).comparator().keyComparator(),
3083 basicAllocator)
3084, d_tree()
3085{
3086 map& lvalue = original;
3087
3088 if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(
3089 nodeFactory().allocator() == lvalue.nodeFactory().allocator())) {
3090 d_compAndAlloc.nodeFactory().adopt(
3091 MoveUtil::move(lvalue.d_compAndAlloc.nodeFactory()));
3092 BloombergLP::bslalg::RbTreeUtil::swap(&d_tree, &lvalue.d_tree);
3093 }
3094 else if (0 < lvalue.size()) {
3095 nodeFactory().reserveNodes(lvalue.size());
3096 BloombergLP::bslalg::RbTreeUtil::moveTree(&d_tree,
3097 &lvalue.d_tree,
3098 &nodeFactory(),
3099 &lvalue.nodeFactory());
3100 }
3101}
3102
3103template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3104template <class INPUT_ITERATOR>
3105inline
3106map<KEY, VALUE, COMPARATOR, ALLOCATOR>::map(INPUT_ITERATOR first,
3107 INPUT_ITERATOR last,
3108 const COMPARATOR& comparator,
3109 const ALLOCATOR& basicAllocator)
3110: d_compAndAlloc(comparator, basicAllocator)
3111, d_tree()
3112{
3113 constructFromRange(first, last);
3114}
3115
3116template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3117template <class INPUT_ITERATOR>
3118inline
3119map<KEY, VALUE, COMPARATOR, ALLOCATOR>::map(INPUT_ITERATOR first,
3120 INPUT_ITERATOR last,
3121 const ALLOCATOR& basicAllocator)
3122: d_compAndAlloc(COMPARATOR(), basicAllocator)
3123, d_tree()
3124{
3125 map other(first, last, COMPARATOR(), nodeFactory().allocator());
3126 quickSwapRetainAllocators(other);
3127}
3128
3129#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
3130template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3131inline
3132map<KEY, VALUE, COMPARATOR, ALLOCATOR>::map(
3133 std::initializer_list<value_type> values,
3134 const COMPARATOR& comparator,
3135 const ALLOCATOR& basicAllocator)
3136: map(values.begin(), values.end(), comparator, basicAllocator)
3137{
3138}
3139
3140template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3141inline
3142map<KEY, VALUE, COMPARATOR, ALLOCATOR>::map(
3143 std::initializer_list<value_type> values,
3144 const ALLOCATOR& basicAllocator)
3145: map(values.begin(), values.end(), COMPARATOR(), basicAllocator)
3146{
3147}
3148#endif
3149
3150template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3151inline
3156
3157// MANIPULATORS
3158template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3159inline
3160map<KEY, VALUE, COMPARATOR, ALLOCATOR>&
3161map<KEY, VALUE, COMPARATOR, ALLOCATOR>::operator=(const map& rhs)
3162{
3163 if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(this != &rhs)) {
3164 if (AllocatorTraits::propagate_on_container_copy_assignment::value) {
3165 map other(rhs, rhs.nodeFactory().allocator());
3166 quickSwapExchangeAllocators(other);
3167 }
3168 else {
3169 map other(rhs, nodeFactory().allocator());
3170 quickSwapRetainAllocators(other);
3171 }
3172 }
3173 return *this;
3174}
3175
3176template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3177inline
3178map<KEY, VALUE, COMPARATOR, ALLOCATOR>&
3179map<KEY, VALUE, COMPARATOR, ALLOCATOR>::operator=(
3180 BloombergLP::bslmf::MovableRef<map> rhs)
3181 BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(
3182 AllocatorTraits::is_always_equal::value &&
3183 std::is_nothrow_move_assignable<COMPARATOR>::value)
3184{
3185 map& lvalue = rhs;
3186
3187 if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(this != &lvalue)) {
3188 if (nodeFactory().allocator() == lvalue.nodeFactory().allocator()) {
3189 map other(MoveUtil::move(lvalue));
3190 quickSwapRetainAllocators(other);
3191 }
3192 else if (
3193 AllocatorTraits::propagate_on_container_move_assignment::value) {
3194 map other(MoveUtil::move(lvalue));
3195 quickSwapExchangeAllocators(other);
3196 }
3197 else {
3198 map other(MoveUtil::move(lvalue), nodeFactory().allocator());
3199 quickSwapRetainAllocators(other);
3200 }
3201 }
3202 return *this;
3203}
3204
3205#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
3206template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3207inline
3208map<KEY, VALUE, COMPARATOR, ALLOCATOR>&
3209map<KEY, VALUE, COMPARATOR, ALLOCATOR>::operator=(
3210 std::initializer_list<value_type> values)
3211{
3212 clear();
3213 insert(values.begin(), values.end());
3214 return *this;
3215}
3216#endif
3217
3218template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3219inline
3220typename add_lvalue_reference<VALUE>::type
3221map<KEY, VALUE, COMPARATOR, ALLOCATOR>::operator[](const key_type& key)
3222{
3223 iterator iter = lower_bound(key);
3224 if (iter == end() || this->comparator()(key, *iter.node())) {
3225#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
3226 iter = emplace_hint(iter,
3227 std::piecewise_construct,
3228 std::forward_as_tuple(key),
3229 std::forward_as_tuple());
3230#else
3231 BloombergLP::bsls::ObjectBuffer<VALUE> temp; // for default 'VALUE'
3232
3233 ALLOCATOR alloc = nodeFactory().allocator();
3234
3235 AllocatorTraits::construct(alloc, temp.address());
3236
3237 BloombergLP::bslma::DestructorGuard<VALUE> guard(temp.address());
3238
3239 // Unfortunately, in C++03, there are user types where a MovableRef
3240 // will not safely degrade to a lvalue reference when a move
3241 // constructor is not available, so 'move' cannot be used directly on a
3242 // user supplied type. See internal bug report 99039150.
3243 iter = emplace_hint(iter, key, temp.object());
3244#endif
3245 }
3246 return iter->second;
3247}
3248
3249template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3250inline
3251typename add_lvalue_reference<VALUE>::type
3252map<KEY, VALUE, COMPARATOR, ALLOCATOR>::operator[](
3253 BloombergLP::bslmf::MovableRef<key_type> key)
3254{
3255 key_type& lvalue = key;
3256
3257 iterator iter = lower_bound(lvalue);
3258 if (iter == end() || this->comparator()(lvalue, *iter.node())) {
3259#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
3260 iter = emplace_hint(
3261 iter,
3262 std::piecewise_construct,
3263 std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(key_type, key)),
3264 std::forward_as_tuple());
3265#else
3266 BloombergLP::bsls::ObjectBuffer<VALUE> temp; // for default 'VALUE'
3267
3268 ALLOCATOR alloc = nodeFactory().allocator();
3269
3270 AllocatorTraits::construct(alloc, temp.address());
3271
3272 BloombergLP::bslma::DestructorGuard<VALUE> guard(temp.address());
3273
3274 // Unfortunately, in C++03, there are user types where a MovableRef
3275 // will not safely degrade to a lvalue reference when a move
3276 // constructor is not available, so 'move' cannot be used directly on a
3277 // user supplied type. See internal bug report 99039150.
3278 iter = emplace_hint(iter, lvalue, temp.object());
3279#endif
3280 }
3281 return iter->second;
3282}
3283
3284template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3285typename add_lvalue_reference<VALUE>::type
3286map<KEY, VALUE, COMPARATOR, ALLOCATOR>::at(const key_type& key)
3287{
3288 BloombergLP::bslalg::RbTreeNode *node =
3289 BloombergLP::bslalg::RbTreeUtil::find(d_tree, this->comparator(), key);
3290 if (d_tree.sentinel() == node) {
3291 BloombergLP::bslstl::StdExceptUtil::throwOutOfRange(
3292 "map<...>::at(key_type): invalid key value");
3293 }
3294 return toNode(node)->value().second;
3295}
3296
3297template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3298inline
3299typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator
3304
3305template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3306inline
3307typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator
3312
3313template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3314inline
3315typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::reverse_iterator
3320
3321template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3322inline
3323typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::reverse_iterator
3328
3329template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3330inline
3331pair<typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator, bool>
3332map<KEY, VALUE, COMPARATOR, ALLOCATOR>::insert(const value_type& value)
3333{
3334 int comparisonResult;
3335 BloombergLP::bslalg::RbTreeNode *insertLocation =
3336 BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation(
3337 &comparisonResult,
3338 &d_tree,
3339 this->comparator(),
3340 value.first);
3341 if (!comparisonResult) {
3342 return pair<iterator, bool>(iterator(insertLocation), false); // RETURN
3343 }
3344
3345 BloombergLP::bslalg::RbTreeNode *node =
3346 nodeFactory().emplaceIntoNewNode(value);
3347 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
3348 insertLocation,
3349 comparisonResult < 0,
3350 node);
3351 return pair<iterator, bool>(iterator(node), true);
3352}
3353
3354template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3355inline
3356pair<typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator, bool>
3357map<KEY, VALUE, COMPARATOR, ALLOCATOR>::insert(
3358 BloombergLP::bslmf::MovableRef<value_type> value)
3359{
3360 value_type& lvalue = value;
3361
3362 int comparisonResult;
3363 BloombergLP::bslalg::RbTreeNode *insertLocation =
3364 BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation(
3365 &comparisonResult,
3366 &d_tree,
3367 this->comparator(),
3368 lvalue.first);
3369 if (!comparisonResult) {
3370 return pair<iterator, bool>(iterator(insertLocation), false); // RETURN
3371 }
3372
3373 BloombergLP::bslalg::RbTreeNode *node =
3374 nodeFactory().emplaceIntoNewNode(MoveUtil::move(lvalue));
3375 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
3376 insertLocation,
3377 comparisonResult < 0,
3378 node);
3379 return pair<iterator, bool>(iterator(node), true);
3380}
3381
3382template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3383template <class INPUT_ITERATOR>
3384inline
3385void map<KEY, VALUE, COMPARATOR, ALLOCATOR>::insert(INPUT_ITERATOR first,
3386 INPUT_ITERATOR last)
3387{
3388 insertFromRange(first, last);
3389}
3390
3391#if defined(BSLS_PLATFORM_CMP_SUN) && BSLS_PLATFORM_CMP_VERSION < 0x5130
3392template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3393inline
3394void map<KEY, VALUE, COMPARATOR, ALLOCATOR>::insert(const_iterator first,
3395 const_iterator last)
3396{
3397 while (first != last) {
3398 insert(*first);
3399 ++first;
3400 }
3401}
3402#endif
3403
3404template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3405inline
3406typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator
3407map<KEY, VALUE, COMPARATOR, ALLOCATOR>::insert(const_iterator hint,
3408 const value_type& value)
3409{
3410 BloombergLP::bslalg::RbTreeNode *hintNode =
3411 const_cast<BloombergLP::bslalg::RbTreeNode *>(hint.node());
3412 int comparisonResult;
3413 BloombergLP::bslalg::RbTreeNode *insertLocation =
3414 BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation(
3415 &comparisonResult,
3416 &d_tree,
3417 this->comparator(),
3418 value.first,
3419 hintNode);
3420 if (!comparisonResult) {
3421 return iterator(insertLocation); // RETURN
3422 }
3423
3424 BloombergLP::bslalg::RbTreeNode *node =
3425 nodeFactory().emplaceIntoNewNode(value);
3426 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
3427 insertLocation,
3428 comparisonResult < 0,
3429 node);
3430 return iterator(node);
3431}
3432
3433template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3434inline
3435typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator
3436map<KEY, VALUE, COMPARATOR, ALLOCATOR>::insert(
3437 const_iterator hint,
3438 BloombergLP::bslmf::MovableRef<value_type> value)
3439{
3440 value_type& lvalue = value;
3441
3442 BloombergLP::bslalg::RbTreeNode *hintNode =
3443 const_cast<BloombergLP::bslalg::RbTreeNode *>(hint.node());
3444 int comparisonResult;
3445 BloombergLP::bslalg::RbTreeNode *insertLocation =
3446 BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation(
3447 &comparisonResult,
3448 &d_tree,
3449 this->comparator(),
3450 lvalue.first,
3451 hintNode);
3452 if (!comparisonResult) {
3453 return iterator(insertLocation); // RETURN
3454 }
3455
3456 BloombergLP::bslalg::RbTreeNode *node =
3457 nodeFactory().emplaceIntoNewNode(MoveUtil::move(lvalue));
3458
3459 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
3460 insertLocation,
3461 comparisonResult < 0,
3462 node);
3463 return iterator(node);
3464}
3465
3466#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
3467template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3468inline
3469void map<KEY, VALUE, COMPARATOR, ALLOCATOR>::insert(
3470 std::initializer_list<value_type> values)
3471{
3472 insert(values.begin(), values.end());
3473}
3474#endif
3475
3476#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
3477template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3478template <class BDE_OTHER_TYPE>
3479inline
3480pair<typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator, bool>
3481map<KEY, VALUE, COMPARATOR, ALLOCATOR>::insert_or_assign(const key_type& key,
3482 BDE_OTHER_TYPE&& obj)
3483{
3484 int comparisonResult;
3485 BloombergLP::bslalg::RbTreeNode *insertLocation =
3486 BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation(
3487 &comparisonResult,
3488 &d_tree,
3489 this->comparator(),
3490 key);
3491
3492 if (!comparisonResult) { // ASSIGN
3493 iterator(insertLocation)->second =
3494 BSLS_COMPILERFEATURES_FORWARD(BDE_OTHER_TYPE, obj);
3495 return pair<iterator, bool>(iterator(insertLocation), false); // RETURN
3496 }
3497
3498 // INSERT
3499 BloombergLP::bslalg::RbTreeNode *node = nodeFactory().emplaceIntoNewNode(
3500 key, BSLS_COMPILERFEATURES_FORWARD(BDE_OTHER_TYPE, obj));
3501
3502 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
3503 insertLocation,
3504 comparisonResult < 0,
3505 node);
3506
3507 return pair<iterator, bool>(iterator(node), true);
3508}
3509
3510template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3511template <class BDE_OTHER_TYPE>
3512inline
3513typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator
3514map<KEY, VALUE, COMPARATOR, ALLOCATOR>::insert_or_assign(const_iterator hint,
3515 const key_type& key,
3516 BDE_OTHER_TYPE&& obj)
3517{
3518 BloombergLP::bslalg::RbTreeNode *hintNode =
3519 const_cast<BloombergLP::bslalg::RbTreeNode *>(hint.node());
3520 int comparisonResult;
3521 BloombergLP::bslalg::RbTreeNode *insertLocation =
3522 BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation(
3523 &comparisonResult,
3524 &d_tree,
3525 this->comparator(),
3526 key,
3527 hintNode);
3528
3529 if (!comparisonResult) { // ASSIGN
3530 iterator(insertLocation)->second =
3531 BSLS_COMPILERFEATURES_FORWARD(BDE_OTHER_TYPE, obj);
3532 return iterator(insertLocation); // RETURN
3533 }
3534
3535 // INSERT
3536 BloombergLP::bslalg::RbTreeNode *node = nodeFactory().emplaceIntoNewNode(
3537 key, BSLS_COMPILERFEATURES_FORWARD(BDE_OTHER_TYPE, obj));
3538
3539 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
3540 insertLocation,
3541 comparisonResult < 0,
3542 node);
3543
3544 return iterator(node);
3545}
3546
3547template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3548template <class BDE_OTHER_TYPE>
3549inline
3550pair<typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator, bool>
3551map<KEY, VALUE, COMPARATOR, ALLOCATOR>::insert_or_assign(
3552 BloombergLP::bslmf::MovableRef<key_type> key,
3553 BDE_OTHER_TYPE&& obj)
3554{
3555 int comparisonResult;
3556 BloombergLP::bslalg::RbTreeNode *insertLocation =
3557 BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation(
3558 &comparisonResult,
3559 &d_tree,
3560 this->comparator(),
3561 key);
3562
3563 if (!comparisonResult) { // ASSIGN
3564 iterator(insertLocation)->second =
3565 BSLS_COMPILERFEATURES_FORWARD(BDE_OTHER_TYPE, obj);
3566 return pair<iterator, bool>(iterator(insertLocation), false); // RETURN
3567 }
3568
3569 // INSERT
3570 BloombergLP::bslalg::RbTreeNode *node = nodeFactory().emplaceIntoNewNode(
3571 BSLS_COMPILERFEATURES_FORWARD(key_type, key),
3572 BSLS_COMPILERFEATURES_FORWARD(BDE_OTHER_TYPE, obj));
3573
3574 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
3575 insertLocation,
3576 comparisonResult < 0,
3577 node);
3578
3579 return pair<iterator, bool>(iterator(node), true);
3580}
3581
3582template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3583template <class BDE_OTHER_TYPE>
3584inline
3585typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator
3586map<KEY, VALUE, COMPARATOR, ALLOCATOR>::insert_or_assign(
3587 const_iterator hint,
3588 BloombergLP::bslmf::MovableRef<key_type> key,
3589 BDE_OTHER_TYPE&& obj)
3590{
3591 BloombergLP::bslalg::RbTreeNode *hintNode =
3592 const_cast<BloombergLP::bslalg::RbTreeNode *>(hint.node());
3593 int comparisonResult;
3594 BloombergLP::bslalg::RbTreeNode *insertLocation =
3595 BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation(
3596 &comparisonResult,
3597 &d_tree,
3598 this->comparator(),
3599 key,
3600 hintNode);
3601
3602 if (!comparisonResult) { // ASSIGN
3603 iterator(insertLocation)->second =
3604 BSLS_COMPILERFEATURES_FORWARD(BDE_OTHER_TYPE, obj);
3605 return iterator(insertLocation); // RETURN
3606 }
3607
3608 // INSERT
3609 BloombergLP::bslalg::RbTreeNode *node = nodeFactory().emplaceIntoNewNode(
3610 BSLS_COMPILERFEATURES_FORWARD(key_type, key),
3611 BSLS_COMPILERFEATURES_FORWARD(BDE_OTHER_TYPE, obj));
3612
3613 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
3614 insertLocation,
3615 comparisonResult < 0,
3616 node);
3617
3618 return iterator(node);
3619}
3620#endif
3621
3622#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
3623
3624template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3625template <class... Args>
3626inline
3627pair<typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator, bool>
3628map<KEY, VALUE, COMPARATOR, ALLOCATOR>::emplace(Args&&... args)
3629{
3630 BloombergLP::bslalg::RbTreeNode *node = nodeFactory().emplaceIntoNewNode(
3631 BSLS_COMPILERFEATURES_FORWARD(Args, args)...);
3632 int comparisonResult;
3633 BloombergLP::bslalg::RbTreeNode *insertLocation =
3634 BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation(
3635 &comparisonResult,
3636 &d_tree,
3637 this->comparator(),
3638 static_cast<const Node *>(node)->value().first);
3639 if (!comparisonResult) {
3640 nodeFactory().deleteNode(node);
3641 return pair<iterator, bool>(iterator(insertLocation), false); // RETURN
3642 }
3643
3644 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
3645 insertLocation,
3646 comparisonResult < 0,
3647 node);
3648 return pair<iterator, bool>(iterator(node), true);
3649}
3650
3651template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3652template <class... Args>
3653inline
3654typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator
3655map<KEY, VALUE, COMPARATOR, ALLOCATOR>::emplace_hint(const_iterator hint,
3656 Args&&... args)
3657{
3658 BloombergLP::bslalg::RbTreeNode *node = nodeFactory().emplaceIntoNewNode(
3659 BSLS_COMPILERFEATURES_FORWARD(Args, args)...);
3660 BloombergLP::bslalg::RbTreeNode *hintNode =
3661 const_cast<BloombergLP::bslalg::RbTreeNode *>(hint.node());
3662 int comparisonResult;
3663 BloombergLP::bslalg::RbTreeNode *insertLocation =
3664 BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation(
3665 &comparisonResult,
3666 &d_tree,
3667 this->comparator(),
3668 static_cast<const Node *>(node)->value().first,
3669 hintNode);
3670 if (!comparisonResult) {
3671 nodeFactory().deleteNode(node);
3672 return iterator(insertLocation); // RETURN
3673 }
3674
3675 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
3676 insertLocation,
3677 comparisonResult < 0,
3678 node);
3679 return iterator(node);
3680}
3681
3682#endif
3683
3684template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3685inline
3686typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator
3687map<KEY, VALUE, COMPARATOR, ALLOCATOR>::erase(const_iterator position)
3688{
3689 BSLS_ASSERT_SAFE(position != end());
3690
3691 BloombergLP::bslalg::RbTreeNode *node =
3692 const_cast<BloombergLP::bslalg::RbTreeNode *>(position.node());
3693 BloombergLP::bslalg::RbTreeNode *result =
3694 BloombergLP::bslalg::RbTreeUtil::next(node);
3695 BloombergLP::bslalg::RbTreeUtil::remove(&d_tree, node);
3696 nodeFactory().deleteNode(node);
3697 return iterator(result);
3698}
3699
3700template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3701inline
3702typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator
3707
3708template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3709inline
3710typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::size_type
3711map<KEY, VALUE, COMPARATOR, ALLOCATOR>::erase(const key_type& key)
3712{
3713 const_iterator it = find(key);
3714 if (it == end()) {
3715 return 0; // RETURN
3716 }
3717 erase(it);
3718 return 1;
3719}
3720
3721template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3722inline
3723typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator
3724map<KEY, VALUE, COMPARATOR, ALLOCATOR>::erase(const_iterator first,
3725 const_iterator last)
3726{
3727 while (first != last) {
3728 first = erase(first);
3729 }
3730 return iterator(last.node());
3731}
3732
3733template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3734inline
3735void map<KEY, VALUE, COMPARATOR, ALLOCATOR>::swap(map& other)
3736 BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(
3737 AllocatorTraits::is_always_equal::value &&
3738 bsl::is_nothrow_swappable<COMPARATOR>::value)
3739{
3740 if (AllocatorTraits::propagate_on_container_swap::value) {
3741 quickSwapExchangeAllocators(other);
3742 }
3743 else {
3744 // C++11 behavior for member 'swap': undefined for unequal allocators.
3745 // BSLS_ASSERT(allocator() == other.allocator());
3746
3747 if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(
3748 nodeFactory().allocator() == other.nodeFactory().allocator())) {
3749 quickSwapRetainAllocators(other);
3750 }
3751 else {
3752 BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
3753
3754 map toOtherCopy(MoveUtil::move(*this),
3755 other.nodeFactory().allocator());
3756 map toThisCopy(MoveUtil::move(other), nodeFactory().allocator());
3757
3758 this->quickSwapRetainAllocators(toThisCopy);
3759 other.quickSwapRetainAllocators(toOtherCopy);
3760 }
3761 }
3762}
3763
3764#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
3765template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3766template <class... Args>
3767inline
3768pair<typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator, bool>
3769map<KEY, VALUE, COMPARATOR, ALLOCATOR>::try_emplace(const key_type& key,
3770 Args&&... args)
3771{
3772 int comparisonResult;
3773 BloombergLP::bslalg::RbTreeNode *insertLocation =
3774 BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation(
3775 &comparisonResult,
3776 &d_tree,
3777 this->comparator(),
3778 key);
3779 if (!comparisonResult) {
3780 return pair<iterator, bool>(iterator(insertLocation), false); // RETURN
3781 }
3782
3783#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
3784 BloombergLP::bslalg::RbTreeNode *node = nodeFactory().emplaceIntoNewNode(
3785 std::piecewise_construct,
3786 std::forward_as_tuple(key),
3787 std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(Args, args)...));
3788#else
3789 BloombergLP::bslalg::RbTreeNode *node = nodeFactory().emplaceIntoNewNode(
3790 key,
3791 mapped_type(BSLS_COMPILERFEATURES_FORWARD(Args, args)...));
3792#endif
3793
3794 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
3795 insertLocation,
3796 comparisonResult < 0,
3797 node);
3798 return pair<iterator, bool>(iterator(node), true);
3799}
3800
3801template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3802template <class... Args>
3803inline
3804typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator
3805map<KEY, VALUE, COMPARATOR, ALLOCATOR>::try_emplace(const_iterator hint,
3806 const key_type& key,
3807 Args&&... args)
3808{
3809 BloombergLP::bslalg::RbTreeNode *hintNode =
3810 const_cast<BloombergLP::bslalg::RbTreeNode *>(hint.node());
3811 int comparisonResult;
3812 BloombergLP::bslalg::RbTreeNode *insertLocation =
3813 BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation(
3814 &comparisonResult,
3815 &d_tree,
3816 this->comparator(),
3817 key,
3818 hintNode);
3819 if (!comparisonResult) {
3820 return iterator(insertLocation); // RETURN
3821 }
3822
3823#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
3824 BloombergLP::bslalg::RbTreeNode *node = nodeFactory().emplaceIntoNewNode(
3825 std::piecewise_construct,
3826 std::forward_as_tuple(key),
3827 std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(Args, args)...));
3828#else
3829 BloombergLP::bslalg::RbTreeNode *node = nodeFactory().emplaceIntoNewNode(
3830 key,
3831 mapped_type(BSLS_COMPILERFEATURES_FORWARD(Args, args)...));
3832#endif
3833
3834 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
3835 insertLocation,
3836 comparisonResult < 0,
3837 node);
3838 return iterator(node);
3839}
3840
3841template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3842template <class... Args>
3843inline
3844pair<typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator, bool>
3845map<KEY, VALUE, COMPARATOR, ALLOCATOR>::try_emplace(
3846 BloombergLP::bslmf::MovableRef<key_type> key,
3847 Args&&... args)
3848{
3849 key_type& lvalue = key;
3850
3851 int comparisonResult;
3852 BloombergLP::bslalg::RbTreeNode *insertLocation =
3853 BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation(
3854 &comparisonResult,
3855 &d_tree,
3856 this->comparator(),
3857 lvalue);
3858 if (!comparisonResult) {
3859 return pair<iterator, bool>(iterator(insertLocation), false); // RETURN
3860 }
3861
3862#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
3863 BloombergLP::bslalg::RbTreeNode *node = nodeFactory().emplaceIntoNewNode(
3864 std::piecewise_construct,
3865 std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(key_type, key)),
3866 std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(Args, args)...));
3867#else
3868 BloombergLP::bslalg::RbTreeNode *node = nodeFactory().emplaceIntoNewNode(
3869 BSLS_COMPILERFEATURES_FORWARD(key_type, key),
3870 mapped_type(BSLS_COMPILERFEATURES_FORWARD(Args, args)...));
3871#endif
3872
3873 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
3874 insertLocation,
3875 comparisonResult < 0,
3876 node);
3877
3878 return pair<iterator, bool>(iterator(node), true);
3879}
3880
3881template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3882template <class... Args>
3883inline
3884typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::iterator
3885map<KEY, VALUE, COMPARATOR, ALLOCATOR>::try_emplace(
3886 const_iterator hint,
3887 BloombergLP::bslmf::MovableRef<key_type> key,
3888 Args&&... args)
3889{
3890 key_type& lvalue = key;
3891
3892 BloombergLP::bslalg::RbTreeNode *hintNode =
3893 const_cast<BloombergLP::bslalg::RbTreeNode *>(hint.node());
3894 int comparisonResult;
3895 BloombergLP::bslalg::RbTreeNode *insertLocation =
3896 BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation(
3897 &comparisonResult,
3898 &d_tree,
3899 this->comparator(),
3900 lvalue,
3901 hintNode);
3902 if (!comparisonResult) {
3903 return iterator(insertLocation); // RETURN
3904 }
3905
3906#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
3907 BloombergLP::bslalg::RbTreeNode *node = nodeFactory().emplaceIntoNewNode(
3908 std::piecewise_construct,
3909 std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(key_type, key)),
3910 std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(Args, args)...));
3911#else
3912 BloombergLP::bslalg::RbTreeNode *node = nodeFactory().emplaceIntoNewNode(
3913 BSLS_COMPILERFEATURES_FORWARD(key_type, key),
3914 mapped_type(BSLS_COMPILERFEATURES_FORWARD(Args, args)...));
3915#endif
3916
3917 BloombergLP::bslalg::RbTreeUtil::insertAt(&d_tree,
3918 insertLocation,
3919 comparisonResult < 0,
3920 node);
3921 return iterator(node);
3922}
3923#endif
3924
3925template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3926inline
3927void map<KEY, VALUE, COMPARATOR, ALLOCATOR>::clear() BSLS_KEYWORD_NOEXCEPT
3928{
3929 BSLS_ASSERT_SAFE(d_tree.firstNode());
3930
3931 if (d_tree.rootNode()) {
3932 BSLS_ASSERT_SAFE( 0 < d_tree.numNodes());
3933 BSLS_ASSERT_SAFE(d_tree.firstNode() != d_tree.sentinel());
3934
3935 BloombergLP::bslalg::RbTreeUtil::deleteTree(&d_tree, &nodeFactory());
3936 }
3937#if defined(BSLS_ASSERT_SAFE_IS_USED)
3938 else {
3939 BSLS_ASSERT_SAFE( 0 == d_tree.numNodes());
3940 BSLS_ASSERT_SAFE(d_tree.firstNode() == d_tree.sentinel());
3941 }
3942#endif
3943}
3944
3945// ACCESSORS
3946template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3947inline
3948typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::allocator_type
3949map<KEY, VALUE, COMPARATOR, ALLOCATOR>::get_allocator() const
3950 BSLS_KEYWORD_NOEXCEPT
3951{
3952 return nodeFactory().allocator();
3953}
3954
3955template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3956inline
3957typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::const_iterator
3962
3963template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3964inline
3965typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::const_iterator
3970
3971template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3972inline
3973typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::const_reverse_iterator
3978
3979template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3980inline
3981typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::const_reverse_iterator
3986
3987template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3988inline
3989typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::const_iterator
3994
3995template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
3996inline
3997typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::const_iterator
4002
4003template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4004inline
4005typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::const_reverse_iterator
4010
4011template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4012inline
4013typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::const_reverse_iterator
4018
4019template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4020inline
4021bool map<KEY, VALUE, COMPARATOR, ALLOCATOR>::contains(
4022 const key_type& key) const
4023{
4024 return find(key) != end();
4025}
4026
4027// capacity:
4028template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4029inline
4030bool map<KEY, VALUE, COMPARATOR, ALLOCATOR>::empty() const
4031 BSLS_KEYWORD_NOEXCEPT
4032{
4033 return 0 == d_tree.numNodes();
4034}
4035
4036template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4037inline
4038typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::size_type
4039map<KEY, VALUE, COMPARATOR, ALLOCATOR>::size() const BSLS_KEYWORD_NOEXCEPT
4040{
4041 return d_tree.numNodes();
4042}
4043
4044template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4045inline
4046typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::size_type
4047map<KEY, VALUE, COMPARATOR, ALLOCATOR>::max_size() const BSLS_KEYWORD_NOEXCEPT
4048{
4049 return AllocatorTraits::max_size(get_allocator());
4050}
4051
4052template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4053typename add_lvalue_reference<const VALUE>::type
4054map<KEY, VALUE, COMPARATOR, ALLOCATOR>::at(
4055 const key_type& key) const
4056{
4057 const BloombergLP::bslalg::RbTreeNode *node =
4058 BloombergLP::bslalg::RbTreeUtil::find(d_tree,
4059 this->comparator(),
4060 key);
4061 if (d_tree.sentinel() == node) {
4062 BloombergLP::bslstl::StdExceptUtil::throwOutOfRange(
4063 "map<...>::at(key_type): invalid key value");
4064 }
4065 return toNode(node)->value().second;
4066}
4067
4068template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4069inline
4070typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::key_compare
4071map<KEY, VALUE, COMPARATOR, ALLOCATOR>::key_comp() const
4072{
4073 return comparator().keyComparator();
4074}
4075
4076template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4077inline
4078typename map<KEY, VALUE, COMPARATOR, ALLOCATOR>::value_compare
4079map<KEY, VALUE, COMPARATOR, ALLOCATOR>::value_comp() const
4080{
4081 return value_compare(key_comp());
4082}
4083
4084} // close namespace bsl
4085
4086// FREE OPERATORS
4087template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4088inline
4089bool bsl::operator==(const bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR>& lhs,
4090 const bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR>& rhs)
4091{
4092 return BloombergLP::bslalg::RangeCompare::equal(lhs.begin(),
4093 lhs.end(),
4094 lhs.size(),
4095 rhs.begin(),
4096 rhs.end(),
4097 rhs.size());
4098}
4099
4100#ifndef BSLS_COMPILERFEATURES_SUPPORT_THREE_WAY_COMPARISON
4101template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4102inline
4103bool bsl::operator!=(const bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR>& lhs,
4104 const bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR>& rhs)
4105{
4106 return !(lhs == rhs);
4107}
4108#endif
4109
4110#ifdef BSLALG_SYNTHTHREEWAYUTIL_AVAILABLE
4111
4112template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4113inline
4114BloombergLP::bslalg::SynthThreeWayUtil::Result<bsl::pair<const KEY, VALUE>>
4115bsl::operator<=>(const map<KEY, VALUE, COMPARATOR, ALLOCATOR>& lhs,
4116 const map<KEY, VALUE, COMPARATOR, ALLOCATOR>& rhs)
4117{
4118 return bsl::lexicographical_compare_three_way(
4119 lhs.begin(),
4120 lhs.end(),
4121 rhs.begin(),
4122 rhs.end(),
4123 BloombergLP::bslalg::SynthThreeWayUtil::compare);
4124}
4125
4126#else
4127
4128template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4129inline
4130bool bsl::operator<(const bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR>& lhs,
4131 const bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR>& rhs)
4132{
4133 return 0 > BloombergLP::bslalg::RangeCompare::lexicographical(lhs.begin(),
4134 lhs.end(),
4135 lhs.size(),
4136 rhs.begin(),
4137 rhs.end(),
4138 rhs.size());
4139}
4140
4141template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4142inline
4143bool bsl::operator>(const bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR>& lhs,
4144 const bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR>& rhs)
4145{
4146 return rhs < lhs;
4147}
4148
4149template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4150inline
4151bool bsl::operator<=(const bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR>& lhs,
4152 const bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR>& rhs)
4153{
4154 return !(rhs < lhs);
4155}
4156
4157template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4158inline
4159bool bsl::operator>=(const bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR>& lhs,
4160 const bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR>& rhs)
4161{
4162 return !(lhs < rhs);
4163}
4164
4165#endif // BSLALG_SYNTHTHREEWAYUTIL_AVAILABLE
4166
4167// FREE FUNCTIONS
4168template <class KEY,
4169 class VALUE,
4170 class COMPARATOR,
4171 class ALLOCATOR,
4172 class PREDICATE>
4173inline
4174typename bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR>::size_type
4175bsl::erase_if(map<KEY, VALUE, COMPARATOR, ALLOCATOR>& m, PREDICATE predicate)
4176{
4177 return BloombergLP::bslstl::AlgorithmUtil::containerEraseIf(m, predicate);
4178}
4179
4180template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4181inline
4182void bsl::swap(bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR>& a,
4183 bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR>& b)
4184 BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(false)
4185{
4186 a.swap(b);
4187}
4188
4189// ============================================================================
4190// TYPE TRAITS
4191// ============================================================================
4192
4193// Type traits for STL *ordered* containers:
4194//: o An ordered container defines STL iterators.
4195//: o An ordered container uses 'bslma' allocators if the (template parameter)
4196//: type 'ALLOCATOR' is convertible from 'bslma::Allocator *'.
4197
4198
4199
4200namespace bslalg {
4201
4202template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4203struct HasStlIterators<bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR> >
4204 : bsl::true_type
4205{
4206};
4207
4208} // close namespace bslalg
4209
4210namespace bslma {
4211
4212template <class KEY, class VALUE, class COMPARATOR, class ALLOCATOR>
4213struct UsesBslmaAllocator<bsl::map<KEY, VALUE, COMPARATOR, ALLOCATOR> >
4214 : bsl::is_convertible<Allocator *, ALLOCATOR>
4215{
4216};
4217
4218} // close namespace bslma
4219
4220
4221
4222#endif // End C++11 code
4223
4224#endif
4225
4226// ----------------------------------------------------------------------------
4227// Copyright 2019 Bloomberg Finance L.P.
4228//
4229// Licensed under the Apache License, Version 2.0 (the "License");
4230// you may not use this file except in compliance with the License.
4231// You may obtain a copy of the License at
4232//
4233// http://www.apache.org/licenses/LICENSE-2.0
4234//
4235// Unless required by applicable law or agreed to in writing, software
4236// distributed under the License is distributed on an "AS IS" BASIS,
4237// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
4238// See the License for the specific language governing permissions and
4239// limitations under the License.
4240// ----------------------------- END-OF-FILE ----------------------------------
4241
4242/** @} */
4243/** @} */
4244/** @} */
bslalg_rangecompare.h
bslalg_rbtreeanchor.h
bslalg_rbtreenode.h
bslalg_rbtreeutil.h
bslalg_synththreewayutil.h
bslalg_typetraithasstliterators.h
bslma_bslallocator.h
bslma_constructionutil.h
bslma_default.h
bslma_destructorguard.h
bslma_isstdallocator.h
bslma_usesbslmaallocator.h
bslmf_addlvaluereference.h
bslmf_containercompatiblerange.h
bslmf_enableif.h
bslmf_isconvertible.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_libraryfeatures.h
bsls_nativestd.h
bsls_objectbuffer.h
bsls_performancehint.h
bsls_platform.h
bsls_util.h
bslstl_algorithm.h
bslstl_iterator.h
bslstl_iteratorutil.h
bslstl_map_cpp03.h
bslstl_mapcomparator.h
bslstl_pair.h
bslstl_ranges.h
bslstl_stdexceptutil.h
bslstl_treeiterator.h
bslstl_treenode.h
bslstl_treenodepool.h
bsl::allocator
Definition bslma_bslallocator.h:588
bsl::basic_string
Definition bslstl_string.h:1252
bsl::map::value_compare
Definition bslstl_map.h:771
bsl::map::value_compare::value_compare
value_compare(const value_compare &original)=default
bsl::map::value_compare::second_argument_type
value_type second_argument_type
Definition bslstl_map.h:803
bsl::map::value_compare::comp
COMPARATOR comp
Definition bslstl_map.h:778
bsl::map::value_compare::~value_compare
~value_compare()=default
bsl::map::value_compare::operator()
bool operator()(const value_type &x, const value_type &y) const
Definition bslstl_map.h:2724
bsl::map::value_compare::first_argument_type
value_type first_argument_type
Definition bslstl_map.h:798
bsl::map::value_compare::operator=
value_compare & operator=(const value_compare &rhs)=default
bsl::map::value_compare::result_type
bool result_type
Definition bslstl_map.h:793
bsl::map
Definition bslstl_map.h:653
bsl::map::reference
value_type & reference
Definition bslstl_map.h:747
bsl::map::erase
iterator erase(const_iterator position)
Definition bslstl_map.h:3687
bsl::map::insert_range
void insert_range(BSLS_COMPILERFEATURES_FORWARD_REF(RANGE) range)
Definition bslstl_map.h:1449
bsl::map::get_allocator
allocator_type get_allocator() const BSLS_KEYWORD_NOEXCEPT
Definition bslstl_map.h:3949
bsl::map::insert
enable_if< is_convertible< ALT_VALUE_TYPE, value_type >::value, iterator >::type insert(const_iterator hint, BSLS_COMPILERFEATURES_FORWARD_REF(ALT_VALUE_TYPE) value)
Definition bslstl_map.h:1408
bsl::map::crend
const_reverse_iterator crend() const BSLS_KEYWORD_NOEXCEPT
Definition bslstl_map.h:4014
bsl::map::insert
void insert(INPUT_ITERATOR first, INPUT_ITERATOR last)
Definition bslstl_map.h:3385
bsl::map::operator[]
map &operator=(BloombergLP::bslmf::MovableRef< map > rhs) BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(AllocatorTraits add_lvalue_reference< VALUE >::type operator[](const key_type &key)
Definition bslstl_map.h:3221
bsl::map::contains
bool contains(const key_type &key) const
Definition bslstl_map.h:4021
bsl::map::const_iterator
BloombergLP::bslstl::TreeIterator< const value_type, Node, difference_type > const_iterator
Definition bslstl_map.h:758
bsl::map::rend
reverse_iterator rend() BSLS_KEYWORD_NOEXCEPT
Definition bslstl_map.h:3324
bsl::map::equal_range
pair< iterator, iterator > equal_range(const key_type &key)
Definition bslstl_map.h:1999
bsl::map::insert_or_assign
bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< COMPARATOR, LOOKUP_KEY >::value, pair< iterator, bool > >::type insert_or_assign(LOOKUP_KEY &&key, BDE_OTHER_TYPE &&obj)
Definition bslstl_map.h:1523
bsl::map::erase
iterator erase(const_iterator first, const_iterator last)
Definition bslstl_map.h:3724
bsl::map::upper_bound
iterator upper_bound(const key_type &key)
Definition bslstl_map.h:1958
bsl::map::lower_bound
bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< COMPARATOR, LOOKUP_KEY >::value, const_iterator >::type lower_bound(const LOOKUP_KEY &key) const
Definition bslstl_map.h:2280
bsl::map::end
iterator end() BSLS_KEYWORD_NOEXCEPT
Definition bslstl_map.h:3308
bsl::map::find
const_iterator find(const key_type &key) const
Definition bslstl_map.h:2187
bsl::map::try_emplace
iterator try_emplace(const_iterator hint, const KEY &key, Args &&... args)
Definition bslstl_map.h:3805
bsl::map::map
map()
Definition bslstl_map.h:3021
bsl::map::~map
~map()
Destroy this object.
Definition bslstl_map.h:3152
bsl::map::crbegin
const_reverse_iterator crbegin() const BSLS_KEYWORD_NOEXCEPT
Definition bslstl_map.h:4006
bsl::map::erase
size_type erase(const key_type &key)
Definition bslstl_map.h:3711
bsl::map::find
bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< COMPARATOR, LOOKUP_KEY >::value, iterator >::type find(const LOOKUP_KEY &key)
Definition bslstl_map.h:1902
bsl::map::try_emplace
bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< COMPARATOR, LOOKUP_KEY >::value &&!bsl::is_convertible< LOOKUP_KEY &&, const_iterator >::value &&!bsl::is_convertible< LOOKUP_KEY &&, iterator >::value, pair< iterator, bool > >::type try_emplace(LOOKUP_KEY &&key, Args &&... args)
Definition bslstl_map.h:1769
bsl::map::rbegin
reverse_iterator rbegin() BSLS_KEYWORD_NOEXCEPT
Definition bslstl_map.h:3316
bsl::map::lower_bound
iterator lower_bound(const key_type &key)
Definition bslstl_map.h:1919
bsl::map::count
size_type count(const key_type &key) const
Definition bslstl_map.h:2216
bsl::map::const_reference
const value_type & const_reference
Definition bslstl_map.h:748
bsl::map::key_type
KEY key_type
Definition bslstl_map.h:742
bsl::map::insert_or_assign
pair< iterator, bool > insert_or_assign(BloombergLP::bslmf::MovableRef< KEY > key, BDE_OTHER_TYPE &&obj)
bsl::map::map
map(const ALLOCATOR &basicAllocator)
Definition bslstl_map.h:3029
bsl::map::insert
iterator insert(const_iterator hint, BloombergLP::bslmf::MovableRef< value_type > value)
Definition bslstl_map.h:3436
bsl::map::lower_bound
bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< COMPARATOR, LOOKUP_KEY >::value, iterator >::type lower_bound(const LOOKUP_KEY &key)
Definition bslstl_map.h:1941
bsl::map::const_pointer
AllocatorTraits::const_pointer const_pointer
Definition bslstl_map.h:753
bsl::map::at
add_lvalue_reference< VALUE >::type at(const key_type &key)
Definition bslstl_map.h:3286
bsl::map::equal_range
bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< COMPARATOR, LOOKUP_KEY >::value, pair< iterator, iterator > >::type equal_range(const LOOKUP_KEY &key)
Definition bslstl_map.h:2030
bsl::map::insert_or_assign
iterator insert_or_assign(const_iterator hint, const KEY &key, BDE_OTHER_TYPE &&obj)
Definition bslstl_map.h:3514
bsl::map::emplace
pair< iterator, bool > emplace(Args &&... args)
bsl::map::map
map(BloombergLP::bslmf::MovableRef< map > original, const typename type_identity< ALLOCATOR >::type &basicAllocator)
Definition bslstl_map.h:3079
bsl::map::map
map(const map &original, const typename type_identity< ALLOCATOR >::type &basicAllocator)
Definition bslstl_map.h:3064
bsl::map::reverse_iterator
bsl::reverse_iterator< iterator > reverse_iterator
Definition bslstl_map.h:759
bsl::map::find
iterator find(const key_type &key)
Definition bslstl_map.h:1885
bsl::map::try_emplace
void swap(map &other) BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(AllocatorTraits pair< iterator, bool > try_emplace(const KEY &key, Args &&... args)
Definition bslstl_map.h:1758
bsl::map::allocator_type
ALLOCATOR allocator_type
Definition bslstl_map.h:746
bsl::map::operator=
map & operator=(const map &rhs)
Definition bslstl_map.h:3161
bsl::map::find
bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< COMPARATOR, LOOKUP_KEY >::value, const_iterator >::type find(const LOOKUP_KEY &key) const
Definition bslstl_map.h:2204
bsl::map::empty
bool empty() const BSLS_KEYWORD_NOEXCEPT
Definition bslstl_map.h:4030
bsl::map::insert_or_assign
pair< iterator, bool > insert_or_assign(const KEY &key, BDE_OTHER_TYPE &&obj)
bsl::map::erase
iterator erase(iterator position)
Definition bslstl_map.h:3703
bsl::map::size
size_type size() const BSLS_KEYWORD_NOEXCEPT
Return the number of elements in this map.
Definition bslstl_map.h:4039
bsl::map::map
map(BloombergLP::bslmf::MovableRef< map > original)
Definition bslstl_map.h:3053
bsl::map::insert
pair< iterator, bool > insert(const value_type &value)
Definition bslstl_map.h:3332
bsl::map::begin
iterator begin() BSLS_KEYWORD_NOEXCEPT
Definition bslstl_map.h:3300
bsl::map::mapped_type
VALUE mapped_type
Definition bslstl_map.h:743
bsl::map::map
map(const COMPARATOR &comparator, const ALLOCATOR &basicAllocator=ALLOCATOR())
Definition bslstl_map.h:937
bsl::map::equal_range
pair< const_iterator, const_iterator > equal_range(const key_type &key) const
Definition bslstl_map.h:2340
bsl::map::clear
void clear() BSLS_KEYWORD_NOEXCEPT
Definition bslstl_map.h:3927
bsl::map::count
bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< COMPARATOR, LOOKUP_KEY >::value, size_type >::type count(const LOOKUP_KEY &key) const
Definition bslstl_map.h:2235
bsl::map::erase
enable_if< BloombergLP::bslmf::IsTransparentPredicate< COMPARATOR, t_KEY >::value &&!is_convertible< BSLS_COMPILERFEATURES_FORWARD_REF(t_KEY), iterator >::value &&!is_convertible< BSLS_COMPILERFEATURES_FORWARD_REF(t_KEY), const_iterator >::value, size_type >::type erase(BSLS_COMPILERFEATURES_FORWARD_REF(t_KEY) key)
Definition bslstl_map.h:1705
bsl::map::try_emplace
pair< iterator, bool > try_emplace(BloombergLP::bslmf::MovableRef< KEY > key, Args &&... args)
bsl::map::try_emplace
bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< COMPARATOR, LOOKUP_KEY >::value, iterator >::type try_emplace(const_iterator hint, LOOKUP_KEY &&key, Args &&... args)
Definition bslstl_map.h:1828
bsl::map::operator[]
add_lvalue_reference< VALUE >::type operator[](BloombergLP::bslmf::MovableRef< key_type > key)
Definition bslstl_map.h:3252
bsl::map::insert_or_assign
bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< COMPARATOR, LOOKUP_KEY >::value, iterator >::type insert_or_assign(const_iterator hint, LOOKUP_KEY &&key, BDE_OTHER_TYPE &&obj)
Definition bslstl_map.h:1598
bsl::map::value_comp
value_compare value_comp() const
Definition bslstl_map.h:4079
bsl::map::cbegin
const_iterator cbegin() const BSLS_KEYWORD_NOEXCEPT
Definition bslstl_map.h:3990
bsl::map::max_size
size_type max_size() const BSLS_KEYWORD_NOEXCEPT
Definition bslstl_map.h:4047
bsl::map::upper_bound
bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< COMPARATOR, LOOKUP_KEY >::value, iterator >::type upper_bound(const LOOKUP_KEY &key)
Definition bslstl_map.h:1980
bsl::map::insert_or_assign
iterator insert_or_assign(const_iterator hint, BloombergLP::bslmf::MovableRef< KEY > key, BDE_OTHER_TYPE &&obj)
Definition bslstl_map.h:3586
bsl::map::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_map.h:2371
bsl::map::map
map(INPUT_ITERATOR first, INPUT_ITERATOR last, const COMPARATOR &comparator=COMPARATOR(), const ALLOCATOR &basicAllocator=ALLOCATOR())
Definition bslstl_map.h:3106
bsl::map::const_reverse_iterator
bsl::reverse_iterator< const_iterator > const_reverse_iterator
Definition bslstl_map.h:760
bsl::map::insert
enable_if< is_convertible< ALT_VALUE_TYPE, value_type >::value, pair< iterator, bool > >::type insert(BSLS_COMPILERFEATURES_FORWARD_REF(ALT_VALUE_TYPE) value)
Definition bslstl_map.h:1333
bsl::map::size_type
AllocatorTraits::size_type size_type
Definition bslstl_map.h:750
bsl::map::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition bslstl_map.h:3655
bsl::map::cend
const_iterator cend() const BSLS_KEYWORD_NOEXCEPT
Definition bslstl_map.h:3998
bsl::map::iterator
BloombergLP::bslstl::TreeIterator< value_type, Node, difference_type > iterator
Definition bslstl_map.h:756
bsl::map::value_type
pair< const KEY, VALUE > value_type
Definition bslstl_map.h:744
bsl::map::insert
iterator insert(const_iterator hint, const value_type &value)
Definition bslstl_map.h:3407
bsl::map::upper_bound
bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< COMPARATOR, LOOKUP_KEY >::value, const_iterator >::type upper_bound(const LOOKUP_KEY &key) const
Definition bslstl_map.h:2321
bsl::map::pointer
AllocatorTraits::pointer pointer
Definition bslstl_map.h:752
bsl::map::difference_type
AllocatorTraits::difference_type difference_type
Definition bslstl_map.h:751
bsl::map::key_comp
key_compare key_comp() const
Definition bslstl_map.h:4071
bsl::map::upper_bound
const_iterator upper_bound(const key_type &key) const
Definition bslstl_map.h:2299
bsl::map::map
map(INPUT_ITERATOR first, INPUT_ITERATOR last, const ALLOCATOR &basicAllocator)
Definition bslstl_map.h:3119
bsl::map::map
map(const map &original)
Definition bslstl_map.h:3037
bsl::map::try_emplace
iterator try_emplace(const_iterator hint, BloombergLP::bslmf::MovableRef< KEY > key, Args &&... args)
Definition bslstl_map.h:3885
bsl::map::at
bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< COMPARATOR, LOOKUP_KEY >::value, typenameadd_lvalue_reference< VALUE >::type >::type at(const LOOKUP_KEY &key)
Definition bslstl_map.h:1249
bsl::map::lower_bound
const_iterator lower_bound(const key_type &key) const
Definition bslstl_map.h:2258
bsl::map::key_compare
COMPARATOR key_compare
Definition bslstl_map.h:745
bsl::pair
Definition bslstl_pair.h:1280
BSLS_ASSERT_SAFE
#define BSLS_ASSERT_SAFE(X)
Definition bsls_assert.h:1917
BSLS_COMPILERFEATURES_FORWARD_REF
#define BSLS_COMPILERFEATURES_FORWARD_REF(T)
Definition bsls_compilerfeatures.h:2343
BSLS_COMPILERFEATURES_FORWARD
#define BSLS_COMPILERFEATURES_FORWARD(T, V)
Definition bsls_compilerfeatures.h:2349
BSLS_IDENT
#define BSLS_IDENT(str)
BSLS_IDENT() - insert string into .comment binary segment (if supported)
Definition bsls_ident.h:238
BSLS_KEYWORD_CONSTEXPR_CPP17
#define BSLS_KEYWORD_CONSTEXPR_CPP17
Definition bsls_keyword.h:639
BSLS_KEYWORD_NOEXCEPT
#define BSLS_KEYWORD_NOEXCEPT
Definition bsls_keyword.h:674
BSLS_KEYWORD_NOEXCEPT_SPECIFICATION
#define BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(...)
Definition bsls_keyword.h:676
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
BSLSTL_MAP_REQUIRES_CONTAINER_COMPATIBLE_RANGE
#define BSLSTL_MAP_REQUIRES_CONTAINER_COMPATIBLE_RANGE(R, T)
Definition bslstl_map.h:613
bsl
Definition bdlat_valuetypefunctions.h:939
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:1709
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:1695
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::rhs
ALLOCATOR const STRING_VIEW_LIKE_TYPE & rhs
Definition bslstl_string.h:3918
bsl::erase
deque< VALUE_TYPE, ALLOCATOR >::size_type erase(deque< VALUE_TYPE, ALLOCATOR > &deq, const BDE_OTHER_TYPE &value)
Definition bslstl_deque.h:4424
bsl::begin
T::iterator begin(T &container)
Definition bslstl_iterator.h:1593
bsl::from_range
const from_range_t from_range
bsl::cbegin
T::const_iterator cbegin(const T &container)
Definition bslstl_iterator.h:1651
bsl::lhs
ALLOCATOR & lhs
Definition bslstl_string.h:3917
bsl::end
T::iterator end(T &container)
Definition bslstl_iterator.h:1621
bsl::erase_if
deque< VALUE_TYPE, ALLOCATOR >::size_type erase_if(deque< VALUE_TYPE, ALLOCATOR > &deq, PREDICATE predicate)
Definition bslstl_deque.h:4433
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:1752
bslalg
Definition bdlc_flathashmap.h:2218
bslma
Definition baljsn_encoder_testtypes.h:76
bslmf
Definition bdlbb_blob.h:579
bsl::Pair_First::first
TYPE first
Definition bslstl_pair.h:587
bsl::add_lvalue_reference
Definition bslmf_addlvaluereference.h:128
bsl::add_lvalue_reference::type
t_TYPE & type
This typedef defines the return type of this meta function.
Definition bslmf_addlvaluereference.h:131
bsl::allocator_traits
Definition bslma_allocatortraits.h:1089
bsl::allocator_traits< ALLOCATOR >::const_pointer
BloombergLP::bslma::AllocatorTraits_ConstPointerType< ALLOCATOR >::type const_pointer
Definition bslma_allocatortraits.h:1183
bsl::allocator_traits< ALLOCATOR >::size_type
BloombergLP::bslma::AllocatorTraits_SizeType< ALLOCATOR >::type size_type
Definition bslma_allocatortraits.h:1196
bsl::allocator_traits< ALLOCATOR >::pointer
BloombergLP::bslma::AllocatorTraits_PointerType< ALLOCATOR >::type pointer
Definition bslma_allocatortraits.h:1180
bsl::allocator_traits< ALLOCATOR >::difference_type
BloombergLP::bslma::AllocatorTraits_DifferenceType< ALLOCATOR >::type difference_type
Definition bslma_allocatortraits.h:1193
bsl::enable_if
Definition bslmf_enableif.h:530
bsl::from_range_t
Definition bslstl_ranges.h:301
bsl::integral_constant< bool, true >
bsl::is_convertible
Definition bslmf_isconvertible.h:875
bslalg::HasStlIterators
Definition bslalg_hasstliterators.h:99
bslma::UsesBslmaAllocator
Definition bslma_usesbslmaallocator.h:344