Solution

I l @ ve RuBoard

Associative Containers: Review

First, a quick review: Here are some key points about what it means to iterate over an associative container, and about what associative containers' iterators do and are.

The four standard associative containers are summarized in Figure 1. Each of these containers internally maintains its elements in a way that allows fast traversal in nondescending key order and fast retrieval by key, where the keys are always compared according to the provided Compare type (this defaults to less<Key> , which uses the operator<() provided for Key objects). Whenever a new key is inserted into a container, the container finds a proper place to insert the new key so that it maintains the proper ordering of its internal data structure.

Figure 1. The standard associative containers (minus the allocator parameters).

Iterators are easy to implement, because they are supposed to traverse the entries in nondescending Key order, and the container already internally stores the elements in a way that naturally supports that ordering. Pretty basic, right?

Which brings us to the "key" issue:

The Key Requirement

An essential requirement, without which associative containers could not work reliably at all, is this: Once a key has been inserted into the container, that key had better not be changed in any way that would change its relative position in the container. If that ever did happen, the container wouldn't know about it, and its assumptions about the ordering of its entries would be violated, searches for valid entries could fail, iterators would no longer be guaranteed to traverse the contents in key order, and in general Bad Things would happen.

I'll illustrate this issue in the context of an example, and then discuss what you can do about it.

A Motivating Example

Consider a map<int,string> named m that has the contents shown in Figure 2; each node within m is shown as a pair<const int,string> . I'm showing the internal structure as a binary tree because this is what all current standard library implementations actually use.

Figure 2. Sample internal contents of a map<int, string> .

As the keys are inserted, the tree's structure is maintained and balanced such that a normal inorder traversal visits the keys in the usual less<int> ordering. So far, so good.

But now say that, through an iterator, we could arbitrarily change the second entry's key, using code that looks something like the following:

1. a) What's wrong with the following code? How would you correct it?

 // Example 8-1: Wrong way to change a // key in a map<int,string> m. //  map<int,string>::iterator i = m.find( 13 );   if( i != m.end() )   {   const_cast<int&>( i->first ) = 9999999; // oops!   }  

Note that we have to cast away const to get this code to compile. More on that in a moment. The problem here is that the code interferes with the map 's internal representation by changing the map 's internals in a way that the map isn't expecting and can't deal with.

Example 8-1 corrupts the map 's internal structure (see Figure 3). Now, for example, an iterator traversal will not return the contents of the map in key order, as it should. For example, a search for key 144 will probably fail, even though the key exists in the map . In general, the container is no longer in a consistent or usable state. Note that it is not feasible to require the map to automatically defend itself against such illicit usage, because it can't even detect this kind of change when it occurs. In Example 8-1, the change was made through a reference into the container, without calling any map member functions.

Figure 3. Figure 2 after Example 8-1 executes. Problem!

If the Example 8-1 code had changed the key in such a way that the relative ordering remained unchanged, there would have been no problem for this implementation of map . The problem is only with code that attempts to change the relative ordering of keys once they are in the container.

What's the best way to deal with this? Ideally, we would like to prevent this through a suitable coding standard. What, then, should such a coding standard say?

Option #1: Say " const Means const !" (Insufficient)

In Example 8-1, we needed to cast away const in order to change the key. This is because standard C++ actively tries to prevent code that changes the relative ordering of keys. In fact, standard C++ enforces a (seemingly) stricter requirement ”namely, that for both map s and multimap s, keys should not be modified at all. A map<Key, Value>::iterator points to a pair<const Key, Value> which, apparently, lets you modify the value part, but not the key part, of the pointed-at map entry. This, again apparently, prevents a key from changing at all, much less changing in a way that would alter its position in the map object's internal ordering.

One option, then, is to print large posters that say " const means const !" and hold rallies with celebrity speakers and incite mass media coverage to increase awareness of this deplorable problem. This would prevent code like that in Example 8-1, which doesn't work in practice anyway, wouldn't it?

It's a good idea, but unfortunately even telling people to respect const isn't enough. For example, if the Key type has a mutable member that affects the way Compare compares Key objects, then calling const member functions on a const key can still change the relative ordering of keys.

Option #2: Say "Always Change Keys Using Erase-Then-Insert" (Better, But Still Insufficient)

A better, but still insufficient, solution is to follow this discipline: To change a key, remove it and reinsert it. For example:

b) To what extent are the problems fixed by writing the following instead?

 // Example 8-2: Better way to change a key // in a map<int,string> m. // map<int,string>::iterator i = m.find( 13 ); if( i != m.end() ) {  string s = i->second;   m.erase( i );   m.insert( make_pair( 9999999, s ) ); // OK   }  

This is better, because it avoids any change to keys, even keys with mutable members that are significant in the ordering. It even works with our specific example. So this must be the solution, right?

Unfortunately, it's still not enough in the general case, because keys can still be changed while they are in the container. "What?" one might ask. "How can keys be changed while they're in the container, if we adopt the discipline of never changing key objects directly?" Here are two counterexamples:

1. Let's say the Key type has some externally available state that other code can get at ”for example, a pointer to a shared buffer that can be modified by other parts of the system without going through the Key object. Let's also say that that externally available state participates in the comparison performed by Compare . Then making a change in the externally available state, even without the knowledge of the Key object and without the knowledge of the code that uses the associative container, can still change the relative ordering of keys. So in this case, even if the code owning the container tries to follow an erase-then-reinsert discipline, a key ordering change can happen at any time somewhere else and therefore without an erase-then-reinsert operation.

2. Consider a Key type of string and a Compare type that interprets the key as a file name and compares the contents of the files. It's obvious that even if the keys are never changed, the relative ordering of keys can still change if the files are modified by another process, or (if the file is shared on a network) even by a user on a different machine on the other side of the world.

What About set?

This brings us to set . Because we haven't found a good answer yet for map , we might as well look to see what set does about it.

2. Can you modify a set 's contents through a set::iterator ? Why or why not?

One way to think of a set is as just a map<Key, Value> with a Value type of void . You might expect that set would do much the same thing with its key type as does map , and that a set<Key>::iterator and a set<Key>::const_iterator would be the same thing ”that is, they would both point to a const Key . This would prevent a programmer from modifying the pointed-at key.

Alas, the standard is not as clear about this for set as it is for map , but it's reasonable to want to change an object inside a set ”after all, the contained object might well contain other information that does not affect comparison. There have been two distinct opinion camps, with differing ideas on the question of whether set::iterator ought to point at a non- const key, and so it should be no surprise that in some standard library implementations it does and in some it doesn't. In other words, in practice you can't portably rely on being able to modify an element of a set through a set::iterator without a const_cast . As this book goes to press, the current intent within the standards committee is to add wording to the standard that formally requires that both set::iterator and set::const_iterator be constant iterators, and that if you want to change an object in a set , you must use the const_cast bazooka.

There are, however, good reasons to want to use the bazooka. Remember that set s and map s are often intended to be used somewhat differently. For example, say you want to implement a lookup that, given a customer's name, finds the customer's address or phone number. Then you might implement a map<string, CustData> , where the key is the customer's name and the value is a CustData structure that contains address and telephone information.

But what if you already have a perfectly good Customer class that contains the customer's name and information? Then it might seem a waste of programmer time to add the needless complexity of yet another CustData structure that contains all the same information except for one name string. On the other hand, it would be wasteful of runtime resources to implement a map<string, Customer> , where the key is a redundant copy of the customer's name, which is already stored inside the Customer object. We really shouldn't have to store that name twice. Instead, you would naturally think of implementing a set<Customer> which needs no new data structure and incurs no redundant string overhead. A map<string, Customer> will let you change the Customer object once it's in the container ”and so should set<Customer> , but in reality (and probably soon in legality) you will have to do it with a const_cast . Some current implementations of set will let you change it without a cast; some won't. If you're using one that will let you change it, and/or are deliberately using const_cast to change it, remember that implementations of set still require that you not change a Customer object in such a way that would change its relative ordering in the container.

Noting that our first two attempts to write a more specific rule didn't cover all the cases, and noting that even set and map handle things a little differently, perhaps we can do no better than a general rule.

The Key Requirement (Reprise)

What rule should we follow to ensure that we're using associative containers correctly? Although it would be nice to codify a more-specific discipline, const alone won't do it (and, at any rate, set and map have divergent "key const ness" policies in practice today), and simple coding rules alone won't do it. So we can't really be much more specific than to simply state the requirement and add: "You have to know what you're doing."

The Associative Container Key Rule

Once a key has been inserted into an associative container, that key must never change its relative position in the container .

Be aware of the direct and indirect ways by which a key might change its relative order, and avoid those practices. You'll be avoiding needless problems with the standard associative containers.

I l @ ve RuBoard