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

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

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

如果我们不受稳定性的限制，我们可以（对于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