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