BDE 4.14.0 Production release
Loading...
Searching...
No Matches
bslstl_unorderedmultiset
Group bsl » Package bslstl

Detailed Description

Outline

Purpose

Provide an STL-compliant unordered_multiset container.

Classes

Canonical header: bsl_unordered_set.h

See also
package bos+stdhdrs in the bos package group

Description

This component defines a single class template, bsl::unordered_multiset, implementing the standard container holding a collection of possibly duplicate keys with no guarantees on ordering (unless keys have the same value).

An instantiation of unordered_multiset is an allocator-aware, value-semantic type whose salient attributes are its size (number of keys) and the set of keys the unordered_multiset contains, without regard to their order. If unordered_multiset is instantiated with a key type that is not itself value-semantic, then it will not retain all of its value-semantic qualities. It is possible to instantiate unordered_multiset with a key type that does not have an accessible copy-constructor, in which case the unordered_multiset will not be copyable. Note that the equality operator for each element is used to determine when two unordered_multiset objects have the same value, and not the equality comparator supplied at construction.

An unordered_multiset meets the requirements of an unordered associative container with forward iterators in the C++11 standard [unord]. The unordered_multiset implemented here adheres to the C++11 standard, except that it may rehash when setting the max_load_factor in order to preserve the property that the value is always respected (which is a potentially throwing operation).

Requirements on KEY

An unordered_multiset instantiation is a fully "Value-Semantic Type" (see bsldoc_glossary ) only if the supplied KEY template parameter is fully value-semantic. It is possible to instantiate an unordered_multiset with a KEY parameter argument that does not provide a full set of value-semantic operations, but then some methods of the container may not be instantiable. The following terminology, adopted from the C++11 standard, is used in the function documentation of unordered_multiset to describe a function's requirements for the KEY template parameter. These terms are also defined in section [utility.arg.requirements] of the C++11 standard. Note that, in the context of an unordered_multiset instantiation, the requirements apply specifically to the unordered_multiset s element type, value_type, which is an alias for KEY.

Legend

X - denotes an allocator-aware container type (unordered_multiset ) T - value_type associated with X A - type of the allocator used by X m - lvalue of type A (allocator) p - address (T *) of uninitialized storage for a T within an X rv - rvalue of type (non-const) T v - rvalue or lvalue of type (possibly const) T args - 0 or more arguments

The following terms are used to more precisely specify the requirements on template parameter types in function-level documentation.

default-insertable: T has a default constructor. More precisely, T is default-insertable into X means that the following expression is well-formed:

allocator_traits<A>::construct(m, p)

move-insertable: T provides a constructor that takes an rvalue of type (non-const) T. More precisely, T is move-insertable into X means that the following expression is well-formed:

allocator_traits<A>::construct(m, p, rv)

copy-insertable: T provides a constructor that takes an lvalue or rvalue of type (possibly const) T. More precisely, T is copy-insertable into X means that the following expression is well-formed:

allocator_traits<A>::construct(m, p, v)

move-assignable: T provides an assignment operator that takes an rvalue of type (non-const) T.

copy-assignable: T provides an assignment operator that takes an lvalue or rvalue of type (possibly const) T.

emplace-constructible: T is emplace-constructible into X from args means that the following expression is well-formed:

allocator_traits<A>::construct(m, p, args)

erasable: T provides a destructor. More precisely, T is erasable from X means that the following expression is well-formed:

allocator_traits<A>::destroy(m, p)

equality-comparable: The type provides an equality-comparison operator that defines an equivalence relationship and is both reflexive and transitive.

Requirements on HASH and EQUAL

The (template parameter) types HASH and EQUAL must be copy-constructible function-objects. Note that this requirement is somewhat stronger than the requirement currently in the standard; see the discussion for Issue 2215 (http://cplusplus.github.com/LWG/lwg-active.html#2215);

HASH shall support a function call operator compatible with the following statements:

HASH hash;
KEY key;
std::size_t result = hash(key);

where the definition of the called function meets the requirements of a hash function, as specified in {bslstl_hash |Standard Hash Function}.

EQUAL shall support the a function call operator compatible with the following statements:

EQUAL equal;
KEY key1, key2;
bool result = equal(key1, key2);

where the definition of the called function defines an equivalence relationship on keys that is both reflexive and transitive.

HASH and EQUAL function-objects are further constrained, such for any two objects whose keys compare equal by the comparator, shall produce the same value from the hasher.

Memory Allocation

The type supplied as an unordered multiset's ALLOCATOR template parameter determines how that unordered multiset will allocate memory. The unordered_multiset template supports allocators meeting the requirements of the C++11 standard [allocator.requirements], and in addition it supports scoped-allocators derived from the bslma::Allocator memory allocation protocol. Clients intending to use bslma-style allocators should use the template's default ALLOCATOR type. The default type for the ALLOCATOR template parameter, bsl::allocator, provides a C++11 standard-compatible adapter for a bslma::Allocator object.

bslma-Style Allocators

If the parameterized ALLOCATOR type of an unordered_multiset instantiation is bsl::allocator, then objects of that unordered multiset type will conform to the standard behavior of a bslma-allocator-enabled type. Such an unordered multiset accepts an optional bslma::Allocator argument at construction. If the address of a bslma::Allocator object is explicitly supplied at construction, it will be used to supply memory for the unordered_multiset throughout its lifetime; otherwise, the unordered_multiset will use the default allocator installed at the time of the unordered_multiset s construction (see bslma_default ). In addition to directly allocating memory from the indicated bslma::Allocator, an unordered_multiset supplies that allocator's address to the constructors of contained objects of the (template parameter) type KEY with the bslalg::TypeTraitUsesBslmaAllocator trait.

Operations

This section describes the run-time complexity of operations on instances of unordered_multiset :

Legend
------
'K' - (template parameter) type 'KEY' of the unordered multiset
'a', 'b' - two distinct objects of type 'unordered_multiset<K>'
'rv' - modifiable rvalue of type 'unordered_multiset<K>'
'n', 'm' - number of elements in 'a' and 'b' respectively
'w' - number of buckets of 'a'
'value_type' - unordered_multiset<K>::value_type
'hf' - hash function for objects of type 'K'
'eq' - equality comparator for objects of type 'K'
'al' - STL-style memory allocator
'i1', 'i2' - two iterators defining a sequence of 'value_type' objects
'li' - object of type 'initializer_list<K>'
'k' - object of type 'K'
'rk' - modifiable rvalue of type 'K'
'v' - object of type 'value_type'
'p1', 'p2' - two 'const_iterator's belonging to 'a'
distance(i1,i2) - number of elements in the range '[i1 .. i2)'
distance(p1,p2) - number of elements in the range '[p1 .. p2)'
+----------------------------------------------------+--------------------+
| Operation | Complexity |
+====================================================+====================+
| unordered_multiset<K> a; (default construction)| O[1] |
| unordered_multiset<K> a(al); | |
+----------------------------------------------------+--------------------+
| unordered_multiset<K> a(b); (copy construction) | Average: O[n] |
| unordered_multiset<K> a(b, al); | Worst: O[n^2] |
+----------------------------------------------------+--------------------+
| unordered_multiset<K> a(rv); (move construction) | O[1] if 'a' and |
| unordered_multiset<K> a(rv, al); | 'rv' use the same |
| | allocator; |
| | otherwise, |
| | Average: O[n] |
| | Worst: O[n^2] |
+----------------------------------------------------+--------------------+
| unordered_multiset<K> a(li); | Average: O[N] |
| unordered_multiset<K> a(li, al); | Worst: O[N^2] |
| unordered_multiset<K> a(li, w, al); | where N = |
| unordered_multiset<K> a(li, w, hf, al); | 'li.size()'|
| unordered_multiset<K> a(li, w, hf, eq, al); | |
+----------------------------------------------------+--------------------+
| unordered_multiset<K> a(w); | O[n] |
| unordered_multiset<K> a(w, hf); | |
| unordered_multiset<K> a(w, hf, eq); | |
| unordered_multiset<K> a(w, hf, eq, al); | |
+----------------------------------------------------+--------------------+
| unordered_multiset<K> a(i1, i2); | Average: O[ |
| unordered_multiset<K> a(i1, i2, w) | distance(i1, i2)]|
| unordered_multiset<K> a(i1, i2, w, hf); | Worst: O[n^2] |
| unordered_multiset<K> a(i1, i2, w, hf, eq); | |
| unordered_multiset<K> a(i1, i2, w, hf, eq, al); | |
+----------------------------------------------------+--------------------+
| a.~unordered_multiset<K>(); (destruction) | O[n] |
+----------------------------------------------------+--------------------+
| a = b; (copy assignment) | Average: O[n] |
| | Worst: O[n^2] |
+----------------------------------------------------+--------------------+
| a = rv; (move assignment) | O[1] if 'a' and |
| | 'rv' use the same |
| | allocator; |
| | otherwise, |
| | Average: O[n] |
| | Worst: O[n^2] |
+----------------------------------------------------+--------------------+
| a = li; | Average: O[N] |
| | Worst: O[N^2] |
| | where N = |
| | 'li.size()'|
+----------------------------------------------------+--------------------+
| a.begin(), a.end(), a.cbegin(), a.cend(), | O[1] |
+----------------------------------------------------+--------------------+
| a == b, a != b | Best: O[n] |
| | Worst: O[n^2] |
+----------------------------------------------------+--------------------+
| a.swap(b), swap(a, b) | O[1] |
+----------------------------------------------------+--------------------+
| a.key_eq() | O[1] |
+----------------------------------------------------+--------------------+
| a.hash_function() | O[1] |
+----------------------------------------------------+--------------------+
| a.size() | O[1] |
+----------------------------------------------------+--------------------+
| a.max_size() | O[1] |
+----------------------------------------------------+--------------------+
| a.empty() | O[1] |
+----------------------------------------------------+--------------------+
| get_allocator() | O[1] |
+----------------------------------------------------+--------------------+
| a.insert(v) | Average: O[1] |
| a.insert(rk) | Worst: O[n] |
| a.emplace(Args&&...) | |
+----------------------------------------------------+--------------------+
| a.insert(p1, v) | Average: O[1] |
| a.insert(p1, rk) | Worst: O[n] |
| a.emplace_hint(p1, Args&&...) | |
+----------------------------------------------------+--------------------+
| a.insert(i1, i2) | Average O[ |
| | distance(i1, i2)]|
| | Worst: O[ n * |
| | distance(i1, i2)]|
+----------------------------------------------------+--------------------+
| a.insert(li); | Average: O[N] |
| | Worst: O[n * N] |
| | where N = |
| | 'li.size()'|
+----------------------------------------------------+--------------------+
| a.erase(p1) | Average: O[1] |
| | Worst: O[n] |
+----------------------------------------------------+--------------------+
| a.erase(k) | Average: O[ |
| | a.count(k)]|
| | Worst: O[n] |
+----------------------------------------------------+--------------------+
| a.erase(p1, p2) | Average: O[ |
| | distance(p1, p2)]|
| | Worst: O[n] |
+----------------------------------------------------+--------------------+
| a.clear() | O[n] |
+----------------------------------------------------+--------------------+
| a.find(k) | Average: O[1] |
| | Worst: O[n] |
+----------------------------------------------------+--------------------+
| a.contains(k) | Average: O[1] |
| | Worst: O[n] |
+----------------------------------------------------+--------------------+
| a.count(k) | Average: O[1] |
| | Worst: O[n] |
+----------------------------------------------------+--------------------+
| a.equal_range(k) | Average: O[ |
| | a.count(k)]|
| | Worst: O[n] |
+----------------------------------------------------+--------------------+
| a.bucket_count() | O[1] |
+----------------------------------------------------+--------------------+
| a.max_bucket_count() | O[1] |
+----------------------------------------------------+--------------------+
| a.bucket(k) | O[1] |
+----------------------------------------------------+--------------------+
| a.bucket_size(k) | O[a.bucket_size(k)]|
+----------------------------------------------------+--------------------+
| a.load_factor() | O[1] |
+----------------------------------------------------+--------------------+
| a.max_load_factor() | O[1] |
| a.max_load_factor(z) | O[1] |
+----------------------------------------------------+--------------------+
| a.rehash(k) | Average: O[n] |
| | Worst: O[n^2] |
+----------------------------------------------------+--------------------+
| a.reserve(k) | Average: O[n] |
| | Worst: O[n^2] |
+----------------------------------------------------+--------------------+

Iterator, Pointer, and Reference Invalidation

No method of unordered_multiset invalidates a pointer or reference to an element in the unordered multiset, unless it also erases that element, such as any erase overload, clear, or the destructor (that erases all elements). Pointers and references are stable through a rehash.

Iterators to elements in the container are invalidated by any rehash, so iterators may be invalidated by an insert or emplace call if it triggers a rehash (but not otherwise). Iterators to specific elements are also invalidated when that element is erased. Note that the end iterator is not an iterator referring to any element in the container, so may be invalidated by any non-const method.

Unordered Multiset Configuration

The unordered multiset has interfaces that can provide insight into and control of its inner workings. The syntax and semantics of these interfaces for bslstl_unorderedmultiset are identical to those of bslstl_unorderedmap . See the discussion in {bslstl_unorderedmap |Unordered Map Configuration} and the illustrative material in {bslstl_unorderedmap |Example 2}.

Practical Requirements on HASH

An important factor in the performance of an unordered multiset (and any of the other unordered containers) is the choice of hash function. Please see the discussion in {bslstl_unorderedmap |Practical Requirements on HASH}.

Usage

In this section we show intended use of this component.

Example 1: Categorizing Data

Unordered sets are useful in situations when there is no meaningful way to order key values, when the order of the values is irrelevant to the problem domain, and (even if there is a meaningful ordering) the value of ordering the results is outweighed by the higher performance provided by unordered sets (compared to ordered sets).

One uses a multiset (ordered or unordered) when there may be more than one instance of an element of a set and when that multiplicity must be preserved.

Note that the data type described below is an augmentation of that used in {bslstl_unorderedset |Example 1}. The data itself (randomly generated) is different.

Suppose one is analyzing data on a set of customers, and each customer is categorized by several attributes: customer type, geographic area, and (internal) project code; and that each attribute takes on one of a limited set of values. Additionally, there is some financial data associated with each customer: past sales and pending sales.

The several customer attributes are modeled by several enumerations:

typedef enum {
REPEAT
, DISCOUNT
, IMPULSE
, NEED_BASED
, BUSINESS
, NON_PROFIT
, INSTITUTE
// ...
} CustomerCode;
typedef enum {
USA_EAST
, USA_WEST
, CANADA
, MEXICO
, ENGLAND
, SCOTLAND
, FRANCE
, GERMANY
, RUSSIA
// ...
} LocationCode;
typedef enum {
TOAST
, GREEN
, FAST
, TIDY
, PEARL
, SMITH
// ...
} ProjectCode;

For printing these values in a human-readable form, we define these helper functions:

static const char *toAscii(CustomerCode value)
{
switch (value) {
case REPEAT: return "REPEAT";
case DISCOUNT: return "DISCOUNT";
case IMPULSE: return "IMPULSE";
case NEED_BASED: return "NEED_BASED";
case BUSINESS: return "BUSINESS";
case NON_PROFIT: return "NON_PROFIT";
case INSTITUTE: return "INSTITUTE";
// ...
default: return "(* UNKNOWN *)";
}
}
static const char *toAscii(LocationCode value)
{
...
}
static const char *toAscii(ProjectCode value)
{
...
}

The data set (randomly generated for this example) is provided in a statically initialized array:

static const struct CustomerDatum {
CustomerCode d_customer;
LocationCode d_location;
ProjectCode d_project;
double d_past;
double d_pending;
} customerData[] = {
{ REPEAT , RUSSIA , SMITH, 75674.00, 455.00 },
{ REPEAT , ENGLAND , TOAST, 35033.00, 8377.00 },
{ BUSINESS , USA_EAST, SMITH, 53942.00, 2782.00 },
...
{ DISCOUNT , MEXICO , GREEN, 99737.00, 3872.00 },
};
const int numCustomerData = sizeof customerData / sizeof *customerData;

Suppose, as a step in analysis, we wish to determine the average of the past sales and the average of the pending sales for each customer for each unique combination of customer attributes (i.e., for each customer profile in the data set). To do so, we must aggregate our data items by customer profile but also retain the unique financial data for each item. The bslstl_unorderedmultiset provides those semantics.

First, as there are no standard methods for hashing or comparing our user- defined types, we define CustomerDatumHash and CustomerDatumEqual classes, each a stateless functor. Note that there is no meaningful ordering of the attribute values, they are merely arbitrary code numbers; nothing is lost by using an unordered multiset instead of an ordered multiset:

class CustomerDatumHash
{
public:
// CREATORS
/// Create a `CustomerDatumHash` object.
//! CustomerDatumHash() = default;
/// Create a `CustomerDatumHash` object. Note that as
/// `CustomerDatumHash` is an empty (stateless) type, this operation
/// has no observable effect.
//! hash(const CustomerDatumHash& original) = default;
/// Destroy this object.
//! ~CustomerDatumHash() = default;
// ACCESSORS
/// Return a hash value computed using the specified `x`.
std::size_t operator()(CustomerDatum x) const;
};
// ACCESSORS
std::size_t CustomerDatumHash::operator()(CustomerDatum x) const
{
return bsl::hash<int>()(x.d_location * 100 * 100
+ x.d_customer * 100
+ x.d_project);
}
class CustomerDatumEqual
{
public:
// CREATORS
/// Create a `CustomerDatumEqual` object.
//! CustomerDatumEqual() = default;
/// Create a `CustomerDatumEqual` object. Note that as
/// `CustomerDatumEqual` is an empty (stateless) type, this
/// operation has no observable effect.
//! CustomerDatumEqual(const CustomerDatumEqual& original) = default;
/// Destroy this object.
//! ~CustomerDatumEqual() = default;
// ACCESSORS
bool operator()(const CustomerDatum& lhs,
const CustomerDatum& rhs) const;
};
// ACCESSORS
bool CustomerDatumEqual::operator()(const CustomerDatum& lhs,
const CustomerDatum& rhs) const
{
return lhs.d_location == rhs.d_location
&& lhs.d_customer == rhs.d_customer
&& lhs.d_project == rhs.d_project;
}
bsl::hash
Definition bslstl_hash.h:498

Notice that many of the required methods of the hash and comparator types are compiler generated. (The declaration of those methods are commented out and suffixed by an = default comment.)

Also notice that the boolean operation provided by CustomerDatumEqual is more properly thought of as "equivalence", not "equality". There may be more than one data item with the same customer profile (i.e., the same for our purpose here), but they have distinct financial data so the two items are not equal (unless the financial data also happens to match).

Next, we define the type of the unordered multiset and a convenience aliases:

typedef bsl::unordered_multiset<CustomerDatum,
CustomerDatumHash,
CustomerDatumEqual> DataByProfile;
typedef DataByProfile::const_iterator DataByProfileConstItr;
bsl::unordered_multiset
Definition bslstl_unorderedmultiset.h:770

Now, create a helper function to calculate the average financials for a category of customer profiles within the unordered multiset.

/// Print to the specified `out` in some human-readable format the
/// averages of the `past` and `pending` attributes of every
/// `CustomerInfoData` object from the specified `start` up to (but not
/// including) the specified `end`. The behavior is undefined unless
/// `end != start`.
void processCategory(DataByProfileConstItr start,
DataByProfileConstItr end,
FILE *out)
{
assert(end != start);
assert(out);
double sumPast = 0.0;
double sumPending = 0.0;
int count = 0;
for (DataByProfileConstItr itr = start; end != itr; ++itr) {
sumPast += itr->d_past;
sumPending += itr->d_pending;
++count;
}
printf("%-10s %-8s %-5s %10.2f %10.2f\n",
toAscii(start->d_customer),
toAscii(start->d_location),
toAscii(start->d_project),
sumPast/count,
sumPending/count);
}

Then, we create an unordered multiset and insert each item of data.

DataByProfile dataByProfile;
for (int idx = 0; idx < numCustomerData; ++idx) {
dataByProfile.insert(customerData[idx]);
}
assert(numCustomerData == dataByProfile.size());

Finally, to calculate the statistics we need, we must detect the transition between categories as we iterate through customerInfoData.

CustomerDatumEqual areEquivalent;
DataByProfileConstItr end = dataByProfile.end();
DataByProfileConstItr startOfCategory = end;
for (DataByProfileConstItr itr = dataByProfile.begin();
end != itr; ++itr) {
if (end == startOfCategory) {
startOfCategory = itr;
continue;
}
if (!areEquivalent(*startOfCategory, *itr)) {
processCategory(startOfCategory, itr, stdout);
startOfCategory = itr;
}
}
if (end != startOfCategory) {
processCategory(startOfCategory, end, stdout);
}

We find on standard output:

BUSINESS GERMANY TIDY 84553.00 3379.00
DISCOUNT ENGLAND TIDY 74110.00 2706.00
NEED_BASED CANADA FAST 97479.00 681.00
...
NEED_BASED SCOTLAND TOAST 27306.00 5084.50
INSTITUTE CANADA TIDY 83528.00 4722.33
NEED_BASED FRANCE FAST 83741.50 5396.50
REPEAT MEXICO TOAST 7469.00 5958.00
BUSINESS SCOTLAND FAST 24443.00 4247.00
INSTITUTE FRANCE FAST 19349.00 3982.00
NEED_BASED RUSSIA TIDY 50712.00 8647.00
INSTITUTE SCOTLAND TIDY 78240.00 6635.00
BUSINESS RUSSIA PEARL 29386.00 3623.00
INSTITUTE FRANCE PEARL 47747.00 3533.00