When Is a Container Not a Container?

. Herb Sutter is Chief Technology Officer at PeerDirect and the principal architect of its heterogeneous database replication product. He is also PeerDirect's representative at the ISO/ANSI C++ and SQL committees, and the author of the forthcoming books Peer Distributed Databases and C++ Guru of the Week (Addison Wesley Longman). He can be contacted at [email protected].

Little Stanislaus watched his mother as she busily rummaged in the refrigerator. "Be a dear, Stan," she said to him without looking around, "and get me a container I can pour this juice into."

Stanislaus was a good boy, and he was pretty sure he knew what a container was. He looked about and saw just the thing: a bright, shiny plastic bowl with a mesh bottom. Well, little Stanislaus knew that a bowl was a container, so he fetched it happily and held it out for his mother. She was very busy and started to pour the juice before she got a good look at what she was pouring it into. As Stanislaus held the sieve with a helpful smile, the juice ran merrily into the sieve ... and through it, onto the floor.

Stanislaus got a scolding that day. He didn't really think it was his fault, though. The bowl with the mesh bottom looked a lot like the other bowls; how was he to know that it didn't meet his mother's container requirements?

In this column we'll take a look at some of the C++ Standard's container requirements, various reasons to use the technique of taking pointers into a container, and—to your possible consternation and likely surprise—a standard container that isn't really a container at all.

Consider the following code:

// Example 1: Is this code valid? safe? good?
vector v;
char* p = &v[0];
... do something with *p ...
Is this code valid? Well, the standard guarantees that if a conforming sequence (such as vector) provides operator[], that function must return an lvalue of type char, which in turn can have its address taken. So the answer to the question is yes; as long as v is not empty, the code in Example 1 is perfectly valid.

Is this code safe? Many programmers are initially surprised at the idea of taking a pointer into a container, but the answer is yes; it's safe as long as we remain aware of when the pointer might be invalidated, which is pretty much whenever an equivalent iterator would be invalidated. For example, if we decide to start inserting or erasing elements of the container, iterators as well as any pointers into the container will be invalidated as the underlying memory moves.

But does this code make sense? Again, yes; it can make perfect sense to have pointers or references into a container. One common case is when you read a data structure into memory once, say on program startup, and thereafter you never modify it, but you do need to access it in different ways. In that case it can make sense to have additional data structures that contain pointers into the main container to optimize different access methods. I'll give a simple example in the next section.

HOW COULD EXAMPLE 1 BE IMPROVED? Example 1 could be improved in one way:

// Example 1(b): An improvement
//		(when it's possible)
vector v;
vector::iterator i = v[0];
... do something with *i ...
In general, it's not a bad guideline to use iterators instead of pointers when you want to point at an object that's inside a container. After all, iterators are invalidated at mostly the same times and the same ways as pointers, and one reason that iterators exist is to provide a way to "point" at a contained object. So if you have a choice, prefer to use iterators into containers.

Unfortunately, you can't always get the same effect with iterators that you can with pointers into a container. There are two main potential drawbacks to the iterator method, and when either applies we have to continue to use pointers:

  1. You can't always conveniently use an iterator where you can use a pointer. (See next example.)

  2. Using iterators might incur extra space and performance overhead in cases in which the iterator is an object and not just a bald pointer.
For example, say that you have a map that is loaded once at program startup and is only queried thereafter. The idea is that, given a name, this makes it easy to look up the corresponding phone number in the fixed dictionary. But what if you need to do the reverse lookup too? A clean solution would be to build a second structure, perhaps a map that enables the reverse lookup but avoids doubling the storage overhead—because, using pointers, there's no need to store each name and phone number twice; the second structure simply has pointers into the first.

That's fine, and it will work well, but note that this effect would be more difficult to achieve using iterators instead of pointers. Why? Because the natural iterator candidate, map::iterator, points to a pair, and there's no handy way to get an iterator to only the name or phone number part by itself. (We could store the entire iterator and always explicitly say ->first and ->second everywhere, but that's inconvenient to code, and it means that the reverse-lookup map would need to be redesigned or replaced by a different structure.)

This brings us to the next (and in my opinion most interesting) point of today's theme:

// Example 2: Is this code valid?
void f( T& t ) {
	typename T::value_type* p1 = &t[0];
	typename T::value_type* p2 = &*t.begin();
	// ... do something with *p1 and *p2 ...
Before reading on, think about these questions: Is this code valid? If yes, under what conditions is it valid? Specifically, what kinds of things can we say about a T that makes this code valid? (Ignore runtime considerations such as whether t happens to be in a suitable state to have t[0] called on it; we're interested in program legality here.)

WHEN IS A CONTAINER NOT A CONTAINER? Well, is Example 2 valid? In short, yes, it can be valid. The longer answer involves thinking about what kinds of T would make the code valid: What characteristics and abilities must a suitable T have? Let's do some detective work:

  • To make the expression &t[0] valid, T::operator[] must exist and return something that understands operator&, which in turn must return a valid T::value_type* (or something that can be meaningfully converted to a valid T::value_type*).

    In particular, this is true of containers that meet the standard's container and sequence requirements and that implement the optional operator[], because that operator must return a reference to the contained object. By definition, you can then take the contained object's address.

  • To make the expression &*t.begin() valid, T::begin() must exist, and it must return something that understands operator*, which in turn must return something that understands operator&, which in turn must return a valid T::value_type* (or something that can be meaningfully converted to a valid T::value_type*).

    In particular, this is true of containers whose iterators meet the standard's iterator requirements because the iterator returned by begin(), when dereferenced using operator*, must return a reference to the contained object. By definition, you can then take the contained object's address.

WHICH BRINGS US TO THE AWKWARD PART So here's the thing: The code in Example 2 will work for any container in the Standard Library that supports operator[]. And if you take away the line containing "&t[0]", it will work for every container in the Standard Library—except for std::vector. To see why, note that the following template works for every type T except bool:

// Example 3: Works for every T except bool
void g( vector& v ) {
	T* p = &v.font();
	// ... do something with *p ...
Do you see why? At first (or even second and third) glance, it may seem odd that this is valid for all types but one. What makes vector so special?

The reason is as simple as it is unfortunate: Not all of the templates defined in the C++ Standard Library that look like containers actually are containers. In particular, the Standard Library requires a specialization of vector for bool, and the specialization std::vector is not a container in that it does not meet the standard library's requirements for containers. True, vector does appear in the "containers and sequences" part of the standard; and true, there's no note to indicate that it's neither a container nor a sequence. But, in fact, vector is not a container, and so it's not surprising that it cannot always be used like one.¥

If this state of affairs seems strange to you, you're not alone, but there is a logical explanation.

THE LIFE AND TIMES OF VECTOR The vector specialization was intentionally put into the standard to provide an example of how to write a proxied container. A "proxied container" is a container whose objects you don't get at directly; instead of giving you pointers or references to a contained object, a proxied container gives you proxy objects that can be used to indirectly access or manipulate a contained object. Proxied collections can be useful for cases in which the objects within the collection cannot be reliably accessed directly as though they were in memory, as with a disk-based collection that automatically pages pieces of itself in and out of memory under the covers as needed. So the idea was to show how to make such a proxied collection meet the requirements of a "container" in the sense defined by the Standard Library.

This would have been well and good, except that the container and iterator requirements were never updated to allow for proxied containers. In fact, proxied containers are categorically disallowed; a container::reference must be a true reference (T&), never a proxy. Iterators have similar requirements; dereferencing a forward, bidirectional, or random-access iterator must yield a true reference (T&), never a proxy. These points preclude any proxy-based containers from meeting the standard container requirements.

The reason vector has to be nonconforming is that it attempts to do extra work invisibly under the covers in an attempt to optimize for space. A normal bool object is at least as big as a char; sizeof(bool) is implementation defined and will vary from compiler to compiler, but it must be at least 1. Does that seem extravagant? Some people thought so, so vector tries to be more efficient about the amount of storage it uses: Instead of storing a full char or int for every contained "bool," it packs the bools and stores them as individual bits (inside, say, chars or ints) in its internal representation. This gives vector a space advantage of at least 8:1 on platforms with 8-bit "normal" bools, and possibly more. (By this point, some of you may have noticed that this optimization makes the name vector rather misleading: The things inside aren't really normal bools at all.)

Clearly one consequence of this packed representation is that vector can't simply return a normal bool& from its operator[] or its dereferenced iterators;§ instead, it has to return a "reference-like" proxy object that in many ways looks and smells like a bool& but is not a bool&. Unfortunately, that can also make access into a vector slower, because we have to deal with proxies instead of direct pointers and references (not to mention the extra bit-fiddling). So vector is not a pure optimization, but a tradeoff that favors "less space" at the expense of "potentially slower speed." More about this in a moment.

For example, whereas the functions vector::operator[]() and vector::front() normally return just a T& (a reference to the contained T), vector::operator[]() and vector::front() actually return a "reference-like" proxy object of type vector::reference. To make this proxy object look and feel as much like a real bool& as possible, reference provides an implicit conversion to booloperator bool()—so that a reference can be used almost anywhere a bool can be used, at least as a value. It also provides member functions operator=(bool), operator=(reference&), and flip(), which can be used to indirectly change the value of the bool that's actually inside the container, enabling natural coding styles like "v[0] = v[1];". (For greater amusement, note that the one service that vector::reference can't ever provide is a "bool* operator&();". That is, it can't provide a suitable address-of operator because there's no way to take the address of the individual bit inside the vector for which the reference object is serving as proxy.)

PROXIED CONTAINERS AND STL ASSUMPTIONS Bottom line: std::vector may be standard, but it's not a container.

Further, both the original STL's container requirements and the C++ Standard's container requirements are based on the implicit assumption (among others) that dereferencing an iterator is a constant-time operation and requires negligible time compared to other operations. As James Kanze correctly pointed out on the comp.std.c++ newsgroup a couple of years ago, neither of these assumptions is true for a disk-based container or a packed-representation container. For a disk-based container, access through the proxy object may require a disk seek, which can be orders of magnitude slower than main memory access. To illustrate, consider that you would be unlikely to apply a standard algorithm like std::find() to a disk-based container; the performance would be abysmal compared to a special-purpose replacement, largely because the fundamental performance assumptions for in-memory containers do not apply to disk-based containers. (For similar reasons, even in-memory containers like std::map provide their own find as a member function.) For a packed-representation container like vector, access through the proxy object requires bitwise operations, which are generally much slower than manipulation of a native type like an int. Further, whenever the proxy object construction and destruction can't be completely optimized away by the compiler, managing the proxies themselves adds further overhead.

Although vector was intended to be an example of how to write a proxied container so that other programmers could follow its example when writing disk-based or other containers whose contained objects cannot reliably be accessed directly, it also serves to demonstrate that the standard's container requirements do not allow proxied containers.

Proxied collections are a useful tool and often can be appropriate, especially for collections that can become very large. Every programmer should know about them. They just don't fit as well into STL as many people thought, that's all. Even vector is still a perfectly good model for how to write a proxied collection; it's just not a container, and it should be called something else ("bitvector" has been suggested) so that people won't think that it has anything to do with a conforming container.

BEWARE PREMATURE OPTIMIZATION If you're a regular reader of this column, you'll already be familiar with my regular harangues against premature optimization.# The rules boil down to: 1) Don't optimize early. 2) Don't optimize until you know that it's needed. 3) Even then, don't optimize until you know what's needed, and where.

By and large, programmers—including you and I—are notoriously bad at guessing the actual space/time performance bottlenecks in their own code. If you don't have performance profiles or other empirical evidence to guide you, you can easily spend days optimizing something that doesn't need optimizing and that won't measurably affect runtime space or time performance. What's even worse, however, is that when you don't understand what needs optimizing, you may actually end up pessimizing (degrading your program) by saving a small cost while unintentionally incurring a large cost.ß Once you've run performance profiles and other tests, and you actually know that a particular optimization will help you in your particular situation, then it's the right time to optimize.

By now you can probably see where I'm going with this: The most premature optimization of all is an optimization that's enshrined in the standard. In particular, vector intentionally favors "less space" at the expense of "slower speed"—and forces this optimization choice on all programs. This optimization choice implicitly assumes that almost all users of a vector of bools will prefer "less space" at the expense of "potentially slower speed"—that they will be more space constrained than performance constrained, and so on. This is clearly untrue; on many popular implementations a bool is the same size as an 8-bit char, and a vector of 1,000 bools consumes about 1K of memory. Saving that 1K is unimportant in many applications. (Yes, saving 1K of space is important in some environments such as embedded systems, and clearly some applications may manipulate vectors containing millions of bools in which the saved megabytes are real and significant.) The point is that the correct optimization depends on the application: If you are writing an application that manipulates a vector with 1,000 entries in an inner loop, you are likely to benefit more from potentially faster raw performance due to reduced CPU workload (without the overhead of proxy objects and bit-fiddling) than from the marginal space savings, even if the space savings would reduce cache misses.

SO WHAT SHOULD YOU DO? If you are using vector in your code, you may be using it with algorithms that expect a real container (and that hence may or may not work portably), and you are using an optimization that favors space over time (possibly imperceptibly). Either point might be inappropriate for your application. The easy way to discover the first is to use the code until it fails to compile; that day may never come. The only way to discover the second is by running empirical tests to measure your code's performance in using vector; in many cases, the performance difference (compared to something like vector, if there is one) may be negligible.

If you are being affected by vector's "non-containerness," or if the measured performance difference is not negligible in your environment and the difference is material in your application, then don't use vector. The easiest and most portable solution is to use a workaround to get past the standard's requirements: Use a vector or vector instead (that is, store a bool as a char or an int), and use casts to bool when accessing values in the container.

CONCLUSION In summary:

  1. vector is not a container.

  2. vector attempts to illustrate how to write standard-conforming proxied containers that do extra work invisibly under the covers. Unfortunately, that's not a sound idea because although a proxied collection can be an important and useful tool, by definition it must violate the standard's container requirements and therefore can never be a conforming container. (See #1.)

    Corollary: Go ahead and write proxied collections, but don't attempt to write ones that still meet the standard's container or sequence requirements. First, it's not possible. Second, the main reason to conform to the standard container requirements is to use the standard algorithms, yet the standard algorithms are typically inappropriate for proxied containers because proxied containers have different performance characteristics than plain-and-in-memory containers.

  3. vector's name is a trifle misleading because the things inside aren't even standard bools. A standard bool is at least as big as a char so that it can be used "normally." So, in fact, vector does not even really store bools, despite the name.

  4. vector forces a specific optimization on all users by enshrining it in the standard. That's probably not a good idea, even if the actual performance overhead turns out to be negligible for a given compiler for most applications; different users have different requirements.
A last word of advice: Optimize wisely. Never succumb to the temptation to perform premature optimizations until you have empirical evidence that the optimization is beneficial in your situation.

Quantity reprints of this article can be purchased by phone: 717.560.2001, ext.39 or by email: [email protected].

* In this article I'm using different phrases for this term, e.g., "pointer into a container," "pointer to an object inside a container," and "pointer to a contained object." They are all intended to mean the same thing.

¥ If anyone else had written vector, it would have been called "nonconforming" and "nonstandard." Well, it's in the standard, making it a bit harder to call it those names at this point. One correct solution to this discrepancy would be to remove clause 23.2.5, the vector specialization requirement, so that vector would be just another instantiation of the primary vector<> template. Therefore, it would be what it claims to be: a vector of plain old bools. (Besides, many aspects of vector are redundant; std::bitset was designed for this kind of packed-representation work.)

§ This is because currently there is no standard way to express a pointer or a reference to a bit.

¶ For all the gory details, surf to DejaNews and do a power search for "Subject='vector and bool'" and "Forum='*c++*'." The discussions took place in Jan./Feb. 1997. You will also find more recent discussions from people asking how to turn off the vector specialization; see the end of this article for my advice.

# See the solution to Guru of the Week #33 (http://www.gotw.ca/gotw/033.htm).

ß For an interesting example of this, see the article coming this summer in C/C++ Users Journal about "Optimizations That Aren't (In a Multithreaded World)" for a case in point. That article dissects a popular optimization that unintentionally turns out to be an optimization principally for single-threaded environments, and which can actually be a distinct pessimization for (possibly) multithreaded code.