Thinking In C++. Volume 2: Practical Programming

  cout << "vector::at() " << clock()-ticks <

  deque di(sz);

  ticks = clock();

  for(int i3 = 0; i3 < count; i3++)

    for(int j = 0; j < sz; j++)

      di[j];

  cout << "deque[] " << clock() - ticks << endl;

  ticks = clock();

  for(int i4 = 0; i4 < count; i4++)

    for(int j = 0; j < sz; j++)

      di.at(j);

  cout << "deque::at() " << clock()-ticks <

  // Demonstrate at() when you go out of bounds:

  try {

    di.at(vi.size() + 1);

  } catch(...) {

    cerr << "Exception thrown" << endl;

  }

} ///:~

As you saw in Chapter 1, different systems may handle the uncaught exception in different ways, but you’ll know one way or another that something went wrong with the program when using at( ), whereas it’s possible to go blundering ahead using operator[ ].

list

A list is implemented as a doubly linked list data structure and is thus designed for rapid insertion and removal of elements anywhere in the sequence, whereas for vector and deque this is a much more costly operation. A list is so slow when randomly accessing elements that it does not have an operator[ ]. It’s best used when you’re traversing a sequence, in order, from beginning to end (or vice-versa), rather than choosing elements randomly from the middle. Even then the traversal can be slower than with a vector, but if you aren’t doing a lot of traversals, that won’t be your bottleneck.

Another thing to be aware of with a list is the memory overhead of each link, which requires a forward and backward pointer on top of the storage for the actual object. Thus, a list is a better choice when you have larger objects that you’ll be inserting and removing from the middle of the list.

It’s better not to use a list if you think you might be traversing it a lot, looking for objects, since the amount of time it takes to get from the beginning of the list—which is the only place you can start unless you’ve already got an iterator to somewhere you know is closer to your destination—to the object of interest is proportional to the number of objects between the beginning and that object.

The objects in a list never move after they are created; "moving" a list element means changing the links, but never copying or assigning the actual objects. This means that iterators aren't invalidated when items are added to the list as it was demonstrated earlier to be the case vector. Here’s an example using the Noisy class:

//: C07:ListStability.cpp

// Things don't move around in lists

//{-bor}

#include "Noisy.h"

#include

#include

#include

#include

using namespace std;

int main() {

  list l;

  ostream_iterator out(cout, " ");

  generate_n(back_inserter(l), 25, NoisyGen());

  cout << "\n Printing the list:" << endl;

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

  cout << "\n Reversing the list:" << endl;

  l.reverse();

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

  cout << "\n Sorting the list:" << endl;

  l.sort();

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

  cout << "\n Swapping two elements:" << endl;

  list::iterator it1, it2;

  it1 = it2 = l.begin();

  it2++;

  swap(*it1, *it2);

  cout << endl;

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

  cout << "\n Using generic reverse(): " << endl;

  reverse(l.begin(), l.end());

  cout << endl;

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

  cout << "\n Cleanup" << endl;

} ///:~

Operations as seemingly radical as reversing and sorting the list require no copying of objects, because instead of moving the objects, the links are simply changed. However, notice that sort( ) and reverse( ) are member functions of list, so they have special knowledge of the internals of list and can rearrange the elements instead of copying them. On the other hand, the swap( ) function is a generic algorithm and doesn’t know about list in particular, so it uses the copying approach for swapping two elements. In general, use the member version of an algorithm if that is supplied instead of its generic algorithm equivalent. In particular, use the generic sort( ) and reverse( ) algorithms only with arrays, vectors, and deques.

If you have large, complex objects, you might want to choose a list first, especially if construction, destruction, copy-construction, and assignment are expensive and if you are doing things like sorting the objects or otherwise reordering them a lot.

Special list operations