“The (B)Leading Edge”

"The (B)Leading Edge"
More STL Gotcha's

Jack Reeves
©The C++ Report

Reader Warren Young pointed out that in my January column[1] on STL gotcha's I did not mention one of the most obvious differences between the current HP STL implementation and the Standard C++ Library implementation: all the header files change names. I offered two excuses. First, this is not an STL specific problem and second, I am planning a future column which enumerates the gross changes between typical current C++ implementations and Standard C++ (things like new keywords, new header files, etc.). In truth, I have been using the new style headers in my own work for several months now and just plain forgot that most people still write

#include <vector.h>

instead of

#include <vector>

Mr. Young raises an interesting point, however, which seems to justify a small digression.

Table 1. lists the C++ headers that are defined by the Standard. Table 2. lists the additional C++ headers that provide access to the Standard C Library. Annex D of the (draft) Standard (Compatibility Features) contains features that are provided as part of the C++ Standard for backward compatibility, but which are "deprecated". The Standard definition of "deprecated" is that the feature is part of the current edition of the Standard, but is not guaranteed to be part of the Standard in future revisions. What that means in practice is that if you use a "deprecated" feature, it is guaranteed to work in Standard C++, but your compiler will probably throw you a warning message about it.

Clause D.3 lists the Standard C Library headers. These are the dot-h versions of the headers in table 2 that we use today. These are the only dot-h headers that are mentioned. Once upon a time, a version of the DWP also made mention of headers such as <new.h> and <iostream.h>. These references have been removed in the final version. This actually makes the (draft) Standard better. To understand why, you have to get into the "standard" mind set. If something is in the "Standard", then it has to be done that way. On the other hand, nothing prevents a vendor from providing additional headers not specified by the (draft) Standard. For that matter, a vendor can even add functionality to the existing headers. As always, the catch is that if you make use of any of these additional headers or functions in your program, there is no guarantee that it will be portable to a different Standard C++ implementation.

You can be pretty sure that as C++ compiler vendors bring out new versions that implement Standard C++, they will go to great lengths to make sure that their customers' existing C++ code base continues to work with their new compilers. You can bet that they will supply versions of <new.h> and <iostreams.h> and anything else that their customers have come to depend upon. In this regard, the STL falls into a gray area. It has become widely distributed, and widely used, but not (typically) as part of any vendor's distribution. It is therefore an open question to what extent vendors will feel obligated to provide backward compatibility with the existing STL headers when they start to supply "standard" versions. Some may do so, but probably most will not.

It may not matter very much because of the second major difference between the current STL and a "standard" implementation that I forgot to mention: namespaces. All the Standard C++ library classes and functions are defined in namespace "std". Therefore, where you once wrote

#include <vector.h>

vector<int> v;

Now you will have to write:

#include <vector>

std::vector<int> v;

You can mitigate this somewhat with a "using" declaration as in:

#include <vector>

using std::vector;

vector<int> v;

You do not have to do this, however. One of the major reasons for the existence of namespaces in the standard is to facilitate using different libraries with clashing names. Since all of the "standard" stuff is in namespace 'std', there should be no problem continuing to use an existing STL library in a "standard" environment. In fact, you should be able to write the following in the same source file:

#include <vector.h>

#include <vector>

vector<int> old_v;

std::vector<int> new_v;

and get away with it. Of course if you try something like

old_v = new_v;

the compiler will most certainly give you a rude wake-up call.

This is not the place for a detailed discussion of namespaces, so suffice it to say that switching from using your current implementation of the STL to using that supplied as part of a Standard C++ implementation will probably mean switching to the new header names, and then either qualifying all references to names declared in namespace 'std', or making use of appropriate "using" declarations or directives. On the other hand, you can probably continue to use your existing STL library for as long as you want. With a few minor problems that I mention below, it should continue to work just fine with a Standard compiler. Table 3 shows the rough correspondence between the current STL headers (HP versions) and the new "standard" headers. I omitted "tree.h" and "projectn.h" which are strictly implementation headers and should ordinarily not be directly included by any client code. "bool.h" is another header that is typically not included directly, but since it defines a type (bool) that is often used directly by client code, I include it in the listing just to indicate that it will no longer be necessary.

More STL Gotha's

Since I started looking at the STL last column, I figured I would continue with this column (and the next two or three). First, let me admit that in my column on STL gotcha's, I completely overlooked one of the most subtle, but insidious gotcha's in the STL. I am referring to post incrementing an iterator. Like so many other things, this problem is discussed by Scott Meyer's in his latest book [8]. I read the section which discussed how post increment when applied to a class type always has to create a temporary object to effect the correct return value. I read it, and even put the knowledge into practice in my own coding, but I did not really appreciate what Scott was trying to say until I ran head-long into the problem in a bad way.

I was recently doing some maintenance on a class hierarchy that contained a number of container classes. These classes all derived from an abstract base class -- PolyField. In the original version, PolyField had a typical "iterator" scheme whereby the class itself had functions begin(), end(), and next() that returned references to values in the container. I decided that PolyField needed a full blown STL style iterator of its own. The listing of class PolyFieldIterator is shown in listing 3. Since PolyField is itself an abstract base class, PolyFieldIterator can not really iterate over anything. Nevertheless, it has to be a concrete class to meet the requirements of an STL style iterator. The class "wraps" a pointer to a derived class that actually implements the iterator functions. For those readers interested in such things, PolyFieldIterator is an envelope in Jim Coplien's[10] envelope-letter idiom. The key point for this discussion is the copy constructor.

The copy constructor is straight forward and typical for this pattern -- it invokes the virtual clone() operation on its "letter" object. clone() is a virtual copy constructor (another idiom, see either of the above references) which looks like:

PolyFieldIterator* ListFieldIterator::clone()

{ return new ListFieldIterator(*this); }

This is all simple, straight forward stuff, especially if you are familiar with the idioms/patterns involved. Now review operator++(int):

Iterator PolyFieldIterator::operator++(int)

{ Iterator tmp = *this; _myImpl->inc(); return tmp; }

Again, a very typical implementation of this operator. What it means in practice, however, is anything but typical. The creation of the temporary Iterator object invokes the PolyField copy constructor, which in turn invokes the memory allocator and the copy constructor of the derived class. The return from operator++(int) also invokes the copy constructor. The destructor for the temporary has to delete the internal pointer. And this destructor has to be called for every copy constructor call. This is a non-trivial amount of activity for a very simple operator.

Even if we assume that the compiler is on the ball and correctly implements the Named Return Value Optimization which eliminates one of the copy constructor invocations and its corresponding destructor, we are still left with the creation (with its memory allocator call) and deletion (with its memory deallocator call) of a temporary PolyFieldIterator object every time operator++(int) is used. You can imagine my horror when I looked into my STL algorithms implementation and discovered such things as this:

template <class InputIterator, class OutputIterator>

OutputIterator

copy(InputIterator first, InputIterator last,

OutputIterator result) {

while (first != last) *result++ = *first++;

return result;

}

and

template <class InputIterator, class Function>

Function

for_each(InputIterator first,

InputIterator last, Function f) {

while (first != last) f(*first++);

return f;

}

This was the so called "HP reference implementation", but I found that all of my various platforms had similar implementations. If you figure that the typical instantiation of either of these common algorithms is going to be with iterators that are class types then these can hardly be considered "efficient" algorithms -- compact, yes; efficient, no! In both these cases, the use of post-increment is just syntactic sugar since there is nothing lost and considerably gained in writing the loops as:

while (first != last)

{ *result = *first; ++result; ++first; }

and

while (first != last)

{ f(*first); ++first; }

This is one of those cases where the expressive power of C++, with its ability to allow user defined types to mimic the functionality of built-in types, is a performance sink-hole. Given this, my first thought was to wonder why post-increment is a required operation for all STL iterator types. I discovered that there are cases where post-increment is necessary (they take some doing to find), so it is reasonable to have it available; it is just not reasonable that the standard algorithms should use it when more efficient approaches work as well. I spent several days writing various pieces of code that used my PolyFieldIterators, being careful to avoid using any of the standard STL algorithms, before I finally woke up and realized that this problem is not solved by ignoring it. Table 4 lists those algorithms in the HP implementation that I felt needed to be changed. I decided not to list the code itself; the changes are all straight forward. Revised versions of the code should be available for downloading from several places by the time you read this.

My advise is to beat on your implementation, or better yet go beat on your STL vendor until they do this right. In your own code, do not use post-increment on iterators unless the alternative is clearly worse.

One final observation: P. J. Plauger's "Standard C/C++" columns in the August, September, October, and November issues of "The C/C++ User's Journal" discussed the STL algorithms. While the listings did not show implementations for all of the algorithms, the ones that were shown correctly avoided post incrementing any iterators. I would therefore assume that users who are using Mr. Plauger's version of the Standard C++ library do not need to worry about this problem.

Why all this fuss over how a few simple loops are written. Two reasons, both important. The first is that the STL, as part of the Standard C++ Library, is more than just a nice collection of reusable software. It is an extensible framework which provides a basic "pattern" for implementing similar constructs. By conforming to the STL's requirements for such things as iterators and containers, user defined classes can "fit" into the STL framework. Not only does this make it possible to use the STL algorithms as part of the class' implementation, but it means that the learning curve for clients to take advantage of the new classes is greatly reduced. It can be disheartening to work hard to make your design conform to STL requirements only to discover that you do not dare use it with other STL components because of the overhead involved in some of the most common idioms.

The other reason is more subtle: you want the STL algorithms to work efficiently because you want to use them. If you are not yet a regular user of the STL algorithms, I strongly urge you to invest the modest amount of time to learn them, and then start using them in your code. This is true of even the simplest algorithms such as copy() and for_each(). The reason: it makes your code better. I know many programmers, like myself, whose first reaction to such basic algorithms was that I could write such simple stuff in my sleep. In particular, it often seems easier to just write the loop and do the operation than it is to encapsulate an operation in a function object and then invoke the algorithm with that functor. This may be partially true, but it is beside the point. When you write something like:

copy(x, x+len, v.begin());

instead of

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

v[i] = x[i];

not only have you implemented the same functionality, but you have also done three other things. First, you have documented what you are doing. It may seem that the intent of the loop is obvious, and it probably is in this case, but consider the following:

remove_copy(x, x+len, v.begin(), NULL);

versus

int j = 0;

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

if (x[i] != NULL)

v[j++] = x[i];

If you have a lot of these loops in your code, after awhile they all start to look pretty much alike. This self-documentation aspect can significantly improve the ease with which the code can be read and understood by someone else.

The second thing using the algorithm does is make your code more flexible and easily changed. In both the above cases the hand coded loops assume that we are dealing with built-in arrays or containers that implement the index operator. The STL algorithms make no such assumptions. Clearly, we know what we are dealing with when we write the code, but changing it later is much easier if we have used the algorithms instead of hard coded a bunch of loops. If we are dealing entirely with STL containers, we may be able to switch from one container type to another without having to do anything but recompile. If we have hard coded a bunch of loops around the specific container representation, then the changes necessary to switch to another container type are much more extensive.

Finally, using the STL algorithms makes it easier to get your code correct. To specifically illustrate this point, consider the need to insert some characters contained in an ordinary array into a vector<char>. Assume that 'x' is the array of characters, 'l' is the data length, 'v' is the vector<char> and 'p' is the iterator into 'v' where the new characters are to be inserted. Right off the bat, let's admit that the "best" way to do this is:

v.insert(p, x, x+l);

This will even work on most implementations today because vector<> iterators are usually ordinary pointers. In general, however, for arbitrary iterator types this requires member template support, which most implementations do not yet have. So let's suppose you try to use the STL copy() algorithm. I will also admit that using the STL algorithms have their own set of gotcha's. For example, in this case, you might initially try:

copy(x, x+l, p);

Of course this does not insert the characters from x into v, it copies them over that portion of v starting at p. You will probably quickly discover this and switch to:

copy(x, x+l, inserter(v,p));

This should work.

Suppose that instead of figuring out how to use the copy() algorithm, you decided you could do it yourself:

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

{ v.insert(p, x[i]); ++p; }

This code has a bug. It is somewhat subtle so it may not turn up in testing. The problem is that the "insert" function of a vector technically invalidates all iterators into the vector. After the first "insert", any further use of 'p' is undefined behavior. In reality, 'p' only becomes invalid when the internal memory of vector has to be reallocated. If you happen to have a vector that was created with a large initial capacity (which you may get by default -- see my previous column[2]), then you may never discover this "bug". Certainly you may not discover it in ordinary testing. The correct form of this loop is:

for (int i = 0; i < l; ++i) {

p = v.insert(p, x[i]);

++p;

}

Needless to say, the insert_iterator<> adapter (created by the call to inserter()) does this correctly.

One final note on my previous column. It had to be pointed out to me that I misspelled David Musser's name[9], not once, but several times. That is one of the great things about computers: if you can manage to get it wrong in the right place, you can be sure to consistently replicate your mistake everywhere. You gotta love um. My appologies.

At the time this is being written (Dec 1996), the X3J16 Committee (C++) has voted to accept the Draft Working Paper (DWP) from the November 1996 meeting as a Committee Draft (CD). As you may recall, the committee released a CD in April of 1995. That process (April 1995) effectively froze the feature set of the language and the standard library. A number of details remained to be worked out, some of which turned out to be thornier than expected. This second committee draft, dated December 1996, will now begin a series of public reviews leading eventually to the final acceptance of C++ as an ANSI/ISO standard language. By the time you actually read this, the first public review period for CD2 will already be nearing completion, so I can hardly recommend that you rush out and get a copy of the CD so you can review it. Nevertheless, I would advise anyone who is serious about C++ development to obtain a copy of the CD.

I offer my congratulations to the committee on producing this standard. It is an impressive accomplishment, on a number of different levels.

References

1. Jack Reeves, "The (B)Leading Edge: STL Gotcha's", C++ Report, Vol. 9, No. 1, January 1997.

3. "Working Paper for Draft Proposed International Standard for Information Systems -- Programming Language C++", December 1996.

4. Tom Cargill, "Exception handling: A false sense of security", C++ Report, Vol. 6, No. 9, November-December 1994.

5. Jack Reeves, "Using Exceptions Effectively: Coping with Exceptions", C++ Report, Vol. 8, No. 2, March 1996.

6. Jack Reeves, "The (B)Leading Edge: Exceptions and Standard C++", C++ Report, Vol. 8, No. 5, May 1996.

7. Bjarne Stroustrup, The Design and Evolution of C++, Addison-Wesley, 1994.

8. Scott Meyers, More Effective C++, Addison-Wesley, 1996.

9. David R. Musser and Atul Saini, STL Tutorial and Reference Guide, Addison-Wesley, 1996.

10. Jim Coplien, Advanced C++ Programming Style and Idioms, Addison-Wesley, 1990.

Table 1.

C++ Library Headers

Table 2.

C++ Headers for C Library Facilities

Table 3.

Current HP STL Headers

vs.

Standard Headers

algo.h ----------> <algorithm>

algobase.h ----------> <algorithm>

bool.h n/a

bvector.h ----------> <vector>

defalloc.h ----------> <memory>

deque.h ----------> <deque>

function.h ----------> <functional>

heap.h ----------> <algorithm>

iterator.h ----------> <iterator>

list.h ----------> <list>

map.h ----------> <map>

multimap.h ----------> <map>

multiset.h ----------> <set>

pair.h ----------> <utility>

set.h ----------> <set>

stack.h ----------> <stack>

tempbuf.h ----------> <memory>

vector.h ----------> <vector>

Table 4.

Changes to HP STL Algorithms

uninitialized_copy

uninitialized_fill

uninitialized_fill_n

copy

fill

fill_n

lexicographical_compare(2)

for_each

count

count_if

swap_ranges

transform(2)

replace_copy

replace_copy_if

generate

generate_n

remove_copy

remove_copy_if

__reverse(2)

reverse_copy

__rotate

__stable_partition

__unguarded_linear_insert(2)

__partial_sort_copy(2)

merge(2)

__borland_bugfix_copy

set_union(2)

set_intersection(2)

set_difference(2)

set_symmetric_difference(2)

accumulate(2)

inner_product(2)

iota