From -2963346686456329705
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: f78e5,e191db47f821e732
X-Google-Attributes: gidf78e5,public
From: Kresimir Fresl <fresl@grad.hr>
Subject: Re: multidimensional array using stl vector
Date: 1997/07/07
Message-ID: <33C0A275.5113F5C6@master.grad.hr>#1/1
X-Deja-AN: 255297106
References: <Pine.GSO.3.96.970630204810.3711A-100000@lise.physik.TU-Berlin.DE> <33B8B20B.7CC8793A@master.grad.hr> <01bc86ed$78217140$ef0810ac@jubilex>
X-Original-Date: Mon, 07 Jul 1997 10:01:57 +0200
Organization: Faculty of Civil Engineering, Zagreb, Croatia
X-Auth: PGPMoose V1.1 PGP comp.std.c++ iQBVAwUBM8Eq/Ey4NqrwXLNJAQGeNwH/Yjuzz+cdzV5StBJfKlvZ/xKaXptMAR7a JaacWAfhrpTdh2UWn8Rlu+gaMP3EWB8LtC/8yaI1NytdUmGdORDlPg== =16p8
Newsgroups: comp.std.c++
Content-Disposition: inline; filename="a2d-2.1"
Originator: austern@isolde.mti.sgi.com


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 
]