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

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

A frequent operation in many programs is using a string as a key for storage and retrieval of information. A database manager is an obvious example; a less obvious example is a language translator, which spends much of its time looking up identifiers in symbol tables. In fact, any program that declares a
       Map<String,T> map;     // an associative array from
                              //  String to some type T
                              // see Map(C++)

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(C++). 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.

Next topic: Symbol tables

© 2005 The SCO Group, Inc. All rights reserved.
SCO OpenServer Release 6.0.0 -- 02 June 2005