469,338 Members | 8,430 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,338 developers. It's quick & easy.

Vector Erase


For discussion purposes, assume the vector ivec contains 67108864 (67
million elements) elements. Lets futher assume nstart and end equal
1008000 and 11088000 respectively.

The question. What's the _fastest_ way to erase element numbers less
than 1008000 and element numbers greater than 11088000. Current
approach.

typedef std::vector < int INT_VEC ;

int main () {

int dummy( 0 ) ;
for ( INT_VEC::iterator it = ivec.begin(); it != ivec.end(); ) {
if ( dummy < nstart || dummy end ) {
it = ivec.erase ( it ) ;
} else {
++ it ;
}
++ dummy ;
}

}

This is 'dog' slow. That said, I thinking it would be ideal if i
copied elements into a separate vector.

Sep 24 '07 #1
3 2060
ma740988 wrote:
For discussion purposes, assume the vector ivec contains 67108864 (67
million elements) elements. Lets futher assume nstart and end equal
1008000 and 11088000 respectively.

The question. What's the _fastest_ way to erase element numbers less
than 1008000 and element numbers greater than 11088000. Current
approach.

typedef std::vector < int INT_VEC ;

int main () {

int dummy( 0 ) ;
for ( INT_VEC::iterator it = ivec.begin(); it != ivec.end(); ) {
if ( dummy < nstart || dummy end ) {
it = ivec.erase ( it ) ;
} else {
++ it ;
}
++ dummy ;
}

}

This is 'dog' slow. That said, I thinking it would be ideal if i
copied elements into a separate vector.
Extract the numbers you want to keep into the separate vector:

std::vector<inttokeep(&ivec[1008000], &ivec[11088000 + 1]);
and clear 'ivec':

std::vector<int>().swap(ivec);

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Sep 24 '07 #2
On 2007-09-24 11:44:40 -0400, ma740988 <ma******@gmail.comsaid:
>
This is 'dog' slow.
Of course it is. Each time the code removes an element it copies all
the elements above that one down one position. You end up with an awful
lot of copying.
That said, I thinking it would be ideal if i
copied elements into a separate vector.
Maybe. Or maybe just erase all the tail elements at one time, then all
the head elements at one time.

vec.erase(vec.begin() + end, vec.end());
vec.erase(vec.begin(), vec.begin() + nstart);

Or, to copy the retained elements:

INT_VEC new_vec(vec.begin() + nstart, vec.begin() + end);

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Sep 24 '07 #3
"Victor Bazarov" <v.********@comAcast.netwrote in message
news:fd**********@news.datemas.de...
ma740988 wrote:
>The question. What's the _fastest_ way to erase element numbers less
than 1008000 and element numbers greater than 11088000. Current
approach.
Extract the numbers you want to keep into the separate vector:

std::vector<inttokeep(&ivec[1008000], &ivec[11088000 + 1]);
and clear 'ivec':

std::vector<int>().swap(ivec);
This approach works, but has the disadvantage of requiring enough memory to
hold two copies of all the elements that are retained, along with the rest
of ivec's original contents.

Instead, how about the following?

ivec.erase(ivec.begin() + 11088000+1, ivec.end());
ivec.erase(ivec.begin(), ivec.begin() + 1008000);

This code copies the elements that are retained, but does so into memory
that is already allocated so there is no additional space overhead.

It is true that after it is done, the capacity of ivec is still what it was
originally, but that can't be helped directly. If you care, you can copy
the remaining elements of ivec into new space and free the original:

std::vector<int>(ivec).swap(ivec);
Sep 25 '07 #4

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

5 posts views Thread by Steve Hill | last post: by
3 posts views Thread by Jonathan | last post: by
9 posts views Thread by david wolf | last post: by
5 posts views Thread by Billy Patton | last post: by
14 posts views Thread by cayblood | last post: by
9 posts views Thread by Amadeus W. M. | last post: by
4 posts views Thread by Christian Bruckhoff | last post: by
3 posts views Thread by =?iso-8859-1?q?Erik_Wikstr=F6m?= | last post: by
3 posts views Thread by chsalvia | last post: by
1 post views Thread by CARIGAR | last post: by
reply views Thread by zhoujie | last post: by
reply views Thread by suresh191 | last post: by
reply views Thread by Purva khokhar | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.