For removing an iterator from std::vector I can do these two things:
std::vector<int>& vec = myNumbers; // use shorter name
vec.erase(std::remove(vec.begin(), vec.end(), number_in), vec.end());
Or I can do this:
auto it = find(vec.begin(), vec.end(), number_in);
vec.erase(it);
The second is more intuitive, I guess, but which one is faster?
EDIT: Elements in vector are unique and we don't have to worry to delete several elements at once.
The first one is guaranteed to work correctly, while your second version may be faster (due to std::find stopping at the first item that matches), but it certainly is not safer.
auto it = find(vec.begin(), vec.end(), number_in);
if (it != vec.end())
vec.erase(it);
That would ensure you are not erasing an invalid iterator.
So it depends on your needs. If you want a program that is correct, the first one works without further intervention, however the second requires a bug ticket from your customer and then you have to go fix it (as above).
PaulMcKenzie and ks1322 answers. :)
end is needed and the implications either way when reading code; that contrasts with the remove approach which firmly suggests potential for multiple values - breaking down the readers mental model of the data and logic, which can lead to errors during program maintenance and evolution.
erase not remove so they discovered the problem earlier...! :-) I would say that either of a check against end() and an assertion that it is not end() are as correct/robust as using remove, without the confusing implication that there might be 0, 1, 2 or even more copies of the value. Anyway - my point's here for readers - not pushing you to also change your answer if you don't heartily agree. Cheers.The second is faster - the first will try to find all of elements which are equal to number_in, although it has already found one. However, the second will stop when it find one.
vector.
erase will keep the order of all other elements, which will all be moved or copied to a new position to fill the gap left by the erased element(s).vec has 5 elements and the 2nd is to be erased, the 3rd will be copied over the 2nd, then the 4th will be copied over the 3rd, then the 5th over the fourth, then the destructor for the fifth element will run. So - there's "compaction" happening. For simple POD types (basically, types without complicated constructors/destructors/pointers/references etc), the implementation may be able to use a memmove style operation to do compaction much faster, but the amount of work is still related to the remaining vector size.std::vector::erase
Removes the element at pos.
Removes the elements in the range [first; last).
Invalidates iterators and references at or after the point of the erase, including the end() iterator. The iterator pos must be valid and dereferenceable. Thus the end() iterator (which is valid, but is not dereferencable) cannot be used as a value for pos. The iterator first does not need to be dereferenceable if first==last: erasing an empty range is a no-op.
http://en.cppreference.com/w/cpp/container/vector/erase
The first approach would be slower since the entire vector will be searched for the number. But it is also the safer way. Consider number_in is not an element of your vector. The first approach would try to erase an empty range which is defined and safe. And the second approach would try to erase the end iterator of your vector which is unsafe and UB.
It appears that you're interested in performance. Finding the (first) matching element cannot be done faster than O(n). So, the part where you can try to improve performance is the removal, which can be O(1), if you allow
the order of the vector elements to change. For example
// find requires up to O(n)
auto it = std::find(v.begin(),v.end(),value);
// remove in O(1) but don't preserve order
if(it!=v.end()) {
std::iter_swap(it,--(v.end()));
v.pop_back();
}
Note that solutions using std::remove() and/or vector::erase() will preserve the order of the remaining elements and hence inevitable still compact the remaining elements (quoted from comment by Tony D), which is almost always more expensive than finding the matching element and hence dominates the computational costs.
Just try which solution is faster – the proof of the pudding is in the eating!
vec.erase(std::remove will not operate in o(n) too? Like std::remove swaps with the last elem, and then erase removes with o(1), right? But we don't preserve the order?std::remove() swap with the last element? I don't think so, since it (according to cppreference) preserves the order of the remaining elements and has complexity O(n).n+2n=3n but my solution only n+1<3n, even though both are O(n).
number_in, and the second removes one of elements which arenumber_in.findthen overwrite the found element withvec.back(), thenvec.pop_back(). That makes the post-finderasepart of the operation O(1), instead of linear in the number of elements thereafter in thevector(as it shuffles them front-ward).