cout << "set:" << clock() - ticks << endl; print(lo);

print(so); } ///:~

When you run the program, you should discover that set is much faster than list. This is reassuring – after all, it is set’s primary job description!

Swapping all basic sequences

It turns out that all basic sequences have a member function swap( ) that’s designed to switch one sequence with another (however, this swap( ) is only defined for sequences of the same type). The member swap( ) makes use of its knowledge of the internal structure of the particular container in order to be efficient:

//: C04:Swapping.cpp

// All basic sequence containers can be swapped #include "Noisy.h"

#include <list> #include <vector> #include <deque> #include <iostream> #include <algorithm> using namespace std;

ostream_iterator<Noisy> out(cout, " ");

template<class Cont>

void print(Cont& c, char* comment = "") { cout << "\n" << comment << ": "; copy(c.begin(), c.end(), out);

cout << endl;

}

template<class Cont>

void testSwap(char* cname) { Cont c1, c2;

generate_n(back_inserter(c1), 10, NoisyGen()); generate_n(back_inserter(c2), 5, NoisyGen()); cout << "\n" << cname << ":" << endl; print(c1, "c1"); print(c2, "c2");

cout << "\n Swapping the " << cname << ":" << endl;

c1.swap(c2);

print(c1, "c1"); print(c2, "c2");

Chapter 15: Multiple Inheritance

191

}

int main() {

testSwap<vector<Noisy> >("vector"); testSwap<deque<Noisy> >("deque"); testSwap<list<Noisy> >("list");

} ///:~

When you run this, you’ll discover that each type of sequence container is able to swap one sequence for another without any copying or assignments, even if the sequences are of different sizes. In effect, you’re completely swapping the memory of one object for another.

The STL algorithms also contain a swap( ), and when this function is applied to two containers of the same type, it will use the member swap( ) to achieve fast performance. Consequently, if you apply the sort( ) algorithm to a container of containers, you will find that the performance is very fast – it turns out that fast sorting of a container of containers was a design goal of the STL.

Robustness of lists

To break a list, you have to work pretty hard:

//: C04:ListRobustness.cpp // lists are harder to break #include <list>

#include <iostream> using namespace std;

int main() {

list<int> li(100, 0); list<int>::iterator i = li.begin(); for(int j = 0; j < li.size() / 2; j++)

i++;

//Walk the iterator forward as you perform

//a lot of insertions in the middle: for(int k = 0; k < 1000; k++)

li.insert(i++, 1); // No problem li.erase(i);

i++;

*i = 2; // Oops! It's invalid

}///:~

When the link that the iterator i was pointing to was erased, it was unlinked from the list and thus became invalid. Trying to move forward to the “next link” from an invalid link is poorly-

Chapter 15: Multiple Inheritance

192