Ostatnio (z jednego komentarza SO) dowiedziałem się tegostd::remove istd:remove_if są stabilne. Czy mylę się, sądząc, że jest to okropny wybór, ponieważ uniemożliwia pewne optymalizacje?

Wyobraź sobie usunięcie pierwszego i piątego elementu 1Mstd::vector. Z powodu stabilności nie możemy wdrożyćremove z zamianą. Zamiast tego musimy przesunąć każdy pozostały element. :(

Gdybyśmy nie byli ograniczeni przez stabilność, moglibyśmy (dla RA i BD iter) praktycznie mieć 2 itery, jeden z przodu, drugi z tyłu, a następnie użyć swap, aby doprowadzić do usunięcia rzeczy do końca. Jestem pewien, że mądrzy ludzie mogą być może nawet lepiej. Moje pytanie jest ogólne, a nie o konkretnej optymalizacji, o której mówię.

EDYTOWAĆ: proszę zauważyć, że C ++ reklamuje zasadę zerowego obciążenia, a także istniejąstd::sort istd::stable_sort algorytmy sortowania.

EDIT2: optymalizacja byłaby następująca:

Dlaremove_if:

bad_iter patrzy od początku na te elementy, dla których predykat zwraca wartość true.good_iter patrzy od końca na te elementy, dla których predykat zwraca false.

kiedy obaj znajdą to, czego się oczekuje, zamieniają swoje elementy. Zakończenie jest nagood_iter <= bad_iter.

Jeśli to pomoże, pomyśl o tym jak o jednym w algorytmie szybkiego sortowania, ale nie porównujemy ich do specjalnego elementu, ale zamiast tego używamy powyższego predykatu.

EDIT3: Grałem i próbowałem znaleźć najgorszy przypadek (najgorszy przypadekremove_if - zwróć uwagę, jak rzadko orzecznik byłby prawdziwy) i dostałem to:

#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

Dla innych zastosowań partycja jest nieco szybsza, taka sama lub wolniejsza. Zabarwienie mnie zdziwiło. :RE