dynamic arrays and loops
Author
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
std::vector<int> myArray;
while (inputTokens != TERMINATOR) {
myArray.push_back( ProcessToken(inputTokesn));<br> i++;<br>}<br><br><br>std::vector<>.push_back will allocate memory as necessary. <br><br>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).<br><br> </i>
while (inputTokens != TERMINATOR) {
myArray.push_back( ProcessToken(inputTokesn));<br> i++;<br>}<br><br><br>std::vector<>.push_back will allocate memory as necessary. <br><br>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).<br><br> </i>
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.
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.
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:
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.
If you are reading from a stream, it's even simpler
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]
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]
What the AP said is good for C++. In C it gets pretty complicated. I use C a lot, and this was my solution:
Probably why nobody uses C anymore.
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.
Author
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
-CProgrammer
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]
edit: @!$# smiley code
[edited by - SiCrane on January 4, 2004 3:18:45 AM]
<a href=http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dv_wcecrt4/html/erlrfrealloc.asp>realloc</a>
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement