std::vector::erase avoiding lots of copying

[savavampir]

I have situation where i have lots of objects in one container and i need to erase some element/s from arbitary position,
but that can envolve lots of copying being made, so i thought i should try to swap object from that position with last one
and erase that one. First question, is there some common function for this one?
Currently i have wrote this:

template<typename T>
void erase(std::vector<T>& v, ulong inx)
{
	std::vector<T>::iterator itr = v.begin() + inx;
	std::swap(*itr, v.back());
	v.erase(v.end() - 1);
}

Note that afer this i don't need right order of elements since i will sort afterwards.

Second question, how to "grab" const_iterator for last element so that i dont need to write:
v.erase(v.end() - 1);

Feel free to point any flows you can see here.

Thanks for your time.

[Disch]

Second question, how to "grab" const_iterator for last element so that i dont need to write:

You could just v.pop_back(); instead of using erase.

[coder777]

You can improve it (a little bit) like so:

template<typename T>
void erase(std::vector<T>& v, ulong inx)
{
	std::swap(v[inx], v.back());
	v.pop_back();
}

[savavampir]

Thank you for hints.

I just realized that i can add one more swap after pop_back and regain order:

template<typename T>
void erase_element(std::vector<T>& v, ulong inx)
{
	std::swap(v[inx], v.back());
	v.pop_back();
        std::swap(v[inx], v.back());
}

[Disch]

That doesn't regain the original order. There's no way to do that without moving every element after the removed one.

[savavampir]

I meant sorted order, not by index order.

[Disch]

There's a difference?

Let's say you have the following data:

1 2 5 8 10 23

anr you remove the 5:

1 2 23 8 10 5 <- 1st swap
1 2 23 8 10 <- pop_back
1 2 10 8 23 <- 2nd swap

Order isn't restored.

[savavampir]

OMG. You're right. Damn it.

[Albatross]

Hmm. Maybe you could setup a vector of pairs which contain the values and the original subscripts of all the data, and after you're done erasing everything that needs to be erased you could just sort by the original subscripts.

-Albatross

[Disch]

If you need the data to stay sorted, just use the built-in erase() function. No need to reinvent the wheel here.

Although your custom function above is good if you don't need it to be sorted.

[Albatross]

What he's trying to avoid is a vector's need to shift all the data after the erased element to maintain an array-like structure. Maybe he has a good reason for that.

Although, why not use an std::deque? It has some higher constant factors, true, but its erase() does seem to me to be a bit more efficient than an std::vector's, albeit not as efficient as an std::list's (though lists have some efficiency problems in other areas...).

-Albatross

[savavampir]

just use the built-in erase()

What built in? std::vector::erase() ? But what if i invoke that on 0 inx of vector of 5000 elements that would invoke almost 5000 copyies just to shift elements?

I would like (if possible) after erase if elements can remain sorted in few cheap steps, so that i don't need to call sort immideatly after.
If you have some ideas please share.
Thanks greatly on your time.

[Disch]

But what if i invoke that on 0 inx of vector of 5000 elements that would invoke almost 5000 copyies just to shift elements?

Yeah, but if you want it to stay sorted, that's what it takes.

The alternative would be to use something like deque as Albatross suggested. It offers [potentially] faster insertion/removal with a tradeoff of [potentially] slower data access.

Or if you don't need random access you could use a list instead.

I would like (if possible) after erase if elements can remain sorted in few cheap steps

If such a thing were possible, vector::erase would do it. The people that wrote those libs knew what they were doing.

[savavampir]

You're right (again). Thanks both of you for tips.