std::remove 和 std::remove_if 设计的稳定性是否失败？

最近（从一条评论中）我了解到std::remove and std:remove_if是稳定的。我是否错误地认为这是一个糟糕的设计选择，因为它阻止了某些优化？

想象一下删除 1M 的第一个和第五个元素std::vector。由于稳定性原因，我们无法实施remove与交换。相反，我们必须移动所有剩余的元素。 :(

如果我们不受稳定性的限制，我们实际上可以（对于 RA 和 BD iter）有 2 个 iter，一个从前面，第二个从后面，然后使用交换来结束要删除的项目。我相信聪明的人也许可以做得更好。我的问题是一般性的，而不是我所说的具体优化。

EDIT:请注意，C++宣扬的是零开销原则，而且还有std::sort and std::stable_sort排序算法。

EDIT2:优化将类似于以下内容：

For remove_if:

• bad_iter 从头开始​​查找谓词返回 true 的元素。
• good_iter 从末尾查找谓词返回 false 的元素。

当双方都找到了预期的结果时，他们就会交换各自的元素。终止时间为good_iter <= bad_iter.

如果有帮助的话，请将其想象为快速排序算法中的一个迭代器，但我们不将它们与特殊元素进行比较，而是使用上面的谓词。

EDIT3:我尝试着寻找最坏的情况（最坏的情况remove_if- 注意谓词为真的可能性是多么的少），我得到了这个：

#include <vector>
#include <string>
#include <iostream>
#include <map>
#include <algorithm>
#include <cassert>
#include <chrono>
#include <memory>
using namespace std;
int main()
{  
    vector<string> vsp;
    int n;
    cin >> n;
    for (int i =0; i < n; ++i)
    {   string s = "123456";
        s.push_back('a' + (rand() %26));
        vsp.push_back(s);
    }
    auto vsp2 = vsp;
    auto remove_start = std::chrono::high_resolution_clock::now();
    auto it=remove_if(begin(vsp),end(vsp), [](const string& s){ return s < "123456b";});
    vsp.erase(it,vsp.end());
    cout << vsp.size() << endl;
    auto remove_end = std::chrono::high_resolution_clock::now();
    cout << "erase-remove: " << chrono::duration_cast<std::chrono::milliseconds>(remove_end-remove_start).count() << " milliseconds\n";

    auto partition_start = std::chrono::high_resolution_clock::now();
    auto it2=partition(begin(vsp2),end(vsp2), [](const string& s){ return s >= "123456b";});
    vsp2.erase(it2,vsp2.end());
    cout << vsp2.size() << endl;
    auto partition_end = std::chrono::high_resolution_clock::now();
    cout << "partition-remove: " << chrono::duration_cast<std::chrono::milliseconds>(partition_end-partition_start).count() << " milliseconds\n";
}



C:\STL\MinGW>g++ test_int.cpp -O2 && a.exe
12345678
11870995
erase-remove: 1426 milliseconds
11870995
partition-remove: 658 milliseconds

对于其他用途，分区会更快、相同或更慢。让我感到困惑。 ：D

我假设你问的是一个假设的定义stable_remove成为什么remove目前是，并且remove然而，实施者认为最好以任何顺序给出正确的值。期望实施者能够在做与以下完全相同的事情的基础上进行改进stable_remove.

实际上，图书馆不能easily做这个优化。这取决于数据，但您不想在决定如何删除每个元素之前花费太长时间来计算将删除多少个元素。例如，您可以进行一次额外的传递来对它们进行计数，但在很多情况下，额外的传递效率很低。仅仅因为在某些情况下不稳定的删除比稳定的删除速度更快，并不一定意味着在两者之间进行选择的自适应算法是一个不错的选择。

我认为之间的区别remove and sort排序是known这是一个复杂的问题，有很多不同的解决方案、权衡和调整。所有“简单”排序算法都很慢一般。大多数标准算法都非常简单，并且remove是其中之一但是sort不是。我认为定义它没有多大意义stable_remove and remove作为单独的标准功能。

编辑：您使用我的调整进行的编辑（类似于std::partition但不需要将值保留在右侧）对我来说似乎相当合理。它需要一个双向迭代器，但标准中已有在不同迭代器类别上表现不同的算法的先例，例如std::distance。因此标准可以定义unstable_remove只有requires一个前向迭代器，但如果它得到一个 bidi 迭代器，你就可以做你的事情了。该标准可能不会列出算法，但它可能有这样的短语“如果迭代器是双向的，则最多min(k, n-k)移动到哪里k是删除的元素数量”，这实际上会强制它。但请注意，该标准目前并未说明移动次数remove_if确实如此，所以我认为确定这一点根本不是一个优先事项。

当然，没有什么可以阻止您实现自己的unstable_remove.

如果我们接受标准不需要指定不稳定的删除，那么问题就归结为是否应该调用它定义的函数stable_remove, 展望未来remove对于双向迭代器来说，它的行为有所不同，并且如果用于执行不稳定删除的一些聪明的启发式方法变得足够众所周知，值得作为标准函数，那么对于前向迭代器来说，它的行为也可能有所不同。我想说不是：如果标准函数的名称不完全规则，那并不是一场灾难。从 STL 中删除稳定性保证可能会造成相当大的破坏remove_if。那么问题就变成了，“为什么 STL 不把它称为stable_remove_if”，对此我只能回答，除了所有答案中提出的所有观点之外，STL设计过程比标准化过程要快得多。

stable_remove还会打开一个关于其他标准功能的蠕虫罐头，这些功能可能理论上有不稳定的版本。对于一个特别愚蠢的例子应该copy叫做stable_copy，以防万一存在某种实现，在复制时反转元素的顺序明显更快？应该copy叫做copy_forward，以便实现可以选择哪一个copy_backward and copy_forward被称为copy根据哪个更快？委员会的部分工作就是在某处划定界限。

我认为实际上当前的标准是明智的，单独定义一个stable_remove and a remove_with_some_other_constraints, but remove_in_some_unspecified_way只是没有提供同样的优化机会sort_in_some_unspecified_way做。 Introsort 是在 1997 年发明的，当时 C++ 正在标准化，但我不认为周围的研究工作remove与过去和周围的情况完全一样sort。我可能错了，正在优化remove可能是下一件大事，如果是这样，那么委员会就错过了一个机会。