memory management and containers

[slurper]

when i do this

vector < vector<int> > p;

later in the code i do things like this:
vector<int> x,y,z;

p.push_back(x);
p.push_back(y);
p.push_back(z);
p[1].push_back(56);

can i do this without problems?
how will C++ allocate memory for these structures? (note that the nr of
elements in the vectors are not known at compile-time)

is a declaration like "vector < vector<int>* > p" more efficient??

 

[Victor Bazarov]

when i do this

vector < vector<int> > p;

later in the code i do things like this:
vector<int> x,y,z;

p.push_back(x);
p.push_back(y);
p.push_back(z);
p[1].push_back(56);

can i do this without problems?

Can you? I mean, you seem to be doing it just fine. Or did I get
it wrong and you do experience some problems? If so, what kind?

how will C++ allocate memory for these structures? (note that the nr of
elements in the vectors are not known at compile-time)

Why does it matter? It will allocate it somehow. If you really need
to know the inner workings of 'vector' template, use the source. It

is a declaration like "vector < vector<int>* > p" more efficient??

What do you mean by "more efficient"?

V

 

[John Harrison]

when i do this

vector < vector<int> > p;

later in the code i do things like this:
vector<int> x,y,z;

p.push_back(x);
p.push_back(y);
p.push_back(z);
p[1].push_back(56);

can i do this without problems?

Yes. It would be simpler to write this

vector < vector<int> > p(3);
p[1].push_back(56);

But both pieces of code are correct.

how will C++ allocate memory for these structures? (note that the nr of
elements in the vectors are not known at compile-time)

In the usual way that all vector memory allocations are done, by using the
allocator object in the vector.

is a declaration like "vector < vector<int>* > p" more efficient??

Possibly, it depends on what you are going to do and how you are going to do
it.

I'm guessing that you are worried about potential inefficiencies of copying
large vectors. There is no such copying going on in the example code you
gave. But if this is a concern the answer is not to reintroduce pointers
because they lead to buggy, complicated (and sometimes inefficient) code. It
hard to give specific advice because I don't know exactly what you are
trying to do or what inefficiencies you have in mind, but I expect you can
to better than declare a vector of pointers.

john

 

[slurper]

when i do this

vector < vector<int> > p;

later in the code i do things like this:
vector<int> x,y,z;

p.push_back(x);
p.push_back(y);
p.push_back(z);
p[1].push_back(56);

can i do this without problems?

Can you? I mean, you seem to be doing it just fine. Or did I get
it wrong and you do experience some problems? If so, what kind?

how will C++ allocate memory for these structures? (note that the nr of
elements in the vectors are not known at compile-time)

Why does it matter? It will allocate it somehow. If you really need
to know the inner workings of 'vector' template, use the source. It

is a declaration like "vector < vector<int>* > p" more efficient??

What do you mean by "more efficient"?

tx for answers so far
i'm probably thinking too low-level (it's not that i have a problem, i just
want to know if i get the theory about c++ right)
what i want to say is: if i declare vector < vector <int> >; i get a vector
of vectors, but at run-time the different vectors in the vector change and
their number of elements change. this means that you can't use a contiguous
block of memory to fill with ints. C++ apparently has much more
sophisticated memory allocation schemes than was the case in C. in C, you
can't make an array grow. if you don't know how many elements you need to
store in an array, you dynamically ask for memory with malloc (which is a
contiguous block of memory). so if you need an array of array (both arrays
have variable elements in time), you need to implement this by asking for a
certain amount of memory which can hold as much pointers as needed. those
pointers point at other allocated blocks which can hold the elements in the
latter array. you can't just say in C that an array holds elements which
can dynamically grow or shrink, unless you use pointers. or do i get this
wrong? that's why i hesitated...

 

[Ron Natalie]

when i do this

vector < vector<int> > p;

later in the code i do things like this:
vector<int> x,y,z;

p.push_back(x);
p.push_back(y);
p.push_back(z);
p[1].push_back(56);

can i do this without problems?
how will C++ allocate memory for these structures? (note that the nr of
elements in the vectors are not known at compile-time)

Each argument to push_back is COPIED to a location in the vector. The
storage for the vector is allocated in a way to make the TIME requirements
for insertion amortize to linear time.

If you really aren't putting anything in x, y, and z PRIOR to pushing them
into the the vector p. There's really no point in even declaring them.

vector<vector<int> > p(3);

is a declaration like "vector < vector<int>* > p" more efficient??

Who knows, it depends what you are doing. However, in the case of using
pointers, you're going to have to manage them seperately.

 

[Victor Bazarov]

[...]
i'm probably thinking too low-level (it's not that i have a problem, i just
want to know if i get the theory about c++ right)

Try looking in "Inside The C++ Object Model" by Stanley Lippman.

what i want to say is: if i declare vector < vector <int> >; i get a vector
of vectors, but at run-time the different vectors in the vector change and
their number of elements change. this means that you can't use a contiguous
block of memory to fill with ints.

Yes, but (a) it has a contiguous block of memory filled by 'vector<int>'
objects and (b) each of them owns another contiguous block of memory
filled with 'int's.

C++ apparently has much more
sophisticated memory allocation schemes than was the case in C.

Not really. Underneath it boils down to the same bytes.

in C, you
can't make an array grow.

Neither can you in C++. But 'vector<int>' or 'vector<anything>' is not
an array. It pretends to be one, but it's not. It even has one inside,
but itself it is not an array.

if you don't know how many elements you need to
store in an array, you dynamically ask for memory with malloc (which is a
contiguous block of memory).

so if you need an array of array (both arrays
have variable elements in time), you need to implement this by asking for a
certain amount of memory which can hold as much pointers as needed.

There are different ways to implement dynamic multidimensional arrays.

those
pointers point at other allocated blocks which can hold the elements in the
latter array. you can't just say in C that an array holds elements which
can dynamically grow or shrink, unless you use pointers. or do i get this
wrong? that's why i hesitated...

Essentially you can do all what 'vector' does behind the scenes, in C. It
will be a bit involved, and you could spend some time writing it and
debugging it, but once you achieve the desired behaviour, you will have
something similar to C++ vector. That's what library implementers do.
They develop and debug the code inside <vector> and other places, which
you will later use. In fact, AIUI, most of the Standard C++ library is
implemented using straight C++.

V