Consider the following straightforward C++ code:

vector v ;
int a[] = {0,1,2,3,4};
int b[] = {5,6,7,8,9};
copy(a,a+5,back_inserter(v));
copy(b,b+5,back_inserter(v));

Now suppose that we need an iterator range for the second batch insertion. That is, we need to know were the first element from ’b’ was inserted.
How could we do it?

Here’s a naive but tempting possibility

vector v ;
int a[] = {0,1,2,3,4};
int b[] = {5,6,7,8,9};
copy(a,a+5,back_inserter(v)); 

// Mark the place were the first ’b’ will be inserted
vector::iterator mark = v.end() ; 

copy(b,b+5,back_inserter(v)); 

// process from the point the first b was inserted
do_something(mark,v.end());

As right as that might appear to be, it has undefined behaviour in the case of a std::vector, even if .reserve() is called. Let me explain:

Inserting elements into a vector invalidates all iterators if and only if reallocation ocurrs. But a proper call to reserve() guarantees that reallocation won’t ocurr, so, to some extent, you don’t have to worry about invalidated iterators when appending into a vector which sufficient capacity. With one exception: the .end() iterator.

The reason is that after c.insert(pos,value), all elements from pos included need to be shifted up, so logically, all iterators >= pos become invalid, whether there is reallocation or not.

c.push_back(value); is equivalent to c.insert(c.end(),value), thus, clearly, end() is always invalid after insert() (thus push_back()) and erase().

OK, but what if the container is a std::list instead. After all list iterators are still valid after insertion/removal.
Well, this is still undefined behaviour because .end(), being still valid for a list, is allowed to keep pointing to the end of the list, so it cannot be assumed to become a valid iterator to the next element to be added.

The correct way to do it becomes ovbious if you consider the simplest case:

vector v ;
v.push_back(0);   

// How do I get an iterator to the lastly added element?
// Like this of course:
vector::iterator last = v.end();
-- last ;

Which extrapolates easily into the general case shown at the beggining:

vector v ;
int a[] = {0,1,2,3,4};
int b[] = {5,6,7,8,9};
copy(a,a+5,back_inserter(v));
copy(b,b+5,back_inserter(v));   

vector::iterator mark = v.end() ;
std::advance(mark,-5);   

// process from the point the first b was inserted
do_something(mark,v.end());

Take a look at the following C++ code snippet

SomeContainer* c_ptr = ..whatever..
for ( some_iterator it = c_ptr->begin()
    ; it != c_ptr->end() && !found
    ; ++ it
    )
{
  while ( some_nested_loop )
  {
    if ( some_condition )
    {
      found = true ;
      c_ptr = c_ptr->OTHER_RELATED_CONTAINER() ;
    }
  }
}

There is very subtle problem here…the loop condition has undefined behavoir.

The problem is that, as you know well, the loop condition is evaluated first and then after each iteration over the loop body, and this body changes c_ptr causing it’s end() iterator to compare against an iterator previously obtained from another container. As it turns out, comparing incompatible iterators is undefined behaviour, and, for instance, the checked iterators feature of Dinkumware’s STL (that ships with VC8) assert that.

But the problem is subtle because the loop is supposed to be aborted right after the assignment, via the boolean flag used to control the loop (a break statement wouldn’t suffice because the assignment ocurrs in a nested loop), so the actual “mistake” here is quite silly and subtle (it touches on a dark corner of the C++ standard nobody knows about): the boolean flag “found” should be tested first to avoid comparing incompatible iterators.

So, here’s a fundamental question: can such a subtle mistake ever be avoided? Well, some mistakes can.

The basic approach is to learn which programming constructs are prone to error and avoid them as much as possible.

One example is using data to control flow. That is, aborting a loop via a boolean flag. There has been an interesting discussion about it, recently, in the ACCU general mailing list.

Another example is assignment, and I mean real assignment, not initialization (that is, when you change the value of a variable). Functional languages just lack assignment, and if you are a functional programming fan, you might even conclude that assignment is unnecesary, even, evil.

I believe there’s some truth in that, after all, assignment changes state and that’s always a source of error… we just saw how a little subtle mistake resulted in a bug because of that.

Of course, in an imperative language like C++ you just can’t avoid assignment altoghether, and there is no reason to do it. It would be like trying to avoid all mutating operations on objects.

Yet many times we do try to avoid mutating operations on objects. In fact, in C++ we even use const to force us to stay on the safe side, because a changing state, neccessary as it is, is error prone.

So, should we avoid assignment? I’d say yes, as much as we can.

Can we write the above code without it then?

How about this?

SomeContainer* c_ptr = ..whatever..
SomeContainer* other_c_ptr = NULL ; // Conceptually uninitialized really
for ( some_iterator it = c_ptr->begin()
    ; other_c_ptr == NULL && it != c_ptr->end()
    ; ++ it
    )
{
  if ( some_condition )
  {
    other_c_ptr = c_ptr->OTHER_RELATED_CONTAINER() ;
  }
}

This comes close: the object determining the search range is held in a variable that never changes (is never assigned), which is great, no more risk of comparing incompatible iterators.

The result, OTOH, is held in a variable that, conceptually, is also just initialized, not really assigned, but with a subtelty: its initialization is conditional.

But yes…there’s no such thing as conditional initialization, of course.

So, can we do better? Let’s see:

SomeContainer* const find ( SomeContainer* const src )
{
  for ( some_iterator it = src->begin()
      ; it != src->end()
      ; ++ it
      )
  {
    if ( some_condition )
      return src->OTHER_RELATED_CONTAINER() ;
  }
  return NULL ;
}
SomeContainer* const source = ..whatever..
SomeContainer* const = find(source);

Voila! No assignment.

Noticed the const qualifiers in the last example? They are not strictly needed (the code would compile anyway), but they enforce the intention at compile time, which is always an excelent idea.

Wrap up: assignment should be used only when it is strictly neccessary to change the value of a variable, that is, when we can’t use a different variable to hold the new value.

If your VC++ console application links to a debug CRT, a failed ‘assert()‘ won’t, by default, print a message to stderr and abort(), as you might expect.

But this is a required behaviour for unit testing which naturally needs to run unattended.

After a little inverstigation, I found out how to control what happens when assert() fails (when a debug CRT is used):

int my_report_hook ( int type, char* msg, int* retval )
{
  if ( type == _CRT_ASSERT )
  {
    fprintf(stderr,msg);
    *retval = 0 ;
    abort();
  }
  return TRUE ;
}
_CrtSetReportHook(my_report_hook);

You should know that abort() calls the hook a second time with the ‘type’ argument as ‘_CRT_ERROR’, so make sure to keep the if clause, unless you want to blow up the stack.

Take a look at the following C++ code snippet:

Container::iterator i ;
Container::iterator j ;
i == j ;


Looks OK doesn’t it?

Well, to many people it does. Let’s see.

What’s the value of the variables i and j?

Formally speaking, a singular value. Practically speaking, it can be anything, because C++ doesn’t force any initialization (like zero, value or default initialization) of uninitialized variables. And yes, these are uninitialized variables for all you know.

A variable of a class type defined without any initializer list is default initialized, and you would be right expecting such a variable to have a non-singular value. At the same time, an iterator can be of a class type, and if it has a default constructor you could be right expecting it to intruduce a non-singular iterator variable. But iterators are not required to do that, so an arbitrary uninitialized iterator variable is not default initialized.

More often than not, people treat uninitialized iterator variables as if they were default initialized iterator variables, ignoring the fact that iterators are not required to be class types. Thus, it is unfortunately more or less common to find errouneous comparisons like the one shown at the beginning.

Why am I bringing this up? Because the STL that ships with Visual C++ 8 has checked iterators by default (in a debug build), and illegal uses of singular iterator values is one of the mistakes it checks. Even though these iterators are of class type, trying to compare two uninitialized iterator variables will assert. And rightly so.

Not incidentally I happen to be figuring out how to fix some illegal uses of uninitialized iterators in a code base. The problem only showed up now thanks to the VC8 STL.

The code base uses lots of custom made iterators, most of them wrapping standard iterators. So at first I thought I could simplify the change by simply disabling all default constructors in all wrapping iterators and change the code on a case by case basis. I figured: why would one need to define an uninitialized iterator variable anyway?, surely there’s always a better construct that avoid the uninitialized variable.

I figured wrong. There is one common idiom-used quite too often to disregard it-that needs uninitialized variables:

SomeIterator b,e ;
for ( boost::tie(b,e) = GetBothBeginAndEndAtOnce(Container); b != e ; ++ b )
...


So the only thing I can do is run the entire project testsuite and hunt each illegal uses (mostly comparisons) one by one.

Fortunately, there is a trick that allows me to run the testsuite unattended:

This line disables (in VC) the pop up windows that by deafult is shown each time an assert fails:

_set_error_mode(_OUT_TO_STDERR);

Or if you are linking to a debug CRT, these lines instead (the above works only in release CRTs):


_CrtSetReportMode( _CRT_ASSERT, _CRTDBG_MODE_FILE );
_CrtSetReportFile( _CRT_ASSERT, _CRTDBG_FILE_STDERR );


Causing the assert message to go to stderr instead, which the test driver nicely captures in a log file.