Thinking In C++. Volume 2: Practical Programming

    cout << *it << " ";

  cout << endl;

}

struct ObjGen {

  Obj operator()() { return Obj(); }

};

int main() {

  const int sz = 5000;

  srand(time(0));

  list lo;

  clock_t ticks = clock();

  generate_n(back_inserter(lo), sz, ObjGen());

  lo.sort();

  lo.unique();

  cout << "list:" << clock() - ticks << endl;

  set so;

  ticks = clock();

  generate_n(inserter(so, so.begin()),

    sz, ObjGen());

  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 basic sequences

We mentioned earlier that all basic sequences have a member function swap( ) that’s designed to switch one sequence with another (but only 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:

//: C07:Swapping.cpp

//{-bor}

// All basic sequence containers can be swapped

#include "Noisy.h"

#include

#include

#include

#include

#include

#include

using namespace std;

ostream_iterator out(cout, " ");

template

void print(Cont& c, char* comment = "") {

  cout << "\n" << comment << ": ";

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

  cout << endl;

}

template

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");

}

int main() {

  testSwap >("vector");

  testSwap >("deque");

  testSwap >("list");

} ///:~

When you run this, you’ll discover that each type of sequence container can 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 resources 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 uses 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.

set

The set produces a container that will accept only one of each thing you place in it; it also sorts the elements. (Sorting isn’t intrinsic to the conceptual definition of a set, but the STL set stores its elements in a balanced tree data structure to provide rapid lookups, thus producing sorted results when you traverse it.) The first two examples in this chapter used sets.

Consider the problem of creating an index for a book. You might like to start with all the words in the book, but you only want one instance of each word, and you want them sorted. Of course, a set is perfect for this and solves the problem effortlessly. However, there’s also the problem of punctuation and any other nonalpha characters, which must be stripped off to generate proper words. One solution to this problem is to use the Standard C library functions isalpha( ) and isspace( ) to extract only the characters you want. You can replace all unwanted characters with spaces so that you can easily extract valid words from each line you read:

//: C07:WordList.cpp

// Display a list of words used in a document

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include "../require.h"

using namespace std;

char replaceJunk(char c) {

   // Only keep alphas, space (as a delimiter), and '

   return (isalpha(c) || c == '\'') ? c : ' ';

}

int main(int argc, char* argv[]) {

  char* fname = "WordList.cpp";

  if(argc > 1) fname = argv[1];

  ifstream in(fname);

  assure(in, fname);

  set wordlist;

  string line;

  while(getline(in, line)) {

    transform(line.begin(), line.end(), line.begin(),

              replaceJunk);

    istringstream is(line);

    string word;

    while (is >> word)

      wordlist.insert(word);

    }

  // Output results:

  copy(wordlist.begin(), wordlist.end(),

       ostream_iterator(cout, "\n"));

} ///:~

The call to transform( ) replaces each character to be ignored with a space. The set container not only ignores duplicate words, but compares the words it keeps according to the function object less (the default second template argument for the set container), which in turn uses string::operator<( ), so the words emerge in alphabetical order^.

You don’t have to use a set just to get a sorted sequence. You can use the sort( ) function (along with a multitude of other functions in the STL) on different STL containers. However, it’s likely that set will be faster. Using a set is particularly handy when you just want to do lookup, since its find( ) member function has logarithmic complexity and therefore is much faster than the generic find( ) algorithm^.