A TR1 Tutorial: Unordered Containers

One of the important additions to the C++ standard in TR1 is the hash tables. There are four such containers: unordered_map and unordered_multimap defined in header <unordered_map> and unordered_set and unordered_multiset defined in header <unordered_set>. Moreover, header <functional> contains a new template class called hash that is the implementation for the default hashing function for these containers.

About STL Containers

Until TR1, there were four types of containers in STL:

  • Containers: A container is an object that stores a sequence of other objects; such a container must:
    • Have a default constructor, a copy constructor, a destructor (that destroys all the objects in the container), and an assignment operator (that copies all the objects from one container to the other)
    • Provide access to the stored objects (elements), both for constant and non-constant container objects (begin() and end())
    • Overload comparison operators (==, !=, <, >, <=, and >=)
    • Provide functions for retrieving the size of the container (size(), max_size(), and si empty())
    • Allow swapping elements between two containers (swap())
  • Reverse containers: Those containers that, in addition to regular containers requirements, allow accessing the elements in reverse order (rbegin() and rend())
  • Sequence containers: These are containers with variable size, with elements arranged in a strict linear order, allowing inserting and removing elements
  • Associative containers: These are containers with variable size that have efficient elements access based on keys (associated with stored values). The difference between an associative container and a sequence container is that the former does not allow insertion of elements at a specified position.

In TR1, a fifth type of containers was added:

  • Unordered containers: (or hash tables) These meet all the requirements for a container except that they don't implement the six comparison operators. They provide two new typenames:
    • key_type: Gives the type of the key
    • key_equal: Gives the type of the predicate used to compare two keys

A hash table groups the stored objects in sequences called "buckets," each such bucket having zero or more elements. Inserting an element in a bucket is done based on the hashing value for the key associated with the element. In the case of Microsoft implementation for TR1, the hash tables have 8 buckets by default, with a loading factor of 4. This means that on average, buckets can store up to 4 elements. (There could be buckets with 20 elements and others with 0; only the average is important.) When a new element is added, and the loading factor becomes greater than the maximum allowed loading factor, a new bucket is added to the hash table.

To add a new element, the hashing value of the associated key is computed, and then the value is trimmed with modulo with the number of existing buckets and the result is the (zero-based) index of the bucket in which the object is stored. Time of insertion for an element is O(1); it does not depend how many elements are stored in the container or the bucket.

When an element is looked up, the same steps are taken to identify the bucket. The standard find() function is applied to localize the element within the bucket. This means the look-up time is proportional with the number of elements in the bucket. For a good performance, the number of elements in a bucket should be kept at a reasonable limit, and the way to do it is by adding more buckets to the container.

Unordered containers (hash tables) can be parameterized in several ways:

  • At compile time, by specifying the hashing function and comparison functions (for comparing two keys)
  • At runtime, by adjusting the maximum load factor for the buckets (which is an average on all buckets).

Examples on how the buckets change

In this section, I will show the buckets' number and their content change when adding new elements to an unordered_map. I must say it again, when adding elements, the value is not important for the insertion point, only the key.

  • Initially, the container is empty
  • buckets: 8
    max load factor: 4
    load factor: 0
    
    bucket 0[0]
    bucket 1[0]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[0]
    bucket 7[0]
    
  • Add (1, 2); hash value is 16807, and to find the bucket index, you apply a modulo 8 (number of buckets), and the result is 7.
  • hash(1) = 16807
    bucket index = 16807 % 8 = 7
    
    buckets: 8
    max load factor: 4
    load factor: 0.125
    
    bucket 0[0]
    bucket 1[0]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[0]
    bucket 7[1]     [1,2]
    
  • Add (2, 3)
  • hash(2) = 33614
    bucket index = 33614 % 8 = 6
    
    buckets: 8
    max load factor: 4
    load factor: 0.25
    
    bucket 0[0]
    bucket 1[0]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[1]     [2,3]
    bucket 7[1]     [1,2]
    
  • Add (55,100)
  • hash(55) = 924385
    bucket index = 924385 % 8 = 1
    
    buckets: 8
    max load factor: 4
    load factor: 0.375
    
    bucket 0[0]
    bucket 1[1]     [55,100]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[1]     [2,3]
    bucket 7[1]     [1,2]
    
  • Add (9,0);
  • hash(9) = 151263
    bucket index = 151263 % 8 = 7
    
    buckets: 8
    max load factor: 4
    load factor: 0.5
    
    bucket 0[0]
    bucket 1[1]     [55,100]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[1]     [2,3]
    bucket 7[2]     [9,0] [1,2]
    
  • Add (17,0);
  • hash(17) = 285719
    bucket index = 285719 % 8 = 7
    
    buckets: 8
    max load factor: 4
    load factor: 0.625
    
    bucket 0[0]
    bucket 1[1]     [55,100]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[1]     [2,3]
    bucket 7[3]     [17,0] [9,0] [1,2]
    
  • Add (25,0). At this point the 8th bucket (with index 7) would have 4 elements, but the loading factor is only 0.75, which means you can still add new elements without adding an additional bucket; the new element is added to the 8th bucket also.
  • hash(25) = 420175
    bucket index = 420175 % 8 = 7
    
    buckets: 8
    max load factor: 4
    load factor: 0.75
    
    bucket 0[0]
    bucket 1[1]     [55,100]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[1]     [2,3]
    bucket 7[4]     [25,0] [17,0] [9,0] [1,2]
    
  • Add (33,0); a fifth element was added to the last (8th) bucket
  • hash(33) = 554631
    bucket index = 554631 % 8 = 7
    
    buckets: 8
    max load factor: 4
    load factor: 0.875
    
    bucket 0[0]
    bucket 1[1]     [55,100]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[1]     [2,3]
    bucket 7[5]     [33,0] [25,0] [17,0] [9,0] [1,2]
    

To see how new buckets are added to the table, I will use a maximum loading factor of 0.2. That means that at the second insertion a new bucket should be added.

  • Initially, the container is empty
  • buckets: 8
    max load factor: 0.2
    load factor: 0
    
    bucket 0[0]
    bucket 1[0]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[0]
    bucket 7[0]
    
  • Add (1,1); this will be added to the 8th bucket (index 7)
  • hash(1) = 16807
    bucket index = 16807 % 8 = 7
    
    buckets: 8
    max load factor: 0.2
    load factor: 0.125
    
    bucket 0[0]
    bucket 1[0]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[0]
    bucket 7[1]     [1,1]
    
  • Add (2,2); new loading factor becomes 2/8 = 0.25, which is greater than 0.2. That means that, before actually inserting the new element, a new bucket must be added to the table. Only then the index of the bucket is computed and the element stored in the appropriate bucket.
  • hash(2) = 33614
    bucket index = 33614 % 8 = 6
    
    buckets: 9
    max load factor: 0.2
    load factor: 0.222222
    
    bucket 0[0]
    bucket 1[0]
    bucket 2[0]
    bucket 3[0]
    bucket 4[0]
    bucket 5[0]
    bucket 6[1]     [2,2]
    bucket 7[1]     [1,1]
    bucket 8[0]
    

A TR1 Tutorial: Unordered Containers

Containers unordered_map and unordered_multimap

These two classes are defined in header <unordered_map> under the namespaces std::tr1. unordered_map is an unordered container, a sequence of key-value pairs, ordered in buckets based on the hashing value of the key. Inserting elements doesn't invalidate any iterator, and removing elements only invalidates iterators to the removed elements. This container does not create a new key-value pair if the key is already present in the container.

unordered_multimap differs from unordered_map in that it allows multiple pairs with the same key to be added to the container.

In the following paragraphs, I will show the basic usage for these two classes. To simplify the examples, I defined a type unordered_map and unordered_multimap with key of type int and value of type double.

typedef std::tr1::unordered_map<int, double> umap_id;
typedef std::tr1::unordered_multimap<int, double> umultimap_id;

I also will use these two functions to print the content of a container.

void print_unordered_map(const umap_id& m)
{
   for(umap_id::const_iterator it = m.begin();
      it != m.end();
      ++it)
   {
      std::cout << "[" << it->first << "," << it->second << "] ";
   }
   std::cout << std::endl;
}

void print_unordered_multimap(const umultimap_id& mm)
{
   for(umultimap_id::const_iterator it = mm.begin();
      it != mm.end();
      ++it)
   {
      std::cout << "[" << it->first << "," << it->second << "] ";
   }
   std::cout << std::endl;
}

Adding elements

unordered_map unordered_multimap
umap_id m;

m[1] = 1.1;
m[2] = 2.2;
m[3] = 3.3;

print_unordered_map(m);

m.insert(umap_id::value_type(4, 4.4));
m.insert(umap_id::value_type(5, 5.5));

print_unordered_map(m);
umultimap_id mm;

mm.insert(umultimap_id::value_type(1, 1.1));
mm.insert(umultimap_id::value_type(1, 2.2));
mm.insert(umultimap_id::value_type(1, 3.3));
mm.insert(umultimap_id::value_type(2, 2.2));
mm.insert(umultimap_id::value_type(3, 3.3));
mm.insert(umultimap_id::value_type(4, 4.4));

print_unordered_multimap(mm);
[3,3.3] [2,2.2] [1,1.1]
[5,5.5] [4,4.4] [3,3.3] [2,2.2] [1,1.1]
[4,4.4] [3,3.3] [2,2.2] [1,1.1] [1,2.2] [1,3.3]

Searching elements

For searching, there are two functions: find() that returns an iterator to the first found element, and equal_range() that returns a pair of iterators to the first and one-beyond-last element with the specified key.

unordered_map unordered_multimap
umap_id m;

m[1] = 1.1;
m[2] = 2.2;
m[3] = 3.3;
m[4] = 4.4;
m[5] = 5.5;

print_unordered_map(m);

umap_id::iterator pos = m.find(3);
if(pos != m.end())
{
   std::cout << "value = " << pos->second
             << std::endl;
}

std::pair<
   umap_id::iterator, 
   umap_id::iterator> range = m.equal_range(1);

std::cout << "equal_range(1): ";
for(umap_id::iterator it = range.first; 
    it != range.second; 
    ++it)
{
   std::cout << "[" << it->first << ","
             << it->second << "] ";
}
std::cout << std::endl;
umultimap_id mm;

mm.insert(umultimap_id::value_type(1, 1.1));
mm.insert(umultimap_id::value_type(1, 2.2));
mm.insert(umultimap_id::value_type(1, 3.3));
mm.insert(umultimap_id::value_type(2, 2.2));
mm.insert(umultimap_id::value_type(3, 3.3));
mm.insert(umultimap_id::value_type(4, 4.4));

print_unordered_multimap(mm);

umultimap_id::iterator pos = mm.find(3);
if(pos != mm.end())
{
   std::cout << "value = " << pos->second
             << std::endl;
}

std::pair<
   umultimap_id::iterator,
   umultimap_id::iterator> range = mm.equal_range(1);

std::cout << "equal_range(1): ";
for(umultimap_id::iterator it = range.first;
    it != range.second; 
    ++it)
{
   std::cout << "[" << it->first << "," 
             << it->second << "] ";
}
std::cout << std::endl;
[5,5.5] [4,4.4] [3,3.3] [2,2.2] [1,1.1]
value = 3.3
equal_range(1): [1,1.1]
[4,4.4] [3,3.3] [2,2.2] [1,1.1] [1,2.2] [1,3.3]
value = 3.3
equal_range(1): [1,1.1] [1,2.2] [1,3.3]

Removing elements

You can delete an element from a specific position (using an iterator), an element with a specific key, a sequence of elements defined by two iterators, or all the elements from the container.

unordered_map unordered_multimap
umap_id m;

m[1] = 1.1;
m[2] = 2.2;
m[3] = 3.3;
m[4] = 4.4;
m[5] = 5.5;
m[6] = 6.6;
print_unordered_map(m);

umap_id::iterator pos = m.find(3);

std::pair<
   umap_id::iterator, 
   umap_id::iterator> range = m.equal_range(1);

// remove from a position
if(pos != m.end())
{
   m.erase(pos);
   print_unordered_map(m);
}

// remove a key
m.erase(5);
print_unordered_map(m);

// remove a sequence
m.erase(range.first, range.second);
print_unordered_map(m);

// remove all elements
m.clear();
print_unordered_map(m);
umultimap_id mm;

mm.insert(umultimap_id::value_type(1, 1.1));
mm.insert(umultimap_id::value_type(1, 2.2));
mm.insert(umultimap_id::value_type(1, 3.3));
mm.insert(umultimap_id::value_type(2, 2.2));
mm.insert(umultimap_id::value_type(3, 3.3));
mm.insert(umultimap_id::value_type(4, 4.4));
print_unordered_multimap(mm);

umultimap_id::iterator pos = mm.find(3);

std::pair<
   umultimap_id::iterator, 
   umultimap_id::iterator> range = mm.equal_range(1);

// remove from a position
if(pos != mm.end())
{
   mm.erase(pos);
   print_unordered_multimap(mm);
}

// remove a key
mm.erase(2);
print_unordered_multimap(mm);

// remove a sequence
mm.erase(range.first, range.second);
print_unordered_multimap(mm);

// remove all elements
mm.clear();
print_unordered_multimap(mm);
[6,6.6] [5,5.5] [4,4.4] [3,3.3] [2,2.2] [1,1.1]
[6,6.6] [5,5.5] [4,4.4] [2,2.2] [1,1.1]
[6,6.6] [4,4.4] [2,2.2] [1,1.1]
[6,6.6] [4,4.4] [2,2.2]
[4,4.4] [3,3.3] [2,2.2] [1,1.1] [1,2.2] [1,3.3]
[4,4.4] [2,2.2] [1,1.1] [1,2.2] [1,3.3]
[4,4.4] [1,1.1] [1,2.2] [1,3.3]
[4,4.4]

Size and elements count

Both containers have the functions size() and max_size() that indicate the number of elements in the container, and empty() that indicates whether the container is empty. Moreover, there is a function called count() that returns the number of elements with a specified key. For unordered_map, this can return only 0 or 1, but for unordered_multimap it can return 0 or any positive number because this container allows inserting multiple pairs with the same key.

unordered_map unordered_multimap
umap_id m;

m[1] = 1.1;
m[2] = 2.2;
m[3] = 3.3;

std::cout << "size: " << m.size() << std::endl;
std::cout << "empty: " << std::boolalpha
          << m.empty() << std::endl;

std::cout << "count(5) = " << m.count(5)
          << std::endl;
std::cout << "count(1) = " << m.count(1)
          << std::endl;
umultimap_id mm;

mm.insert(umultimap_id::value_type(1, 1.1));
mm.insert(umultimap_id::value_type(1, 2.2));
mm.insert(umultimap_id::value_type(1, 3.3));

std::cout << "size: " << mm.size() << std::endl;
std::cout << "empty: " << std::boolalpha
          << mm.empty() << std::endl;

std::cout << "count(5) = " << mm.count(5)
          << std::endl;
std::cout << "count(1) = " << mm.count(1)
          << std::endl;
size: 3
empty: false
count(5) = 0
count(1) = 1
size: 3
empty: false
count(5) = 0
count(1) = 3

Swapping

To swap the content of two containers, you can use either function swap from header <unordered_map>, or the method with the same name, that exists in both classes.

unordered_map unordered_multimap
umap_id m1, m2;

m1[1] = 1.1;
m1[2] = 2.2;
m1[3] = 3.3;

m2[3] = 4.4;
m2[4] = 5.5;
m2[5] = 6.6;

std::cout << "before swapping" << std::endl;
print_unordered_map(m1);
print_unordered_map(m2);

m1.swap(m2);
std::cout << "after first swapping" << std::endl;
print_unordered_map(m1);
print_unordered_map(m2);

std::cout << "after second swapping" << std::endl;
std::tr1::swap(m1, m2);
print_unordered_map(m1);
print_unordered_map(m2);
umultimap_id mm1, mm2;

mm1.insert(umultimap_id::value_type(1, 1.1));
mm1.insert(umultimap_id::value_type(1, 2.2));
mm1.insert(umultimap_id::value_type(3, 3.3));

mm2.insert(umultimap_id::value_type(3, 4.4));
mm2.insert(umultimap_id::value_type(4, 5.5));
mm2.insert(umultimap_id::value_type(6, 6.6));

std::cout << "before swapping" << std::endl;
print_unordered_multimap(mm1);
print_unordered_multimap(mm2);

mm1.swap(mm2);
std::cout << "after first swapping" << std::endl;
print_unordered_multimap(mm1);
print_unordered_multimap(mm2);

std::cout << "after second swapping" << std::endl;
std::tr1::swap(mm1, mm2);
print_unordered_multimap(mm1);
print_unordered_multimap(mm2);
before swapping
[3,3.3] [2,2.2] [1,1.1]
[5,6.6] [4,5.5] [3,4.4]
after first swapping
[5,6.6] [4,5.5] [3,4.4]
[3,3.3] [2,2.2] [1,1.1]
after second swapping
[3,3.3] [2,2.2] [1,1.1]
[5,6.6] [4,5.5] [3,4.4]
before swapping
[3,3.3] [1,1.1] [1,2.2]
[6,6.6] [4,5.5] [3,4.4]
after first swapping
[6,6.6] [4,5.5] [3,4.4]
[3,3.3] [1,1.1] [1,2.2]
after second swapping
[3,3.3] [1,1.1] [1,2.2]
[6,6.6] [4,5.5] [3,4.4]

Hashing and comparison

Both containers allow you to access the hashing function and the comparison function (for comparing two keys).

unordered_map unordered_multimap
umap_id m;

umap_id::hasher hfunc = m.hash_function();
std::cout << "hash(1)   = " << hfunc(1)   << std::endl;
std::cout << "hash(22)  = " << hfunc(22)  << std::endl;
std::cout << "hash(333) = " << hfunc(333) << std::endl;

umap_id::key_equal eqfunc = m.key_eq();
std::cout << "key_eq(1, 1) = "  << std::boolalpha
          << eqfunc(1, 1) << std::endl;
std::cout << "key_eq(1, 2) = "  << std::boolalpha
          << eqfunc(1, 2) << std::endl;
umultimap_id mm;

umultimap_id::hasher hfunc = mm.hash_function();
std::cout << "hash(1)   = " << hfunc(1)   << std::endl;
std::cout << "hash(22)  = " << hfunc(22)  << std::endl;
std::cout << "hash(333) = " << hfunc(333) << std::endl;

umultimap_id::key_equal eqfunc = mm.key_eq();
std::cout << "key_eq(1, 1) = "  << std::boolalpha
          << eqfunc(1, 1) << std::endl;
std::cout << "key_eq(1, 2) = "  << std::boolalpha
          << eqfunc(1, 2) << std::endl;
hash(1)      = 16807
hash(22)     = 369754
hash(333)    = 5596731
key_eq(1, 1) = true
key_eq(1, 2) = false
hash(1)      = 16807
hash(22)     = 369754
hash(333)    = 5596731
key_eq(1, 1) = true
key_eq(1, 2) = false

A TR1 Tutorial: Unordered Containers

Containers unordered_set and unordered_multiset

These classes are defined in header <unordered_set> under namespaces std::tr1. unordered_set is an unordered container, a sequence of elements grouped in buckets based on the hashing value computed on the value (that is basically the key). As in the case of the other previous two containers, adding new elements does not invalidate any iterator and removing elements only invalidates the iterators to the removed elements. This container does not insert a value if it is already present.

unordered_multiset differs by allowing objects with the same value to be inserted multiple times.

I defined two unordered set types that I will used in the following paragraphs.

typedef std::tr1::unordered_set<int> uset_i;
typedef std::tr1::unordered_multiset<int> umultiset_i;

I also will use the following functions to print the content of a container.

void print_unordered_set(const uset_i& s)
{
   for(uset_i::const_iterator it = s.begin();
       it != s.end();
       ++it)
   {
      std::cout << *it << " ";
   }
   std::cout << std::endl;
}

void print_unordered_multiset(const umultiset_i& ms)
{
   for(uset_i::const_iterator it = ms.begin();
       it != ms.end();
       ++it)
   {
      std::cout << *it << " ";
   }
   std::cout << std::endl;
}

Adding elements

unordered_set unordered_multiset
uset_i s;

s.insert(1);
s.insert(2);
s.insert(3);
s.insert(1);
s.insert(1);

print_unordered_set(s);
umultiset_i ms;

ms.insert(1);
ms.insert(2);
ms.insert(3);
ms.insert(1);
ms.insert(1);

print_unordered_multiset(ms);
3 2 1
3 2 1 1 1

Searching elements

To search elements, you can use either method find() (present in both classes) that returns an interator to the element (first on for unordered_multiset if more exists), or method equal_range() that returns a pair of iterators defining a sequence of the value with the searched value.

unordered_set unordered_multiset
uset_i s;

s.insert(1);
s.insert(2);
s.insert(3);
s.insert(1);
s.insert(1);

uset_i::iterator pos = s.find(2);
if(pos != s.end())
{
   std::cout << "value = " << *pos << std::endl;
}

std::pair<
   uset_i::iterator,
   uset_i::iterator> range = s.equal_range(1);

for(uset_i::iterator it = range.first;
    it != range.second;
    ++it)
{
   std::cout << *it << " ";
}
std::cout << std::endl;
umultiset_i ms;

ms.insert(1);
ms.insert(2);
ms.insert(3);
ms.insert(1);
ms.insert(1);

umultiset_i::iterator pos = ms.find(2);
if(pos != ms.end())
{
   std::cout << "value = " << *pos << std::endl;
}

std::pair<
   umultiset_i::iterator,
   umultiset_i::iterator> range = ms.equal_range(1);

for(umultiset_i::iterator it = range.first;
    it != range.second;
    ++it)
{
   std::cout << *it << " ";
}
std::cout << std::endl;
value = 2
1
value = 2
1 1 1

Removing elements

You can remove an element from a specific position (using an iterator), an element with a specific value, a sequence of elements (delimited by two iterators), or all the elements from the container.

unordered_set unordered_multiset
uset_i s;

s.insert(1);
s.insert(2);
s.insert(3);
s.insert(4);
s.insert(5);
s.insert(6);
print_unordered_set(s);

uset_i::iterator pos = s.find(2);

std::pair<
   uset_i::iterator,
   uset_i::iterator> range = s.equal_range(1);

// remove from a position
if(pos != s.end())
{
   s.erase(pos);
   print_unordered_set(s);
}

// remove a value
s.erase(3);
print_unordered_set(s);

// remove a range
s.erase(range.first, range.second);
print_unordered_set(s);

// remove all
s.clear();
print_unordered_set(s);
umultiset_i ms;

ms.insert(1);
ms.insert(2);
ms.insert(3);
ms.insert(4);
ms.insert(1);
ms.insert(1);
print_unordered_multiset(ms);

umultiset_i::iterator pos = ms.find(2);

std::pair<
   umultiset_i::iterator,
   umultiset_i::iterator> range = ms.equal_range(1);

// remove from a position
if(pos != ms.end())
{
   ms.erase(pos);
   print_unordered_multiset(ms);
}

// remove a value
ms.erase(3);
print_unordered_multiset(ms);

// remove a sequence
ms.erase(range.first, range.second);
print_unordered_multiset(ms);

// remove all
ms.clear();
print_unordered_multiset(ms);
6 5 4 3 2 1
6 5 4 3 1
6 5 4 1
6 5 4
4 3 2 1 1 1
4 3 1 1 1
4 1 1 1
4

Size and elements count

Both containers have the functions size() and max_size() that indicate the number of elements in the container, and empty() that indicates whether the container is empty. Moreover, there is a function called count() that returns the number of elements with a specified value. For unordered_set, this can return only 0 or 1, but for unordered_multiset it can return 0 or any positive number because this container allows inserting multiple objects with the same value.

unordered_set unordered_multiset
uset_i s;

s.insert(1);
s.insert(2);
s.insert(3);

std::cout << "size: "  << s.size() << std::endl;
std::cout << "empty: " << std::boolalpha
          << s.empty() << std::endl;

std::cout << "count(5) = " << s.count(5)
          << std::endl;
std::cout << "count(1) = " << s.count(1)
          << std::endl;
umultiset_i ms;

ms.insert(1);
ms.insert(2);
ms.insert(1);

std::cout << "size: " << ms.size() << std::endl;
std::cout << "empty: " << std::boolalpha
          << ms.empty() << std::endl;

std::cout << "count(5) = " << ms.count(5)
          << std::endl;
std::cout << "count(1) = " << ms.count(1)
          << std::endl;
size: 3
empty: false
count(5) = 0
count(1) = 1
size: 3
empty: false
count(5) = 0
count(1) = 2

Swapping

To swap the content of two containers, you can use either function swap from header <unordered_set>, or the method with the same name. it exists in both classes.

unordered_set unordered_multiset
uset_i s1, s2;

s1.insert(1);
s1.insert(2);
s1.insert(3);

s2.insert(4);
s2.insert(5);
s2.insert(6);

std::cout << "before swapping" << std::endl;
print_unordered_set(s1);
print_unordered_set(s2);

s1.swap(s2);
std::cout << "after first swapping" << std::endl;
print_unordered_set(s1);
print_unordered_set(s2);

std::cout << "after second swapping" << std::endl;
std::tr1::swap(s1, s2);
print_unordered_set(s1);
print_unordered_set(s2);
umultiset_i ms1, ms2;

ms1.insert(1);
ms1.insert(2);
ms1.insert(3);

ms2.insert(4);
ms2.insert(5);
ms2.insert(6);

std::cout << "before swapping" << std::endl;
print_unordered_multiset(ms1);
print_unordered_multiset(ms2);

ms1.swap(ms2);
std::cout << "after first swapping" << std::endl;
print_unordered_multiset(ms1);
print_unordered_multiset(ms2);

std::cout << "after second swapping" << std::endl;
std::tr1::swap(ms1, ms2);
print_unordered_multiset(ms1);
print_unordered_multiset(ms2);
before swapping
3 2 1
6 5 4
after first swapping
6 5 4
3 2 1
after second swapping
3 2 1
6 5 4
before swapping
3 2 1
6 5 4
after first swapping
6 5 4
3 2 1
after second swapping
3 2 1
6 5 4

Hashing and comparison

Both containers allow you to access the hashing function and the comparison function (for comparing two values).

unordered_set unordered_multiset
uset_i s;

uset_i::hasher hfunc = s.hash_function();
std::cout << "hash(1)   = " << hfunc(1)   << std::endl;
std::cout << "hash(22)  = " << hfunc(22)  << std::endl;
std::cout << "hash(333) = " << hfunc(333) << std::endl;

uset_i::key_equal eqfunc = s.key_eq();
std::cout << "key_eq(1, 1) = "  << std::boolalpha
          << eqfunc(1, 1) << std::endl;
std::cout << "key_eq(1, 2) = "  << std::boolalpha
          << eqfunc(1, 2) << std::endl;
umultiset_i ms;

umultiset_i::hasher hfunc = ms.hash_function();
std::cout << "hash(1)   = " << hfunc(1)   << std::endl;
std::cout << "hash(22)  = " << hfunc(22)  << std::endl;
std::cout << "hash(333) = " << hfunc(333) << std::endl;

umultiset_i::key_equal eqfunc = ms.key_eq();
std::cout << "key_eq(1, 1) = "  << std::boolalpha
          << eqfunc(1, 1) << std::endl;
std::cout << "key_eq(1, 2) = "  << std::boolalpha
          << eqfunc(1, 2) << std::endl;
hash(1)      = 16807
hash(22)     = 369754
hash(333)    = 5596731
key_eq(1, 1) = true
key_eq(1, 2) = false
hash(1)      = 16807
hash(22)     = 369754
hash(333)    = 5596731
key_eq(1, 1) = true
key_eq(1, 2) = false

Conclusions

Hash tables were long awaited in the C++ library because they perform insertion and look-up time based on hash values. TR1 defines four hash tables in headers <unordered_map> and <unordered_set>. These new classes fulfill all the requirements for containers and provide methods for accessing the elements. Hopefully, this article provided a good introduction for using these new classes.



About the Author

Marius Bancila

Marius Bancila is a Microsoft MVP for VC++. He works as a software developer for a Norwegian-based company. He is mainly focused on building desktop applications with MFC and VC#. He keeps a blog at www.mariusbancila.ro/blog, focused on Windows programming. He is the co-founder of codexpert.ro, a community for Romanian C++/VC++ programmers.

Comments

  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Event Date: April 15, 2014 The ability to effectively set sales goals, assign quotas and territories, bring new people on board and quickly make adjustments to the sales force is often crucial to success--and to the field experience! But for sales operations leaders, managing the administrative processes, systems, data and various departments to get it all right can often be difficult, inefficient and manually intensive. Register for this webinar and learn how you can: Align sales goals, quotas and …

  • Live Event Date: August 20, 2014 @ 1:00 p.m. ET / 10:00 a.m. PT When you look at natural user interfaces as a developer, it isn't just fun and games. There are some very serious, real-world usage models of how things can help make the world a better place – things like Intel® RealSense™ technology. Check out this upcoming eSeminar and join the panel of experts, both from inside and outside of Intel, as they discuss how natural user interfaces will likely be getting adopted in a wide variety …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds