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