//: C06:NString.h
// A "numbered string" that indicates which
// occurrence this is of a particular word
#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);
}
// 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<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;}
};
// 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);
generate( ) makes a call to gen( ) for each element in the range [first, last), presumably to produce a different value for each element. generate_n( ) calls gen( ) n times and assigns each result to n elements starting at first.
Example
The following example fills and generates into vectors. It also shows the use of print( ):
//: C06:FillGenerateTest.cpp
// Demonstrates "fill" and "generate"
#include "Generators.h"
#include "PrintSequence.h"
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main() {
vector<string> v1(5);
fill(v1.begin(), v1.end(), "howdy");
print(v1.begin(), v1.end(), "v1", " ");
vector<string> v2;
fill_n(back_inserter(v2), 7, "bye");
print(v2.begin(), v2.end(), "v2");
vector<int> v3(10);
generate(v3.begin(), v3.end(), SkipGen(4,5));
print(v3.begin(), v3.end(), "v3", " ");
vector<int> v4;
generate_n(back_inserter(v4),15, URandGen(30));
print(v4.begin(), v4.end(), "v4", " ");
} ///:~
A vector<string> is created with a predefined size. Since storage has already been created for all the string objects in the vector, fill( ) can use its assignment operator to assign a copy of "howdy" to each space in the vector. Also, the default newline separator is replaced with a space.
The second vector<string> v2 is not given an initial size, so back_inserter must be used to force new elements in instead of trying to assign to existing locations. Just as an example, the other print( ) is used, which requires a range.
The generate( ) and generate_n( ) functions have the same form as the "fill" functions except that they use a generator instead of a constant value; here, both generators are demonstrated.
Counting
All containers have a member function size( ) that will tells you how many elements they hold. The return type of size( ) is the iterator’s difference_type[87] (usually ptrdiff_t), which we denote by IntegralValue in the following. The following two algorithms count objects that satisfy certain criteria.