Недавно (из одного комментария SO) я узнал, что std::remove и std:remove_if являются стабильными. Я ошибаюсь, думая, что это ужасный выбор дизайна, поскольку он предотвращает определенные оптимизации?
Представьте себе удаление первого и пятого элементов 1M std::vector. Из-за стабильности мы не можем реализовать remove с помощью swap. Вместо этого мы должны сдвигать каждый оставшийся элемент.:(
Если бы мы не были ограничены стабильностью, мы могли бы (для RA и BD iter) иметь практически 2 итератора, один спереди, второй сзади, а затем использовать swap для вывода объектов, которые нужно удалить. Я уверен, что умные люди могли бы сделать еще лучше. Мой вопрос в целом, а не о конкретной оптимизации, о которой я говорю.
РЕДАКТИРОВАТЬ: обратите внимание, что С++ рекламирует принцип нулевой надбавки, а также есть алгоритмы сортировки 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
