Bug Vanquisher

28 February 2007

Another way of making your iterators safe!

Filed under: C++ — Tanveer Badar @ 12:01 PM

We all know what a problem a runaway pointer can be. Most of the time, things seem to work properly as memory in C/C++ is never garbage collected. As soon as you add memory pressure and that page is marked for some other process, hell unleashes itself. Memory access violation, buffer overruns, security problems, out-of-bound access to array members, dangling references to stale data. The list goes on
and on.

Most iterator implementations face these problems, because according to Stroustrup, an iterator is a pure abstraction and anything that acts like an iterator is an iterator. Pointers fit this pattern, so by transitivity of this principle, iterators also are problematic.

Here is how a typical vector iterator is implemented:

[Update: I had code here previously, but apparently, wordpress doesn’t like rich formatting and kept messing up the colorful syntax highlighting I was using. To make things readable again, I have moved the code to another place. Get the code here]

Now, No. 1 is the only choice when you want all the speed and don’t care about memory access violations. iterator and const_iterator for this case are simply typedefs for value_type* and const value_type*.

No. 2 is the style of nerds. It does not achieve a single goal about safety but adds tons of overhead to a simple pointer. Compiler may be smart enough to optimize out most of the dirt, but you cannot rely on that always. Therefore, don’t fall into the trap of writing a simple iterator class when it just wraps a pointer and does nothing else.

No. 3 is also an iterator class, but this time it has additional functionality that is added conditionally during compilation. also one additional pointer is added. This dialect of iterators is useful during all sorts of debugging and when you want safety over all concerns of performance. When  _SECURE_STL is not defined, this class degenerates into No. 2 with an additional member, a performance nightmare for nothing. Therefore, it is recommended
that you choose a variation of preprocessor directives that allows pointer declaration of iterators when it is not defined. Otherwise, you pay the costs for nothing.

However, when it is defined, the class is a wonderful piece of ingenuity. Every dereferencing and increment/decrement operation is checked to verify that it is still pointing at a valid position into the container. Also, this iterator will not suffer from dangling references problem, where an iterator is left to pointing at the old location after the container re-allocated its storage. The container is directly dereferenced when required. Through this extra layer of indirection, we avoid storing the pointer and access it through container itself.

However, this class is not without its costs. An additional member is defined, doubling storage requirements. Every member function executes additional code that checked for proper access and mostly lies in the critical path. Also, if the containers [ ] operator depends on its iterator implementation, infinite recursion occurs, when not all compilers may point-out at compile time.

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: