Associative containers

The set, map, multiset and multimap are called associative containers because they associate keys with values. Well, at least maps and multimaps associate keys to values, but you can look at a set as a map that has no values, only keys (and they can in fact be implemented this way), and the same for the relationship between multiset and multimap. So, because of the structural similarity sets and multisets are lumped in with associative containers.

The most important basic operations with associative containers are putting things in, and in the case of a set, seeing if something is in the set. In the case of a map, you want to first see if a key is in the map, and if it exists you want the associated value for that key to be returned. Of course, there are many variations on this theme but that’s the fundamental concept. The following example shows these basics:

//: C04:AssociativeBasics.cpp

// Basic operations with sets and maps #include "Noisy.h"

#include <iostream> #include <set> #include <map>

using namespace std;

int main() {

Noisy na[] = { Noisy(), Noisy(), Noisy(), Noisy(), Noisy(), Noisy(), Noisy() };

// Add elements via constructor:

set<Noisy> ns(na, na+ sizeof na/sizeof(Noisy));

//Ordinary insertion: Noisy n;

ns.insert(n); cout << endl;

//Check for set membership:

cout << "ns.count(n)= " << ns.count(n) << endl; if(ns.find(n) != ns.end())

cout << "n(" << n << ") found in ns" << endl; // Print elements:

copy(ns.begin(), ns.end(), ostream_iterator<Noisy>(cout, " "));

cout << endl;

cout << "\n-----------\n"; map<int, Noisy> nm;

for(int i = 0; i < 10; i++)

Chapter 15: Multiple Inheritance

232

cout << "nm[" << j <<"] = " << nm[j] << endl;

nm.insert(make_pair(47, n));

<<nm.count(10) << endl; cout << "nm.count(11)= "

<<nm.count(11) << endl;

map<int, Noisy>::iterator it = nm.find(6); if(it != nm.end())

cout << "value:" << (*it).second

<<" found in nm at location 6" << endl; for(it = nm.begin(); it != nm.end(); it++)

cout << (*it).first << ":"

<<(*it).second << ", ";

The set<Noisy> object ns is created using two iterators into an array of Noisy objects, but there is also a default constructor and a copy-constructor, and you can pass in an object that provides an alternate scheme for doing comparisons. Both sets and maps have an insert( ) member function to put things in, and there are a couple of different ways to check to see if an object is already in an associative container: count( ), when given a key, will tell you how many times that key occurs (this can only be zero or one in a set or map, but it can be more than one with a multiset or multimap). The find( ) member function will produce an iterator indicating the first occurrence (with set and map, the only occurrence) of the key that you give it, or the past-the-end iterator if it can’t find the key. The count( ) and find( ) member functions exist for all the associative containers, which makes sense. The associative containers also have member functions lower_bound( ), upper_bound( ) and

equal_range( ), which actually only make sense for multiset and multimap, as you shall see (but don’t try to figure out how they would be useful for set and map, since they are designed for dealing with a range of duplicate keys, which those containers don’t allow).

Designing an operator[ ] always produces a little bit of a dilemma because it’s intended to be treated as an array-indexing operation, so people don’t tend to think about performing a test before they use it. But what happens if you decide to index out of the bounds of the array? One option, of course, is to throw an exception, but with a map “indexing out of the array” could mean that you want an entry there, and that’s the way the STL map treats it. The first for loop after the creation of the map<int, Noisy> nm just “looks up” objects using the operator[ ], but this is actually creating new Noisy objects! The map creates a new key-value

Chapter 15: Multiple Inheritance

233

pair (using the default constructor for the value) if you look up a value with operator[ ] and it isn’t there. This means that if you really just want to look something up and not create a new entry, you must use count( ) (to see if it’s there) or find( ) (to get an iterator to it).

The for loop that prints out the values of the container using operator[ ] has a number of problems. First, it requires integral keys (which we happen to have in this case). Next and worse, if all the keys are not sequential, you’ll end up counting from 0 to the size of the container, and if there are some spots which don’t have key-value pairs you’ll automatically create them, and miss some of the higher values of the keys. Finally, if you look at the output from the for loop you’ll see that things are very busy, and it’s quite puzzling at first why there are so many constructions and destructions for what appears to be a simple lookup. The answer only becomes clear when you look at the code in the map template for operator[ ], which will be something like this:

mapped_type& operator[] (const key_type& k) { value_type tmp(k,T());

return (*((insert(tmp)).first)).second;

}

Following the trail, you’ll find that map::value_type is:

typedef pair<const Key, T> value_type;

Now you need to know what a pair is, which can be found in <utility>:

template <class T1, class T2> struct pair {

typedef T1 first_type; typedef T2 second_type; T1 first;

T2 second; pair();

pair(const T1& x, const T2& y)

:first(x), second(y) {}

//Templatized copy-constructor: template<class U, class V>

pair(const pair<U, V> &p);

};

It turns out this is a very important (albeit simple) struct which is used quite a bit in the STL. All it really does it package together two objects, but it’s very useful, especially when you want to return two objects from a function (since a return statement only takes one object). There’s even a shorthand for creating a pair called make_pair( ), which is used in

AssociativeBasics.cpp.

So to retrace the steps, map::value_type is a pair of the key and the value of the map – actually, it’s a single entry for the map. But notice that pair packages its objects by value, which means that copy-constructions are necessary to get the objects into the pair. Thus, the

Chapter 15: Multiple Inheritance

234

creation of tmp in map::operator[ ] will involve at least a copy-constructor call and destructor call for each object in the pair. Here, we’re getting off easy because the key is an int. But if you want to really see what kind of activity can result from map::operator[ ], try running this:

//: C04:NoisyMap.cpp

// Mapping Noisy to Noisy #include "Noisy.h" #include <map>

using namespace std;

int main() {

map<Noisy, Noisy> mnn; Noisy n1, n2;

cout << "\n--------\n"; mnn[n1] = n2;

cout << "\n--------\n"; cout << mnn[n1] << endl; cout << "\n--------\n";

} ///:~

You’ll see that both the insertion and lookup generate a lot of extra objects, and that’s because of the creation of the tmp object. If you look back up at map::operator[ ] you’ll see that the second line calls insert( ) passing it tmp – that is, operator[ ] does an insertion every time. The return value of insert( ) is a different kind of pair, where first is an iterator pointing to the key-value pair that was just inserted, and second is a bool indicating whether the insertion took place. You can see that operator[ ] grabs first (the iterator), dereferences it to produce the pair, and then returns the second which is the value at that location.

So on the upside, map has this fancy “make a new entry if one isn’t there” behavior, but the downside is that you always get a lot of extra object creations and destructions when you use map::operator[ ]. Fortunately, AssociativeBasics.cpp also demonstrates how to reduce the overhead of insertions and deletions, by not using operator[ ] if you don’t have to. The insert( ) member function is slightly more efficient than operator[ ]. With a set you only hold one object, but with a map you hold key-value pairs, so insert( ) requires a pair as its argument. Here’s where make_pair( ) comes in handy, as you can see.

For looking objects up in a map, you can use count( ) to see whether a key is in the map, or you can use find( ) to produce an iterator pointing directly at the key-value pair. Again, since the map contains pairs that’s what the iterator produces when you dereference it, so you have to select first and second. When you run AssociativeBasics.cpp you’ll notice that the iterator approach involves no extra object creations or destructions at all. It’s not as easy to write or read, though.

If you use a map with large, complex objects and discover there’s too much overhead when doing lookups and insertions (don’t assume this from the beginning – take the easy approach

Chapter 15: Multiple Inheritance

235