469,622 Members | 1,445 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

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

std::vector - fast way to crop?

Is there a fast way to crop a vector? I have a vector of size n, and
want to reduce it to some subregion (x,y ). Seems like you shouldn't
have to recopy all of those elements into a new vector, since they are
already contiguous in memory.

Thanks,

Isaac

Jul 23 '05 #1
6 4366
is******@gmail.com wrote:
Is there a fast way to crop a vector? I have a vector of size n, and
want to reduce it to some subregion (x,y ). Seems like you shouldn't
have to recopy all of those elements into a new vector, since they are
already contiguous in memory.


vector<blah> v;
...
vector<blah>(v.begin()+x, v.begin()+y).swap(v);

or

vector<blah> v;
...
v.resize(y+1);
v.erase(0, v.begin()+x);

Both approaches involve copying and destroying of the vector's elements.
In order to understand the performance you would need to time them.

V
Jul 23 '05 #2
On 2005-02-22 15:12:12 -0500, is******@gmail.com said:
Is there a fast way to crop a vector? I have a vector of size n, and
want to reduce it to some subregion (x,y ). Seems like you shouldn't
have to recopy all of those elements into a new vector, since they are
already contiguous in memory.


You will have to do some copying, as STL containers "own" the contained
objects. There is no way to transfer those objects to a new vector, or
make them outlive the container. It would be possible to write a
container that could do this (i.e. have it store five pointers:
"storage begin", "begin", "end" and "storage end"), but that could be
pretty wasteful in the general case.

There are several ways to accomplish what you want, but they all
involve copying in the general case:

Assuming:
v is a vector of <foo>
x and y are iterators pointing into v

1)
std::copy(x, y, v.begin());
v.resize(y-x);

2)
v.resize(y - v.begin());
v.erase(v.begin(), x);

3)
std::swap(v, std::vector<foo>(x,y));

.... among others. The only case that I can think of off the top of my
head where no copying is needed is if (x == v.begin()):
v.resize(y - x);

--
Clark S. Cox, III
cl*******@gmail.com

Jul 23 '05 #3
is******@gmail.com wrote:
Is there a fast way to crop a vector? I have a vector of size n, and
want to reduce it to some subregion (x,y ). Seems like you shouldn't
have to recopy all of those elements into a new vector, since they are
already contiguous in memory.


What exactly do you mean by "crop"? If you mean delete everything before x,
and after y(inclusive?), then look at using a deque. Deque provides
amortized constant time insert/delete to both the front and back of the
sequence.

Jeff Flinn
Jul 23 '05 #4
is******@gmail.com wrote:
Is there a fast way to crop a vector? I have a vector of size n, and
want to reduce it to some subregion (x,y ). Seems like you shouldn't
have to recopy all of those elements into a new vector, since they
are already contiguous in memory.


The usual way to handle this is to rearrange the items in the vector so
the ones you want to keep are all at the beginning, followed by all
those you want to get rid of. std::remove will rearrange items into an
order like this.

Once you've done that, you use vector.erase to get rid of the items you
no longer need.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Jul 23 '05 #5
Jerry Coffin wrote:
is******@gmail.com wrote:
Is there a fast way to crop a vector? I have a vector of size n, and
want to reduce it to some subregion (x,y ). Seems like you shouldn't
have to recopy all of those elements into a new vector, since they
are already contiguous in memory.

The usual way to handle this is to rearrange the items in the vector so
the ones you want to keep are all at the beginning, followed by all
those you want to get rid of. std::remove will rearrange items into an
order like this.

Once you've done that, you use vector.erase to get rid of the items you
no longer need.


I wonder, would it actually be any faster than, say, two erases?
My guess is that it wouldn't but I am open for a demonstration that
would prove me wrong.

V
Jul 23 '05 #6
Victor Bazarov wrote:

[ ... ]
The usual way to handle this is to rearrange the items in the
vector so the ones you want to keep are all at the beginning,
followed by all those you want to get rid of.

[ ... ]
I wonder, would it actually be any faster than, say, two erases?
My guess is that it wouldn't but I am open for a demonstration that
would prove me wrong.


I suspect it'll depend on the implementation and probably on the
amounts of data involved as well as whether you need to maintain the
order of the items you keep.

If you're removing N items from the beginning of a vector of M items,
if you need to maintain the order, you have to move M-N items. If you
don't need to maintain the relative order, you only need to move N
items.

Whether this will save significant time will depend on the size of N
relative to M-N.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Jul 23 '05 #7

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

18 posts views Thread by Janina Kramer | last post: by
11 posts views Thread by Steve | last post: by
32 posts views Thread by zl2k | last post: by
21 posts views Thread by Peter Olcott | last post: by
82 posts views Thread by Peter Olcott | last post: by
2 posts views Thread by Chris Forone | last post: by
reply views Thread by devrayhaan | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.