Simple Trie implementation of a Word Dictionary

dict-trie.cc

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

using namespace std;

typedef struct dict {
	map<char, struct dict *> child_map;
	bool is_word;
} dict_t;

static void insert(dict_t *dict, string &str)
{
	map<char, struct dict *>::const_iterator it;
	dict_t *curr = dict;
	for (int i = 0; i < str.size(); i++) {
		it = curr->child_map.find(str[i]);
		if (it == curr->child_map.end()) {
			dict_t *n = new dict_t;
			curr->child_map[str[i]] = n;
			n->is_word = false;
			curr = n;
		} else {
			curr = curr->child_map[str[i]];
		}
	}
	curr->is_word = true;
}

bool find(dict_t *dict, string &str)
{
	map<char, struct dict *>::const_iterator it;
	dict_t *curr = dict;
	for (int i = 0; i < str.size(); i++) {
		it = curr->child_map.find(str[i]);
		if (it == curr->child_map.end()) {
			return false;
		} else {
			curr = curr->child_map[str[i]];
		}
	}

	return curr->is_word;
}

int main()
{
	dict_t *root = new dict_t;
	int n;
	cout << "Enter the number of words you want to add to dictionary" << endl;
	cin >> n;
	cout << "Enter words (each per line)" << endl;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		insert(root, s);
	}
	cout << "Enter strings to find" << endl;
	string quit("quit");
	while (1) {
		string s;
		cin >> s;
		if (s.compare(quit) == 0) {
			cout << "Quitting" << endl;
			break;
		}
		if (find(root, s))
			cout << s << " found in dict" << endl;
		else
			cout << s << " not found in dict" << endl;
	}
	return 0;
}