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

[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:perator= only three times no matter
what size of vector you are removing from and no matter where the removed
element is located.

 

[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: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

 

[Calum Grant]

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: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...

 

[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: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].

 

[Bob Hairgrove]

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

[snip]

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

 

[Calum Grant]

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: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.

 

[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.

 

[red floyd]

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: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).

 

[Andrew Koenig]

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: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?