- Generated by
1.9.8
|
BDE 4.14.0 Production release
|
Provide a hash-container with support for duplicate values.
This component defines a single class template, HashTable, implementing a value-semantic container that can be used to easily implement the four unordered containers specified by the C++11 standard.
An instantiation of HashTable is an allocator-aware, value-semantic type whose salient attributes are its size (number of keys) and the ordered sequence of keys the HashTable contains. If HashTable is instantiated with a key type that is not itself value-semantic, then it will not retain all of its value-semantic qualities. In particular, if the key type cannot be tested for equality, then a HashTable containing that type cannot be tested for equality. It is even possible to instantiate HashTable with a key type that does not have a copy-constructor, in which case the HashTable will not be copyable.
The elements stored in a HashTable and the key by which they are indexed are defined by a KEY_CONFIG template type parameter. The user-supplied KEY_CONFIG type must provide two type aliases named ValueType and KeyType that name the type of element stored and its associated key type respectively. In addition, a KEY_CONFIG class shall provide a static member function which may be called as if it had the following signature:
Optionally, the KEY_CONFIG class might provide an extractKey function with the alternative signature:
This alternative signature is necessary to support the rare case that a hash function or comparator used to configure the HashTable template below take their arguments by non-const reference. This is subject to additional constraints that these functions may not modify the passed arguments, and is inherently a fragile interface and not recommended. It is supported only for C++ Standard conformance.
A HashTable is a "Value-Semantic Type" (see bsldoc_glossary ) only if the configured ValueType is value-semantic. It is possible to instantiate a HashTable configured with a ValueType that does not provide a full HashTable 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 HashTable to describe a function's requirements for the KEY template parameter. These terms are also defined in [utility.arg.requirements] (section 17.6.3.1 of the C++11 standard). Note that, in the context of a HashTable instantiation, the requirements apply specifically to the HashTables element type, ValueType.
X - denotes an allocator-aware container type (e.g., unordered_set) 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.
The type supplied as a HashTable's ALLOCATOR template parameter determines how that HashTable will allocate memory. The HashTable template supports allocators meeting the requirements of the C++ standard allocator requirements ([allocator.requirements], C++11 17.6.3.5); 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.
If the parameterized ALLOCATOR type of an HashTable instantiation is bsl::allocator, then objects of that HashTable type will conform to the standard behavior of a bslma-allocator-enabled type. Such a HashTable 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 HashTable throughout its lifetime; otherwise, the HashTable will use the default allocator installed at the time of the HashTable's construction (see bslma_default ). In addition to directly allocating memory from the indicated bslma::Allocator, a HashTable supplies that allocator's address to the constructors of contained objects of the configured ValueType with the bslalg::TypeTraitUsesBslmaAllocator trait.
The operations of a HashTable provide the strong exception guarantee (see bsldoc_glossary ) except in the presence of a hash-functor or equality-comparator that throws exceptions. If either the hash-functor or equality-comparator throws an exception from a non-const method, HashTable provides only the basic exception guarantee, and the operation will leave the container in a valid but unspecified (potentially empty) state.
This implementation of a hash-table uses a single bidirectional list, to hold all the elements stored in the container, and the elements in this list are indexed by a dynamic array of buckets, each of which holds a pointer to the first and last element in the linked-list whose adjusted hash-values are equal to that bucket's index.
As we do not cache the hashed value, if any hash function throws we will either do nothing and allow the exception to propagate, or, if some change of state has already been made, clear the whole container to provide the basic exception guarantee. There are similar concerns for the COMPARATOR predicate.
This section illustrates intended use of this component. The bslstl::HashTable class template provides a common foundation for implementing the four standard unordered containers:
bsl::unordered_mapbsl::unordered_multisetbsl::unordered_multimapbsl::unordered_set This and the subsequent examples in this component use the bslstl::HashTable class to implement several model container classes, each providing a small but representative sub-set of the functionality of one of the standard unordered containers.Suppose we wish to implement, MyHashedSet, a greatly abbreviated version of bsl::unordered_set. The bslstl::HashTable class template can be used as the basis of that implementation.
First, we define UseEntireValueAsKey, a class template we can use to configure bslstl::HashTable to use its entire elements as keys for its hasher, a policy suitable for a set container. (Later, in {Example 2}, we will define UseFirstValueOfPairAsKey for use in a map container. Note that, in practice, developers can use the existing classes in bslstl_unorderedmapkeyconfiguration and bslstl_unorderedsetkeyconfiguration .)
Next, we define our MyHashedSet class template with an instance of bslstl::HashTable (configured using UseEntireValueAsKey) as its sole data member. We provide insert method, to allow us to populate these sets, and the find method to allow us to examine those elements. We also provide size and bucket_count accessor methods to let us check the inner workings of our class.
Note that the standard classes define aliases for the templated parameters and other types. In the interest of brevity, this model class (and the classes in the subsequent examples) do not define such aliases except where strictly needed for the example.
Next, we implement the methods of MyHashedSet. In many cases, the implementations consist mainly in forwarding arguments to and returning values from the underlying bslstl::HashTable.
Note that the insertIfMissing method of bslstl::HashTable provides the semantics needed for adding values (unique values only) to sets.
Finally, we create mhs, an instance of MyHashedSet, exercise it, and confirm that it behaves as expected.
Notice that the newly created set is empty and has a single bucket.
Inserting a value (10) succeeds the first time but correctly fails on the second attempt.
We can insert a different value (20) and thereby increase the set size to 2.
Each of the inserted values (10, 20) can be found in the set.
However, a value known to absent from the set (0), is correctly reported as not there.
Suppose we wish to implement, MyHashedMap, a greatly abbreviated version of bsl::unordered_map. As with MyHashedSet (see {Example 1}), the bslstl::HashTable class template can be used as the basis of our implementation.
First, we define UseFirstValueOfPairAsKey, a class template we can use to configure bslstl::HashTable to use the first member of each element, each a bsl::pair, as the key-value for hashing. Note that, in practice, developers can use class defined in bslstl_unorderedmapkeyconfiguration .
Next, we define our MyHashedMap class template with an instance of bslstl::HashTable (configured using UseFirstValueOfPairAsKey) as its sole data member. In this example, we choose to implement operator[] (corresponding to the signature method of bsl::unordered_map) to allow us to populate our maps and to examine their elements.
Then, we implement the methods MyHashedMap. The construct need merely forward its arguments to the constructor of d_impl,
As with MyHashedSet, the insertIfMissing method of bslstl::HashTable provides the semantics we need: an element is inserted only if no such element (no element with the same key) in the container, and a reference to that element (node) is returned. Here, we use node to obtain and return a reference offering modifiable access to the second member of the (possibly newly added) element. Note that the static_cast from HashTableLink * to HashTableNode * is valid because the nodes derive from the link type (see bslalg_bidirectionallink and bslalg_hashtableimputil ).
Finally, we create mhm, an instance of MyHashedMap, exercise it, and confirm that it behaves as expected. We can add an element (with key value of 0).
We can change the value of the element with key value 0.
We can add a new element (key value 1), without changing the previously existing element (key value 0).
Accessing a non-existing element (key value 2) creates that element and populates it with the default value of the mapped value (0.0).
Suppose we wish to implement, MyHashedMultiMap, a greatly abbreviated version of bsl::unordered_multimap. As with MyHashedSet and MyHashedMap (see {Example 1}, and {Example 2}, respectively), the bslstl::HashTable class template can be used as the basis of our implementation.
First, we need a class template to configure bslstl::HashTable to extract key values in manner appropriate for maps. The previously defined UseFirstValueOfPairAsKey class template (see {Example 2}) suits perfectly.
Next, we define our MyHashedMultiMap class template with an instance of bslstl::HashTable (configured using UseFirstValueOfPairAsKey) as its sole data member. In this example, we choose to implement an insert method to populate our container, and an equal_range method (a signature method of the multi containers) to provide access to those elements.
Then, we implement the methods MyHashedMultiMap. The construct need merely forward its arguments to the constructor of d_impl,
Note that here we forgo use of the insertIfMissing method and use the insert method of bslstl::HashTable. This method supports the semantics of the multi containers: there can be more than one element with the same key value.
The equal_range method need only convert the values returned by the findRange method to the types expected by the caller.
Finally, we create mhmm, an instance of MyHashedMultiMap, exercise it, and confirm that it behaves as expected.
We define several aliases to make our code more concise.
Searching for an element (key value 10) in a newly created, empty container correctly shows the absence of any such element.
We can insert a value (the pair 10, 100.00) into the container...
... and we can do so again.
We can now find elements with the key value of 10.
As expected, there are two such elements, and both are identical in key value (10) and mapped value (100.00).
}
Although the bslstl::HashTable class was created to be a common implementation for the standard unordered classes, this class can also be used in its own right to address other user problems.
Suppose that we wish to retain a record of sales orders, that each record is characterized by several integer attributes, and that we must be able to find records based on any of those attributes. We can use bslstl::HashTable to implement a custom container supporting multiple key-values.
First, we define MySalesRecord, our record class:
Notice that only each orderNumber is unique. We expect multiple sales to any given customer (customerId) and multiple sales by any given vendor (vendorId).
We will use a bslstl::HashTable object (a hashtable) to save record values based on the unique orderNumber, and two auxiliary hashtables to provide map customerId and vendorId values to the addresses of the records in the first bslstl::HashTable object. Note that this implementation relies on the fact that nodes in our hashtables remain stable until they are removed and that in this application we do not allow the removal (or modification) of records once they are inserted.
To configure these hashtables, we will need several policy objects to extract relevant portions the MySalesRecord objects for hashing.
Next, define UseOrderNumberAsKey, a policy class for the hashtable holding the sales record objects. Note that the ValueType is MySalesRecord and that the extractKey method selects the orderNumber attribute:
Then, we define UseCustomerIdAsKey, the policy class for the hashtable that will multiply map customerId to the addresses of records in the first hashtable. Note that in this policy class the ValueType is const MySalesRecord *.
Notice that, since the values in the second hashtable are addresses, the key-value is extracted by reference. This second hashtable allows what map-like semantics, without having to store key-values; those reside in the records in the first hashtable.
The UseVendorIdAsKey class, the policy class for the hashtable providing an index by vendorId, is almost a near clone of UseCustomerIdAsKey. It is shown for completeness:
Next, we define MySalesRecordContainer, our customized container:
The ItrByOrderNumber type is used to provide access to the elements of the first hash table, the one that stores the records.
The ItrPtrById type is used to provide access to the elements of the other hashtables, the ones that store pointers into the first hashtable.
If we were to provide iterators of type ItrPtrById to our users, dereferencing the iterator would provide a MySalesRecord pointer, which would then have to be dereferences. Instead, we use ItrPtrById to define ItrById in which accessors have been overridden to provide that extra dereference implicitly.
Notice that this interface provides map-like semantics for finding records. We need only specify the orderNumber attribute of the record of interest; however, the return value is set-like: we get access to the record, not the more complicated key-value/record pair that a map would have provided.
Internally, the hash table need only store the records themselves. A map would have had to manage key-value/record pairs, where the key-value would be a copy of part of the record.
Then, we implement the methods of MySalesRecordContainer, our customized container:
Now, create an empty container and load it with some sample data.
We find on standard output:
We can search our container by order number and find the expected records.
We find on standard output:
We can search our container by customer identifier and find the expected records.
We find on standard output:
Lastly, we can search our container by vendor identifier and find the expected records.
We find on standard output:
1.9.8