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.

WHY TAKE POINTERS OR REFERENCES INTO CONTAINERS?*
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 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 ...

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.

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

// Example 2: Is this code valid?
//
template
void f( T& t ) {
	typename T::value_type* p1 = &t[0];
	typename T::value_type* p2 = &*t.begin();
	// ... do something with *p1 and *p2 ...
}

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.

// Example 3: Works for every T except bool
//
template
void g( vector& v ) {
	T* p = &v.font();
	// ... do something with *p ...
}

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 bool—operator 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.

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