Solution

I l @ ve RuBoard

Implementing Original::String

Here is a straightforward implementation. The default constructor and destructor are simple to write:

 namespace Original {   String::String() : buf_(0), len_(0), used_(0) { }   String::~String() { delete[] buf_; } 

Next, to implement copy assignment, we just make a new buffer and use the standard copy() algorithm to make a copy of the original's contents:

 String::String( const String& other )   : buf_(new char[other.len_]),     len_(other.len_),     used_(other.used_) {   copy( other.buf_, other.buf_ + used_, buf_ ); } 

I've chosen to implement an additional Reserve() helper function for code clarity because it will be needed by other mutators besides Append() . Reserve() ensures that our internal buffer is at least n bytes long, and allocates additional space using an exponential-growth strategy:

 void String::Reserve( size_t n ) {   if( len_ < n )   {     size_t newlen = max( len_ * 1.5, n );     char*  newbuf = new char[ newlen ];     copy( buf_, buf_+used_, newbuf );     delete[] buf_;  // now all the real work is     buf_ = newbuf;  //  done, so take ownership     len_ = newlen;   } } 

Finally, Append() just makes sure there's enough space, then tacks on the new character:

 void String::Append( char c )   {     Reserve( used_+1 );     buf_[used_++] = c;   } } 

Aside: What's the Best Buffer Growth Strategy?

When a String object runs out of room in its currently allocated buffer, it needs to allocate a larger one. The key question is: How big should the new buffer be? Note that the question is important because the analysis we're about to do holds for other structures and containers that use allocated buffers, such as a standard vector .

There are several popular buffer growth strategies. I'll note each strategy's complexity in terms of the number of allocations required, and the average number of times a given character must be copied , for a string of eventual length N.

1. Exact growth. In this strategy, the new buffer is made exactly as large as required by the current operation. For example, appending one character and then appending another will force two allocations. First, a new buffer is allocated, with space for the existing string and the first new character. Next, another new buffer is allocated, with space for that and the second new character.

   • Advantage: no wasted space.

   • Disadvantage: poor performance. This strategy requires O(N) allocations and an average of O(N) copy operations per char , but with a high constant factor in the worst case (same as option (b) below with an increment size of 1 ). Control of the constant factor is in the hands of the user code, not controlled by the String implementer.

2. Fixed-increment growth. The new buffer should be a fixed amount larger than the current buffer. For example, a 64-byte increment size would mean that all string buffers would be an integer multiple of 64 bytes long.

   • Advantage: little wasted space. The amount of unused space in the buffer is bounded by the increment size, and does not vary with the length of the string.

   • Disadvantage: moderate performance. This strategy requires both O(N) allocations and an average of O(N) copy operations per char . That is, both the number of allocations and the average number of times a given char is copied vary linearly with the length of the string. However, control of the constant factor is in the hands of the String implementer.

Exponential growth. The new buffer is a factor of F larger than the current buffer. For example, with F = .5, appending one character to a full string that is already 100 bytes long will allocate a new buffer of length 150 bytes.

Advantage: good performance. This strategy requires O(logN) allocations and an average of O(1) copy operations per char . That is, the number of allocations varies as the log of the length of the string, but the average number of times a given char is copied is constant, which means that the amount of copying work to create a string using this strategy is at most a constant factor greater than the amount of work that would have been required had the size of the string been known in advance.

Disadvantage: some wasted space. The amount of unused space in the buffer will always be strictly less than NxF bytes, but that's still O(N) average space wastage.

The following chart summarizes the trade-offs:

Growth Strategy	Allocations	Char Copies	Wasted Space
Exact	O(N) with high const.	O(N) with high const.	none
Fixed-increment	O(N)	O(N)	O(1)
Exponential	O(logN)	O(1)	O(N)

In general, the best-performing strategy is exponential growth. Consider a string that starts empty and grows to 1,200 characters long. Fixed-increment growth requires O(N) allocations and, on average, requires copying each character O(N) times (in this case, using 32-byte increments , that's 38 allocations and, on average, 19 copies of each character). Exponential growth requires O(logN) allocations and, on average, requires making only O(1) ”one or two ”copies of each character (yes, really; see the reference below). In this case, using a factor of 1.5, that's 10 allocations and on average 2 copies of each character.

	1,200-char string			12,000-char string
	Fixed-incr growth (32 bytes)	Exponential growth (1.5x)		Fixed-incr growth (32 bytes)	Exponential growth (1.5x)
# of memory allocations	38	10		380	16
avg # ofcopies made of each char	19	2		190	2

This result can be surprising. For more information, see Andrew Koenig's column in the September 1998 issue of JOOP (Journal of Object-Oriented Programming) . Koenig also shows why, again in general, the best growth factor is not 2 but probably about 1.5. He also shows why the average number of times a given character is copied is constant ”that is, it doesn't depend on the length of the string.

I l @ ve RuBoard