A Class for Efficient Key Lookup in C++ - Symbol(3C++)

       Map<String,T> map;     // an associative array from
                              //  String to some type T
                              // see Map(3C++)

is using strings as keys for storage and retrieval. Unfortunately, representing keys by Strings or char*'s -- although common -- is usually inefficient. The problem is that Strings and char*'s have inefficient comparison operations, requiring a call to memcmp() in general. Key storage and retrieval operations frequently need to perform many key comparisons. Hence, use of Strings or char*'s as keys, although conceptually correct, is inefficient. In this tutorial, we present a C++ class ``Symbol'' (see Symbol(3C++). Symbols are like character strings, but they are designed for efficient use as keys. They are characterized by extremely efficient equality and total order relations whose speed is independent of the length of the string on which the Symbol is based. The efficiency of these operations is gained at the expense of Symbol construction, which is considerably slower than String construction, and at the expense of not supporting all the operations provided by String. However, in the intended uses of Symbol, these restrictions are not important. For some applications Symbols are the superior choice. This tutorial will explain the design and use of the Symbol class. The running example will be a compiler symbol table. We will also show a sample program illustrating the superiority of Symbol over String and char*. Finally, we will summarize the differences in complexity between Symbol and String.