Kürzlich (aus einem SO-Kommentar) habe ich das gelerntstd::remove undstd:remove_if sind stabil. Bin ich falsch zu denken, dass dies eine schreckliche Design-Wahl ist, da es bestimmte Optimierungen verhindert?

Stellen Sie sich vor, Sie entfernen das erste und fünfte Element eines 1Mstd::vector. Aus Stabilitätsgründen können wir das nicht umsetzenremove mit Swap. Stattdessen müssen wir jedes verbleibende Element verschieben. :(

Wenn wir nicht durch die Stabilität eingeschränkt wären, könnten wir (für RA- und BD-Iter) praktisch 2 Iter haben, einen von vorne, einen von hinten, und dann Swap verwenden, um zu entfernende Elemente zu beenden. Ich bin sicher, kluge Leute könnten es vielleicht noch besser machen. Meine Frage betrifft im Allgemeinen nicht die spezifische Optimierung, über die ich spreche.

BEARBEITEN: Bitte beachten Sie, dass C ++ das Null-Overhead-Prinzip ankündigt, und es gibt es auchstd::sort undstd::stable_sort Sortieralgorithmen.

EDIT2: Die Optimierung würde ungefähr so ​​aussehen:

Zumremove_if:

bad_iter sucht von Anfang an nach den Elementen, für die das Prädikat true zurückgibt.good_iter sucht am Ende nach den Elementen, für die das Prädikat false zurückgibt.

wenn beide gefunden haben, was erwartet wird, tauschen sie ihre Elemente aus. Kündigung ist umgood_iter <= bad_iter.

Wenn es hilft, stellen Sie es sich wie einen Iter im schnellen Sortieralgorithmus vor, aber wir vergleichen sie nicht mit einem speziellen Element, sondern verwenden stattdessen das obige Prädikat.

EDIT3: Ich habe herumgespielt und versucht, den schlimmsten Fall zu findenremove_if - beachte, wie selten das Prädikat wahr sein würde) und ich habe folgendes erhalten:

#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

Für andere Verwendungen ist die Partition etwas schneller, gleich oder langsamer. Färbe mich verwirrt. : D