String Bar) and the compiler will
only apply one-step conversion implicitly.
The second and third calls are OK because
they require a single implicit conversion step.
#include <String.h>
namespace SCO_SC {
// Auxiliary types
class Substring;
class Tmpstring;
class Stringsize{
public:
Stringsize(unsigned n);
unsigned size()const;
};
class String{
public:
// Constructors, destructor
String();
String(const char* p);
String(const char* p,unsigned n);
String(char c);
String(const Substring& s);
String(const Tmpstring& s);
String(Stringsize n);
~String();
// Conversion to char*
operator const char*()const;
char* dump(char* p)const;
// Conversion from integer
friend String int_to_str(int i);
friend String long_to_str(long i);
// Length
unsigned length()const;
friend unsigned length(const String& s);
int is_empty()const;
// Length adjustment
void shrink(int n);
void pad(int n,int pad_char = -1);
// Copy and assign
String(const String& s);
String& operator=(const String& s);
String& operator=(const char* p);
void assign(const char* p,unsigned n);
String& operator=(char c);
void make_empty();
// Concatenation
friend Tmpstring operator+(const String& s,
const String& t);
friend Tmpstring operator+(const String& s,
const char* p);
friend Tmpstring operator+(const String& s,char c);
friend Tmpstring operator+(const char* p,
const String& s);
friend Tmpstring operator+(char c,const String& s);
// Append
String& operator+=(const String& s);
String& operator+=(const char* p);
String& operator+=(char c);
void append(const char* p,unsigned n);
// Element selection
char& operator[](unsigned i);
char operator[](unsigned i)const;
char& operator[](int i);
char operator[](int i)const;
char char_at(unsigned i)const;
// Substring selection
Substring operator()(unsigned i,unsigned n);
Substring operator()(unsigned i);
String chunk(unsigned i,unsigned n)const;
String chunk(unsigned i)const;
// Queue operations
int firstX(char& c)const;
int lastX(char& c)const;
String& put(const String& s);
String& put(const char* p);
String& put(char c);
int get();
int getX(char& c);
int unput();
int unputX(char& c);
String& unget(char c);
String& unget(const String& s);
// Relations
friend int operator==(const String& s,const String& t);
friend int operator==(const String& s,const char* p);
friend int operator==(const char* p,const String& s);
friend int operator!=(const String& s,const String& t);
friend int operator!=(const String& s,const char* p);
friend int operator!=(const char* p,const String& s);
friend int operator<(const String& s,const String& t);
friend int operator<=(const String& s,const String& t);
friend int operator>(const String& s,const String& t);
friend int operator>=(const String& s,const String& t);
friend int operator<(const String& s,const char* p);
friend int operator<=(const String& s,const char* p);
friend int operator>(const String& s,const char* p);
friend int operator>=(const String& s,const char* p);
friend int operator<(const char* p,const String& s);
friend int operator<=(const char* p,const String& s);
friend int operator>(const char* p,const String& s);
friend int operator>=(const char* p,const String& s);
int compare(const String& s)const;
int compare(const char* p)const;
friend int compare(const String& s,const String& t);
// string(3C) functions
int strchr(char c)const;
friend int strchr(const String& s,int c);
int strrchr(char c)const;
friend int strrchr(const String& s,int c);
int strpbrk(const String& s)const;
friend int strpbrk(const String& s,const String& t);
friend int strpbrk(const char* p,const String& s);
friend int strpbrk(const String& s,const char* p);
int strspn(const String& s)const;
friend int strspn(const String& s,const String& t);
friend int strspn(const char* p,const String& s);
friend int strspn(const String& s,const char* p);
int strcspn(const String& s)const;
friend int strcspn(const String& s,const String& t);
friend int strcspn(const char* p,const String& s);
friend int strcspn(const String& s,const char* p);
friend int strcmp(const String& s,const String& t);
friend int strcmp(const char* p,const String& s);
friend int strcmp(const String& s,const char* p);
// UNIX system functions
friend int read(int fildes,String& s,integral_type n);
friend int write(int fildes,const String& s);
friend int puts(const String& s);
friend int fputs(const String& s,FILE* stream);
friend int gets(String& s);
friend int fgets(String& s,int n,FILE* stream);
friend int fgets(String& s,FILE* stream);
// Change case
String upper()const;
String lower()const;
// String searching
int match(const String& s)const;
int match(const char* p)const;
int firstdiff(const String& s)const;
int firstdiff(const char* p)const;
int index(const String& s,unsigned i = 0)const;
int index(char c,unsigned i = 0)const;
// Hash value
int hashval()const;
friend int hashval(const String& s);
// Stream insertion and extraction
friend ostream& operator<<(ostream& os,
const String& s);
friend istream& operator>>(istream& is,String& s);
int read(istream& is,int n);
friend String sgets(istream& is);
// Storage management
unsigned max()const;
int nrefs()const;
void reserve(Stringsize n)const;
void uniq()const;
// Compatibility
String& operator=(Stringsize n);
};
}
A String is a variable-length sequence of characters. Strings differ from the standard C null-terminated character array representation in the following ways:
The current implementation uses a shared internal representation to avoid making physical copies wherever possible. For example, although s=t creates a logical copy of t (where s and t are Strings), a physical copy is avoided by simply making s share storage with t. Assignment therefore runs in O(1), not O(#characters in t), which would be expected if a physical copy were performed. Note, however, that sharing requires that whenever one of the Strings is modified, a unique copy of that String's representation must first be made to avoid changing other Strings as a side-effect. Because of this phenomenon, the worst-case order estimates for mutative operations may be unduly pessimistic. We therefore give both best-case and worst-case order estimates for all such operations.
These types are for String temporaries. Although they are normally converted automatically to String, there are a few cases where programmers need to know about the types (see the Example).
This type is used for specifying the size of the initial memory chunk allocated for a String (see the constructor String::String(Stringsize n)).
String(); The empty String (a String of length zero). Runs in O(1).
String(const char* p); The String constructed from the first strlen(p) characters of the null-terminated character array pointed to by p (see string(3C)). Runs in O(#characters).
String(const char* p,unsigned n); The String constructed from the first n characters pointed to by p. Note that if any of these characters is the null byte, it is not given any special interpretation; in particular, a null byte is not interpreted as terminating the character array, but instead becomes part of the String. Runs in O(n).
String(char c); The String containing c as its only character. Runs in O(1).
String(const Substring& s); Conversion from type Substring to type String. Users need not normally be concerned with this constructor; it is usually applied implicitly (by the compiler) to convert expressions of type Substring to type String (see the Example). Runs in O(1).
String(const Tmpstring& s); Conversion from type Tmpstring to type String. Users need not normally be concerned with this constructor; it is usually applied implicitly (by the compiler) to convert expressions of type Tmpstring to type String (see the Example). Runs in O(1).
String(Stringsize n); The empty String occupying a pre-allocated chunk of n.size() characters (see the discussion under Storage management). The use of Stringsize as the argument type (rather than some integral type) prevents this constructor from being used in implicit conversions from integer to String. Runs in O(n).
~String(); Destructor.
The following functions provide an interface to C-style functions that expect pointers to null-terminated character arrays.
operator const char*()const; If length() is N, this operator works by stuffing a null character into cell N+1 and returning a pointer to the first cell. Runs in O(length()) when space must be acquired to make room for the extra cell (worst case), and O(1) otherwise.
char* dump(char* p)const; Copies the characters of this String into the character array pointed to by p, adding a null character at the end. The array is assumed to be at least length()+1 characters in length, but this requirement is not checked for. Runs in O(length()).
friend String int_to_str(int i);
friend String long_to_str(long i); Returns a String containing an ASCII representation of the integer i. Runs in O(#digits).
The following functions run in O(1).
unsigned length()const; The number of characters in the String.
friend unsigned length(const String& s); The number of characters in String s.
int is_empty()const; Returns non-zero if the String is empty, zero if the String is non-empty.
void shrink(int n); If this String is longer that n, truncate it to that length. Otherwise leave the String unchanged. Returns non-zero if the String is non-empty. Runs in O(1).
void pad(int n,int pad_char = -1); Appends n characters to this String. If pad_char != -1, n repetitions of the character whose ASCII code is pad_char are appended; otherwise, n arbitrary characters are appended. Runs in O(n) unless pad_char is -1, in which case it runs in O(1).
String(const String& s); Copy constructor. Runs in O(1), unless the internal representation of the String s is shared by exactly 255 Strings. In that special case, it runs in O(s.length()).
String& operator=(const String& s); Assignment. Runs in O(1), unless the internal representation of the String s is shared by exactly 255 Strings. In that special case, it runs in O(s.length()).
String& operator=(const char* p); Assigns the first strlen(p) characters of the null-terminated character array pointed to by p. Runs in O(#characters).
void assign(const char* p,unsigned n); Assigns the first n characters pointed to by p. Note that if any of these characters is the null byte, it is not given any special interpretation; in particular, a null byte is not interpreted as terminating the character array, but instead becomes part of the String. Runs in O(n).
String& operator=(char c); Assigns the String containing c as its only character. Runs in O(1).
void make_empty(); Assigns the empty string (a String of length zero). Runs in O(1).
The following functions return a type that is usually converted implicitly (by the compiler) to type String by applying the constructor String(Tmpstring&), although it may occasionally be necessary to explicitly convert some expressions explicitly (see the Example). All functions in this group run in O(max(N,M)), where N and M are the number of characters in the first and second operand, respectively.
friend Tmpstring operator+(const String& s, const String& t); The Tmpstring consisting of the characters of s followed by the characters of t.
friend Tmpstring operator+(const String& s, const char* p); The Tmpstring consisting of the characters of s followed by the first strlen(p) characters of the null-terminated character array pointed to by p.
friend Tmpstring operator+(const String& s,char c); The Tmpstring consisting of the characters of s followed by the character c.
friend Tmpstring operator+(const char* p, const String& s); The Tmpstring consisting of the first strlen(p) characters of the null-terminated character array pointed to by p followed by the characters of s.
friend Tmpstring operator+(char c,const String& s); The Tmpstring consisting of the character c followed by the characters of s.
Worst-case time order estimates for all functions in this group is O(max(length(),N)), where N is the number of characters in the operand. Best-case is O(N).
String& operator+=(const String& s);
String& operator+=(const char* p);
String& operator+=(char c); Append the character(s) of the operand to this String (the new characters become the rightmost characters of this String).
void append(const char* p,unsigned n); Appends the String constructed from the first n characters pointed to by p to this String. Note that if any of these characters is the null byte, it is not given any special interpretation; in particular, a null byte is not interpreted as terminating the character array, but instead becomes part of this String.
char& operator[](unsigned i); Preconditions: i < length(). Returns a reference to character number i so that the result may be used as the target of an assignment. Runs in O(length()) (worst-case) or O(1) (best-case).
char operator[](unsigned i)const;
char$amp; operator[](int i);
char operator[](int i)const;
char char_at(unsigned i)const; Preconditions: i < length(). Return character number i. Runs in O(1).
Substring operator()(unsigned i,unsigned n); Preconditions: the specified Substring lies completely within this String. Returns a substring of this String, allowing the substring to be replaced by assigning to it. For technical reasons, the result type is Substring, which is normally converted implicitly (by the compiler) to String using the constructor String(const Substring&), although it may occasionally be necessary to explicitly convert some expressions explicitly (see the Example). The result Substring consists of the n characters starting at character number i. Runs in O(max(length(),N)), where N is the number of characters in the specified substring (worst-case) or O(N) (best-case).
Substring operator()(unsigned i); s(i) is equivalent to s(i,s.length()-i).
String chunk(unsigned i,unsigned n)const;
String chunk(unsigned i)const; Similar to the two operators above, except that these are used for "read-only" access to substrings and do not require an intermediate conversion. Runs in O(N), where N is the number of characters in the specified substring.
int firstX(char& c)const;
int lastX(char& c)const; Assigns the leftmost (rightmost) character to c. The value of c is undefined if the String is empty. Returns non-zero if the value of c is defined. Run in O(1).
String& put(const String& s);
String& put(const char* p);
String& put(char c); Equivalent to the three append() functions.
int get(); Removes the leftmost character, if possible. Returns non-zero if the String changed. Runs in O(length()).
int getX(char& c); Like get(), except that the removed character is assigned to c.
int unput(); Removes the rightmost character, if possible. Returns non-zero if the String changed. Runs in O(length()) (worst-case) or O(1) (best-case).
int unputX(char& c); Like unput(), except that the removed character is assigned to c.
String& unget(char c); Makes c the leftmost character of this String. Runs in O(length()).
String& unget(const String& s); Makes the characters of s the leftmost characters of this String. Runs in O(max(length(),s.length()).
friend int operator==(const String& s,const String& t);" Equality relation. Returns non-zero if s and t contain the same sequence of characters. Runs in O(length of shorter operand).
friend int operator==(const String& s,const char* p);
friend int operator==(const char* p,const String& s); Like the above, except that either one of the operands may be a pointer to a null-terminated character array.
friend int operator!=(const String& s,const String& t);" Inequality relation. Returns non-zero if s and t contain a different sequence of characters. Runs in O(length of shorter operand).
friend int operator!=(const String& s,const char* p);
friend int operator!=(const char* p,const String& s); Like the above, except that either one of the operands may be a pointer to a null-terminated character array.
friend int operator<(const String& s,const String& t);"
friend int operator<=(const String& s,const String& t);"
friend int operator>(const String& s,const String& t);"
friend int operator>=(const String& s,const String& t);" The usual (lexicographic) ordering relations, returning non-zero if the relation is true. Run in O(length of longer operand).
friend int operator<(const String& s,const char* p);"
friend int operator<=(const String& s,const char* p);"
friend int operator>(const String& s,const char* p);
friend int operator>=(const String& s,const char* p);
friend int operator<(const char* p,const String& s);"
friend int operator<=(const char* p,const String& s);"
friend int operator>(const char* p,const String& s);
friend int operator>=(const char* p,const String& s); Like the above, except that either one of the operands may be a pointer to a null-terminated character array.
int compare(const String& s)const; Returns negative, zero, or positive, depending on whether this String is lexically less than, equal to, or greater than, String s. Uses the most natural character comparison available on the machine. Thus the sign of the result when one of the characters has its high-order bit set is not the same in all implementations, and should not be relied upon.
int compare(const char* p)const; Like the above, except that this String is compared with the characters of the null-terminated character array pointed to by p.
friend int compare(const String& s,const String& t);" Returns negative, zero, or positive, depending on whether s is lexically less than, equal to, or greater than, t.
The following are analogous to the "standard" C functions used for operating on null-terminated character arrays, as defined in string(3C).
int strchr(char c)const; Returns the index of the leftmost occurrence of c in this String. Returns -1 if c does not occur. Runs in O(length()).
friend int strchr(const String& s,int c); Like the above, except that it searches String s.
int strrchr(char c)const;
friend int strrchr(const String& s,int c); Like strchr, except that these search for the rightmost occurrence.
int strpbrk(const String& s)const; Returns the index of the first occurrence in this String of any character in s. Returns -1 if no such character can be found. Runs in O(max(length(),s.length()).
friend int strpbrk(const String& s,const String& t);" Returns the index of the first occurrence in s of any character in t. Returns -1 if no such characters can be found. Runs in O(max(s.length(),t.length()).
friend int strpbrk(const char* p,const String& s);
friend int strpbrk(const String& s,const char* p); Like the above, except that either one of the operands may be a pointer to a null-terminated character array.
int strspn(const String& s)const; Returns the length of the initial segment of this String consisting entirely of characters from s. Runs in O(max(length(),s.length()).
friend int strspn(const String& s,const String& t);" Returns the length of the initial segment of s consisting entirely of characters from t. Runs in O(max(s.length(),t.length()).
friend int strspn(const char* p,const String& s);
friend int strspn(const String& s,const char* p); Like the above, except that either one of the operands may be a pointer to a null-terminated character array.
int strcspn(const String& s)const; Returns the length of the initial segment of this String consisting entirely of characters not from s. Runs in O(max(length(),s.length()).
friend int strcspn(const String& s,const String& t);" Returns the length of the initial segment of s consisting entirely of characters not from t. Runs in O(max(s.length(),t.length()).
friend int strcspn(const char* p,const String& s);
friend int strcspn(const String& s,const char* p); Like the above, except that either one of the operands may be a pointer to a null-terminated character array.
friend int strcmp(const String& s,const String& t);" Returns negative, zero, or positive, depending on whether s is lexically less than, equal to, or greater than, t.
friend int strcmp(const char* p,const String& s);
friend int strcmp(const String& s,const char* p); Like the above, except that either one of the operands may be a pointer to a null-terminated character array.
friend int read(int fildes,String& s,integral_type n);"
friend int write(int fildes,const String& s);
friend int puts(const String& s);
friend int fputs(const String& s,FILE* stream);
friend int gets(String& s);
friend int fgets(String& s,int n,FILE* stream); These are overloadings of some of the functions described in sections 2 and 3S of the UNIX Programmer's Reference Manual. A function is included in this section if it meets the following two criteria: (1) it has one or more char* arguments and (2) the function can be implemented in such a way that it is more efficient to use it than to convert String arguments to const char* and then call the standard version of the function. The functions have identical semantics to those described in the UNIX Programmer's Reference Manual.
friend int fgets(String& s,FILE* stream); Like fgets(3S) except that this version reads a (conceptually) infinite number of characters.
String upper()const; The result has the same characters as this String, except that lower-case alphabetic characters are converted to upper-case ones. Runs in O(length()).
String lower()const; The result has the same characters as this String, except that upper-case alphabetic characters are converted to lower-case ones. Runs in O(length()).
All functions run in O(min(N,M)), where N and M are the number of characters in the first and second operand, respectively.
int match(const String& s)const; Returns the length of the initial common substring of this String and s. Returns the length if this String matches s.
int match(const char* p)const; Returns the length of the initial common substring of this String and the characters in the null-terminated character array pointed to by p. Returns length if this String matches p.
int firstdiff(const String& s)const; Returns the index of the first character at which this String differs from s. Returns -1 if this String matches s or if this String is an initial substring of s.
int firstdiff(const char* p)const; Returns the index of the first character at which this String differs from the characters in the null-terminated character array pointed to by p. Returns -1 if this String matches p or if this String is an initial substring of p.
int index(const String& s,unsigned i = 0)const; Returns the lowest index in this String beginning at which the characters of s match those of this String. Begins searching from index i. Returns -1 if no match is found, or if i is not a legal index in this String.
int index(char c,unsigned i = 0)const; Like the above, except that it searches for the character c.
int hashval()const;
friend int hashval(const String& s); Returns a non-negative integer suitable for use as a hash table probe. Runs in O(#characters).
friend ostream& operator<<(ostream& os,const String& s);" Inserts the characters of s into os.
friend istream& operator>>(istream& is,String& s);" Extracts the next whitespace-separated sequence of characters from is, constructs a String from them, and assigns the String to s.
int read(istream& is,int n); Extracts at most n characters from is (including whitespace characters), constructs a String from them, and assigns the String to s. Returns the number of characters actually extracted. Returns a negative value if the stream was exhausted before any characters were found.
friend String sgets(istream& is); Extracts characters from is up to and including the next newline (including whitespace characters), constructs a String from them (not including the newline), and returns it as the function result.
The functions in this group allow the programmer some control over details of the internal String representation; they should be used only in time-critical code where optimum performance, or accurate knowledge of the complexity of mutative operations, is essential. For an explanation of the terms memory chunk and sharing, see the Notes section.
unsigned max()const; Returns the size of the memory chunk containing this String's internal representation.
int nrefs()const; Returns the number of Strings currently sharing this String's internal representation. Runs in O(1) (currently implemented as one inline instruction).
reserve(Stringsize n)const; Guarantees that the size of the memory chunk occupied by this String is at least n.size() characters. Runs in O(length()) (tests inline to see if the current chunk is large enough).
void uniq()const; Guarantees that nrefs()==1. That is, calling uniq() guarantees that this String does not share memory with any other String, allowing you to accurately predict the cost of any operation on this String (see Complexity).
The following functions are retained for compatibility with earlier releases.
String& operator=(Stringsize n);
See the Notes section for a description of the current String implementation. Because it is not always possible to predict, by means of static program analysis alone, when a String's representation is shared or when its memory chunk is full, the cost of mutative operations cannot, in general, be predicted. When it is essential to know the cost of such operations (for example, in innermost loops of programs with strict performance requirements), the best-case order estimates can be guaranteed by calling uniq() or reserve(). For example, while the worst-case order estimate for functions in the Append group is O(max(length(),N)), where N is the length of the appendage, this estimate includes the cost of (1) uniquification and (2) re-allocation. By calling uniq() and then reserve() prior to appending, the caller is guaranteed a cost of O(N).
In the current implementation, a String's characters are held internally in a contiguous memory chunk. The chunk may be larger than the length of the String, allowing a certain amount of growth before re-allocation is necessary. The implementation generally manages these chunks quite efficiently. However there are certain situations where information from the client is needed to achieve optimum performance. For example, if the client knows in advance that a String will eventually grow to 1000 characters, it would be nice to be able to request that a chunk of 1000 characters be allocated in advance for it. This can be done using the constructor String(Stringsize). A chunk of a specified size may also be reserved for an existing String by calling the function reserve().
The current implementation uses a shared internal representation to avoid copying wherever possible. For example, although s1=s2 creates a logically unique copy of s2, physical copy is delayed by simply making s1 temporarily share storage with s2. Physical copy only becomes necessary if one of the Strings is changed. In typical code, this scheme completely avoids physical copy much of the time.
Use Symbol(3C++) instead of String(3C++) in applications with the following characteristics: (1) Strings would be 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.
The following example illustrates a situation requiring an explicit cast from Tmpstring to String:
class Bar{
public:
Bar(const String& s);
};
void foo(const Bar& b);
String s,t;
foo(s+t); illegal
foo(String(s+t)); legal
foo(Bar(s+t)); legal
The first call to foo() is illegal because
it would require a two-step conversion
(Tmpstring String Bar) and the compiler will
only apply one-step conversion implicitly.
The second and third calls are OK because
they require a single implicit conversion step.