No More Array Errors (Part I) - Block(C++)

The reserve operation

In the section, ``What is array reallocation?'', we gave an example that used the reserve() operation. To really understand what reserve() does and how to use it, it helps to look at the code:

       inline int Block(T)::reserve(unsigned i) {
           return i<n || grow(i);

In the above, n is the size of the current allocation and grow(unsigned i) is a private function that reallocates the Block to a size at least as great as i. The present strategy is to multiply the current size by the smallest power of 1.5 needed to increase it beyond i.

The important thing to note is that when k<n, the second term of the logical OR is not evaluated. This means that the cost of calling reserve is the same as the cost of comparing two integers except when the test is false.

reserve() was designed to be used in situations like the following. Consider a program that reads file of integers into an array; although 100 is the expected maximum number of integers, the actual number may be larger, and the programmer wants to allow for this possibility.

       unsigned i = 0;
       Block<int> b(100);   // 100 is the expected maximum
       int x;

while(cin >> x){ b.reserve(i); b[i++] = x; }

The program runs with virtually no overhead due to using Block until reserve is called with for the argument 100; this causes reallocation. (With the present strategy, the new size will be 150.)

Next topic: The size operation
Previous topic: Changing Block Size

© 2005 The SCO Group, Inc. All rights reserved.
SCO OpenServer Release 6.0.0 -- 02 June 2005