pointer to an array of pointers - allocate

[Christopher]

I need to have an array of pointers to something. I do not know how
many I will have until runtime. How do you allocate?

Is something like this simple array of int pointers example correct?


class A
{
public:

A()
{
// I know I need 3 pointers to integers here
m_integers = new int * [3];

m_integers[0] = new int(1);
m_integers[1] = new int(2);
m_integers[2] = new int(3);
}

private:

int ** m_integers
};


It needs to be in the form: type **, because the API I am using asks
for it in that way.

 

[Thomas J. Gritzan]

I need to have an array of pointers to something. I do not know how
many I will have until runtime. How do you allocate?
std::vector

Is something like this simple array of int pointers example correct?

Correct. But why bother with allocation?

class A
{

[...example using new int*[]...]

It needs to be in the form: type **, because the API I am using asks
for it in that way.

#include <vector>

void some_function(int**);

class A
{
A()
{
// append with push_back
for (int i = 1; i < 4; ++i) {
m_integers.push_back( new int(i) );
}

// pass to C API
int** pint = &m_integers[0];
some_function(pint);
}

// add copy, assignment and destructor
// remember to delete the ints

private:
std::vector<int*> m_integers;
};

 

[Kai-Uwe Bux]

I need to have an array of pointers to something. I do not know how
many I will have until runtime. How do you allocate?

You don't. Use a vector<int*>.

[rearranged:]

It needs to be in the form: type **, because the API I am using asks
for it in that way.

No it doesn't need to be int**. With

vector<int*> the_ptr_vector;

you can pass &the_ptr_vector[0]. This will be of type int** and is
guaranteed to work since std::vector is guaranteed to be contiguous.

Is something like this simple array of int pointers example correct?


class A
{
public:

A()
{
// I know I need 3 pointers to integers here
m_integers = new int * [3];

m_integers[0] = new int(1);
m_integers[1] = new int(2);
m_integers[2] = new int(3);
}

private:

int ** m_integers
};

It is correct (in that it will do the expected if nothing bad happens), but
not exception safe (i.e., it will do bad things if something bad happens
elsewhere): if one of the the lines
new int (...)
throws, then memory will leak.

It is actually a little difficult to manage containers of pointers so that
nothing bad can happen. I think, the following will do, but I did not think
through all the possible mishaps.

#include <vector>

class auto_ptr_vector : private std::vector<int*> {

typedef std::vector<int*> base;

public:

using base:perator[];
using base::at;
using base::begin;
using base::end;

auto_ptr_vector ( base::size_type n )
: base ( n, 0 )
{}

~auto_ptr_vector ( void ) {
for ( base::size_type n = 0; n < this->size(); ++n ) {
delete (*this)[n];
}
}

};

class A {
public:

A()
: m_integers ( 3 )
{
m_integers[0] = new int(1);
m_integers[1] = new int(2);
m_integers[2] = new int(3);
}

private:

auto_ptr_vector m_integers;

};


Again, you can use the API via &m_integers[0].


Best

Kai-Uwe Bux

 

[Michael Mol]

I need to have an array of pointers to something. I do not know how
many I will have until runtime. How do you allocate?

You don't. Use a vector<int*>.

[rearranged:]

It needs to be in the form: type **, because the API I am using asks
for it in that way.

No it doesn't need to be int**. With

  vector<int*> the_ptr_vector;

you can pass &the_ptr_vector[0]. This will be of type int** and is
guaranteed to work since std::vector is guaranteed to be contiguous.

First, it was my understanding that std::vector was *not* guaranteed
to be contiguous, though everyone who I've read make this assertion
went on to say that they hadn't seen an implementation that wasn't.
Checking SGI's public spec for vector (I don't have a better source),
it's only given requirements that it satisfy the requirements of
Random Access Container and Back Insertion Sequence, neither of which
require contiguity.

Second, it was also my understanding that should a vector need to
grow, it will attempt to realloc for a larger block of memory at the
same base address, but will settle for a new base address if a block
of suitable size is not available at the current base. If a vector
thus rebases itself, all pointers to elements within the vector would
be invalidated; Your int** pointer to the vector element wouldn't be
updated to reflect the location of the new int* element.

While the contiguity issue appears to be moot in light of existing
implementations, the rebasing problem makes storing off pointers to
elements risky behavior, unless you can guarantee that the vector
won't grow to the point of rebase or shrink to the point removing the
element before you (and everyone else) are done using that pointer.

 

[Kai-Uwe Bux]

I need to have an array of pointers to something. I do not know how
many I will have until runtime. How do you allocate?

You don't. Use a vector<int*>.

[rearranged:]

It needs to be in the form: type **, because the API I am using asks
for it in that way.

No it doesn't need to be int**. With

vector<int*> the_ptr_vector;

you can pass &the_ptr_vector[0]. This will be of type int** and is
guaranteed to work since std::vector is guaranteed to be contiguous.

First, it was my understanding that std::vector was *not* guaranteed
to be contiguous, though everyone who I've read make this assertion
went on to say that they hadn't seen an implementation that wasn't.
Checking SGI's public spec for vector (I don't have a better source),
it's only given requirements that it satisfy the requirements of
Random Access Container and Back Insertion Sequence, neither of which
require contiguity.

Your understanding is wrong as of 2003 and when the standard was changed.
Please see [23.2.4/1]:

... 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().

Second, it was also my understanding that should a vector need to
grow, it will attempt to realloc for a larger block of memory at the
same base address, but will settle for a new base address if a block
of suitable size is not available at the current base.
Correct.

If a vector
thus rebases itself, all pointers to elements within the vector would
be invalidated; Your int** pointer to the vector element wouldn't be
updated to reflect the location of the new int* element.

Let's be more precise here. Suppose you have an API

void foo ( int ** the_array );

and you call it as

foo( &m_integers[0] );

which I suggested, where m_integers is a private member of class A of type
vector<int*>. Then, there is no danger that foo will cause a reallocation
of that private member. The int** that is passed will _always_ point to the
first int* in the vector regardless of how many reallocations have taken
place.

While the contiguity issue appears to be moot in light of existing
implementations, the rebasing problem makes storing off pointers to
elements risky behavior, unless you can guarantee that the vector
won't grow to the point of rebase or shrink to the point removing the
element before you (and everyone else) are done using that pointer.

I did not recommend _storing_ a pointer into the vector at some other place.
You do have a point in multithreaded applications, though. In that case,
however, mutexes would be needed anyway.

In any case, if int** is a viable implementation technique, then so is
vector<int*> and _you_ are in control of when reallocation happens.


Also: in the code you snipped, I used private inheritance and did not make
any method of vector available that would possibly cause reallocation. The
reason is that reallocation causes a much more serious concern, namely
exception safety. The vector may fail to allocate the needed memory and
throw an exception.


Best

Kai-Uwe Bux

 

[Zachary Turner]

I need to have an array of pointers to something. I do not know how
many I will have until runtime. How do you allocate?

You don't. Use a vector<int*>.

[rearranged:]

It needs to be in the form: type **, because the API I am using asks
for it in that way.

No it doesn't need to be int**. With

  vector<int*> the_ptr_vector;

you can pass &the_ptr_vector[0]. This will be of type int** and is
guaranteed to work since std::vector is guaranteed to be contiguous.

Is something like this simple array of int pointers example correct?

class A
{
   public:

   A()
   {
         // I know I need 3 pointers to integers here
         m_integers = new int * [3];

         m_integers[0] = new int(1);
         m_integers[1] = new int(2);
         m_integers[2] = new int(3);
   }

   private:

   int ** m_integers
};

It is correct (in that it will do the expected if nothing bad happens), but
not exception safe (i.e., it will do bad things if something bad happens
elsewhere): if one of the the lines
    new int (...)
throws, then memory will leak.

It is actually a little difficult to manage containers of pointers so that
nothing bad can happen. I think, the following will do, but I did not think
through all the possible mishaps.

#include <vector>

class auto_ptr_vector : private std::vector<int*> {

  typedef std::vector<int*> base;

public:

  using base:perator[];
  using base::at;
  using base::begin;
  using base::end;

  auto_ptr_vector ( base::size_type n )
    : base ( n, 0 )
  {}

  ~auto_ptr_vector ( void ) {
    for ( base::size_type n = 0; n < this->size(); ++n ) {
      delete (*this)[n];
    }
  }

};

class A {
public:

  A()
    : m_integers ( 3 )
  {
    m_integers[0] = new int(1);
    m_integers[1] = new int(2);
    m_integers[2] = new int(3);
  }

private:

  auto_ptr_vector m_integers;

};

Again, you can use the API via &m_integers[0].

Best

Kai-Uwe Bux  

This is really a terrible idea, why break the rule? The rule, of
course being, NEVER USE AN AUTO_PTR IN A CONTAINER. While it might be
possible to get it to work under really limited circumstances, do you
really want to have to remember what those circumstances are? And
what if later you realize you need to be able to use the push_back
method, and then forget that it's going to screw up the auto_ptr's due
to reallocation? What happens if you called std::swap() on two
iterators from auto_ptr_vector above? What if you use the above
auto_ptr_vector in an algorithm such as sort? Can you really
guarantee that not only will reallocation never occur, but an element
is never even -copied-?

If the "loop-through-and-delete-container-pointers-in-destructor" is
not good enough with a container of raw pointers, then download boost,
and use boost::shared_ptr<>.

 

[Michael Mol]

Christopher wrote:
I need to have an array of pointers to something. I do not know how
many I will have until runtime. How do you allocate?
You don't. Use a vector<int*>.
[rearranged:]
It needs to be in the form: type **, because the API I am using asks
for it in that way.
No it doesn't need to be int**. With
vector<int*> the_ptr_vector;
you can pass &the_ptr_vector[0]. This will be of type int** and is
guaranteed to work since std::vector is guaranteed to be contiguous.

First, it was my understanding that std::vector was *not* guaranteed
to be contiguous, though everyone who I've read make this assertion
went on to say that they hadn't seen an implementation that wasn't.
Checking SGI's public spec for vector (I don't have a better source),
it's only given requirements that it satisfy the requirements of
Random Access Container and Back Insertion Sequence, neither of which
require contiguity.

Your understanding is wrong as of 2003 and when the standard was changed.
Please see [23.2.4/1]:

  ... 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().

I suppose I need to spring for a copy of the standard.
Recommendations?

Second, it was also my understanding that should a vector need to
grow, it will attempt to realloc for a larger block of memory at the
same base address, but will settle for a new base address if a block
of suitable size is not available at the current base.
Correct.

If a vector
thus rebases itself, all pointers to elements within the vector would
be invalidated; Your int** pointer to the vector element wouldn't be
updated to reflect the location of the new int* element.

Let's be more precise here. Suppose you have an API

  void foo ( int ** the_array );

and you call it as

  foo( &m_integers[0] );

which I suggested, where m_integers is a private member of class A of type
vector<int*>. Then, there is no danger that foo will cause a reallocation
of that private member. The int** that is passed will _always_ point to the
first int* in the vector regardless of how many reallocations have taken
place.

But in the case of a rebase, m_integers[0] will no longer be located
at the same point in memory, so if the implementation of foo() saved
the pointer for later reference, the pointer it saved will no longer
be valid. Hopefully, the API documentation mentions any such
caveats. The OP didn't specify.

I did not recommend _storing_ a pointer into the vector at some other place.
You do have a point in multithreaded applications, though. In that case,
however, mutexes would be needed anyway.

No, you didn't, but the implementation of the API the OP is using is
left unclear, so it's something that should be guarded against, IMHO.

In any case, if int** is a viable implementation technique, then so is
vector<int*> and _you_ are in control of when reallocation happens.

Also: in the code you snipped, I used private inheritance and did not make
any method of vector available that would possibly cause reallocation. The
reason is that reallocation causes a much more serious concern, namely
exception safety. The vector may fail to allocate the needed memory and
throw an exception.

Granted, but I wasn't sure if the OP was indicating that the number
may change at runtime, or if it would set at some early point and
remain constant for the life of the class and interaction with the
API.

 

[Kai-Uwe Bux]

I need to have an array of pointers to something. I do not know how
many I will have until runtime. How do you allocate?

You don't. Use a vector<int*>.

[rearranged:]

It needs to be in the form: type **, because the API I am using asks
for it in that way.

No it doesn't need to be int**. With

vector<int*> the_ptr_vector;

you can pass &the_ptr_vector[0]. This will be of type int** and is
guaranteed to work since std::vector is guaranteed to be contiguous.

Is something like this simple array of int pointers example correct?

class A
{
public:

A()
{
// I know I need 3 pointers to integers here
m_integers = new int * [3];

m_integers[0] = new int(1);
m_integers[1] = new int(2);
m_integers[2] = new int(3);
}

private:

int ** m_integers
};

It is correct (in that it will do the expected if nothing bad happens),
but not exception safe (i.e., it will do bad things if something bad
happens elsewhere): if one of the the lines
new int (...)
throws, then memory will leak.

It is actually a little difficult to manage containers of pointers so
that nothing bad can happen. I think, the following will do, but I did
not think through all the possible mishaps.

#include <vector>

class auto_ptr_vector : private std::vector<int*> {

typedef std::vector<int*> base;

public:

using base:perator[];
using base::at;
using base::begin;
using base::end;

auto_ptr_vector ( base::size_type n )
: base ( n, 0 )
{}

~auto_ptr_vector ( void ) {
for ( base::size_type n = 0; n < this->size(); ++n ) {
delete (*this)[n];
}
}

};

class A {
public:

A()
: m_integers ( 3 )
{
m_integers[0] = new int(1);
m_integers[1] = new int(2);
m_integers[2] = new int(3);
}

private:

auto_ptr_vector m_integers;

};

Again, you can use the API via &m_integers[0].

Best

Kai-Uwe Bux

This is really a terrible idea, why break the rule? The rule, of
course being, NEVER USE AN AUTO_PTR IN A CONTAINER.

[snip]

I didn't use auto_ptr in a container. Please read the code more carefully,
in particular if you feel like using all caps.


Best

Kai-Uwe Bux

 

[Kai-Uwe Bux]

Christopher wrote:
I need to have an array of pointers to something. I do not know how
many I will have until runtime. How do you allocate?

You don't. Use a vector<int*>.

[rearranged:]

It needs to be in the form: type **, because the API I am using asks
for it in that way.

No it doesn't need to be int**. With

vector<int*> the_ptr_vector;

you can pass &the_ptr_vector[0]. This will be of type int** and is
guaranteed to work since std::vector is guaranteed to be contiguous.

[snip about vector being contiguous]

I suppose I need to spring for a copy of the standard.
Recommendations?

I find the pdf file quite usefull. I purchased it from the ANSI store
website. It was pretty cheap ($18) back then.

Second, it was also my understanding that should a vector need to
grow, it will attempt to realloc for a larger block of memory at the
same base address, but will settle for a new base address if a block
of suitable size is not available at the current base.
Correct.

If a vector
thus rebases itself, all pointers to elements within the vector would
be invalidated; Your int** pointer to the vector element wouldn't be
updated to reflect the location of the new int* element.

Let's be more precise here. Suppose you have an API

void foo ( int ** the_array );

and you call it as

foo( &m_integers[0] );

which I suggested, where m_integers is a private member of class A of
type vector<int*>. Then, there is no danger that foo will cause a
reallocation of that private member. The int** that is passed will
_always_ point to the first int* in the vector regardless of how many
reallocations have taken place.

But in the case of a rebase, m_integers[0] will no longer be located
at the same point in memory, so if the implementation of foo() saved
the pointer for later reference, the pointer it saved will no longer
be valid. Hopefully, the API documentation mentions any such
caveats. The OP didn't specify.

Ah, true.

[snip]

Granted, but I wasn't sure if the OP was indicating that the number
may change at runtime, or if it would set at some early point and
remain constant for the life of the class and interaction with the
API.

Well, if the length of the array can change, then reallocation might be
necessary whether vector<int*> or int** is chosen as the base for the
implementation. In either case, the API better not store (and use) the old
value.

BTW: From the code sample, I thought that the OP does not need reallocation,
but also does not know the size at compile time. The problem of dealing
with reallocation in an exception safe way is much harder, I think.


Best

Kai-Uwe Bux

 

[Michael Mol]

I find the pdf file quite usefull. I purchased it from the ANSI store
website. It was pretty cheap ($18) back then.

It's currently listed at $363. Maybe I can get the company to pay for
it...

Well, if the length of the array can change, then reallocation might be
necessary whether vector<int*> or int** is chosen as the base for the
implementation. In either case, the API better not store (and use) the old
value.

This is true, and something I hadn't considered. If the API stores
the values given to it, and if the array size grows at run time, then
perhaps a non-contiguous container would be more appropriate. If
elements are removed, though, there's still the problem of
deregistering the pointer with the API.

BTW: From the code sample, I thought that the OP does not need reallocation,
but also does not know the size at compile time. The problem of dealing
with reallocation in an exception safe way is much harder, I think.

Probably true.

 

[Kai-Uwe Bux]

It's currently listed at $363.

Bummer! Are you sure, you are not looking at the dead-tree version?

Maybe I can get the company to pay for it...

I wish you the best of luck. With that price, you (or your company) might
want to wait until C++0X becomes available. (should be soon right


[snip]


Best

Kai-Uwe Bux

 

[Kai-Uwe Bux]

Bummer! Are you sure, you are not looking at the dead-tree version?

Well, I checked, and indeed it is a pdf-version.

However, there is an ISO/IEC version for $363 and an INCITS/ISO/IEC version
for $30. I do not understand the difference in price as both seem to be the
same document "ISO/IEC 14882 Second edition 2003-10-15". The link for the
cheaper one is:

http://webstore.ansi.org/RecordDetail.aspx?sku=INCITS/ISO/IEC+14882-2003


Best

Kai-Uwe Bux

 

[Fred Zwarts]

Christopher wrote:

Second, it was also my understanding that should a vector need to
grow, it will attempt to realloc for a larger block of memory at the
same base address, but will settle for a new base address if a block
of suitable size is not available at the current base. If a vector
thus rebases itself, all pointers to elements within the vector would
be invalidated; Your int** pointer to the vector element wouldn't be
updated to reflect the location of the new int* element.

Even when allocating memory by other means there is a risk that
a rebase your block of memory is needed if later on more space is needed.
For vectors, rebasing can be prevented if the maximum possible number
of elements is known, by reserving the necessary capacity ahead.
Changing the size of the vector within the capacity will not cause a rebase.

 

[James Kanze]

Well, I checked, and indeed it is a pdf-version.

However, there is an ISO/IEC version for $363 and an
INCITS/ISO/IEC version for $30. I do not understand the
difference in price as both seem to be the same document
"ISO/IEC 14882 Second edition 2003-10-15".

I'm just guessing, but one might be the US (ANSI) standard, and
the other the international (ISO) one. In which case, there may
be a difference on the cover page. And the difference that ISO
determines the price of the international standard, but ANSI
determines it for the US one.

 

[Thomas J. Gritzan]

It is actually a little difficult to manage containers of pointers so that
nothing bad can happen. I think, the following will do, but I did not think
through all the possible mishaps.

#include <vector>

class auto_ptr_vector : private std::vector<int*> {

typedef std::vector<int*> base;

public:

using base:perator[];
using base::at;
using base::begin;
using base::end;

auto_ptr_vector ( base::size_type n )
: base ( n, 0 )
{}

~auto_ptr_vector ( void ) {
for ( base::size_type n = 0; n < this->size(); ++n ) {
delete (*this)[n];
}
}

};

Forbid copy & assignment (by making the functions private or derive from
a class like boost::noncopyable). When you copy the class, the pointers
will be deleted twice.

An exception safe resize (maybe using copy&swap) would be nice to have, too.

 

[Kai-Uwe Bux]

It is actually a little difficult to manage containers of pointers so
that nothing bad can happen. I think, the following will do, but I did
not think through all the possible mishaps.

#include <vector>

class auto_ptr_vector : private std::vector<int*> {

typedef std::vector<int*> base;

public:

using base:perator[];
using base::at;
using base::begin;
using base::end;

auto_ptr_vector ( base::size_type n )
: base ( n, 0 )
{}

~auto_ptr_vector ( void ) {
for ( base::size_type n = 0; n < this->size(); ++n ) {
delete (*this)[n];
}
}

};

Forbid copy & assignment (by making the functions private or derive from
a class like boost::noncopyable). When you copy the class, the pointers
will be deleted twice.

Good point.

An exception safe resize (maybe using copy&swap) would be nice to have,
too.

I thought about that, but I think then one could go all the way and support
more or less all vector operations (like, insert, erase, push_back, etc.)


Best

Kai-Uwe Bux