Thinking In C++. Volume 2: Practical Programming

Finally, a number of the STL algorithms that move elements of a sequence around distinguish between "stable" and "unstable" reordering of a sequence. This refers to preserving the original relative order of those elements that are equivalent as far as the comparison function is concerned. For example, consider a sequence { c(1), b(1), c(2), a(1), b(2), a(2) }. These elements are tested for equivalence based on their letters, but their numbers indicate how they first appeared in the sequence. If you sort (for example) this sequence using an unstable sort, there’s no guarantee of any particular order among equivalent letters, so you could end up with { a(2), a(1), b(1), b(2), c(2), c(1) }. However, if you use a stable sort, you will get { a(1), a(2), b(1), b(2), c(1), c(2) }. The STL sort( ) algorithm uses a variation of quicksort and is therefore unstable, but a stable_sort( ) is also provided.^[86] 

To demonstrate the stability versus instability of algorithms that reorder a sequence, we need some way to keep track of how the elements originally appeared. The following is a kind of string object that keeps track of the order in which that particular object originally appeared, using a static map that maps NStrings to Counters. Each NString then contains an occurrence field that indicates the order in which this NString was discovered^.

//: C06:NString.h

// A "numbered string" that indicates which

// occurrence this is of a particular word

#ifndef NSTRING_H

#define NSTRING_H

#include

#include

#include

#include

#include

typedef std::pair psi;

// Only compare on the first element

bool operator==(const psi& l, const psi& r) {

  return l.first == r.first;

}

class NString {

  std::string s;

  int thisOccurrence;

  // Keep track of the number of occurrences:

  typedef std::vector vp;

  typedef vp::iterator vpit;

  static vp words;

  void addString(const std::string& x) {

    psi p(x, 0);

    vpit it = std::find(words.begin(), words.end(), p);

    if(it != words.end())

      thisOccurrence = ++it->second;

    else {

      thisOccurrence = 0;

      words.push_back(p);

    }

  }

public:

  NString() : thisOccurrence(0) {}

  NString(const std::string& x) : s(x) {

    addString(x);

  }

  NString(const char* x) : s(x) {

    addString(x);

  }

  // The implicit operator= and

  // copy-constructor are OK here

  friend std::ostream& operator<<(

    std::ostream& os, const NString& ns) {

    return os << ns.s << " ["

      << ns.thisOccurrence << "]";

  }

  // Need this for sorting. Notice it only

  // compares strings, not occurrences:

  friend bool

  operator<(const NString& l, const NString& r) {

    return l.s < r.s;

  }

  friend

  bool operator==(const NString& l, const NString& r) {

    return l.s == r.s;

  }

  // For sorting with greater:

  friend bool

  operator>(const NString& l, const NString& r) {

    return l.s > r.s;

  }

  // To get at the string directly:

  operator const std::string&() const {return s;}

};

// Allocate static member object. Done here for

// brevity, but should normally be done in a

// separate cpp file:

NString::vp NString::words;

#endif // NSTRING_H ///:~

We would normally use a map container to associate a string with its number of occurrences, but maps don’t appear until the next chapter, so we use a vector of pairs instead. You’ll see plenty of similar examples there^.

To do an ordinary ascending sort, the only operator that’s necessary is NString::operator<( ); however, to sort in reverse order, the operator>( ) is also provided so that the greater template can call it^.

As this is just a demonstration class, we are taking the liberty of placing the definition of the static members words and occurrences in this header file, but this will break down if the header file is included in more than one place, so you should normally place all static definitions in cpp files^.

Filling and generating

These algorithms let you automatically fill a range with a particular value or generate a set of values for a particular range. The "fill" functions insert a single value multiple times into the container, and the "generate" functions use an object called a generator (described earlier) to create the values to insert into the container^.

void fill(ForwardIterator first, ForwardIterator last, const T& value); void fill_n(OutputIterator first, Size n, const T& value);

fill( ) assigns value to every element in the range [first, last). fill_n( ) assigns value to n elements starting at first^.

void generate(ForwardIterator first, ForwardIterator last, Generator gen); void generate_n(OutputIterator first, Size n, Generator gen);