Hi

I am using a "std::vector<std::pair<stuff1, stuff2>> myvec" that holds temporary data. A random element in the vector may be erased at any time. I don't want to use the std::vector::erase method as it will shuffle all elements which degrades performance.

What I want to do instead is to take the element to be erased and set it equal to the back() element, then pop_back(). This won't shuffle the elements down as the erase() method does (I think).

Now, will the std::pair class assign operator mess with me when I do this or is this code good?

void EfficientEraseElement(std::vector<std::pair<stuff1, stuff2>> &myvec, int i)
{
	myvec.at(i) = myvec.back();
	myvec.pop_back();
}

Normally you use move-semantics to avoid the copies (for non-trivial types). std::swap() handles that for you, though a single std::move() would work.

Here's my general function for swap-and-popping vectors:

//Swap-and-pop a specific element of a container, swapping the element with the element at the back of the container and then popping it off the stack.
//This does not preserve the order of the elements.
template<typename ContainerType>
void SwapAndPopAtIndex(ContainerType &container, size_t index)
{
	//Don't swap the back element with itself, and also don't swap out of range.
	/*
		The (index+1) is to prevent the back element from swapping with itself.

		This could be more clearly written as:	if(index >= (container.size()-1))
		...but since 'container.size()' is unsigned,
		the -1 would accidentally loop it around if size() returns 0, which is a likely occurance.
	*/
	if((index+1) >= container.size())
		return;

	//Swap the element with the back element.
	std::swap(container[index], container.back());

	//Pop the back of the container, deleting our old element.
	container.pop_back();
}

It does not preserve the order of elements.

AFAIK, std::vector needs to guarantee contiguous storage at all times, so I don't think there's any way to avoid memory moves when you delete an item. Std::list does not have that requirement, and it is designed specifically for random deletions and insertions. However, it does not provide random access (by index).

Another thing you could do if you still need to work with std::vector is to mark items as deleted instead of actually deleting them. For basic data types, you could reserve a specific value (like NULL for pointers) as meaning "deleted item". For structures and classes, you probably already use pointers, so NULL is good. If not, you could add a member m_bIsDeleted.

Out of curiosity, does anyone know if there is any chance the swap can be optimized to a move when the items don't have destructors?

I guess that could be difficult unless the memory in the vector is actually shrunk..

Not that it should really matter, but for large POD types it seems unnecessary to exchange the memory instead of just copying.

If by "items don't have destructors" you mean to say that your items are not pointers to objects, structures or other data, then no, there is not way to avoid a copy/move (actually three - one for the first item being moved to aux, one for the second item being moved into the first, and one for aux being moved to the second item).

Also, for 64-bit targets, the compiler will optimize those data moves into SSE instructions, if the data to be moved is 8 bytes or less...

Out of curiosity, does anyone know if there is any chance the swap can be optimized to a move when the items don't have destructors?
I guess that could be difficult unless the memory in the vector is actually shrunk..
Not that it should really matter, but for large POD types it seems unnecessary to exchange the memory instead of just copying.

C++11 introduced a POD testing template, so you could write:

if( std::is_pod<T>::value )
  container[index] = container.back();
else
  std::swap(container[index], container.back());