CODEWITHSUNDEEP
c++
Alok
Alok

Reputation: 2035

why Vector doesn't provide the remove() member function while list provides?

If I want to delete all the elements with a value from vector,I call remove algorithm and then call vector's erase member function to physically delete it. But in the case of list , simple call remove member function and it will delete all elements with that value. I am not sure why vector does't provide the remove MF while list does it.

For Exp: I want to delete value '4' from vector v. 

vector<int> v;
vector<int> ::iterator Itr;
for (int i=0; i< 6; i++)
   v.push_back(i*2);
v.push_back(4);
v.push_back(8);
v.push_back(4);
v.erase(remove(v.begin(),v.end(),4), v.end());

and for list:

list.remove(4); // will delete all the element which has value 4

Upvotes: 8

Views: 1057

Answers (5)

David Rodr&#237;guez - dribeas
David Rodr&#237;guez - dribeas

Reputation: 208446

The question is not why std::vector does not offer the operation, but rather why does std::list offer it. The design of the STL is focused on the separation of the containers and the algorithms by means of iterators, and in all cases where an algorithm can be implemented efficiently in terms of iterators, that is the option.

There are, however, cases where there are specific operations that can be implemented much more efficiently with knowledge of the container. That is the case of removing elements from a container. The cost of using the remove-erase idiom is linear in the size of the container (which cannot be reduced much), but that hides the fact that in the worst case all but one of those operations are copies of the objects (the only element that matches is the first), and those copies can represent quite a big hidden cost.

By implementing the operation as a method in std::list the complexity of the operation will still be linear, but the associated cost for each one of the elements removed is very low, a couple of pointer copies and releasing of a node in memory. At the same time, the implementation as part of the list can offer stronger guarantees: pointers, references and iterators to elements that are not erased do not become invalidated in the operation.

Another example of an algorithm that is implemented in the specific container is std::list::sort, that uses mergesort that is less efficient than std::sort but does not require random-access iterators.

So basically, algorithms are implemented as free functions with iterators unless there is a strong reason to provide a particular implementation in a concrete container.

Upvotes: 9

Alexander Gessler
Alexander Gessler

Reputation: 46657

I believe the rationale is that std::list offers a very efficient remove method (if implemented as a doubly linked listed it just adjusts the pointers to the element and deallocates its storage), while element removal for std::vector is comparably slow.

The remove+erase trick is the standard way which works for all container types that offer the required iterator type. Presumably, the designers of the STL wanted to point out this difference. They could have opted to give all containers a remove method, which would be remove+erase for all containers except those who knew a better way, but they didn't.

This seems to violate the idea of generic code at a first glance, but I don't think it really does. Having a simple, generic remove that is easily accessible makes it easy to write generic code that compiles fine with all container types, but at the end generic code that would run extremely slow in 9 out of 10 cases and blazingly fast in the tenth is not truly generic, it just looks so.

The same pattern can be found at std::map::find vs. the generic std::find.

Upvotes: 4

Node
Node

Reputation: 3509

I imagine its due to efficiency, its slower to remove random elements from a vector than it is from a list. It might mean a little more typing for situations like this, but at least its obvious in the interface that the std::vector isn't the best data structure if you need to do this often.

Upvotes: 0

Nikolai Fetissov
Nikolai Fetissov

Reputation: 84239

Because dropping item from a list is cheap, while doing so on a vector is expensive - all following elements have to be shifted, i.e. copied/moved.

Upvotes: 1

Brennan Vincent
Brennan Vincent

Reputation: 10675

Removing an element from a vector is much slower than doing so for a list: it is (on average) proportional to the size of the vector, whereas the operation on a list is executed in constant time.

The designers of the standard library decided not to include this feature under the principle of "things that look easy should BE (computationally) easy".

I'm not sure whether I agree with this philosophy, but it's considered a design goal for C++.

Upvotes: 3

Related Questions