HP Integrity NonStop H-Series - Manual (Page 106)

string city = que.top().second;
que.pop();
// if we haven't seen it already, process it
if (0 == distances.count(city)) {
// then add it to shortest distance map
distances[city] = distance;
// and put values into queue
const stringVector & cities = cityMap[city];
stringVector::const_iterator start = cities.begin();
stringVector::const_iterator stop = cities.end();
for (; start != stop; ++start)
que.push(DistancePair(distance + (*start).second,
(*start).first));
}
}
}
Notice that this relatively simple algorithm makes use of vector s, map s, string s and priority_queue s.
priority_queues are described in greater detail in Chapter 11 .
A Concordance
Obtaining the Sample Program
A concordance is an alphabetical listing of words in a text, that shows the line numbers on which
each word occurs. We develop a concordance to illustrate the use of the
map and multimap container
classes. The data values will be maintained in the concordance by a multimap, indexed by strings (the
words) and will hold integers (the line numbers). A multimap is employed because the same word
will often appear on multiple different lines; indeed, discovering such connections is one of the
primary purposes of a concordance. Another possibility would have been to use a map and use a
set
of integer elements as the associated values.
class concordance {
typedef multimap > wordDictType;
public:
void addWord (string, int);
void readText (istream &);
void printConcordance (ostream &);
private:
wordDictType wordMap;
};
The creation of the concordance is divided into two steps: first the program generates the
concordance (by reading lines from an input stream), and then the program prints the result on the
output stream. This is reflected in the two member functions readText() and printConcordance(). The
first of these, readText(), is written as follows: