|
Quick Links: |
Provide a hash-container with support for duplicate values. More...
Namespaces | |
| namespace | bslstl |
| bslstl::HashTable | hashed-table container for user-supplied object types |
HashTable, implementing a value-semantic container that can be used to easily implement the four unordered containers specified by the C++11 standard. 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. 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: static const KeyType& extractKey(const ValueType& value); // Return a reference offering non-modifiable access to the key for the // specified 'value'.
KEY_CONFIG class might provide an extractKey function with the alternative signature: static KeyType& extractKey(ValueType& value); // Return a reference to the key for the specified 'value'.
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. 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 T has a default constructor. More precisely, T is default-insertable into X means that the following expression is well-formed: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. 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. 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. COMPARATOR predicate. bslstl::HashTable class template provides a common foundation for implementing the four standard unordered containers:
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. MyHashedSet, a greatly abbreviated version of bsl::unordered_set. The bslstl::HashTable class template can be used as the basis of that implementation. 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.) // ========================== // struct UseEntireValueAsKey // ========================== template <class VALUE_TYPE> struct UseEntireValueAsKey { // This 'struct' provides a namespace for types and methods that define // the policy by which the key value of a hashed container (i.e., the // value passed to the hasher) is extracted from the objects stored in // the hashed container (the 'value' type). typedef VALUE_TYPE ValueType; // Alias for 'VALUE_TYPE', the type stored in the hashed container. typedef ValueType KeyType; // Alias for the type passed to the hasher by the hashed container. // In this policy, that type is 'ValueType'. static const KeyType& extractKey(const ValueType& value); // Return the key value for the specified 'value'. In this policy, // that is 'value' itself. }; // -------------------------- // struct UseEntireValueAsKey // -------------------------- template <class VALUE_TYPE> inline const typename UseEntireValueAsKey<VALUE_TYPE>::KeyType& UseEntireValueAsKey<VALUE_TYPE>::extractKey( const ValueType& value) { return value; }
MyPair, a class template that can hold a pair of values of arbitrary types. This will be used to in MyHashedSet to return the status of the insert method, which must provide an iterator to the inserted value and a boolean value indicating if the value is newly inserted if it previously exiting in the set. The MyPair class template will also appear in Example 2 and Example 3. Note that in practice, users can use the standard bsl::pair in this role; the MyPair class template is used in these examples to avoid creating a dependency of bslstl_hashtable on bslstl_pair. // ============= // struct MyPair // ============= template <class FIRST_TYPE, class SECOND_TYPE> struct MyPair { // PUBLIC TYPES typedef FIRST_TYPE first_type; typedef SECOND_TYPE second_type; // DATA first_type first; second_type second; // CREATORS MyPair(); // Create a 'MyPair' object with a default constructed 'first' // member and a default constructed 'second' member. MyPair(first_type firstValue, second_type secondValue); // Create a 'MyPair' object with a 'first' member equal to the // specified 'firstValue' and the 'second' member equal to the // specified 'secondValue'. }; // FREE OPERATORS template <class FIRST_TYPE, class SECOND_TYPE> inline bool operator==(const MyPair<FIRST_TYPE, SECOND_TYPE>& lhs, const MyPair<FIRST_TYPE, SECOND_TYPE>& rhs); // Return 'true' if the specified 'lhs' and 'rhs' MyPair objects have // the same value, and 'false' otherwise. 'lhs' has the same value as // 'rhs' if 'lhs.first == rhs.first' and 'lhs.second == rhs.second'. template <class FIRST_TYPE, class SECOND_TYPE> inline bool operator!=(const MyPair<FIRST_TYPE, SECOND_TYPE>& lhs, const MyPair<FIRST_TYPE, SECOND_TYPE>& rhs); // Return 'true' if the specified 'lhs' and 'rhs' MyPair objects do not // have the same value, and 'false' otherwise. 'lhs' does not have the // same value as 'rhs' if 'lhs.first != rhs.first' or // 'lhs.second != rhs.second'. // ------------- // struct MyPair // ------------- // CREATORS template <class FIRST_TYPE, class SECOND_TYPE> inline MyPair<FIRST_TYPE,SECOND_TYPE>::MyPair() : first() , second() { } template <class FIRST_TYPE, class SECOND_TYPE> inline MyPair<FIRST_TYPE,SECOND_TYPE>::MyPair( first_type firstValue, second_type secondValue) : first(firstValue) , second(secondValue) { } // FREE OPERATORS template <class FIRST_TYPE, class SECOND_TYPE> inline bool operator==(const MyPair<FIRST_TYPE, SECOND_TYPE>& lhs, const MyPair<FIRST_TYPE, SECOND_TYPE>& rhs) { return lhs.first == rhs.first && lhs.second == rhs.second; } template <class FIRST_TYPE, class SECOND_TYPE> inline bool operator!=(const MyPair<FIRST_TYPE, SECOND_TYPE>& lhs, const MyPair<FIRST_TYPE, SECOND_TYPE>& rhs) { return lhs.first != rhs.first || lhs.second != rhs.second; }
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. // ================= // class MyHashedSet // ================= template <class KEY, class HASH = bsl::hash<KEY>, class EQUAL = bsl::equal_to<KEY>, class ALLOCATOR = bsl::allocator<KEY> > class MyHashedSet { private: // PRIVATE TYPES typedef bsl::allocator_traits<ALLOCATOR> AllocatorTraits; typedef typename AllocatorTraits::difference_type difference_type; typedef BloombergLP::bslstl::HashTableIterator<const KEY, difference_type> iterator; // DATA BloombergLP::bslstl::HashTable<UseEntireValueAsKey<KEY>, HASH, EQUAL, ALLOCATOR> d_impl; public: // TYPES typedef typename AllocatorTraits::size_type size_type; typedef iterator const_iterator; // CREATORS explicit MyHashedSet(size_type initialNumBuckets = 0, const HASH& hash = HASH(), const EQUAL& keyEqual = EQUAL(), const ALLOCATOR& allocator = ALLOCATOR()); // Create an empty 'MyHashedSet' object having a maximum load // factor of 1. Optionally specify at least 'initialNumBuckets' in // this container's initial array of buckets. If // 'initialNumBuckets' is not supplied, an implementation defined // value is used. Optionally specify a 'hash' used to generate the // hash values associated to the keys extracted from the values // contained in this object. If 'hash' is not supplied, a // default-constructed object of type 'HASH' is used. Optionally // specify a key-equality functor 'keyEqual' used to verify that // two key values are the same. If 'keyEqual' is not supplied, a // default-constructed object of type 'EQUAL' is used. Optionally // specify an 'allocator' used to supply memory. If 'allocator' is // not supplied, a default-constructed object of the (template // parameter) type 'ALLOCATOR' is used. If the 'ALLOCATOR' is // 'bsl::allocator' (the default), then 'allocator' shall be // convertible to 'bslma::Allocator *'. If the 'ALLOCATOR' is // 'bsl::allocator' and 'allocator' is not supplied, the currently // installed default allocator is used to supply memory. // Destroy this object. // MANIPULATORS MyPair<const_iterator, bool> insert(const KEY& value); // Insert the specified 'value' into this set if the 'value' does // not already exist in this set; otherwise, this method has no // effect. Return a pair whose 'first' member is an iterator // providing non-modifiable access to the (possibly newly inserted) // 'KEY' object having 'value' (according to 'EQUAL') and whose // 'second' member is 'true' if a new element was inserted, and // 'false' if 'value' was already present. // ACCESSORS size_type bucket_count() const; // Return the number of buckets in this set. const_iterator cend() const; // Return an iterator providing non-modifiable access to the // past-the-end element (in the sequence of 'KEY' objects) // maintained by this set. const_iterator find(const KEY& value) const; // Return an iterator providing non-modifiable access to the 'KEY' // object in this set having the specified 'value', if such an // entry exists, and the iterator returned by the 'cend' method // otherwise. size_type size() const; // Return the number of elements in this set. };
MyHashedSet. In many cases, the implementations consist mainly in forwarding arguments to and returning values from the underlying bslstl::HashTable. // ================= // class MyHashedSet // ================= // CREATORS template <class KEY, class HASH, class EQUAL, class ALLOCATOR> inline MyHashedSet<KEY, HASH, EQUAL, ALLOCATOR>::MyHashedSet( size_type initialNumBuckets, const HASH& hash, const EQUAL& keyEqual, const ALLOCATOR& allocator) : d_impl(hash, keyEqual, initialNumBuckets, allocator) { }
insertIfMissing method of bslstl::HashTable provides the semantics needed for adding values (unique values only) to sets. // MANIPULATORS template <class KEY, class HASH, class EQUAL, class ALLOCATOR> inline MyPair<typename MyHashedSet<KEY, HASH, EQUAL, ALLOCATOR>::iterator, bool> MyHashedSet<KEY, HASH, EQUAL, ALLOCATOR>::insert( const KEY& value) { typedef MyPair<iterator, bool> ResultType; bool isInsertedFlag = false; bslalg::BidirectionalLink *result = d_impl.insertIfMissing( &isInsertedFlag, value); return ResultType(iterator(result), isInsertedFlag); } // ACCESSORS template <class KEY, class HASH, class EQUAL, class ALLOCATOR> inline typename MyHashedSet<KEY, HASH, EQUAL, ALLOCATOR>::size_type MyHashedSet<KEY, HASH, EQUAL, ALLOCATOR>::bucket_count() const { return d_impl.numBuckets(); } template <class KEY, class HASH, class EQUAL, class ALLOCATOR> inline typename MyHashedSet<KEY, HASH, EQUAL, ALLOCATOR>::const_iterator MyHashedSet<KEY, HASH, EQUAL, ALLOCATOR>::cend() const { return const_iterator(); } template <class KEY, class HASH, class EQUAL, class ALLOCATOR> inline typename MyHashedSet<KEY, HASH, EQUAL, ALLOCATOR>::const_iterator MyHashedSet<KEY, HASH, EQUAL, ALLOCATOR>::find(const KEY& key) const { return const_iterator(d_impl.find(key)); } template <class KEY, class HASH, class EQUAL, class ALLOCATOR> inline typename MyHashedSet<KEY, HASH, EQUAL, ALLOCATOR>::size_type MyHashedSet<KEY, HASH, EQUAL, ALLOCATOR>::size() const { return d_impl.size(); }
mhs, an instance of MyHashedSet, exercise it, and confirm that it behaves as expected. MyHashedSet<int> mhs; assert( 0 == mhs.size()); assert( 1 == mhs.bucket_count());
MyPair<MyHashedSet<int>::const_iterator, bool> status; status = mhs.insert(10); assert( 1 == mhs.size()); assert(10 == *status.first); assert(true == status.second); status = mhs.insert(10); assert( 1 == mhs.size()); assert(10 == *status.first); assert(false == status.second);
status = mhs.insert(20);
assert( 2 == mhs.size());
assert(20 == *status.first);
assert(true == status.second);
MyHashedSet<int>::const_iterator itr, end = mhs.cend(); itr = mhs.find(10); assert(end != itr); assert(10 == *itr); itr = mhs.find(20); assert(end != itr); assert(20 == *itr);
itr = mhs.find(0); assert(end == itr);
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. UseFirstValueOfPairAsKey, a class template we can use to configure bslstl::HashTable to use the first member of each element, each a MyPair, as the key-value for hashing. Note that, in practice, developers can use class defined in bslstl_unorderedmapkeyconfiguration. // =============================== // struct UseFirstValueOfPairAsKey // =============================== template <class VALUE_TYPE> struct UseFirstValueOfPairAsKey { // This 'struct' provides a namespace for types and methods that define // the policy by which the key value of a hashed container (i.e., the // value passed to the hasher) is extracted from the objects stored in // the hashed container (the 'value' type). typedef VALUE_TYPE ValueType; // Alias for 'VALUE_TYPE', the type stored in the hashed container. // For this policy 'ValueType' must define a public member named // 'first' of type 'first_type'. typedef typename ValueType::first_type KeyType; // Alias for the type passed to the hasher by the hashed container. // In this policy, that type is the type of the 'first' element of // 'ValueType'. static const KeyType& extractKey(const ValueType& value); // Return the key value for the specified 'value'. In this policy, // that is the value of the 'first' member of 'value'. }; // ------------------------------- // struct UseFirstValueOfPairAsKey // ------------------------------- template <class VALUE_TYPE> inline const typename UseFirstValueOfPairAsKey<VALUE_TYPE>::KeyType& UseFirstValueOfPairAsKey<VALUE_TYPE>::extractKey( const ValueType& value) { return value.first; }
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. // ================= // class MyHashedMap // ================= template <class KEY, class VALUE, class HASH = bsl::hash<KEY>, class EQUAL = bsl::equal_to<KEY>, class ALLOCATOR = bsl::allocator<KEY> > class MyHashedMap { private: // PRIVATE TYPES typedef bsl::allocator_traits<ALLOCATOR> AllocatorTraits; typedef BloombergLP::bslstl::HashTable< UseFirstValueOfPairAsKey<MyPair<const KEY, VALUE> >, HASH, EQUAL, ALLOCATOR> HashTable; // DATA HashTable d_impl; public: // TYPES typedef typename AllocatorTraits::size_type size_type; // CREATORS explicit MyHashedMap(size_type initialNumBuckets = 0, const HASH& hash = HASH(), const EQUAL& keyEqual = EQUAL(), const ALLOCATOR& allocator = ALLOCATOR()); // Create an empty 'MyHashedMap' object having a maximum load factor // of 1. Optionally specify at least 'initialNumBuckets' in this // container's initial array of buckets. If 'initialNumBuckets' is not // supplied, one empty bucket shall be used and no memory allocated. // Optionally specify 'hash' to generate the hash values associated // with the key-value pairs contained in this unordered map. If 'hash' // is not supplied, a default-constructed object of (template // parameter) 'HASH' is used. Optionally specify a key-equality // functor 'keyEqual' used to determine whether two keys have the same // value. If 'keyEqual' is not supplied, a default-constructed object // of (template parameter) 'EQUAL' is used. Optionally specify an // 'allocator' used to supply memory. If 'allocator' is not supplied, // a default-constructed object of the (template parameter) type // 'ALLOCATOR' is used. If 'ALLOCATOR' is 'bsl::allocator' (the // default), then 'allocator' shall be convertible to // 'bslma::Allocator *'. If 'ALLOCATOR' is 'bsl::allocator' and // 'allocator' is not supplied, the currently installed default // allocator is used to supply memory. Note that more than // 'initialNumBuckets' buckets may be created in order to preserve the // bucket allocation strategy of the hash-table (but never fewer). // Destroy this object. // MANIPULATORS VALUE& operator[](const KEY& key); // Return a reference providing modifiable access to the // mapped-value associated with the specified 'key' in this // unordered map; if this unordered map does not already contain a // 'value_type' object with 'key', first insert a new 'value_type' // object having 'key' and a default-constructed 'VALUE' object. // Note that this method requires that the (template parameter) // type 'KEY' is "copy-constructible" and the (template parameter) // 'VALUE' is "default-constructible". };
MyHashedMap. The construct need merely forward its arguments to the constructor of d_impl, // ================= // class MyHashedMap // ================= // CREATORS template <class KEY, class VALUE, class HASH, class EQUAL, class ALLOCATOR> inline MyHashedMap<KEY, VALUE, HASH, EQUAL, ALLOCATOR>::MyHashedMap( size_type initialNumBuckets, const HASH& hash, const EQUAL& keyEqual, const ALLOCATOR& allocator) : d_impl(hash, keyEqual, initialNumBuckets, allocator) { }
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). // MANIPULATORS template <class KEY, class VALUE, class HASH, class EQUAL, class ALLOCATOR> inline VALUE& MyHashedMap<KEY, VALUE, HASH, EQUAL, ALLOCATOR>::operator[]( const KEY& key) { typedef typename HashTable::NodeType HashTableNode; typedef BloombergLP::bslalg::BidirectionalLink HashTableLink; HashTableLink *node = d_impl.insertIfMissing(key); return static_cast<HashTableNode *>(node)->value().second; }
mhm, an instance of MyHashedMap, exercise it, and confirm that it behaves as expected. We can add an element (with key value of 0). MyHashedMap<int, double> mhm; mhm[0] = 1.234; assert(1.234 == mhm[0]);
mhm[0] = 4.321; assert(4.321 == mhm[0]);
mhm[1] = 5.768; assert(5.768 == mhm[1]); assert(4.321 == mhm[0]);
assert(0.000 == mhm[2]);
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. bslstl::HashTable to extract key values in manner appropriate for maps. The previously defined UseFirstValueOfPairAsKey class template (see Example 2) suits perfectly. 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. // ====================== // class MyHashedMultiMap // ====================== template <class KEY, class VALUE, class HASH = bsl::hash<KEY>, class EQUAL = bsl::equal_to<KEY>, class ALLOCATOR = bsl::allocator<KEY> > class MyHashedMultiMap { private: // PRIVATE TYPES typedef MyPair<const KEY, VALUE> value_type; typedef bsl::allocator_traits<ALLOCATOR> AllocatorTraits; typedef typename AllocatorTraits::difference_type difference_type; typedef BloombergLP::bslstl::HashTable< UseFirstValueOfPairAsKey<MyPair<const KEY, VALUE> >, HASH, EQUAL, ALLOCATOR> HashTable; // DATA HashTable d_impl; public: // TYPES typedef typename AllocatorTraits::size_type size_type; typedef BloombergLP::bslstl::HashTableIterator<value_type, difference_type> iterator; typedef BloombergLP::bslstl::HashTableIterator<const value_type, difference_type> const_iterator; // CREATORS explicit MyHashedMultiMap( size_type initialNumBuckets = 0, const HASH& hash = HASH(), const EQUAL& keyEqual = EQUAL(), const ALLOCATOR& allocator = ALLOCATOR()); // Create an empty 'MyHashedMultiMap' object having a maximum load // factor of 1. Optionally specify at least 'initialNumBuckets' in // this container's initial array of buckets. If 'initialNumBuckets' // is not supplied, an implementation defined value is used. // Optionally specify a 'hash', a hash-functor used to generate the // hash values associated to the key-value pairs contained in this // object. If 'hash' is not supplied, a default-constructed object of // (template parameter) 'HASH' type is used. Optionally specify a // key-equality functor 'keyEqual' used to verify that two key values // are the same. If 'keyEqual' is not supplied, a default-constructed // object of (template parameter) 'EQUAL' type is used. Optionally // specify an 'allocator' used to supply memory. If 'allocator' is not // supplied, a default-constructed object of the (template parameter) // 'ALLOCATOR' type is used. If 'ALLOCATOR' is 'bsl::allocator' (the // default), then 'allocator' shall be convertible to // 'bslma::Allocator *'. If the 'ALLOCATOR' is 'bsl::allocator' and // 'allocator' is not supplied, the currently installed default // allocator is used to supply memory. // Destroy this object. // MANIPULATORS template <class SOURCE_TYPE> iterator insert(const SOURCE_TYPE& value); // Insert the specified 'value' into this multi-map, and return an // iterator to the newly inserted element. Note that this method // requires that the (class template parameter) types 'KEY' and // 'VALUE' types both be "copy-constructible", and that the // (function template parameter) 'SOURCE_TYPE' be convertible to // the (class template parameter) 'VALUE' type. // ACCESSORS MyPair<const_iterator, const_iterator> equal_range(const KEY& key) const; // Return a pair of iterators providing non-modifiable access to // the sequence of 'value_type' objects in this container matching // the specified 'key', where the first iterator is positioned at // the start of the sequence and the second iterator is positioned // one past the end of the sequence. If this container contains no // 'value_type' objects matching 'key', then the two returned // iterators will have the same value. };
MyHashedMultiMap. The construct need merely forward its arguments to the constructor of d_impl, // ====================== // class MyHashedMultiMap // ====================== // CREATORS template <class KEY, class VALUE, class HASH, class EQUAL, class ALLOCATOR> inline MyHashedMultiMap<KEY, VALUE, HASH, EQUAL, ALLOCATOR>::MyHashedMultiMap( size_type initialNumBuckets, const HASH& hash, const EQUAL& keyEqual, const ALLOCATOR& allocator) : d_impl(hash, keyEqual, initialNumBuckets, allocator) { }
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. // MANIPULATORS template <class KEY, class VALUE, class HASH, class EQUAL, class ALLOCATOR> template <class SOURCE_TYPE> inline typename MyHashedMultiMap<KEY, VALUE, HASH, EQUAL, ALLOCATOR>::iterator MyHashedMultiMap<KEY, VALUE, HASH, EQUAL, ALLOCATOR>::insert( const SOURCE_TYPE& value) { return iterator(d_impl.insert(value)); }
equal_range method need only convert the values returned by the findRange method to the types expected by the caller. // ACCESSORS template <class KEY, class VALUE, class HASH, class EQUAL, class ALLOCATOR> MyPair<typename MyHashedMultiMap<KEY, VALUE, HASH, EQUAL, ALLOCATOR>::const_iterator, typename MyHashedMultiMap<KEY, VALUE, HASH, EQUAL, ALLOCATOR>::const_iterator> MyHashedMultiMap<KEY, VALUE, HASH, EQUAL, ALLOCATOR>::equal_range( const KEY& key) const { typedef MyPair<const_iterator, const_iterator> ResultType; typedef BloombergLP::bslalg::BidirectionalLink HashTableLink; HashTableLink *first; HashTableLink *last; d_impl.findRange(&first, &last, key); return ResultType(const_iterator(first), const_iterator(last)); }
mhmm, an instance of MyHashedMultiMap, exercise it, and confirm that it behaves as expected. typedef MyHashedMultiMap<int, double>::iterator Iterator; typedef MyHashedMultiMap<int, double>::const_iterator ConstIterator; typedef MyPair<ConstIterator, ConstIterator> ConstRange;
MyHashedMultiMap<int, double> mhmm; ConstRange range; range = mhmm.equal_range(10); assert(range.first == range.second);
MyPair<const int, double> value(10, 100.00); Iterator itr; itr = mhmm.insert(value); assert(value == *itr);
itr = mhmm.insert(value); assert(value == *itr);
range = mhmm.equal_range(10); assert(range.first != range.second);
int count = 0; for (ConstIterator cur = range.first, end = range.second; end != cur; ++cur, ++count) { assert(value == *cur); } assert(2 == count);
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. bslstl::HashTable to implement a custom container supporting multiple key-values. MySalesRecord, our record class: enum { MAX_DESCRIPTION_SIZE = 16 }; typedef struct MySalesRecord { int orderNumber; // unique int customerId; // no constraint int vendorId; // no constraint char description[MAX_DESCRIPTION_SIZE]; // ASCII string } MySalesRecord;
orderNumber is unique. We expect multiple sales to any given customer (customerId) and multiple sales by any given vendor (vendorId). 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. MySalesRecord objects for hashing. 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: // ========================== // struct UseOrderNumberAsKey // ========================== struct UseOrderNumberAsKey { // This 'struct' provides a namespace for types and methods that define // the policy by which the key value of a hashed container (i.e., the // value passed to the hasher) is extracted from the objects stored in // the hashed container (the 'value' type). typedef MySalesRecord ValueType; // Alias for 'MySalesRecord', the type stored in the first // hashtable. typedef int KeyType; // Alias for the type passed to the hasher by the hashed container. // In this policy, the value passed to the hasher is the // 'orderNumber' attribute, an 'int' type. static const KeyType& extractKey(const ValueType& value); // Return the key value for the specified 'value'. In this policy, // that is the 'orderNumber' attribute of 'value'. }; // -------------------------- // struct UseOrderNumberAsKey // -------------------------- inline const UseOrderNumberAsKey::KeyType& UseOrderNumberAsKey::extractKey(const ValueType& value) { return value.orderNumber; }
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 *. // ========================= // struct UseCustomerIdAsKey // ========================= struct UseCustomerIdAsKey { // This 'struct' provides a namespace for types and methods that define // the policy by which the key value of a hashed container (i.e., the // value passed to the hasher) is extracted from the objects stored in // the hashed container (the 'value' type). typedef const MySalesRecord *ValueType; // Alias for 'const MySalesRecord *', the type stored in second // hashtable, a pointer to the record stored in the first // hashtable. typedef int KeyType; // Alias for the type passed to the hasher by the hashed container. // In this policy, the value passed to the hasher is the // 'orderNumber' attribute, an 'int' type. static const KeyType& extractKey(const ValueType& value); // Return the key value for the specified 'value'. In this policy, // that is the 'customerId' attribute of 'value'. }; // ------------------------- // struct UseCustomerIdAsKey // ------------------------- inline const UseCustomerIdAsKey::KeyType& UseCustomerIdAsKey::extractKey(const ValueType& value) { return value->customerId; }
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: // ======================= // struct UseVendorIdAsKey // ======================== struct UseVendorIdAsKey { // This 'struct' provides a namespace for types and methods that define // the policy by which the key value of a hashed container (i.e., the // value passed to the hasher) is extracted from the objects stored in // the hashed container (the 'value' type). typedef const MySalesRecord *ValueType; // Alias for 'const MySalesRecord *', the type stored in second // hashtable, a pointer to the record stored in the first // hashtable. typedef int KeyType; // Alias for the type passed to the hasher by the hashed container. // In this policy, the value passed to the hasher is the // 'vendorId' attribute, an 'int' type. static const KeyType& extractKey(const ValueType& value); // Return the key value for the specified 'value'. In this policy, // that is the 'vendorId' attribute of 'value'. }; // ----------------------- // struct UseVendorIdAsKey // ----------------------- inline const UseVendorIdAsKey::KeyType& UseVendorIdAsKey::extractKey(const ValueType& value) { return value->vendorId; }
MySalesRecordContainer, our customized container: // ---------------------------- // class MySalesRecordContainer // ---------------------------- class MySalesRecordContainer { private: // PRIVATE TYPES typedef BloombergLP::bslstl::HashTable< UseOrderNumberAsKey, bsl::hash< UseOrderNumberAsKey::KeyType>, bsl::equal_to<UseOrderNumberAsKey::KeyType> > RecordsByOrderNumber; typedef bsl::allocator_traits< bsl::allocator<UseOrderNumberAsKey::ValueType> > AllocatorTraits; typedef AllocatorTraits::difference_type difference_type;
ItrByOrderNumber type is used to provide access to the elements of the first hash table, the one that stores the records. typedef BloombergLP::bslstl::HashTableIterator<const MySalesRecord, difference_type> ItrByOrderNumber;
ItrPtrById type is used to provide access to the elements of the other hashtables, the ones that store pointers into the first hashtable. typedef BloombergLP::bslstl::HashTableIterator<const MySalesRecord *, difference_type> ItrPtrById;
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. class ItrById : public ItrPtrById { public: // CREATORS explicit ItrById(bslalg::BidirectionalLink *node) : ItrPtrById(node) { } // ACCESSORS const MySalesRecord& operator*() const { return *ItrPtrById::operator*(); } const MySalesRecord *operator->() const { return &(*ItrPtrById::operator*()); } }; typedef BloombergLP::bslstl::HashTable< UseCustomerIdAsKey, bsl::hash< UseCustomerIdAsKey::KeyType>, bsl::equal_to<UseCustomerIdAsKey::KeyType> > RecordsPtrsByCustomerId; typedef BloombergLP::bslstl::HashTable< UseVendorIdAsKey, bsl::hash< UseVendorIdAsKey::KeyType>, bsl::equal_to<UseVendorIdAsKey::KeyType> > RecordsPtrsByVendorId; // DATA RecordsByOrderNumber d_recordsByOrderNumber; RecordsPtrsByCustomerId d_recordptrsByCustomerId; RecordsPtrsByVendorId d_recordptrsByVendorId; public: // PUBLIC TYPES typedef ItrByOrderNumber ConstItrByOrderNumber; typedef ItrById ConstItrById; // CREATORS explicit MySalesRecordContainer(bslma::Allocator *basicAllocator = 0); // Create an empty 'MySalesRecordContainer' object. If // 'basicAllocator' is 0, the currently installed default allocator // is used. // Destroy this object. // MANIPULATORS MyPair<ConstItrByOrderNumber, bool> insert(const MySalesRecord& value); // Insert the specified 'value' into this set if the 'value' does // not already exist in this set; otherwise, this method has no // effect. Return a pair whose 'first' member is an iterator // providing non-modifiable access to the (possibly newly inserted) // 'MySalesRecord' object having 'value' and whose 'second' member // is 'true' if a new element was inserted, and 'false' if 'value' // was already present. // ACCESSORS ConstItrByOrderNumber cend() const; // Return an iterator providing non-modifiable access to the // past-the-end element (in the sequence of 'MySalesRecord' // objects) maintained by this set. ConstItrByOrderNumber findByOrderNumber(int value) const; // Return an iterator providing non-modifiable access to the // 'MySalesRecord' object in this set having the specified 'value', // if such an entry exists, and the iterator returned by the 'cend' // method otherwise.
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. MyPair<ConstItrById, ConstItrById> findByCustomerId(int value) const; // Return a pair of iterators providing non-modifiable access to // the sequence of 'MySalesRecord' objects in this container having // a 'customerId' attribute equal to the specified 'value' where // the first iterator is positioned at the start of the sequence // and the second iterator is positioned one past the end of the // sequence. If this container has no such objects, then the two // iterators will be equal. MyPair<ConstItrById, ConstItrById> findByVendorId(int value) const; // Return a pair of iterators providing non-modifiable access to // the sequence of 'MySalesRecord' objects in this container having // a 'vendorId' attribute equal to the specified 'value' where the // first iterator is positioned at the start of the sequence and // the second iterator is positioned one past the end of the // sequence. If this container has no such objects, then the two // iterators will be equal. };
MySalesRecordContainer, our customized container: // ---------------------------- // class MySalesRecordContainer // ---------------------------- // CREATORS inline MySalesRecordContainer::MySalesRecordContainer( bslma::Allocator *basicAllocator) : d_recordsByOrderNumber(basicAllocator) , d_recordptrsByCustomerId(basicAllocator) , d_recordptrsByVendorId(basicAllocator) { } // MANIPULATORS inline MyPair<MySalesRecordContainer::ConstItrByOrderNumber, bool> MySalesRecordContainer::insert(const MySalesRecord& value) { // Insert into internal container that will own the record. bool isInsertedFlag = false; BloombergLP::bslalg::BidirectionalLink *result = d_recordsByOrderNumber.insertIfMissing(&isInsertedFlag, value); // Index by other record attributes RecordsByOrderNumber::NodeType *nodePtr = static_cast<RecordsByOrderNumber::NodeType *>(result); d_recordptrsByCustomerId.insert(&nodePtr->value()); d_recordptrsByVendorId.insert(&nodePtr->value()); // Return of insertion. return MyPair<ConstItrByOrderNumber, bool>( ConstItrByOrderNumber(result), isInsertedFlag); } // ACCESSORS inline MySalesRecordContainer::ConstItrByOrderNumber MySalesRecordContainer::cend() const { return ConstItrByOrderNumber(); } inline MySalesRecordContainer::ConstItrByOrderNumber MySalesRecordContainer::findByOrderNumber(int value) const { return ConstItrByOrderNumber(d_recordsByOrderNumber.find(value)); } inline MyPair<MySalesRecordContainer::ConstItrById, MySalesRecordContainer::ConstItrById> MySalesRecordContainer::findByCustomerId(int value) const { typedef BloombergLP::bslalg::BidirectionalLink HashTableLink; HashTableLink *first; HashTableLink *last; d_recordptrsByCustomerId.findRange(&first, &last, value); return MyPair<ConstItrById, ConstItrById>(ConstItrById(first), ConstItrById(last)); } inline MyPair<MySalesRecordContainer::ConstItrById, MySalesRecordContainer::ConstItrById> MySalesRecordContainer::findByVendorId(int value) const { typedef BloombergLP::bslalg::BidirectionalLink HashTableLink; HashTableLink *first; HashTableLink *last; d_recordptrsByVendorId.findRange(&first, &last, value); return MyPair<ConstItrById, ConstItrById>(ConstItrById(first), ConstItrById(last)); }
MySalesRecordContainer msrc;
const MySalesRecord DATA[] = {
{ 1000, 100, 10, "hello" },
{ 1001, 100, 20, "world" },
{ 1002, 200, 10, "how" },
{ 1003, 200, 20, "are" },
{ 1004, 100, 10, "you" },
{ 1005, 100, 20, "today" }
};
const int numDATA = sizeof DATA / sizeof *DATA;
printf("Insert sales records into container.\n");
for (int i = 0; i < numDATA; ++i) {
const int orderNumber = DATA[i].orderNumber;
const int customerId = DATA[i].customerId;
const int vendorId = DATA[i].vendorId;
const char *description = DATA[i].description;
printf("%d: %d %d %s\n",
orderNumber,
customerId,
vendorId,
description);
MyPair<MySalesRecordContainer::ConstItrByOrderNumber,
bool> status = msrc.insert(DATA[i]);
assert(msrc.cend() != status.first);
assert(true == status.second);
}
Insert sales records into container. 1000: 100 10 hello 1001: 100 20 world 1002: 200 10 how 1003: 200 20 are 1004: 100 10 you 1005: 100 20 today
printf("Find sales records by order number.\n"); for (int i = 0; i < numDATA; ++i) { const int orderNumber = DATA[i].orderNumber; const int customerId = DATA[i].customerId; const int vendorId = DATA[i].vendorId; const char *description = DATA[i].description; printf("%d: %d %d %s\n", orderNumber, customerId, vendorId, description); MySalesRecordContainer::ConstItrByOrderNumber itr = msrc.findByOrderNumber(orderNumber); assert(msrc.cend() != itr); assert(orderNumber == itr->orderNumber); assert(customerId == itr->customerId); assert(vendorId == itr->vendorId); assert(0 == strcmp(description, itr->description)); }
Find sales records by order number. 1000: 100 10 hello 1001: 100 20 world 1002: 200 10 how 1003: 200 20 are 1004: 100 10 you 1005: 100 20 today
printf("Find sales records by customer identifier.\n"); for (int customerId = 100; customerId <= 200; customerId += 100) { MyPair<MySalesRecordContainer::ConstItrById, MySalesRecordContainer::ConstItrById> result = msrc.findByCustomerId(customerId); int count = std::distance(result.first, result.second); printf("customerId %d, count %d\n", customerId, count); for (MySalesRecordContainer::ConstItrById itr = result.first, end = result.second; end != itr; ++itr) { printf("\t\t%d %d %d %s\n", itr->orderNumber, itr->customerId, itr->vendorId, itr->description); } }
Find sales records by customer identifier.
customerId 100, count 4
1005 100 20 today
1004 100 10 you
1001 100 20 world
1000 100 10 hello
customerId 200, count 2
1003 200 20 are
1002 200 10 how
printf("Find sales records by vendor identifier.\n"); for (int vendorId = 10; vendorId <= 20; vendorId += 10) { MyPair<MySalesRecordContainer::ConstItrById, MySalesRecordContainer::ConstItrById> result = msrc.findByVendorId(vendorId); int count = std::distance(result.first, result.second); printf("vendorId %d, count %d\n", vendorId, count); for (MySalesRecordContainer::ConstItrById itr = result.first, end = result.second; end != itr; ++itr) { printf("\t\t%d %d %d %s\n", (*itr).orderNumber, (*itr).customerId, (*itr).vendorId, (*itr).description); } }
Find sales records by vendor identifier.
vendorId 10, count 3
1004 100 10 you
1002 200 10 how
1000 100 10 hello
vendorId 20, count 3
1005 100 20 today
1003 200 20 are
1001 100 20 world
1.7.1