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

Question

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

想象一下,删除1M的第一个和第五个元素std::vector.由于稳定性,我们不能remove用swap 实现.相反,我们必须改变所有剩余的元素 :(

如果我们不受稳定性的限制,我们可以(对于RA和BD iter)实际上有2个iters,一个从前面,第二个从后面,然后使用swap来将待移除的项目结束.我相信聪明的人可能会做得更好.我的问题一般,而不是我正在谈论的具体优化.

编辑:请注意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排序是一个复杂的问题,有许多不同的解决方案和权衡和调整.所有"简单"排序算法平均来说都很慢.大多数标准算法都非常简单,并且是其中之一但不是.因此,我认为定义和作为单独的标准函数并不是很有意义.removesortstable_removeremove

编辑:你的编辑与我的调整(类似std::partition但不需要保持右边的值)对我来说似乎很合理.它需要一个双向迭代器,但在标准中有一些先例可用于在不同的迭代器类别上表现不同的算法,例如std::distance.因此,标准可以定义unstable_remove只需要一个前向迭代器,但如果它得到一个bidi迭代器就可以.标准可能不会列出算法,但它可能有一个短语,如"如果迭代器是双向的,最多min(k, n-k)移动的位置k是移除的元素数量",这实际上会强制它.但请注意,该标准目前尚未说明有多少动作remove_if,所以我认为将其固定下来并不是优先考虑的事情.

当然没有什么能阻止你实现自己的unstable_remove.

如果我们接受标准不需要指定不稳定的删除,则问题归结为它是否应该调用它所定义的函数stable_remove,预测removebidi迭代器的行为方式不同,并且对于正向迭代器可能表现不同如果一个聪明的启发式用于做一个不稳定的删除变得已经足够已知值得一个标准的功能.我不这样说:如果标准功能的名称不完全正规,那不是灾难.从STL中删除稳定性的保证可能非常具有破坏性remove_if.然后问题就变成了"STL为什么不称呼它stable_remove_if",除了所有答案中的所有要点之外,我只能回答这个问题,STL设计过程比标准化过程更快.

stable_remove还会打开一些关于其他标准函数的蠕虫,它们理论上可能具有不稳定的版本.对于一个特别愚蠢的例子应该copy被调用stable_copy,以防万一存在一些实现,它在复制时明显更快地反转元素的顺序？应该copy调用copy_forward,以便实现可以根据哪个更快地选择copy_backward和copy_forward调用copy哪个？委员会的部分工作是在某处画一条线.

我认为现实标准是合情合理的,单独定义a stable_remove和a 是明智的remove_with_some_other_constraints,但remove_in_some_unspecified_way只是没有为优化提供相同的机会sort_in_some_unspecified_way.Introsort是在1997年发明的,正如C++正在被标准化一样,但我不认为研究工作remove的本质就是它的本质和存在sort.我可能错了,优化remove可能是下一件大事,如果是这样,那么委员会就错过了一招.

Answer 2

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

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