Removing a vector element using std::swap and std::vector::resize.

J

Jason Heyes

Does the STL have a function like this one?

template <typename T>
void remove(std::vector<T> &v, std::vector<T>::size_type index)
{
std::swap(v[index], v.back());
v.resize(index);
}

Unlike std::vector::erase, it calls T::eek:perator= only three times no matter
what size of vector you are removing from and no matter where the removed
element is located.
 
A

Alf P. Steinbach

* Jason Heyes:
Does the STL have a function like this one?

template <typename T>
void remove(std::vector<T> &v, std::vector<T>::size_type index)
{
std::swap(v[index], v.back());
v.resize(index);
}

Unlike std::vector::erase, it calls T::eek:perator= only three times no matter
what size of vector you are removing from and no matter where the removed
element is located.

Possibly you meant

v.resize( v.size() - 1 );

And possibly, when you write "the STL" you mean the C++ standard library,
not the STL.

Regarding whether there is such a function, do read the documentation.

Cheers,

- Alf
 
C

Calum Grant

Jason said:
Does the STL have a function like this one?

template <typename T>
void remove(std::vector<T> &v, std::vector<T>::size_type index)
{
std::swap(v[index], v.back());
v.resize(index);

Do you mean v.pop_back()?
}

Unlike std::vector::erase, it calls T::eek:perator= only three times no matter
what size of vector you are removing from and no matter where the removed
element is located.

I suggest you try using that function to see what happens! I don't
think it works quite the same as erase...
 
B

Bob Hairgrove

template <typename T>
void remove(std::vector<T> &v, std::vector<T>::size_type index)
{
std::swap(v[index], v.back());
v.resize(index);

Do you mean v.pop_back()?

He means v.back() -- how could he mean anything else?
I suggest you try using that function to see what happens! I don't
think it works quite the same as erase...

True, it doesn't work the same. But as long as the remaining elements
don't have to be in any specific order, I suppose it would be much
faster than calling (v.size()-index) times T::eek:perator=(). Indeed,
this would perform in O(1) time for any given type T, whereas
v.erase() could only do O(n) at best (where n == v.size()-index).

As an aside, it should work for v.front() as well as v.back() (or *it
for any iterator it of v where it != v.end()). As it is, there should
be a little more sanity-checking; e.g., v cannot be empty, and
v.back() should point to a different element than v[index].
 
B

Bob Hairgrove

On Sun, 15 Jan 2006 17:16:07 +0100, Bob Hairgrove

[snip]

PS -- what Alf said, re: v.resize(v.size()-1);
 
C

Calum Grant

Bob said:
template <typename T>
void remove(std::vector<T> &v, std::vector<T>::size_type index)
{
std::swap(v[index], v.back());
v.resize(index);

Do you mean v.pop_back()?


He means v.back() -- how could he mean anything else?

I mean, v.pop_back() instead of v.resize(index) -- how could I mean
anything else ;-)

Personally I prefer v.pop_back() to v.resize(v.size()-1).
I suggest you try using that function to see what happens! I don't
think it works quite the same as erase...


True, it doesn't work the same. But as long as the remaining elements
don't have to be in any specific order, I suppose it would be much
faster than calling (v.size()-index) times T::eek:perator=(). Indeed,
this would perform in O(1) time for any given type T, whereas
v.erase() could only do O(n) at best (where n == v.size()-index).

As an aside, it should work for v.front() as well as v.back() (or *it
for any iterator it of v where it != v.end()). As it is, there should
be a little more sanity-checking; e.g., v cannot be empty, and
v.back() should point to a different element than v[index].

It certainly wouldn't work if you used v.front(). Doing a
resize()/pop_back() would erase the wrong element.

Your suggestion might work on a std::deque however. This does have an
efficient pop_front() function.

The algorithm would certainly work if index == size()-1. std::swap
works to swap an item with itself. I would follow the general precedent
of the standard library - the caller is responsible for ensuring the
validity of the iterator.



 
B

Bob Hairgrove

I mean, v.pop_back() instead of v.resize(index) -- how could I mean
anything else ;-)

Personally I prefer v.pop_back() to v.resize(v.size()-1).

LOL ... my bad ... sorry about the FUD!

Thought you meant "pop_back() instead of back()". Well, I guess that
was more than a little stupid of me.
 
R

red floyd

Calum said:
Jason said:
Does the STL have a function like this one?

template <typename T>
void remove(std::vector<T> &v, std::vector<T>::size_type index)
{
std::swap(v[index], v.back());
v.resize(index);

Do you mean v.pop_back()?
}

Unlike std::vector::erase, it calls T::eek:perator= only three times no
matter what size of vector you are removing from and no matter where
the removed element is located.

I suggest you try using that function to see what happens! I don't
think it works quite the same as erase...

1. should use v.at(index) instead of v[indexx]
2. Is not safe for empty vector (but item 1 takes care of that).
 
A

Andrew Koenig

Jason Heyes said:
Does the STL have a function like this one?
template <typename T>
void remove(std::vector<T> &v, std::vector<T>::size_type index)
{
std::swap(v[index], v.back());
v.resize(index);
}
Unlike std::vector::erase, it calls T::eek:perator= only three times no
matter what size of vector you are removing from and no matter where the
removed element is located.

Even though the example above is incorrect (v.resize(index) should be
v.resize(v.size()-1) or, better yet, v.pop_back()), it's hard to imagine
that this operation would be useful enough to merit a standard function to
implement it.

For one thing, it's only two statements. For another, it doesn't preserve
the ordering of the vector elements, which rather limits its usefulness.
For a third, most of the operations on vectors use iterators, not indices.

Can you show us an example of where such a function would be useful?
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,733
Messages
2,569,440
Members
44,832
Latest member
GlennSmall

Latest Threads

Top