Removing a vector element using std::swap and std::vector::re size.

[Jason Heyes]

Does the STL have a function like this one?

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

Unlike std::vector::er ase, it calls T::operator= 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::vec tor<T> &v, std::vector<T>: :size_type index)
{
std::swap(v[index], v.back());
v.resize(index) ;
}

Unlike std::vector::er ase, it calls T::operator= 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

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Calum Grant]

Jason Heyes wrote:

Does the STL have a function like this one?

template <typename T>
void remove(std::vec tor<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::er ase, it calls T::operator= 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]

On Sun, 15 Jan 2006 14:14:21 GMT, Calum Grant
<bo*****@visula .nospamplease.o rg> wrote:

template <typename T>
void remove(std::vec tor<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?

}

Unlike std::vector::er ase, it calls T::operator= 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...

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::operator=(). 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
No**********@Ho me.com

[Bob Hairgrove]

On Sun, 15 Jan 2006 17:16:07 +0100, Bob Hairgrove
<in*****@bigfoo t.com> wrote:

[snip]

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

--
Bob Hairgrove
No**********@Ho me.com

[Calum Grant]

Bob Hairgrove wrote:

On Sun, 15 Jan 2006 14:14:21 GMT, Calum Grant
<bo*****@visula .nospamplease.o rg> wrote:

template <typename T>
void remove(std::vec tor<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).

}

Unlike std::vector::er ase, it calls T::operator= 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...

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::operator=(). 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
No**********@Ho me.com

[Bob Hairgrove]

On Sun, 15 Jan 2006 17:35:29 GMT, Calum Grant
<bo*****@visula .nospamplease.o rg> wrote:

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

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.

--
Bob Hairgrove
No**********@Ho me.com

[red floyd]

Calum Grant wrote:

Jason Heyes wrote:

Does the STL have a function like this one?

template <typename T>
void remove(std::vec tor<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::er ase, it calls T::operator= 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]

"Jason Heyes" <ja********@opt usnet.com.au> wrote in message
news:43******** *************** @news.optusnet. com.au...

Does the STL have a function like this one? template <typename T>
void remove(std::vec tor<T> &v, std::vector<T>: :size_type index)
{
std::swap(v[index], v.back());
v.resize(index) ;
} Unlike std::vector::er ase, it calls T::operator= 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?