最近（1つのSOコメントから）私はそれを学び、std::remove安定std:remove_ifしています。特定の最適化を妨げるので、これがひどい設計選択であると考えるのは間違っていますか?
1M の 1 番目と 5 番目の要素を削除することを想像してくださいstd::vector。remove安定性のため、スワップで実装することはできません。代わりに、残りのすべての要素をシフトする必要があります。:(
安定性によって制限されていなければ、(RA と BD iter の場合) 実質的に 2 つの iter (前から 1 つ、後ろから 2 つ) を使用し、スワップを使用して削除するアイテムを終了させることができます。頭のいい人ならもっとうまくやれると思います。私の質問は一般的なものであり、私が話している特定の最適化についてではありません。
編集: C++ はゼロ オーバーヘッドの原則をアドバタイズすることに注意してください。また、ソート アルゴリズムもありstd::sortますstd::stable_sort。
EDIT2: 最適化は次のようになります。
の場合remove_if:
- bad_iter は、述語が true を返す要素を最初から探します。
- good_iter は、述語が false を返す要素を最後から探します。
両方が期待されるものを見つけたら、要素を交換します。で終了ですgood_iter <= bad_iter。
役立つ場合は、クイック ソート アルゴリズムの 1 つの 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