From eavis@lonhp01.lon.amadeus.net Mon May 12 19:42:59 2003
Date: Tue, 6 May 2003 11:33:34 +0100 (BST)
From: Edward Avis <eavis@lonhp01.lon.amadeus.net>
To: undisclosed-recipients:  ;

// For jgreenwood, who wanted a two-dimensional container that would
// resize as needed (unlike ordinary arrays).
//

#include <string>
#include <iostream>

// One approach using a map of maps.  Simple, but not particularly
// efficient.
//
#include <map>
using std::map;
using std::string;
void test_map() {
    map<int, map<int, string> > m;
    m[5][6] = "hello";
    std::cout << m[5][6] << std::endl;
}

// Vector of vectors approach.
#include <vector>
using std::vector;

// But because vectors must be grown by hand, and this is awkward for
// multiple dimensions, we first define:
//
// A vector that resizes itself whenever you try to set an element.
// Missing elements will be default-constructed.  (It should still go
// wrong if you try to merely fetch an element which isn't there,
// because the const operator[] isn't overridden.)
//
template<class T> struct Vector_autosize: public vector<T> {
    void ensure_size(int s) { if (size() < s) { resize(s); } }
    T& operator[](int i) {
        ensure_size(i + 1);
        return vector<T>::operator[](i);
    }
};

// An n-dimensional vector which (as above) resizes itself when
// elements are asked for.
//
template<int n, class T> struct Vector_dim;

// The base case is a zero-dimensional Vector_dim of T, which is just a T!
template<class T> struct Vector_dim<0, T>: public T {
    using T::operator=;
};

// An (n+1)-dimensional Vector_dim is a vector of n-dimensional
// Vector_dims.
//
template<int n, class T> struct Vector_dim:
    public Vector_autosize<Vector_dim<n-1, T> > {};

void test_vector() {
    Vector_dim<2, string> v;
    v[1][2] = "fa";
    std::cout << v[1][2] << std::endl;

    // Note that v[1][1], for example, has been default-constructed
    // during the vector's expansion.
    //
    // However there is a bug (arguably): not all the rows have grown
    // equally.  The row v[1] has been created and grown to length 3
    // to accommodate v[1][2], but the row v[0] has only been created
    // and not grown.  So an access to v[0][1] would be an error
    // (unless it is assigned to first).
    //
    // There are two ways to fix this.  One would be to make all
    // elements spring into existence when accessed for reading (not
    // just when accessed for assignment).  That would mean altering
    // Vector_autosize and giving it a 'const T& operator[](int i)
    // const' method as well as the existing operator[].  But that
    // might hide bugs when you intend to grow an n-dimensional vector
    // to a certain size and then access it only inside that size.
    //
    // The other way would be to keep the convention that assignment
    // dynamically resizes the container while mere access does not -
    // but make sure that when one dimension grows it does so evenly
    // (eg, if one row becomes longer all the others do too).  I have
    // some idea how to implement this but haven't yet had time.
    //
}

int main() {
    test_map();
    test_vector();
    return 0;
}