dynamic array or STL vector

[Vasileios Zografos]

Hello,

I have a function that generates some values (e.g. vertices in 2d space)
the number of which I dont know. So, it could generate 20 vertices, 100
vertices, or even 1 vertex.

void generateVals()
{
.....
//generate some values
....
}

What I want to do is store these values as they are generated.

I thought of using something like int *data = int[num_of_vertices] but I
will not know the num_of_vertices until after the generateVals()
function has finished, and when the function has finished I wont be able
to get/store the values any more.

I thought of using a dynamic linked list (such as the STL vector) and
after the generateVals function has finished to copy the values back to
the dynamic array *data (I need this in order to pass the values into
another function that uses int * arrays as input).


Anyways, my question is. Is there a more elegant way to do this by using
a dynamic array? or a linked list is the only way?

Thank you
Vasileios

P.S.
Some people might say that this posting is a bit of topic and should be
sent to a programming newsgroup, but I am looking for an answer specific
to c++ , so if you please know something do tell me.

 

[Rob Williscroft]

Vasileios Zografos wrote in
[snip]

I thought of using something like int *data = int[num_of_vertices] but
I will not know the num_of_vertices until after the generateVals()
function has finished, and when the function has finished I wont be
able to get/store the values any more.

I thought of using a dynamic linked list (such as the STL vector) and

STL vector or I like to call it std::vector is not a linked list.
Its a kinda "dynamic array".

[snip]

Anyways, my question is. Is there a more elegant way to do this by
using a dynamic array? or a linked list is the only way?
[snip]

... so if you please know something do tell me.

std::vector (post a fixed standard and all known implementations)
stores it elements in a contiguous array.

HTH.

Rob.

 

[Victor Bazarov]

I have a function that generates some values (e.g. vertices in 2d space)
the number of which I dont know. So, it could generate 20 vertices, 100
vertices, or even 1 vertex.

void generateVals()
{
....
//generate some values
...
}

What I want to do is store these values as they are generated.

I thought of using something like int *data = int[num_of_vertices] but I
will not know the num_of_vertices until after the generateVals()
function has finished, and when the function has finished I wont be able
to get/store the values any more.

I thought of using a dynamic linked list (such as the STL vector) and
after the generateVals function has finished to copy the values back to
the dynamic array *data (I need this in order to pass the values into
another function that uses int * arrays as input).


Anyways, my question is. Is there a more elegant way to do this by using
a dynamic array? or a linked list is the only way?

The usual approach in the case where you need some storage but
are not sure of its size ahead of time (like when reading a file
or other stream), a linked list (singly, often) is quite enough.
You can always convert (copy) it into some other kind of storage
with different traits (like into a vector or an array).

AFAICT, such way is "elegant" enough. When time comes to concern
yourself with performance, you may choose to use 'std::vector'
instead of 'std::list' even for the first, growing, storage. It
is relatively efficient in resizing when necessary, and later when
you need to pass the array to your next function, you just pass
the address of the first element. Just don't try to optimise it
before you are really sure you need it optimised. Make it work
first.

Victor

 

[lilburne]

Anyways, my question is. Is there a more elegant way to do this by using
a dynamic array? or a linked list is the only way?

std::vector is normally implemented as a dynamic array. If
you are going to be using no more than a few 100 elements
then a dynamic array is probably ok. Once you get into a few
1000 elements or more than a dynamic array (whether it is
std::vector or something else) is a poor choice. We use what
we call paged arrays. You can think of it in terms of

std::vector< std::vector<T>* >

where the std::vectorT>* are fixed size pages containing N
elements. As the container fills up only the vector of
vector pointers has to resize.

But if you really need to deal with raw arrays of ints you
should be able to roll your own dynamic int array fairly easily.

 

[Jon Bell]

I have a function that generates some values (e.g. vertices in 2d space)
the number of which I dont know. So, it could generate 20 vertices, 100
vertices, or even 1 vertex.

void generateVals()
{
....
//generate some values
...
}

What I want to do is store these values as they are generated.

I thought of using something like int *data = int[num_of_vertices] but I
will not know the num_of_vertices until after the generateVals()
function has finished, and when the function has finished I wont be able
to get/store the values any more.

I thought of using a dynamic linked list (such as the STL vector) and
after the generateVals function has finished to copy the values back to
the dynamic array *data (I need this in order to pass the values into
another function that uses int * arrays as input).

Use a std::vector. It's not a linked list (there's a separate std::list
class for that), but rather a dynamic array wrapped up in a class. If you
start with a vector of zero size and append new items with push_back(),
the vector will expand as necessary in a reasonably efficient way. When
you're done, you can easily get a pointer to the beginning of the data and
pass it to the other function.

void generateVals()
{
vector<int> Values;
while (whatever)
{
int nextValue;
// ...generate nextValue here...
Values.push_back(Value);
}
FunctionThatUsesTheValues (&Values[0]);
}

If you want to call the other function outside of generateVals, the most
effective way to do it is probably to declare the vector in the calling
function and then pass it to generateVals() by reference:

void generateVals (vector<int>& Values);
{
while (whatever)
{
int nextValue;
// ...generate nextValue here...
Values.push_back(Value);
}
}

int main ()
{
// ...whatever other stuff the program does...
vector<int> Values;
generateVals (Values);
FunctionThatUsesTheValues (&Values[0]);
// ...carry on...
}

 

[Peter Koch Larsen]

std::vector is normally implemented as a dynamic array. If
you are going to be using no more than a few 100 elements
then a dynamic array is probably ok. Once you get into a few
1000 elements or more than a dynamic array (whether it is
std::vector or something else) is a poor choice.
Why??

We use what
we call paged arrays. You can think of it in terms of

std::vector< std::vector<T>* >

where the std::vectorT>* are fixed size pages containing N
elements. As the container fills up only the vector of
vector pointers has to resize.

Is this resize stuff necesarrily a problem?

But if you really need to deal with raw arrays of ints you
should be able to roll your own dynamic int array fairly easily.

You're sure? And why should they be better than std::vector?
Kind regards
Peter

 

[Andrew Koenig]

std::vector is normally implemented as a dynamic array. If

you are going to be using no more than a few 100 elements
then a dynamic array is probably ok. Once you get into a few
1000 elements or more than a dynamic array (whether it is
std::vector or something else) is a poor choice.

Why? The amortized time needed to reallocate even a very large vector is at
worst proportional to the time needed to fill the vector.

We use what
we call paged arrays. You can think of it in terms of

std::vector< std::vector<T>* >

where the std::vectorT>* are fixed size pages containing N
elements. As the container fills up only the vector of
vector pointers has to resize.

If you need such a data structure, why not use std::deque?