Efficient way to erase an element from std::vector

Started by
21 comments, last by SmkViper 9 years, 2 months ago

http://stackoverflow.com/questions/62340/does-pop-back-really-invalidate-all-iterators-on-an-stdvector

However, in your code example, it can invalidate it when it is pointing to the last element and the value is below 10. In which case Visual Studio debug STL will mark iterator as invalidated, and further check for it not being equal to end() will show an assert.

Edit: Baw, can't solve using this code where I try to update the iterator :(


	auto EndIt = Futures.end();
	for (auto it = Futures.begin() ; it != EndIt ; it++)
	{
		if (it->wait_for(std::chrono::seconds(0)) == std::future_status::ready)
		{
			std::swap(*it, Futures.back());
			Futures.pop_back();
			EndIt = Futures.end();
		}
	}
Advertisement

threw away interators in favor of indices:


	for (size_t i = 0; i < Futures.size(); )
	{
		if (Futures[i].wait_for(std::chrono::seconds(0)) == std::future_status::ready)
		{
			std::swap(Futures[i], Futures.back());
			Futures.pop_back();
		} else {
			i++;
		}
	}

http://stackoverflow.com/questions/62340/does-pop-back-really-invalidate-all-iterators-on-an-stdvector







However, in your code example, it can invalidate it when it is pointing to the last element and the value is below 10. In which case Visual Studio debug STL will mark iterator as invalidated, and further check for it not being equal to end() will show an assert.


Edit: Baw, can't solve using this code where I try to update the iterator sad.png


	auto EndIt = Futures.end();
	for (auto it = Futures.begin() ; it != EndIt ; it++)
	{
		if (it->wait_for(std::chrono::seconds(0)) == std::future_status::ready)
		{
			std::swap(*it, Futures.back());
			Futures.pop_back();
			EndIt = Futures.end();
		}
	}

Edit: Original diagnostics incorrect.

It doesn't work cause all you did is re-assign your end check when the iterator that has the problem is "it". There's a reason that erasing from a vector returns a new iterator for you to use.

Honestly, just save yourself some headache and use the standard library remove_if, followed by the vector's erase member. These functions are provided for your convenience so you don't have to re-invent the wheel all the time smile.png

Plus the remove->erase idiom can do things more efficiently then your pop_back because it can remove a whole swath of elements at once, rather then one at a time.


// Replace "auto& item" with the correct type if you aren't using C++14
const auto eraseStart = std::remove_if(Futures.begin(), Futures.end(), [] (auto& item)
  {
    return item.wait_for(std::chrono::seconds(0) == std::future_status::ready;
  }
);
Futures.erase(eraseStart, Futures.end());

This topic is closed to new replies.

Advertisement