std::vector - fast way to crop?

[isaacyho]

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

[Victor Bazarov]

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

[Clark S. Cox III]

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

[Jeff Flinn]

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

[Jerry Coffin]

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.

[Victor Bazarov]

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

[Jerry Coffin]

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.