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.

       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).