用便宜的方式从任意容器中移除元素的习惯性方法？

Question

所有C++标准库容器都有insert()方法;但它们并不都有一个不采用任何参数的方法，而是以任意顺序执行尽可能便宜的移除。现在，对于不同的容器，这当然会有所不同：在一个向量中，我们将从后面移除，在我们从前面移除的单列表中（除非我们保持指向尾部的指针），依此类推到实施细节。

那么，有没有一种更习惯的方式来做到这一点，而不是为每个容器滚动我自己的模板专门化？

Answer 1

标准容器设计的一部分是，只有在可以为该容器提供最佳（通过选定度量）的情况下，它们才会将操作提供为成员函数。

如果一个容器提供了一个成员函数，那是因为有某种实现该函数的方法是对该容器最优的一种方式。

如果无法提供操作的最佳实施（如remove()），则不提供。

只有std::list和（C++ 11及更高版本）std::forward_list设计用于高效去除元素，这就是为什么它们是具有remove()成员函数的唯一容器。

其他容器的设计不适合有效去除任意元素;

• std::array不能调整大小，所以它是没有意义都要么一个insert()或remove()成员函数。
• std::deque仅针对在开始或结束时移除进行了优化。
• 从std::vector中删除元素比其他容器效率低，除了（可能）从最后。

对这些容器实现remove()成员函数因此违反了设计原则。

所以，如果你想能够有效地从一个容器中删除元素，你需要选择合适的工作容器。

为标准容器滚动自己的包装，以模拟某些容器不支持的操作仅仅是误导 - 从鼓励包装类的用户认为他们不需要小心他们的如果容器对性能或内存使用有特殊要求，可以选择容器。

Answer 2

因此，要回答你的问题

“那么，有没有一种更地道的方式比我自己的滚动模板专门为每个容器要做到这一点其他？

有很多方法可以做到去除

1. Sequence容器和无序容器的擦除（）返回删除项目之后的下一个 迭代器。

2. 关联容器的擦除（）不返回任何内容。

/* * 从vector或deque */

vector<int> vec = {1, 4, 1, 1, 1, 12, 18, 16}; // To remove all '1' 
    for (vector<int>::iterator itr = vec.begin(); itr != vec.end(); ++itr) { 
    if (*itr == 1) { 
     vec.erase(itr); 
    } 
    } // vec: { 4, 12, 18, 16} 
    // Complexity: O(n*m) 

    remove(vec.begin(), vec.end(), 1); // O(n) 
             // vec: {4, 12, 18, 16, ?, ?, ?, ?} 




    vector<int>::iterator newEnd = remove(vec.begin(), vec.end(), 1); // O(n) 
    vec.erase(newEnd, vec.end()); 

    // Similarly for algorithm: remove_if() and unique() 


    // vec still occupy 8 int space: vec.capacity() == 8 
    vec.shrink_to_fit(); // C++ 11 
    // Now vec.capacity() == 4 

    // For C++ 03: 
    vector<int>(vec).swap(vec); // Release the vacant memory 

/* * 取下列表 */

list<int> mylist = {1, 4, 1, 1, 1, 12, 18, 16}; 

    list<int>::iterator newEnd = remove(mylist.begin(), mylist.end(), 1); 
    mylist.erase(newEnd, mylist.end()); 


    mylist.remove(1); // faster 

/* 删除* 从关联容器或容器无序 */

multiset<int> myset = {1, 4, 1, 1, 1, 12, 18, 16}; 

    multiset<int>::iterator newEnd = remove(myset.begin(), myset.end(), 1); 
    myset.erase(newEnd, myset.end()); // O(n) 

    myset.erase(1); // O(log(n)) or O(1)