The STL also provides an explicit map container, based on balanced trees, that stores key-value pairs and provides O(logn) retrieva l of the value associated with any key. Maps might not be as efficient as O(1) hash tables, but it’s nice not to have to write any code whatsoever to use them. (Some non-standard C++(www.cppentry.com) libraries includea hash or hash_map container whose performance may be better.)

We also use the built-in comparison functions,which in this case will do string comparisons using the individual strings in the prefix.

With these components in hand, the code goes together smoothly. Here are the declarations:

  
The STL provides a template for deques; the notation deque<string> spe- cializes it to a deque whose elements are strings. Since this type appears several times in the program, we used a typedef to give it the name Prefix. The map type that stores prefixes and suffixes occurs only once, however, so we did not give it a separate name; the map declaration declares a variable statetab that is a map from prefixes to vectors of strings. This is more convenient than either C or Java, because we don’t need to provide a hash function or equals method.