Thinking In C++. Volume 2: Practical Programming

There is a darker side to vector’s reallocation of memory, however. Because vector keeps its objects in a nice, neat array (allowing, for one thing, maximally fast random access), the iterators used by vector can be simple pointers. This is a good thing—of all the sequence containers, these pointers allow the fastest selection and manipulation. Whether they are simple pointers, or whether they are iterator objects that hold an internal pointer into their container, consider what happens when you add the one additional object that causes the vector to reallocate storage and move it elsewhere. The iterator’s pointer is now pointing off into nowhere:^.

//: C07:VectorCoreDump.cpp

// Invalidating an iterator

#include

#include

#include

using namespace std;

int main() {

  vector vi(10, 0);

  ostream_iterator out(cout, " ");

  vector::iterator i = vi.begin();

  *i = 47;

  copy(vi.begin(), vi.end(), out);

  cout << endl;

  // Force it to move memory (could also just add

  // enough objects):

  vi.resize(vi.capacity() + 1);

  // Now i points to wrong memory:

  *i = 48;  // Access violation

  copy(vi.begin(), vi.end(), out); // No change to vi[0]

} ///:~

This illustrates the concept of iterator invalidation. Certain operations cause internal changes to a container’s underlying data, so any iterators in effect before such changes may no longer be valid afterward. If your program is breaking mysteriously, look for places where you hold onto an iterator while adding more objects to a vector. You’ll need to get a new iterator after adding elements or use operator[ ] instead for element selections. If you combine this observation with the awareness of the potential expense for adding new objects to a vector, you may conclude that the safest way to use one is to fill it up all at once (ideally, knowing first how many objects you’ll need) and then just use it (without adding more objects) elsewhere in the program. This is the way vector has been used in the book up to this point. The standard C++ library documents which container operations invalidate iterators.

You may observe that using vector as the "basic" container in the earlier chapters of this book might not be the best choice in all cases. This is a fundamental issue in containers and in data structures in general: the "best" choice varies according to the way the container is used. The reason vector has been the "best" choice up until now is that it looks a lot like an array and was thus familiar and easy for you to adopt. But from now on it’s also worth thinking about other issues when choosing containers.

Inserting and erasing elements

The vector is most efficient if:

5.You reserve( ) the correct amount of storage at the beginning so the vector never has to reallocate.

6.You only add and remove elements from the back end.

It is possible to insert and erase elements from the middle of a vector using an iterator, but the following program demonstrates what a bad idea this is:

//: C07:VectorInsertAndErase.cpp

// Erasing an element from a vector

//{-bor}

#include

#include

#include

#include

#include "Noisy.h"

using namespace std;

int main() {

  vector v;

  v.reserve(11);

  cout << "11 spaces have been reserved" << endl;

  generate_n(back_inserter(v), 10, NoisyGen());

  ostream_iterator out(cout, " ");

  cout << endl;

  copy(v.begin(), v.end(), out);

  cout << "Inserting an element:" << endl;

  vector::iterator it =

    v.begin() + v.size() / 2; // Middle

  v.insert(it, Noisy());

  cout << endl;

  copy(v.begin(), v.end(), out);

  cout << "\nErasing an element:" << endl;

  // Cannot use the previous value of it:

  it = v.begin() + v.size() / 2;

  v.erase(it);

  cout << endl;

  copy(v.begin(), v.end(), out);

  cout << endl;

} ///:~

When you run the program, you’ll see that the call to reserve( ) really does only allocate storage—no constructors are called. The generate_n( ) call is busy: each call to NoisyGen::operator( ) results in a construction, a copy-construction (into the vector), and a destruction of the temporary. But when an object is inserted into the vector in the middle, it must shove everything down to maintain the linear array, and, since there is enough space, it does this with the assignment operator. (If the argument of reserve( ) is 10 instead of 11, it would have to reallocate storage.) When an object is erased from the vector, the assignment operator is once again used to move everything up to cover the place that is being erased. (Notice that this requires that the assignment operator properly clean up the lvalue.) Last, the object on the end of the array is deleted.

deque