Re: Constant Time std::vector Item Removal
On 2010-07-15 15:46:12 -0400, Nick Hounsome said:
That's essentially how you work with std algorithms such as
std::remove - They can't actually remove stuff from a collection
bacause they don't take the collection as an argument so they just
reorder it such that the dead stuff is at the end and return you an
iterator to the first 'dead' element. You then use this with
collection to actually erase them.
e.g.
std::vector<int> v;
// fill it up somehow
v.erase(std::remove(v.begin(), v.end(), 99), v.end()); // really
remove all elements with value 99
It's even a bit more subtle than the description above. remove doesn't
reorder, it overwrites and leaves the dead stuff at the end untouched:
iterator current = first;
while (first != last)
{
if (!(*first == to_remove))
*current++ = *first;
++first;
}
return current;
(In real life, the algorithm would scan for the first non-matching
value instead of copying each of the first values on top of itself, but
that's just efficiency. <g>)
So if you were removing all the 2's from { 1, 2, 3, 2, 4, 2, 5} you'd
end up with { 1, 3, 4, 5, 4, 2, 5 } and a returned iterator pointing to
the fifth element.
--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]