Why doesn't Vector provide a remove () member function while the list is being displayed?

Question

If I want to remove all elements with a value from a vector, I call remove algorithm and then I call the function of the element to erase the vector to physically remove it. But in the case of a list, a simple call removes the member function, and it removes all the elements with this value. I'm not sure why vector does not provide MF removal while the list does this.

For Exp: I want to remove the value '4' from the 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 the list:

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

Answer 1

The question is not why std::vector does not offer an operation, but why std::list offers it. The STL design is focused on the separation of containers and algorithms using iterators, and in all cases when the algorithm can be effectively implemented from the point of view of iterators, that is, an option.

However, there are cases when there are specific operations that can be implemented much more efficiently with knowledge of the container. This is a case of removing items from a container. The cost of using the delete-erase idiom is linear in size of the container (which cannot be significantly reduced), but this hides the fact that in the worst case, all but one operation are copies of objects (the only element is that the match is the first), and these copies can be quite a significant hidden cost.

Performing the operation as a method in std::list , the complexity of the operation will still be linear, but the cost associated with it for each of the deleted elements is very small, several copies of the pointer and the release of node in memory. At the same time, implementation as part of a list can provide more reliable guarantees: pointers, links, and iterators to elements that are not erased, do not become invalid in the operation.

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

Thus, algorithms are implemented as free functions using iterators, if there are no good reasons for providing a specific implementation in a specific container.

Answer 2

I believe the rationale is that std::list offers a very efficient remove method (if implemented as doubly linked, it just adjusts the pointers to the element and frees its memory), and deleting the element for std::vector is relatively slow .

The remove+erase is a standard way that works for all types of containers that offer the required type of iterator. Presumably, STL designers wanted to point out this difference. They could select all remove containers, which would be remove+erase for all containers except those who knew the best way, but they did not.

This seems to violate the idea of ​​generic code at first glance, but I don't think it really is. Having a simple, general remove that is easy to access, a generic code that compiles using all types of containers is easily written, but at the end a generic code that will work very slowly in 9 out of 10 cases and incredibly fast in the tenth is not really generic, it just looks like this.

The same pattern can be found in std::map::find compared to the generic std::find .

Answer 3

Removing an element from a vector is much slower than when using it for a list: it (on average) is proportional to the size of the vector, while the operation in the list is performed in constant time.

The designers of the standard library decided not to include this feature in accordance with the principle of "things that look easy should be (computationally) easy."

I'm not sure if I agree with this philosophy, but he considered the design goal for C ++.

Answer 4

Because removing an item from the list is cheap, while on a vector is expensive - all of the following items must be shifted, that is, copied / moved.

Answer 5

I suppose this is due to efficiency, it is slower to remove random elements from a vector than from a list. This may mean a bit more typing for such situations, but at least it's obvious in the interface that std::vector not the best data structure if you need to do this often.