One of the more confusing parts of the C++ standard library algorithms is remove/remove_if. A new user would think calling remove(v.begin(), v.end(), value_to_remove) would result in the value being removed from the container[1]. Instead, they'll find that all it did was shift around the ordering of the vector and leave the elements you wanted removed in place at the end (if you read the linked article you can already see where this is going) which is a very unintuitive result. They might look up the function signature and notice it returns an iterator which is also surprising.
Even after discovering they have to call the container's erase method using the result of remove and an iterator to the end of the container[2] they'd probably just decide that remove just has a terrible design. It takes experience and some data structures knowledge to realize why it is designed the way it is.
The design of remove means every element that remains are only be shifted (in the case of an array/vector), at most, one time. The naive approach results in the problem described in the article where you are constantly shifting the elements forward as you progress through the container.
The usability of remove is still a problem (the concept shouldn't need a wikipedia page explaining it) but the way it was done was done for good reasons (within the design decisions of STL at least). It's probably fixed in the C++ ranges proposal but I haven't looked.
D's standard algorithm library remove[3] (which is very much based on Stepanov's STL too) goes one performance step further and lets you specify the swap strategy so that if stability isn't a requirement the number of shifts required is the absolute minimum possible (essentially moving elements from the end of the range into spots freed up by the items being removed).
1. Slightly more experienced users would quickly notice that it can't remove the value, it has no reference to the container to change its length.
My homegrown C dynamic array has remove() macro with the same purpose (I didn't know it is in c++). Except that it takes range instead of index and doesn't move to the end, because you checkout/delete item first, and then remove, not vice versa. It also has insert function that does guess what. The module takes around one screen.
Cool thing is that it is not C++, where remove is hardcore stl magic, and I can just iterate over elements' memory and remove them in sliding ranges, so multi-remove problem simply doesn't exist. Idk why c++ overengineers everything. We abstract a generic vector away from our convenience only to to store items in regular array, because it is the only fast solution for generic cases.
This is one of those things that makes perfect sense after you actually tried to
implement it, but not necessarily beforehand. I think this happens a lot with
C++ that design decision are quite well though through, but it is hard to
appreciate this without taking time to understand the rationale.
Even after discovering they have to call the container's erase method using the result of remove and an iterator to the end of the container[2] they'd probably just decide that remove just has a terrible design. It takes experience and some data structures knowledge to realize why it is designed the way it is.
The design of remove means every element that remains are only be shifted (in the case of an array/vector), at most, one time. The naive approach results in the problem described in the article where you are constantly shifting the elements forward as you progress through the container.
The usability of remove is still a problem (the concept shouldn't need a wikipedia page explaining it) but the way it was done was done for good reasons (within the design decisions of STL at least). It's probably fixed in the C++ ranges proposal but I haven't looked.
D's standard algorithm library remove[3] (which is very much based on Stepanov's STL too) goes one performance step further and lets you specify the swap strategy so that if stability isn't a requirement the number of shifts required is the absolute minimum possible (essentially moving elements from the end of the range into spots freed up by the items being removed).
1. Slightly more experienced users would quickly notice that it can't remove the value, it has no reference to the container to change its length.
2. So common and unintuitive it gets its own wikipedia page: https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom
3. http://dlang.org/phobos/std_algorithm_mutation.html#.remove