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

Summary comparison

To summarize, here is a comparison of the complexity of Symbols and Strings, for the operations they both support:

  Symbol String
null constructor 1 inline pointer assignment plus one increment O(1)
copy constructor 1 inline pointer assignment plus one increment O(1)
construct from char* O(length of string) + O(length of string
assignment 1 inline pointer assignment O(1)
equality 1 inline pointer comparison O(length of longer string)
comparison ++ 1 inline pointer comparison O(length of shorter string)
hash 0(hash value is cached) O(length of string) ++

With a large constant factor.

Symbol comparison is non-lexicographic.
Notice the note above, that Symbol comparison is non-lexicographic. This means that if you say
       Symbol foo("foo");
       Symbol bar("bar");
       if (foo > bar)  // ??
           // ..

the comparison may or may not be true; indeed, the result may change from execution to execution. Comparison is still always a total order, however. The reason for providing this behavior is because a non-lexicographic total order operation can be implemented by a single inline pointer comparison:

       int Symbol::operator<(const Symbol& s) {
           return p < s.p;

Since certain typical uses of Symbol require a total order operation, but do not require that operation to be lexicographic (for example, as the key type of Map(C++), this behavior is desirable. If the user needs to do lexicographic comparison, the underlying strings can be compared:

       if (foo.the_string() > bar.the_string())
           // true, lexicographic comparison
           // ...

Notice, however, that the complexity of this operation is now O(length of shorter string).

Previous topic: An example

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