Archived

This topic is now archived and is closed to further replies.

CProgrammer

dynamic arrays and loops

Recommended Posts

CProgrammer    303
What is usually done when one doesnt know the size of an array until the end of the loop, but one wants to insert data as the loop goes along? Go through the loop twice or reserve an amount of memory that one is shure not to exceed and erase the unnecessary memory later or what? -CProgrammer

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
std::vector<int> myArray;

while (inputTokens != TERMINATOR) {
myArray.push_back( ProcessToken(inputTokesn[i]));
i++;
}


std::vector<>.push_back will allocate memory as necessary.

This is the easy way, although may not be the most effecient in terms of processing time (std::vector may do multiple applciations in the above piece of code, which may be more expensive than performing two loops, for readability however, I would choose the code above).

Share this post


Link to post
Share on other sites
Fruny    1658
The standard vector class allocates a larger chunk (by how much depends on the implementation, half-again or twice as much is typical) and copies the data over.

The standard deque class may be implemented as a vector of arrays. When the deque need to grows, a new array is allocated and is appended to the index, without perturbating the other arrays (though the index itself may need to be expanded vector-style).

Tradeoff: discontiguous storage vs. necessary copy-over.

Share this post


Link to post
Share on other sites
Fruny    1658
An alternative would be to read into a deque and then copy the deque into a vector, which is easy.

Expanding on the AP's code:


std::deque<int> buffer;
std::vector<int> array;

while ( condition )
buffer.push_back( data );

array.reserve(buffer.size());
array.assign(buffer.begin(), buffer.end());


That way, you get contiguous storage at the cost of a single extra copy operation.

If you desire a C-style dynamic array as the final result, it is possible too.

#include <algorithm>

int* array = new int[buffer.size()];
std::copy(buffer.begin(), buffer.end(), array);


If you are reading from a stream, it's even simpler

#include <algorithm>
#include <iterator>
#include <fstream>

std::ifstream ifs("blah");
std::vector<int> array( std::istream_iterator<int>(ifs),
std::istream_iterator<int>() );


If you want low-level (e.g. binary, or character) IO, use istreambuf_iterator instead.

[edited by - Fruny on January 4, 2004 1:53:51 AM]

Share this post


Link to post
Share on other sites
smart_idiot    1298
What the AP said is good for C++. In C it gets pretty complicated. I use C a lot, and this was my solution:


somestruct *start = malloc(sizeof(somestruct)), *end = start, *allocated_end = start + 1;

// Add an element. . .


if(end == allocated_end)
{
somestruct *old = start;

if(!(start = realloc(old, sizeof *old * 2*(allocated_end - old)))
{
start = old;
// not enough memory. . .

return;
}

end = end - old + start;
allocated_end = 2*(allocated_end - old) + start;
}

*(end++) = something;


Probably why nobody uses C anymore.

Share this post


Link to post
Share on other sites
CProgrammer    303
But whats fastest? Isn''t push_back quite performance intensive. Wouldn''t allocating too much memory and then releasing the overhead after the process be fastest, while needing a bit of extra memory shortly, which is usually easy to spare?
-CProgrammer

Share this post


Link to post
Share on other sites
SiCrane    11839
If you're worried about the overhead with vector::push_back() use vector::reserve() before you do processing. Then if you're right about the amount of memory you need, you incur no extra cost. And if you're wrong, your program will still run without doing horrible buffer overruns.

edit: @!$# smiley code

[edited by - SiCrane on January 4, 2004 3:18:45 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
<a href=http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dv_wcecrt4/html/erlrfrealloc.asp>realloc</a>

Share this post


Link to post
Share on other sites