Сбой стабильности std :: remove и std :: remove_if?

Недавно (из одного комментария ТАК) я узнал, чтоstd::remove а такжеstd:remove_if стабильны Я ошибаюсь, считая, что это ужасный выбор дизайна, поскольку он предотвращает определенные оптимизации?

Представьте себе удаление первого и пятого элементов 1Мstd::vector, Из-за стабильности мы не можем реализоватьremove со свопом. Вместо этого мы должны сдвинуть каждый оставшийся элемент. :(

Если бы мы не были ограничены стабильностью, мы могли бы (для RA и BD iter) фактически иметь 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

Ответы на вопрос(3)

Ваш ответ на вопрос