Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Mail Systems
Eclipse Documentation

How To Guides
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Problem Solutions
Privacy Policy




Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

Support tools for example creation

It s useful to create some basic tools to test the algorithms. In the examples that follow we ll use the generators mentioned earlier in Generators.h, as well as what appears below.

Displaying a range is a frequent task, so here is a function template to print any sequence, regardless of the type contained in that sequence:

//: C06:PrintSequence.h
// Prints the contents of any sequence.
#include <algorithm>
#include <iostream>
#include <iterator>
template<typename Iter>
void print(Iter first, Iter last, const char* nm = "",
const char* sep = "\n",
std::ostream& os = std::cout) {
if(nm != 0 && *nm != '\0')
os << nm << ": " << sep;
typedef typename
std::iterator_traits<Iter>::value_type T;
std::copy(first, last,
std::ostream_iterator<T>(std::cout, sep));
os << std::endl;
#endif // PRINTSEQUENCE_H ///:~

By default this function template prints to cout with newlines as separators, but you can change that by modifying the default argument. You can also provide a message to print at the head of the output. Since print( ) uses the copy( ) algorithm to send objects to cout via an ostream_iterator, the ostream_iterator must know the type of object it is printing, which we infer from the value_type member of the iterator passed.

The std::iterator_traits template enables the print( ) function template to process sequences delimited by any type of iterator. The iterator types returned by the standard containers such as vector define a nested type, value_type, which represents the element type, but when using arrays, the iterators are just pointers, which can have no nested types. To supply the conventional types associated with iterators in the standard library, std::iterator_traits provides the following partial specialization for pointer types:

template<class T>
struct iterator_traits<T*> {
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;

This makes the type of the elements pointed at (namely, T) available via the type name value_type.

Stable vs. unstable reordering

A number of the STL algorithms that move elements of a sequence around distinguish between stable and unstable reordering of a sequence. A stable sort preserves the original relative order of the 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 thus unstable, but a stable_sort( ) is also provided.[94]

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 keeps track of the
// number of occurrences of the word it contains.
#ifndef NSTRING_H
#define NSTRING_H
#include <algorithm>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
typedef std::pair<std::string, int> 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<psi> 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;
NString() : thisOccurrence(0) {}
NString(const std::string& x) : s(x) { addString(x); }
NString(const char* x) : s(x) { addString(x); }
// 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;
bool operator==(const NString& l, const NString& r) {
return l.s == r.s;
// For sorting with greater<NString>:
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; }
// Because NString::vp is a template and we are using the
// inclusion model, it must be defined in this header 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 in Chapter 7.

The only operator necessary to perform an ordinary ascending sort is NString::operator<( ). To sort in reverse order, the operator>( ) is also provided so that the greater template can call it.

Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

   Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire