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 looked something like the following:

  // Example 1(a): 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 given code is interfering 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:

Figure 3: Figure 2 after Example 1(a) executes... Problem!

Example 1(a) corrupts the map's internal structure. 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; in Example 1(a), the change was made through a reference into the container, without calling any map member functions.

Note that, if the Example 1(a) code had changed the key in such a way that the relative ordering remained unchanged, there would have been no problem. 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 1(a), 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 maps and multimaps, 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 celebrities and incite mass media coverage to increase awareness of this deplorable problem. This would prevent code like that in Example 1(a), 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 Remove-Then-Insert"
(Better, But Still Insufficient)

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

  // Example 1(b): 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.remove( 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:

o         If the Key type has state that is visible to other code (for example, if Key contains a pointer to a shared buffer that can be modified by other parts of the system without going through the Key object) and that affects the way Compare compares Key objects, then changing the visible state can still change the relative ordering of keys. Note that this change can happen without the knowledge of the code that uses the associative container, hence without a remove-then-reinsert operation.

o         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. Now 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 since we haven't found a good answer yet we might as well look to see what set does about it. Now, since a set can be thought of as just a map<Key, Value> without a Value type, you might expect that set would do much the same thing with its key type as map does, and that a set<Key>::iterator and a set<Key>::const_iterator would be the same thing, that is, that they would both point to a const Key. This would prevent a programmer from modifying the pointed-at key.

This is not the case, however, and set::iterator was deliberately designed to point at a non-const key because the contained value might contain other information that does not affect comparison.

Why does the standard treat set and map keys differently, and seemingly contradictorily? The difference comes about because sets and maps are intended to be used somewhat differently. For example, say that 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 of 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 being 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. And, in fact, both a map<string, Customer> and a set<Customer> will let you change the Customer object once it's in the container, except that the set<Customer> method requires that you not change a Customer object in such a way that would change its relative ordering in the container.

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

The Key Requirement (Reprise)

So what rule should we follow to ensure that we're using associative containers correctly? Although it would be nice to codify more specific discipline, const alone won't do it (and, at any rate, set and map have inconsistent "key constness" policies), 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.

In the Mail

In the previous column, among other things I recommended that you consider using deque by default instead of vector, on the grounds that deque is easier to use because it's naturally more efficient for growth, and at the same time deque isn't much slower across the board in real-world implementations of the standard library.^[2] In the column before that, I criticized the standard vector<bool> specialization because it forces on all users the choice of optimizing for space at the possible expense of speed, and because it breaks the standard container requirements.^[3]

Astute Reader Mark Frey wrote me about a seeming dichotomy in this advice. In part, he wrote:

"I find it a little bit hard to reconcile your complaint that this specialization [vector<bool>] sacrifices speed for space savings on one hand, with your recommendation that std::deque be preferred because of its friendly memory use despite its performance penalty."

This is a good point, and others may be wondering about this too, so let me explain why I don't think I'm being inconsistent. I'm actually following a basic principle of optimization:

Don't optimize prematurely: Write for clarity and correctness first, and only optimize once a profiler tells you when and where it's needed.

From this principle we can draw both conclusions:

1.       The vector<bool> specialization is a classic premature optimization in that it's forced on all users regardless of their programming environment and context, and is rightly criticized on those grounds. (It also has a bigger problem that's not related to optimization: It breaks container requirements and therefore can't be used reliably with generic algorithms.)

2.       The advice to "prefer deque" was based on the principle of writing for clarity and correctness first. When you know, by measuring, that the deque is causing a performance bottleneck, it should of course be replaced with something faster. But in general it's best to prefer habits that encourage simplicity and correctness first, and here deque helps out because it eliminates the need to know about and consider vector's reserve() baggage when growing vectors.