Peter Mancini <peter_mancini@Sp-am-blo-ck.onesource.com> wrote:
[snip]
+ Is vector a typename?  is vector<int> a typename?  I still don't get why I
+ can't do vector< vector<int> > multidim_array_of_int;

You can.  It's not a very efficient method of storage for an array (of
however many dimensions) whose size isn't going to change at runtime,
however.  There's a lot of wasted memory due to the extra allocation
that's often done by compilers in order to meet the Standard
requirements regarding growth.

I've written a 2D matrix class using vector<double> for one dimension,
and a simple vector<double>* (i.e., the usual array method) as
controlling the other dimension.  It was originally for porting MATLAB
code to C++; since MATLAB matrices may grow arbitrarily during the
course of a program, e.g.,

 an_MbyN_matrix = [ the_same_MbyN_matrix  an_Mby1_column_vector ]

and so I wanted the storage-management routines of vector<>, so that
I'd have to mess with [de]allocation as little as possible.  It's not
very efficient when using matrices which don't change in size.


/dev/phil
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Peter Mancini wrote:

> [...] OK, so I just answered my own question,

Yes, indeed.

> Is vector a typename?  is vector<int> a typename?

No. Typename is eg. `iterator' in `vector<T>::iterator'.
As far as I can understand it, keyword `typename' is used
to identify qualified names as types (and not as data
members or member functions). I am not sure if it is
necessary in

  typedef typename vector<T>::iterator iterator;

(How can one typedef a data or function member? Can some
kind soul explain that?), but my compiler (which, as
its authors claim, `is the result of serious tracking of
the ANSI/ISO C++ committee deliberations to date', that is,
to `December 9, 1996') didn't complain.

> I still don't get why I
> can't do vector< vector<int> > multidim_array_of_int;

You can. But...

If you declare `ivv' as

  vector< vector<int> > ivv;

you must resize it first

  ivv.resize (no_of_rows);

[with SGI STL: ivv.reserve(...); not the same function, but
there's no `resize()' yet], and then resize all `rows'

  for (int i = 0; i < no_of_rows; ++i)
    ivv[i].resize (no_of_cols);

Of course, you can write

  vector< vector<int> > ivv (no_of_rows);

but not

  vector< vector<int> > ivv (no_of_rows, no_of_cols);

Of course, you can wrap it in a class and let constructor do
the resizing.

But, this approach (with or without wrapping it in a class)
is not very efficent:

1) declaration `vector< vector<int> > ivv (nr);' first calls
   constructor

     vector (nr, vector<int>())

   which calls `new' to allocate memory for
   `vector< vector<int> >', and then calls `vector<int>'s
   default (or copy) constructor `nr' times to initialize
   `nr' empty `vector<int>'s which are members of
   `vector< vector<int> >';

2) then, in a loop, `resize()' is called `nr' times to resize
   individual `rows', and each time `resize()' calls `new'.

Besides, as Phil Edwards points out in his reply, ``There's a
lot of wasted memory due to the extra allocation that's often
done by compilers in order to meet the Standard requirements
regarding growth.''


Approach from `Numerical Recipes' has some other advantages, too.

For example, as all data are (is?) in one memory chunk, in some
(almost all, matrix multiplication is a notable exception) matrix
operations (if you derive `matrix' from `array2d') you can treat
array2d as a long vector:

  template <typename T>
  class array2d {
  // ...
  protected:
    vector<T> elems;         // actual data
    vector<iterator> rows;   // beginnings of rows
  };

  template <typename T>
  class matrix : public array2d<T> {
  public:
    matrix<T>& operator+= (matrix<T> const&);
  // ...
  };

  template <typename T>
  matrix<T>& matrix<T>::operator+= (matrix<T> const& a){
    transform (elems.begin(), elems.end(),
               a.elems.begin(), plus<T>());
    return *this;
  }

You can even combine this with Daveed Vandevoorde's `static
expression trees' (again, matrix multiplication is an
exception).


fres

fresl@grad.hr
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Peter Kelm wrote:

> I want to create a two-dimensional array using stl vector
> size is determined at runtime. But how do I do this?
>
> #include <vector>
>
> typedef vector<double> row;
> typedef vector<row*>   matrix;
> matrix myMatrix;
>
> the code above works but if I do it like this i cannot use
> the "common" subscript operator
>
> myMatrix[1][2] = 5.4;
>
> Ideas for a simple solution?


My solution (C++ version of 2D arrays in `Numerical Recipes'
2nd ed. by Press et al.) is:

  template <typename T>
  class array2d {
  public:
    typedef typename vector<T>::iterator        iterator;
    typedef typename vector<T>::const_iterator  const_iterator;
    typedef typename vector<T>::size_type       size_type;

    // ...
    array2d (size_type r, size_type c, T const& val = T())
    : elems (r*c, val), rows (r), nr (r), nc (c) {
      init_rows();
    }

    iterator operator[] (size_type i) { return rows[i]; }
    const_iterator operator[] (size_type i) const { return rows[i]; }

  protected:
    vector<T> elems;         // actual data
    vector<iterator> rows;   // beginnings of rows
    size_type nr;            // number of rows
    size_type nc;            // number of columns

    void init_rows() {
      rows[0] = elems.begin();
      for (size_type i = 1; i < nr; ++i)
        rows[i] = rows[i-1] + nc;
    }
  };


In the expression a2d[i][j] first operator[] is
array2d::operator[] which returns vector<T>::iterator
(lets call it `temp') which `points' to the beginning
of the ith row. Because vector<T>::iterator is random
access iterator, there must be (according to the CD)
operator[] defined for it, with operational semantics
*(temp+j).

Dec. '96 CD says that for random acces iterators
temp[j] should only have type convertible to T.
It seems therefore that non-const version of
array2d::operator[] is not guaranteed to work. But
in a recent post (thread `Questions about iterator
library') Brian Parker wrote:

: That's got to be a bug in the draft. The latest SGI version
: of the STL (at www.sgi.com) specifies that for an iterator x,
: *x returns a type convertible to T to allow for a proxy
: implementation, but also specifies that for mutable iterators
: the dereference assignment expression *x = t is defined
: (output iterators are an exception). [...]

: I don't know what is on the committee's agenda, but hopefully
: these bugs will be fixed.

As for current vector implementations, vector<T>::iterator
is simply T* (that is `plain' pointer), and for pointers
operator[] is defined.


fres

fresl@grad.hr


PS. All comments on the above code are welcome.
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

That's a really interesting solution.  I have a couple of question about
the solution and a general question though.

In the constructor you have elems initialized with:
elems (r*c, val)
How does that work with templates?  I assume that the compiler treats it as
vector<r*c, val) which in VC++ would use:
explicit vector(size_type n, const T& v = T(), const A& al = A());
In VC++ 4.x you would need to indicate the allocator class for A however.

OK, so I just answered my own question, but the second is still a mystery
for me.

Is vector a typename?  is vector<int> a typename?  I still don't get why I
can't do vector< vector<int> > multidim_array_of_int;

--Pete
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]