Need help allocatig memory for vectorized 2D array

[Mike Pliam]

I want to be able to dynamically allocate and index an array like the following: vv2d[1][2].x and vv2d[1][2].y. In order to accomplish that I have chosen to use a std::vector of a std::vector of a 2D point class.

/// Here is my templated version of a 2d point class which I have adopted from
/// one by Alexander Chernosvitov, Function Graphics, 2001 (see ogview.h)
/// http://www.codeguru.com/cpp/g-m/opengl/article.php/c5581/Function-graphics-in-3D.htm
template <typename T>
class CPoint2D
{
public:
	T x, y;
	CPoint2D () { x=y=0; }
	CPoint2D (T c1, T c2)
	{
		x = c1;		y = c2;
	}
	CPoint2D& operator=(const CPoint2D& pt)
	{
		x = pt.x;	y = pt.y;
		return *this;
	}
	CPoint2D (const CPoint2D& pt)
	{
		*this = pt;
	}
};

I have attempted to use this class as follows:

	typedef vector<CPoint2D<double>> V2D;
	vector<V2D> vv2d;

	vv2d.resize(2);		// there will be two vectorized sets of x,y
	vv2d[0].resize(3);	// each set will contain 3 members

However, when I try to assign values to what I believed to be a suitably allocated vectorized 2D point set, I am unable to do so as a vector boundary error invariably occurs.

	// here's the first set
	vv2d[0][0].x = 0.234;  vv2d[0][0].y = 0.345;
	vv2d[0][1].x = 0.321;  vv2d[0][1].y = 0.432;
	vv2d[0][2].x = 0.111;  vv2d[0][2].y = 0.222;

	// here's the second set
	vv2d[1][0].x = 0.234;  vv2d[1][0].y = 0.345;  // problem here
	vv2d[1][1].x = 0.321;  vv2d[1][1].y = 0.432;
	vv2d[1][2].x = 0.111;  vv2d[1][2].y = 0.222;

Boundary violation occurs as soon as vv2d[1][0].x is encountered. I believe the problem is my inability to dynamically allocate the size of the (primary) typedef vector. However, eliminating the typedef for the following does not change the result. Further examination shows the vv2d[1][0] size and capacity to be 0.

	vector<vector<CPoint2D<double>>> vv2d;
	vv2d.resize(3);
	vv2d[0].resize(3);

What am I missing here? Any help greatly appreciated.

[Philip Nicoletti]

You have :

vv2d[0].resize(3);	// each set will contain 3 members

only the first set is resized. Either explicitly resize both vv2d[0] and vv2d[1] or

vv2d.resize( 2 , vector<CPoint2D<double>>(3) );

Note: this does not result in an array with contiguous memory. This could cause issues when trying to interface with C routines.

[Mike Pliam]

Thanks Philip. That seems to solve the problem.

Note: this does not result in an array with contiguous memory. This could cause issues when trying to interface with C routines.

I have heard this comment before regarding C arrays. However, if this algorithm allows for accessing values by index, that's really all that I would need. Specifically, what sort of C (or C++) routines represent potential problems?

[Philip Nicoletti]

The comment in your code mentioned opengl. So pretty much any function that take data with more than one dimension.

Some examples:

1) gluBuild2DMipmaps

2) The ctrlpoints data in the following example:

http://stackoverflow.com/questions/1...-nurbs-surface

[Mike Pliam]

There seems to be some differing opinions on whether or not std::vector stores elements in contiguous memory. I found this interesting post.

http://stackoverflow.com/questions/2...ays-contiguous

The C++03 standard added wording to make it clear that vector elements must be contiguous.

C++03 23.2.4 Paragraph 1 contains the following language which is not in the C++98 standard document:


The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] +
n for all 0 <= n < v.size().

Herb Sutter talks about this change in one of his blog entries, Cringe not: Vectors are guaranteed to be contiguous:


... contiguity is in fact part of the vector abstraction. It’s so important, in fact, that when it was discovered that the C++98 standard didn’t completely guarantee contiguity, the C++03 standard was amended to explicitly add the guarantee.

So at least for implementations after 2003, std:vector contiguous memory storage should be guaranteed. What's your opinion?

[2kaud]

The memory for a vector is contiguous. However in your example you have a vector of vectors. So whilst the memory for each of the individual vectors is contiguous, this is not necessarily true - and can't be assumed - across them all.

[Mike Pliam]

I wonder how one could test for integrity of contiguousness of memory allocation for a given object?

[2kaud]

If you need contiguous memory then it all needs to be allocated with just one call to the memory manager - multiple calls to the memory manager can never guarantee contiguous memory. So in the case of a multi-dimensional array then the linear memory requirement is calculated when the array is initialised and the memory referenced for a particular set of indexes is calculated for each access. In this case if the size of the array changes during the program from its initial size then new contiguous memory needs to be allocated, the contents of the previous copied to the new and the old released. Any existing iterators would become invalid.

[2kaud]

I wonder how one could test for integrity of contiguousness of memory allocation for a given object?

The c++ standard states whether for a given container the memory will be contiguous or not (eg vector yes, list no). If an object is composed of more than one container (or from multiple memory allocations) and you test the object for memory contiguousness and you find it's not and you want it to be - what are going to do??

[OReubens]

a vector of vectors is NOT a 2D array

if you want a 2D array, then you can 'sort of' simulate this with a vector of vectors, but it has a number of issues that may or may not be relevant to you.
One of the issues morem important issues is that you may be incurring a huge performance hit without realising it depending on your code, compiler and compiler switches.

If dynamic 2D arrays are an important part of your application, you need to create your own 2D array class, and you NEED to get rid of the idea that you can access the array like you have been accessing your 2D 'fixed size'.
so accessing via a double operator[] as in a[x][y] is a bad idea. (it's the underlying problem of the vector of vectors).
a single operator() with 2 parameters as in a(x,y) is the way to go. (yes, it may "look weird")

see: http://isocpp.org/wiki/faq/operator-...x-subscript-op and the 2 subtopics following that one to understand the motivation behind that.

[OReubens]

for a "simple" approach to a 2D class, here's a concept, you'll need to fill in some the blanks...

template <typename T>   // todo: may need allocator
class twodee
{
public:
        twodee() : xdim(0),ydim(0) {}
        twodee(int x, int y) { setsize(x,y); }

        void setsize(int x, int y)
        {
               data.resize(x*y);
               xdim=x;
               ydim=y;
        }
       void resize(int x, int y)  
      {
          std::vector<T> copy(data); // make copy of old vector
          int copyxdim(xdim); // make copy of old x dimension
          int copyydim(ydim); // make copy of old y dimension
          setsize(x,y);
          // todo copy items from data over into tmp, if x or y is now larger, initialise the new items.


         // a bit more work (but more efficient) would be to do this with creating a new vector sizing it, copying content
         //  then calling vector::swap()
      }
    // todo: access may want to add range checks in these
      const T& at(int x, int y) const { return data[y*xdim+x]; }
      T& at(int x, int y) { return data[y*xdim+x]; }
      const T& operator()(int x,int y) const { return data[y*xdim+x]; }
      T& operator()(int x,int y) { return data[y*xdim+x]; }

      // you prob want helper functions like getsize, assignment operator, copy constructor, swap, empty etc.
      // There may be a need for iterators that iterate over the entire 2D array

private
       std::vector<T> data;
       int xdim, ydim;
};

[2kaud]

so accessing via a double operator[] as in a[x][y] is a bad idea.

Not only is accessing via multiple [] a bad idea, it's also non-trivial to implement for contiguous memory!

Unless you absolutely need the multiple [] to be compatible with existing code IMO I would strongly suggest you use the () method of access.

[Philip Nicoletti]

Just a small point:

return data[y*xdim+x];

I believe that is the FORTRAN ordering.

[monarch_dodra]

Yeah, the take home point here is that "[][]" is a bad idea. "(x, y)" (or "get(x ,y)" if you don't like operator()) is the way to go.

An argument in favour of "[]" is that it could return an actual row object, with row-specific begin/end and whatever. But even then, you'd ideally want it called "row(x)", so you can mirror it with "column()".

[Pavuluri]

memory allocation and deallocationhttp://www.cpptutorials.com/2014/11/...ns-malloc.html