Thinking In C++. Volume 2: Practical Programming

The naming of the member function swap( ) is a little confusing, since there’s also a nonmember swap( ) algorithm that interchanges the values of any two objects of same type. The member swap( ) swaps everything in one container for another (if the containers hold the same type), effectively swapping the containers themselves. It does this efficiently by swapping the contents of each container, which consists mostly of just pointers. The nonmember swap( ) algorithm normally uses assignment to interchange its arguments (an expensive operation for an entire container), but is customized through template specialization to call the member swap( ) for the standard containers. There is also an iter_swap algorithm that interchanges two elements in the same container pointed to by iterators^.

The following sections discuss the particulars of each type of sequence container.

vector

The vector class template is intentionally made to look like a souped-up array, since it has array-style indexing, but also can expand dynamically. The vector class template is so fundamentally useful that it was introduced in a primitive way early in this book and was used regularly in previous examples. This section will give a more in-depth look at vector.

To achieve maximally fast indexing and iteration, the vector maintains its storage as a single contiguous array of objects. This is a critical point to observe in understanding the behavior of vector. It means that indexing and iteration are lightning-fast, being basically the same as indexing and iterating over an array of objects. But it also means that inserting an object anywhere but at the end (that is, appending) is not really an acceptable operation for a vector. In addition, when a vector runs out of preallocated storage, to maintain its contiguous array it must allocate a whole new (larger) chunk of storage elsewhere and copy the objects to the new storage. This approach produces a number of unpleasant side-effects.

Cost of overflowing allocated storage

A vector starts by grabbing a block of storage, as if it’s taking a guess at how many objects you plan to put in it. As long as you don’t try to put in more objects than can be held in the initial block of storage, everything is rapid and efficient. (If you do know how many objects to expect, you can preallocate storage using reserve( ).) But eventually you will put in one too many objects, and the vector responds by:

1.Allocating a new, bigger piece of storage

2.Copying all the objects from the old storage to the new (using the copy-constructor)

3.Destroying all the old objects (the destructor is called for each one)

4.Releasing the old memory

For complex objects, this copy-construction and destruction can end up being expensive if you overfill your vector a lot, which is why vectors (and STL containers in general) are designed for value types (i.e. types that are cheap to copy). Of course, that includes pointers.

To see what happens when you’re filling a vector, here is the Noisy class mentioned earlier that prints information about its creations, destructions, assignments, and copy-constructions:

//: C07:Noisy.h

// A class to track various object activities

#ifndef NOISY_H

#define NOISY_H

#include

using std::endl;

class Noisy {

  static long create, assign, copycons, destroy;

  long id;

public:

  Noisy() : id(create++) {

    std::cout << "d[" << id << "]" << std::endl;

  }

  Noisy(const Noisy& rv) : id(rv.id) {

    std::cout << "c[" << id << "]" << std::endl;

    copycons++;

  }

  Noisy& operator=(const Noisy& rv) {

    std::cout << "(" << id << ")=[" <<

      rv.id << "]" << std::endl;

    id = rv.id;

    assign++;

    return *this;

  }

  friend bool

  operator<(const Noisy& lv, const Noisy& rv) {

    return lv.id < rv.id;

  }

  friend bool

  operator==(const Noisy& lv, const Noisy& rv) {

    return lv.id == rv.id;

  }

  ~Noisy() {

    std::cout << "~[" << id << "]" << std::endl;

    destroy++;

  }

  friend std::ostream&

  operator<<(std::ostream& os, const Noisy& n) {

    return os << n.id;

  }

  friend class NoisyReport;

};

struct NoisyGen {

  Noisy operator()() { return Noisy(); }

};

// A Singleton. Will automatically report the

// statistics as the program terminates:

class NoisyReport {

  static NoisyReport nr;

  NoisyReport() {} // Private constructor

public:

  ~NoisyReport() {

    std::cout << "\n-------------------\n"

      << "Noisy creations: " << Noisy::create

      << "\nCopy-Constructions: "

      << Noisy::copycons

      << "\nAssignments: " << Noisy::assign

      << "\nDestructions: " << Noisy::destroy

      << std::endl;

  }

};

// Because of the following definitions, this file

// can only be used in simple test situations. Move

// them to a .cpp file for more complex programs:

long Noisy::create = 0, Noisy::assign = 0,

  Noisy::copycons = 0, Noisy::destroy = 0;

NoisyReport NoisyReport::nr;

#endif // NOISY_H ///:~