Instantiating the Unordered Containers






Instantiating the Unordered Containers

As we've seen, the template classes unordered_set and unordered_multiset take a single template parameter, referred to as the Key type, that gives the type of the objects to be held in the container. They both take additional template parameters that have default values, so you often won't have to write them out.

Similarly, the template classes unordered_map and unordered_multimap take two template parameters: a Key type that gives the type of the objects to be used as keys and an associated type Ty that gives the type of the objects that will be associated with those keys. They also take the same list of additional template parameters with default values that unordered_set and unordered_multiset take.

The Key type is used to store and find objects in the unordered associative containers. In order to do this, it must be possible to compute hash values for objects of type Key. By default, the containers all use the callable type std::tr1::hash<Key>. If that type is valid for the Key type, either because it's supported by the implementation or because your code supplies a specialization for your key type, the default will work. Otherwise, you need to provide your own type for computing hash values. You do that by passing the name of your type as the next argument in the template's parameter list:

           
struct MyKey                                          
{                                                     
// whatever...                   
};                                                    
                                                      
struct MyHash                                         
{                                                     
size_t operator ()(myKey key) const;                  
};                                                    
                                                      
  // uses hash<MyKey>:     
std::tr1::unordered_set <MyKey> set1;           
  // uses MyHash:                
std::tr1::unordered_set <MyKey, MyHash> set2;   

The containers also use std::equal_to<Key> to decide whether two key values are equal. That template, in turn, returns the result of applying operator== to the key objects. So if you have an operator== for your key types, or if you have a specialization of std::equal_to for your key types, the default equality predicate will work. Otherwise, you'll need to provide your own predicate type:

           
namespace std { // put specialization in std
template <>                                     
struct equal_to <MyKey>:                        
  public binary_function <MyKey, MyKey, bool>   
{                                                     
bool operator ()(const MyKey&, const MyKey&) const;
};                                                    
}                                                     
                                                      
struct MyEq                                           
{                                                     
bool operator ()(const MyKey&, const MyKey&) const;
};                                                    
                                                      
   // uses equal_to<MyKey>:
std::tr1::unordered_set <MyKey, MyHash> set3;   
   // uses MyEq:                 
std::tr1::unordered_set <MyKey, MyHash, MyEq> set4;

Finally, as with all the other containers, you can pass a final template parameter that gives the type of the allocator for the container to use when it needs to allocate memory.

In all these cases, the container will use the default constructor to create the objects that it uses for hashing, comparing, and allocating. If your type needs something more than default construction, in addition to naming the type as a template parameter, you must pass a suitably constructed object to the container's constructor. The container will make copies of those objects and use them for hashing and comparing.



 Python   SQL   Java   php   Perl 
 game development   web development   internet   *nix   graphics   hardware 
 telecommunications   C++ 
 Flash   Active Directory   Windows