|
|
#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;
};
}
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++)).
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.
Symbol(const Symbol& s);
Symbol& operator=(const Symbol& s); Copying or assigning a Symbol creates a copy of its value.
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.
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++)).
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.
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;
}
The total order relations are not lexicographic.