Let us consider a word processor that needs to keep track of index entries. An index consists of two parts: the text of the index, and a destination address (which is a page number for a printed document, or an anchor for an HTML document). As a document is scanned, index items are collected.
When the document is about to be published, the index is rendered based on the alphabetical order of the text of each index item. Note that multiple index items may share the same index text, but have different destinations.
In this case, as we scan through (parse) the document, we need to insert items into a container. Even without knowing what kind of container will be chosen, we know that it needs to support an “insert iterator” to add entries into the container. Note that there are different types of insert iterators, some insert at the front, and some inert at the end.
When the document is rendered, the index must be generated. The generation of the index requires the contained index items be presented in a sorted fashion. This can be done by two methods. We can sort the container when the index needs to be rendered, or we can maintain index items already sorted in the container.
In this case, we have many choices. The most efficient method, however, is to use a vector as an underlying container, then use a back_insert_iterator to insert items into the container. When a document is parsed, then the program can use the stable_sort algorithm to sort the index entries. Once the entries are sorted, the vector iterator can be used to extract the index entries.
Listing 1 is a sample program to illustrate this example.
| Listing 1: | indexing |