Symbol(3C++)


Symbol -- unique identifiers based on character strings

Synopsis

   #include <Symbol.h>
   namespace SCO_SC {
   

class Symbol{ public: // Constructors, destructor Symbol(); Symbol(const String& s); Symbol(const char* cp); ~Symbol(); // Copy and assign Symbol(const Symbol& s); Symbol& operator=(const Symbol& s); // Relations int operator==(const Symbol& b)const; int operator!=(const Symbol& b)const; int operator<(const Symbol& b)const; int operator<=(const Symbol& b)const; int operator>(const Symbol& b)const; int operator>=(const Symbol& b)const; // Miscellaneous String the_string()const; unsigned long hashval()const; }; }

Description

Symbols are unique identifiers based on character strings. 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. Symbols should be used instead of strings (either null-terminated character arrays or String(3C++)) in applications with the following characteristics: (1) the strings are used primarily as keys for data storage and retrieval (2) the application is lookup-intensive (keys are used many times over their lifetimes) and (3) lexicographic ordering of keys is not required. A good example is a compiler symbol table. For such applications, Set<Symbol>, Map<Symbol,V>, and Block<Symbol> provide appealing alternatives to Set<String>, Map<String,V>, and Block<String>, respectively (see Set(3C++), Map(3C++), and Block(3C++)).

Constructors, destructor

Symbol(); The Symbol associated with the empty string (").

Symbol(const String& s); The Symbol associated with String s.

Symbol(const char* cp); The Symbol associated with the null-terminated character array pointed to by cp. If cp is zero, the result is the same as if the parameterless constructor had been used.

~Symbol(); Destructor. Memory used for Symbols is not freed until the last Symbol object existing (at any given point in time) is destructed.

Copy and assign

Symbol(const Symbol& s);

Symbol& operator=(const Symbol& s); Copying or assigning a Symbol creates a copy of its value.

Relations

int operator==(const Symbol& b)const;

int operator!=(const Symbol& b)const; Equality and inequality relations. Two Symbols are equal if their associated strings are equal.

int operator<(const Symbol& b)const;

int operator<=(const Symbol& b)const;

int operator>(const Symbol& b)const;

int operator>=(const Symbol& b)const; Non-lexicographic total order relations.

Miscellaneous

String the_string()const; The String associated with this Symbol.

unsigned long hashval()const; A perfect hash function that can be used when creating Sets or Bags of Symbols (see Set(3C++)).

Complexity

The constructors run in O(#characters in associated string) and all other operations run in O(1). Destructors run in O(1) except for the last one, which runs in O(#Symbol objects created).

Symbols are constructed by inserting their associated Strings into a Set<String> (see Set(3C++)). Although Set insertion runs in constant time, it is a rather large constant. The equality, inequality, and ordering relations, on the other hand, are each implemented as a single inline pointer comparison.

Example

The following two versions of lookup() are functionally equivalent, but the second version is much faster than the first:

       #include <Block.h>
       #include <String.h>
       #include <Symbol.h>
       int lookup(Block<String>& table, const String& arg){
           for(String* p = table;p<table.end();p++){
               if(*p==arg)return 1;
           }
           return 0;
       }
       int lookup(Block<Symbol>& table, const Symbol& arg){
           for(Symbol* p = table;p<table.end();p++){
               if(*p==arg)return 1;
           }
           return 0;
       }

Warnings

The total order relations are not lexicographic.

References

Block(3C++), Map(3C++), Set(3C++), String(3C++)
© 2004 The SCO Group, Inc. All rights reserved.
UnixWare 7 Release 7.1.4 - 25 April 2004