- Generated by
1.9.8
|
BDE 4.14.0 Production release
|
Provide a bucket-group locking (i.e., striped) unordered map.
This component provides a single concurrent (fully thread-safe) associative container, bdlcc::StripedUnorderedMap, that partitions the underlying hash table into a (user defined) number of "bucket groups" and controls access to each bucket group by a separate read-write lock. This design allows greater concurrency (and improved performance) than a bsl::unordered_map object protected by a single lock.
The terms "bucket", "load factor", and "rehash" have the same meaning as they do in the bslstl_unorderedmap component (see {bslstl_unorderedmap |Unordered Map Configuration}). A general introduction to these ideas can be found at: https://en.wikipedia.org/wiki/Hash_table
bdlcc::StripedUnorderedMap (and concurrent containers in general) does not provide iterators that allow users to manipulate or traverse the values of elements in a map. Alternatively, this container provides the setComputedValue method that allows users to change the value for a given key via a user provided functor and the visit method that will apply a user provided functor the value of every key in the map.
The bdlcc::StripedUnorderedMap class is an irregular value-semantic type, even if KEY and VALUE are VSTs. This class does not implement equality comparison, assignment operator, or copy constructor.
The bdlcc::StripedUnorderedMap class template is fully thread-safe (see {bsldoc_glossary |Fully Thread-Safe}), assuming that the allocator is fully thread-safe. Each method is executed by the calling thread.
Performance improves monotonically when the number of stripes increases. However, the rate of improvement decreases, and reaches a plateau. The plateau is reached roughly at four times the number of the threads concurrently using the hash map.
This container provides several set* methods and analogously named insert* methods having semantics that are identical except for the meaning of the return value. The rationale is best explained in the context of the bdlcc::StripedUnorderedMultiMap class. See {bdlcc_stripedunorderedmultimap |Set vs. Insert methods}. The behavior as seen in this component is the degenerate case when the number of elements updated (or inserted) is limited to 0 or 1.
A rehash operation is a re-organization of the hash map to a different number of buckets. This is a heavy operation that interferes with, but does not disallow, other operations on the container. Rehash is warranted when the current load factor exceeds the current maximum allowed load factor. Expressed explicitly:
This above condition is tested implicitly by several methods and if found true (and if rehash is enabled and rehash is not underway), a rehash is started. The methods that check the load factor are:
size()).maxLoadFactor(newMaxLoadFactor) method.rehash method.enableRehash and disableRehash methods are provided to control the rehash enable flag. Note that disabling rehash does not impact a rehash in progress.
In this section we show intended use of this component.
This example shows some basic usage of bdlcc::StripedUnorderedMap.
First, we define a bdlcc::StripedUnorderedMap object, myFriends, that maps int to bsl::string:
Notice that we are using the default value number of buckets, number of stripes, and allocator.
Then, we insert three elements into the map and verify that the size is the expected value:
Next, we demonstrate insertBulk by creating a vector of three key-value pairs and add them to the map using a single method call:
Then, we getValue method to retrieve the previously inserted string associated with the value 1:
Now, we change the value associated with 1 from "John" to "Jack" and confirm that the size of the map has not changed:
Finally, we erase the element (3, "Jim") from the map, confirm that the map size is decremented, and that element can no longer be found in the map:
This example uses the setComputedValue and update methods to keep track of user ID usage counts (stats). A striped unordered map has the user ID as the key, and the count as the value. There are 2 functors, one used to increase the count (and set it to 1 if the user ID has not been referenced yet), and the other is used to decrease the count.
First, define a functor, IncFunctor, that has parameters corresponding to the KEY and VALUE types of StatsMap and, when invoked, adds 1 to whatever existing value is associated with the given KEY value. As a new value is initialized with default (0), adding 1 to it works correctly:
Next, define a functor, DecFunctor, that has parameters corresponding to the KEY and VALUE types of StatsMap and, when invoked, subtracts 1 from whatever existing value is associated with the given KEY value:
Then, create myStats, a StatsMap object with (as we did in {Example 1} default number of buckets, number of stripes, and allocator:
Next, instantiate myIncFunctor and myDecFunctor from IncFunctor and DecFunctor, respectively:
Next, increase count for three user IDs:
Now, increase count for existing user IDs. Confirm that the values have been updated as expected.
Finally decrease count for existing user IDs. Confirm that the values have been updated as expected.
This example uses the visit method to apply a transformation (as defined by a functor) to the value of every key-value pair in the map. This example will construct a map from names (type bsl::string) to some (arbitrary) measure of salary (type int):
First, define a functor, mySalaryAdjustmentVisitor, that increases values above 1000 by 3% and lower values by 5%. The fractional part of increases are truncated to int values:
Then, default create mySalaries, a SalaryMap object:
Next, load mySalaries with some representative elements:
Now, apply mySalaryAdjustmentVisitor to every element in the map:
Finally, confirm that the values have been adjusted as expected:
1.9.8