Understanding the New Set and Map Containers in the C++11 Standard Library

by Steve Clamage and Darryl Gove

One of the areas in the new C++ standard that has seen the most enhancement is the Standard Library. The functionality that is most likely to be immediately useful to developers is the additions to the container classes. This article describes the new set and map containers.


Published April 2014


Want to comment on this article? Post the link on Facebook's OTN Garage page.  Have a similar article to share? Bring it up on Facebook or Twitter and let's discuss.

Unordered Maps

There has been a map template in the Standard Library since C++03, which has now been augmented with an unordered map. An unordered map, as its name suggests, maintains an unordered mapping from one type of element to another. It is possible that an unordered map might have faster lookups than an ordered map in some situations.

The code in Listing 1 demonstrates how elements can be inserted into and read from an unordered map. The map is instantiated to be a mapping from one integer to another. The code inserts 10 mappings into the map, and then the subsequent loop prints them out.

#include <unordered_map>
#include <algorithm>

int main()
{
    std::unordered_map <int, int> m;
    for (int i=0; i<10; i++)
      { m[i]=((i*32315^393)&15); }

    for( std::unordered_map<int,int>::value_type p : m)
      { printf("%i -> %i\n",p.first, p.second); }
}

Listing 1

In Listing 1, we are also using the new C++11 range-based for. This iterates over all the elements in the container passing each one into the loop body. Each element in an unordered map is a pair of elements. In the loop body, we access the individual components of this pair. Listing 2 demonstrates compiling and running the code in Listing 1.

$ CC -std=c++11 t.c
$ ./a.out
9 -> 10
8 -> 1
7 -> 4
6 -> 11
5 -> 14
4 -> 5
3 -> 8
2 -> 15
1 -> 2
0 -> 9

Listing 2

Unordered Sets

Similarly, ordered sets have existed in C++ since C++03. The C++11 standard introduces unordered sets, which might have improved performance for some workloads. Listing 3 shows an example of an unordered set.

#include <unordered_set>
#include <algorithm>

int main()
{
    std::unordered_set <int> s;
    for (int i=0; i<10; i++) { s.insert((i*32315^393)&15); }

    std::for_each( s.begin(), s.end(),
                  [](int v ) { printf("%i\n",v); } );
}

Listing 3

The code in Listing 3 inserts a group of numbers into the set and then prints the contents of the set using the for_each operator.

In Listing 3, we are also using the new C++11 feature for_each. As its name suggests, this feature iterates over a range of elements applying a function to each element. In the example, the function is specified as a lambda expression. The mappings are passed into the lambda expression as pairs. The first element in the pair is the key, and the second element is the value.

Unordered Multimaps and Multisets

The Standard Library now has support for unordered multimaps and multisets. A multiset allows the same element to be inserted into a set multiple times; in contrast, an unordered set allows an element to be inserted only a single time. Similarly, a multimap allows multiple copies of the same mapping.

In Listing 4, we repeatedly insert the value one into an unordered multiset. When the set is printed, we see all the copies printed.

#include <unordered_set>
#include <algorithm>

int main()
{
    std::unordered_multiset <int> s;
    for (int i=0; i<10; i++) {s.insert(1); }

    std::for_each(s.begin(), s.end(),
                  [](int v ) { printf("%i\n",v); } );
}

Listing 4

In Listing 5, we repeatedly insert an identical mapping into a multimap, and we then print all the mappings.

#include <unordered_map>
#include <algorithm>

int main()
{
    std::unordered_multimap <int, int> m;
    for (int i=0; i<10; i++)
      { m.insert({1,1}); }

    for( std::unordered_map<int,int>::value_type p : m)
      { printf("%i -> %i\n",p.first, p.second); }
}

Listing 5

Conclusion

The new C++11 standard introduces some very useful new types of containers for sets and maps. Oracle Solaris Studio 12.4 includes support for these containers.

See Also

Further details can be found on the Oracle Solaris Studio website.

About the Authors

Steve Clamage is a senior engineer in the Oracle Solaris Studio team and project lead for Oracle's C++ compiler. He has been the chair of the U.S. C++ Standards Committee since 1996.

Darryl Gove is a senior engineer in the Oracle Solaris Studio performance team, working on optimizing applications and benchmarks for current and future processors. He is also the author of the books Multicore Application Programming, Solaris Application Programming, and The Developer's Edge. He has a blog at http://blogs.oracle.com/d/.

Revision 1.0, 04/07/2014

Follow us:
Blog | Facebook | Twitter | YouTube