A Class for Efficient Key Lookup in C++ - Symbol(3C++)
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(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.
Next topic:
Symbol tables
© 2004 The SCO Group, Inc. All rights reserved.
UnixWare 7 Release 7.1.4 - 27 April 2004