Wednesday, March 05, 2003

Using associative containers (K&M Chapter 7)

A Word counting program

#include <iostream>
#include <map>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::map;
using std::string;

int main()
{
	string s;
	map<string, int> counters; // store each word and an associated counter

	// read the input, keeping track of each word and how often we see it
	while (cin >> s)
		++counters[s];

	// write the words and associated counts
	for (map<string, int>::const_iterator it = counters.begin();
	     it != counters.end(); ++it) {
		cout << it->first << "\t" << it->second << endl;
	}
	return 0;
}

A Cross reference table

#include <map>
#include <iostream>
#include <string>
#include <vector>

#include "split.h"

using std::cin;            using std::cout;
using std::endl;           using std::getline;
using std::istream;        using std::string;
using std::vector;         using std::map;

// find all the lines that refer to each word in the input
map<string, vector<int> >
xref(istream& in, vector<string> find_words(const string&) = split)
{
	string line;
	int line_number = 0;
	map<string, vector<int> > ret;

	// read the next line
	while (getline(in, line)) {
		++line_number;

		// break the input line into words
		vector<string> words = find_words(line);

		// remember that each word occurs on the current line
		for (vector<string>::const_iterator it = words.begin();
		     it != words.end(); ++it)
			ret[*it].push_back(line_number);
	}
	return ret;
}

int main()
{
	// call `xref' using `split' by default
	map<string, vector<int> > ret = xref(cin);

	// write the results
	for (map<string, vector<int> >::const_iterator it = ret.begin();
	     it != ret.end(); ++it) {
		// write the word
		cout << it->first << " occurs on line(s): ";

		// followed by one or more line numbers
		vector<int>::const_iterator line_it = it->second.begin();
		cout << *line_it;	// write the first line number

		++line_it;
		// write the rest of the line numbers, if any
		while (line_it != it->second.end()) {
			cout << ", " << *line_it;
			++line_it;
		}
		// write a new line to separate each word from the next
		cout << endl;
	}

	return 0;
}

A simple spell checker (not in book)

#include	<iostream>
#include	<vector>
#include	<string>
#include	<map>
#include	<fstream>
#include	<stdexcept>
#include	<iomanip>

using std::string;		using std::map;
using std::vector;		using std::ifstream;
using std::invalid_argument;	using std::cerr;
using std::cout;		using std::endl;
using std::setw;

const string dictionary_file = "/usr/share/dict/words";

string
lowercase(const string &str)
{
	string	ret;
	string::const_iterator	it;
	for (it = str.begin(); it != str.end(); it++) 
		ret += tolower(*it);
	return ret;
}

map<string, bool>
read_dictionary()
{
	ifstream in(dictionary_file.c_str());
	map<string, bool> dictionary;

	if (! in)
		throw invalid_argument("Invalid: \"" + dictionary_file + "\"");

	string word;
	while (in >> word)
		dictionary[lowercase(word)] = true;

	return dictionary;
}

void
strip_non_chars(string &word)
{
	string::iterator it = word.begin();
	while (it != word.end()) {
		if (!isalpha(*it)) {
			it = word.erase(it);
		} else {
			++it;
		}
	}
}

map<string, int>
spell_check_file(const char *file, const map<string, bool> &dictionary)
{
	ifstream in(file);

	if (! in)
		throw invalid_argument("Invalid file \"" + string(file) + "\"");

	string word;
	map<string, int> misspellings;
	while (in >> word) {
		strip_non_chars(word);
		if (word.empty())
			continue;
		if (dictionary.find(lowercase(word)) == dictionary.end())
			misspellings[word] ++;
	}
	return misspellings;
}

int
main(int argc, char **argv)
{
	if (argc != 2) {
		cerr << "Must specify a file name" << endl;
		return -1;
	}

	try {
		map<string, bool> dict = read_dictionary();
		map<string, int> misspellings = spell_check_file(argv[1], dict);
		map<string, int>::const_iterator it;
		for (it = misspellings.begin(); it != misspellings.end(); it++) 		{
			cout << setw(15) << it->first
			     << " was misspelled "
			     << it->second
			     << " time" << (it->second == 1 ? "" : "s")
			     << endl;
		}
	} catch (invalid_argument e) {
		cerr << e.what() << endl;
		return -1;
	}

}

Writing generic functions (K&M Chapter 8)

A generic median function

template <class T>
T median(vector<T> v)
{
	typedef typename vector<T>::size_type vec_sz;

	vec_sz size = v.size();
	if (size == 0)
		throw domain_error("median of an empty vector");

	sort(v.begin(), v.end());

	vec_sz mid = size/2;

	return size % 2 == 0 ? (v[mid] + v[mid-1]) / 2 : v[mid];
}

Last modified: Fri Mar 7 13:11:27 2003