STL 101 Part D - sorted associative containers, Set and Map

• Download demo project - 83.7 Kb
• Download source - 6.28 Kb

Introduction

Welcome to part IV of my series on the STL. This time around I want to lok at two containers called set and map. I'll explain set first and then look at what map brings to the party.

Creating a set

Both of these containers are implemented as a binary tree by every STL implementation I know of. As a result, the push_back/pop_back paradigm does not work here - items are inserted in order, so you are not able to specify a location. Instead we use the insert method, which can take a location as an option, this is a suggestion to the STL where to start looking for an insert location, and can obviously speed things up tremendously if a large set is being built. To remove items from a set, we need to use the find algorithm and pass the returned iterator into the erase function. Whenever you use the find algorithm, you should check if the return value is the same as end(), just in case the item was not found.

set<STRING> setString; 
setString.insert("this"); 
setString.insert("is"); 
setString.insert("a"); 
setString.insert("test"); 
setString.insert("boys"); 
cout << "setString" << endl << endl; 

set<STRING>::iterator it = setString.begin(); 

while(it != setString.end()) 
{
    cout << *it << endl; 
    ++it; 
} 

it = setString.find("boys"); 
if (it != setString.end()) 
    setString.erase(it); 
    
it = setString.begin(); 

cout << endl << endl << "We removed the 'boys'" << endl << endl; 

while(it != setString.end()) 
{ 
    cout << *it << endl; 
    ++it;
}

This produces the following output:

setString
a
boys
is
test
this

We removed the 'boys'
a
is
test
this

Specifying sort order

The other thing we can do when we create a set is specify the manner in which items are sorted. I could use string in this container also, but I've elected to use char * from here on instead. We are going to create a set with the same data as before, but sort it in reverse order through a functor as follows.

struct gtstr
{
    bool operator()(const char * s1, const char * s2) const
    {
        return (strcmp(s1, s2) > 0);
    }
};

now in our main function:

set<char gtstr*,> setString2;
setString2.insert("this");
setString2.insert("is");
setString2.insert("a");
 setString2.insert("test");
setString2.insert("boys");
cout
<<
endl
<<

"setString2"  <<  endl  <<  endl;

copy(setString2.begin(), setString2.end(),
     ostream_iterator<char*>(cout, "\r\n"));

The output looks like this:

setString2
this
test
is
boys
a

As you can see, our policy has allowed the items to be sorted in reverse order. While this is a trivial case, user defined types will always require such a functor because no default sort order will be possible.

Advantages of set

The set has a number of advantages over other containers. It has a much better insert cost than vector, and a much better search cost than list, making it an excellent trade off in some situations. As Scott Meyers points out though, if you're creating a container which does not change much, then a sorted array may be a better choice. In both cases the main advantage comes from the ease of searching a container that is sorted, and the STL provides a number of functions especially for use with set.

Set algorithms

The STL contains a number of algorithms that perform set related functions on a sorted range, as follows:

Set and map offer bidirectional iterators, so any other algorithms that accept these iterators can be used with them, and any sorted container that supports at least these iterators can be used with the set functions listed above. The following code uses the last four of these algorithms on two sets that are similar, but not the same

set<char gtstr*,> setString3;

setString3.insert("this");
setString3.insert("could");
setString3.insert("well");
setString3.insert("be");
setString3.insert("the");
setString3.insert("test");

cout << endl << "Set  3"  << endl  <<  endl;

copy(setString3.begin(), setString3.end(), ostream_iterator<char*>(cout, "\r\n"));

cout << endl << endl <<  "Set  Difference"  << endl  <<  endl;

std::set_difference(setString2.begin(), setString2.end(), 
         setString3.begin(), setString3.end(),
    ostream_iterator<char *>(cout, " "));

cout << endl << endl <<  "Set  Intersection"  << endl  <<  endl;

std::set_intersection(setString2.begin(), setString2.end(), 
         setString3.begin(), setString3.end(),
    ostream_iterator<char *>(cout, " "));

cout << endl << endl <<  "Set  Symmetric  Difference" << endl  <<  endl;

std::set_symmetric_difference(setString2.begin(), setString2.end(), 
         setString3.begin(), setString3.end(),
    ostream_iterator<char *>(cout, " "));

cout << endl << endl <<  "Set  Union"  << endl  <<  endl;

std::set_union(setString2.begin(), setString2.end(), 
         setString3.begin(), setString3.end(),
    ostream_iterator<char *>(cout, " "));

and the output is as follows:

Set 3
well
this
the
test
could
be
Set Difference
is boys a
Set Intersection
this test
Set Symmetric Difference
well the could be is boys a
Set Union
well this the test could be is boys a

A note about hashed sets

As has been noted, set and map are generally implemented as binary trees. The other option is to use has tables, and while they are not part of the standard yet, many implimentation offer hashed sets and maps. The advantage of hashing is that it provides potentially better performance than a binary tree, but a binary tree provides stable performance where a hash table at worst can provide O(n) performance. I'm guessing that is the reason that when time became tight, the binary tree implementation got into the standard and the hash one was made to wait.

Map

A map is essentially a set which also stores a second value in each location. The first value can then be considered a key whereby the second can be found. An example we have all probably used exists in the heart of MFC. Because MFC wraps a HWND into a class, but must ultimately process it in a global WndProc, it creates a map which links a HWND to an instance of a CWnd*. Then the WinProc can access the class by looking it up through the

HWND

To add to a map, we can use the insert method, but it is much easier to use array type notation, like this:

map<int string,> mapInt2String;

mapInt2String[0] = "string number 0";
mapInt2String[2] = "string number 2";
mapInt2String[3] = "string number 3";
mapInt2String[5] = "string number 5";
mapInt2String[6] = "the quick brown fox jumped over the lazy dog";

Items can be extracted in the same manner, but there is a slight problem. The [] operator will create a new item if one does not exist in that location. The following code illustrates the problem:

cout << "\r\n\r\n\r\nMap Int2String has " << mapInt2String.size() 
     << " elements\r\n";

cout << "mapInt2String[6] = " << mapInt2String[6];

cout << "\r\nMap Int2String has " << mapInt2String.size()
     << " elements\r\n";

cout << "mapInt2String[1] = " <<mapInt2String[1];

cout << "\r\nMap Int2String has " << mapInt2String.size() 
     << " elements\r\n";

This outputs the following:

mapInt2String has 5 elements
mapInttoString[6] = the quick brown fox jumped over the lazy dog
mapInt2String has 5 elements
mapInttoString[1] =
mapInt2String has 6 elements

Correctly accessing elements in a map

The way to remove an element is to use the erase function, and the way to check if an element exists is to use find prior to accessing it.

cout << "\r\nErase rogue element...\r\n";

mapInt2String.erase(mapInt2String.find(1));

cout << "\r\nMap Int2String has " << mapInt2String.size() 
     << " elements\r\n";

if (mapInt2String.find(4) != mapInt2String.end())
    cout << "mapInt2String[4] = " << mapInt2String[4];

cout << "\r\nMap Int2String has " << mapInt2String.size() 
     << " elements\r\n\r\n\r\n\r\n";

This outputs the following:

Erase rogue element....
mapInt2String has 5 elements
mapInt2String has 5 elements

In other words, our second attempt to access a non-existent element did not result in an unwanted insertion.

Map Iterators

Being an STL container, a map uses iterators to control access to it's elements. However, a map stores two values in each location, so what does the iterator give us to deal with this ? An iterator from a map returns a pair<key, value>, and the two values involved can be accessed using

pair.first

std::map<int string,>::iterator itMap = mapInt2String.begin();

while (itMap != mapInt2String.end())
{
    cout << "First element = " << itMap->first << endl;
    cout << "Second element = " << itMap->second << endl;
    ++itMap;
}

This will output the following

First element = 0
Second element = string number 0
First element = 2
Second element = string number 2
First element = 3
Second element = string number 3
First element = 5
Second element = string number 5
First element = 6
Second element = the quick brown fox jumped over the lazy dog

The first and second elements provide read and write access, so that an element can be changed as follows:

itMap = mapInt2String.find(0);

if (itMap != mapInt2String.end())
    itMap->second = "Would you, could you in a car ? "
                         "Eat them, eat them, here they are !!";

Printing out the list again would reveal that this element has now been changed. Accessing first allows changing of the key for an element in the same way.

Having established this, a better way to access an element would be to catch the iterator returned by our find test, and call second on it, as using the [] operators after establishing the existence of an element requires two lookups, whereas storing the iterator means only one is required.

Using multiset/multimap

The set and map both require a unique key, that is to say, inserting the same value into a set twice results in only one insertion, the same is true of two elements with the same key into a map. Where more than one element of the same value is required, we must use multiset/multimap. These containers work the same as thier single element cousins, but have some extra functions to assist us in using them

I hope you've found this article useful, and that it inspires you to make use of the STL. Up until now I have spoken mainly about the different containers the STL provides ( although some remain uncovered as of yet ), and how they can be specialised. However, the real power of the STL lies in the way it interfaces with the algorithms the standard library provides. A selection of these algorithms have appeared in the series to date, but the next article will seek to list a good number of them and explore the ways in which they can be used.

See you then.