I was reading this book by Bruce Eckel and found a small correction that needs to be done in NString.h header file in Chapter 6 - Generic Algorithms.
NString is a kind of string object that keeps track of the order in which that particular object originally appeared, using a static map (
static vp words) that maps
NStrings to counters(
int thisOccurence).
thisOccurence field indicates the order in which this
NString was discovered. Lets get into the issue. The original code is like this.
//: C06:NString.h
// From "Thinking in C++, Volume 2", by Bruce Eckel & Chuck Allison.
// (c) 1995-2004 MindView, Inc. All Rights Reserved.
// See source code use permissions stated in the file 'License.txt',
// distributed with the code package available at www.MindView.net.
// A "numbered string" that keeps track of the
// number of occurrences of the word it contains.
#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); }
// 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; }
};
// 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 ///:~
The plot here is every time a new
NString is added,it first updates the member
string s, and calls the function
addString(). This function creates a pair of
(psi) and compares it with the
words vector(which holds uniquely every string along with its number of occurences).If it does not find a match, it means the
psi containing the first string element is occuring for the first time, so it updates the
NString's thisOccurence with zero and pushes the word to
static words vector.If it finds a match through find function, it increases the second element( holding the number of occurences ) of the iterator (which points to the match found). Thus incrementing the count of occurences of that particular string in the
vp words.
The
operator== function is supposed to help the
psi( pair ) in comparing the
words( std::vector ) in the
find function. The
words should be compared with its first element the
string . But it is not happening so. As a result, when second time a
psi string comes, the particular count in
static words is incremented to 1 from 0. Next time the same string comes, the
psi p(x,0) is compared with
words(x,1), but the match is not found , because comparison is done on pair as a whole. As a result duplicate
p(x,0) is inserted. The problem here is the comparison of
psi should be solely based on the first element ( the string).
My solution:
Add this Binay Predicate
struct FindEqual: public std::binary_function< psi, std::string, bool >
{
bool operator () ( const psi &word, const std::string &pString ) const {
return word.first ==pString ;
}
};
And modify the find function this way
vpit it = std::find_if(words.begin(), words.end(),bind2nd(FindEqual(),p.first));
Here we are using
Binary Predicate to compare only the first element of words with the first element of
psi p.
