1. Preventing errors in accessing an array

   struct stringarr
   {
     protected:

       string * arr;
       int size;

     public:

       stringarr()
       { /* default constructor as before */ }

       stringarr(int initsize)
       { /* extra constructor as before */ }

       void resize(int newsize)
       { /* as before */ }

       string value(int i)
       { if (i<0 || i>=size)
         { cerr << "index " << i << " out of bounds 0.." << size-1 << "\n";
           exit(1); }
         return arr[i]; }

       void change(int i, string val)
       { if (i<0 || i>=size)
         { cerr << "index " << i << " out of bounds 0.." << size-1 << "\n";
           exit(1); }
         arr[i]=val; }

       int howmany()
       { return size; }
   };

   protected: means that the following things are protected from outside
   interference. Only the methods of stringarr (that is the constructors,
   resize, value, change, and howmany) even know they exist. It is impossible
   to change arr or size except by using one of those methods.

   public: switches back to normal, so the two constructors and three
   methods can be used freely in the rest of the program.

   Making data items protected allows programs to be made much more reliable
   than would otherwise be possible. Anybody who uses a stringarr in a
   program instead of a normal array of strings is incapable of accidentally
   corrupting other data by miscalculating an array index.


2. Extension to make stringarr more convenient. You never have to keep
   track of how many items are stored in it, just add more as desired.

   This is another method, put inside the stringarr struct

      void add(string newval)
      { resize(size+1);
        change(size-1, newval); }

   So to read a bunch of strings from a file, you could have something
   as simple as this (assuming the file has already been opened)

      stringarr X;
      while (true)
      { string s;
        fin >> s;
        if (fin.fail())
          break;
        X.add(s); }


3. Analysis of time efficiency
   
   Starting with an empty stringarr, adding new things one-by-one.

   1. add first item, current size is 0
        resize to 1
        copy new item into array           data-size   copies  total-copies
                                               1          1         1

   2. add second item, current size is 1
        resize to 2
        copy existing 1 item into array
        copy new item into array           data-size   copies  total-copies
                                               2          2         3

   3. add second item, current size is 2
        resize to 3
        copy existing 2 items into array
        copy new item into array           data-size   copies  total-copies
                                               3          3         6

   4. add second item, current size is 3
        resize to 4
        copy existing 3 items into array
        copy new item into array           data-size   copies  total-copies
                                               4          4        10

   5. add second item, current size is 4
        resize to 5
        copy existing 4 items into array
        copy new item into array           data-size   copies  total-copies
                                               5          5        15

   6. add second item, current size is 5
        resize to 6
        copy existing 5 items into array
        copy new item into array           data-size   copies  total-copies
                                               6          6        21

   7. add second item, current size is 6
        resize to 7
        copy existing 6 items into array
        copy new item into array           data-size   copies  total-copies
                                               7          7        28

   8. add second item, current size is 7
        resize to 8
        copy existing 7 items into array
        copy new item into array           data-size   copies  total-copies
                                               8          8        36

   9. add second item, current size is 8
        resize to 9
        copy existing 8 items into array
        copy new item into array           data-size   copies  total-copies
                                               9          9        45

   10. add second item, current size is 9
         resize to 10
         copy existing 9 items into array
         copy new item into array          data-size   copies  total-copies
                                              10         10        55

   Just getting 10 strings into the array requires a total of 55 string
   copying operations.

   The pattern is data size of N requires N(N+1)/2 operations.
   For our purposes, calling it half N squared is accurate enough.

   A moderate database of 1,000,000 items would require 500,000,000,000
   operations, whereas if we knew the size in advance and created an
   array of just the right size, it would have needed only 1,000,000
   operations.

   Number of operations directly determines time taken.

   Quadratic (N squared) relationship means double the data size, 
   quadruply the time. Ten times more data, a hundred times more
   time.


4. Improvement: When the array isn't big enough, don't just increase
   the capacity by one, think ahead and add more space. How much extra?
   Who knows. Let's say 9 extra.

       string * arr;
       int numitems, capacity, increment;

       stringarr()
       { arr = new string[0];
         numitems = 0;
         capacity = 0;
         increment = 10; }

       void resize(int newcapacity)
       { /* same as before, except that it does not care
            about size, at the end it changes capacity to
            newcapacity */ }

       void add(string newval)
       { if (numitems>=capacity)
           resize(capacity+increment);
         change(numitems, newval);
         numitems+=1; }

   So after doing all the work of copying all existing items
   into a new array, the next nine add operations won't have to,
   the array will already have extra capacity.

   Just how much does this help us?