14

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

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

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

编辑：std::sort请注意，C++ 宣传零开销原则，还有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

4

3 回答 3

13

我假设您询问的是当前的假设定义stable_remove，remove并且remove要实施，但是实施者认为最好以任何顺序给出正确的值。期望实现者能够在与stable_remove.

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

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

编辑：您对我的调整进行的编辑（类似于std::partition但不需要保留右侧的值）对我来说似乎很合理。它需要一个双向迭代器，但在标准中有先例，算法在不同的迭代器类别上表现不同，例如std::distance. 因此，标准可以定义unstable_remove只需要一个前向迭代器，但如果它得到一个双向迭代器就可以了。该标准可能不会对算法进行布局，但它可能会有一个短语，例如“如果迭代器是双向的，则最多只在移除元素数量的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和copy_forward被调用？copy委员会的部分工作是在某处划清界限。

我认为实际上当前的标准是明智的，分开定义 astable_remove和 a是明智的remove_with_some_other_constraints，但remove_in_some_unspecified_way只是没有提供同样的优化机会sort_in_some_unspecified_way。Introsort 是在 1997 年发明的，就像 C++ 正在标准化一样，但我不认为围绕它的研究工作remove完全是它过去和现在的样子sort。我可能错了，优化remove可能是下一件大事，如果是这样，那么委员会就错过了一个窍门。

于 2012-12-11T10:47:32.023 回答
3

std::remove指定使用前向迭代器。

从头到尾使用一对迭代器的方法要么增加对迭代器的要求，从而降低函数的效用，要么违反/恶化渐近复杂性保证。

于 2012-12-11T11:15:36.600 回答
1

> 3年后回答我自己的问题:)
是的，这是一个“失败”。

有一个提案D0041R0将添加unstable_remove. 有人可能会争辩说，仅仅因为有一项提案要补充std::unstable_remove，并不意味着这std::remove是一个错误，但我不同意。:)

于 2016-04-27T19:49:56.297 回答