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

Question

最近(从一个 SO 评论)我了解到 std::remove 和 std:remove_if 是稳定的。我认为这是一个糟糕的设计选择，因为它阻止了某些优化，我错了吗？

想象一下删除 1M std::vector 的第一个和第五个元素。因为稳定性，我们不能用swap来实现remove。相反，我们必须移动每个剩余的元素。 :(

如果我们不受稳定性的限制，我们可以(对于 RA 和 BD 迭代器)实际上有 2 个迭代器，一个在前面，第二个在后面，然后使用交换来结束要删除的项目。我相信聪明的人可能会做得更好。我的问题是一般性的，而不是我正在谈论的特定优化。

编辑: 请注意，C++ 宣传零开销原则，并且还有 std::sort 和 std::stable_sort 排序算法。

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

对于 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

Answer 1

我假设您是在询问 stable_remove 的假设定义是什么remove目前是，和 remove然而实现者认为最好以任何顺序给出正确的值。希望实现者能够在与 stable_remove 完全相同的情况下进行改进。 .

在实践中，库不能轻易地进行这种优化。这取决于数据，但在决定如何删除每个元素之前，您不想花太长时间计算将删除多少元素。例如，您可以执行额外的传递来计算它们，但在很多情况下，额外传递是低效的。仅仅因为在某些情况下不稳定的移除比稳定的更快并不一定意味着在两者之间进行选择的自适应算法是一个不错的选择。

我认为 remove 之间的区别和 sort众所周知，排序是一个复杂的问题，有很多不同的解决方案以及权衡和调整。所有“简单”排序算法的平均速度都很慢。大多数标准算法都非常简单，remove是其中之一，但 sort不是。我认为定义 stable_remove 没有多大意义。和 remove作为单独的标准功能。

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

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

如果我们接受标准不需要指定不稳定删除，那么问题就归结为它定义的函数是否应该被称为 stable_remove ，期待 future remove这对于 bidi 迭代器的行为不同，如果一些用于执行不稳定删除的巧妙启发式方法变得众所周知值得一个标准函数，则对于前向迭代器的行为可能会有所不同。我会说不是:如果标准函数的名称不完全规则，这不是灾难。从 STL 的 remove_if 中删除稳定性保证可能会非常具有破坏性。 .那么问题就变成了“为什么 STL 不叫它 stable_remove_if”，对此我只能回答，除了所有答案中的所有要点外，STL 设计过程比标准化过程更快.
stable_remove还会打开一堆关于其他标准功能的蠕虫，这些功能理论上可能具有不稳定的版本。对于一个特别愚蠢的例子应该 copy被称为 stable_copy ，以防万一存在某些实现，在复制时反转元素的顺序明显更快？应copy被称为 copy_forward ，以便实现可以选择 copy_backward 中的哪一个和 copy_forward由 copy 调用根据哪个更快？委员会的部分工作是在某处划清界限。

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