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