| Thinking in C++ Vol 2 - Practical Programming |
|
Prev |
Home |
Next |
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.
#ifndef
PRINTSEQUENCE_H
#define
PRINTSEQUENCE_H
#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.
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;
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); }
// 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<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 |
