Recientemente (de un comentario SO) aprendí questd::remove ystd:remove_if son estables ¿Me equivoco al pensar que esta es una elección de diseño terrible ya que impide ciertas optimizaciones?

Imagina eliminar los elementos primero y quinto de un 1M.std::vector. Debido a la estabilidad, no podemos implementarremove Con swap. En su lugar, debemos cambiar cada elemento restante. :(

Si no estuviéramos limitados por la estabilidad, podríamos (para RA y BD iter) prácticamente tener 2 iters, uno desde el frente, el segundo desde atrás, y luego usar el intercambio para poner los elementos que se quitan para terminar. Estoy seguro de que las personas inteligentes tal vez podrían hacerlo incluso mejor. Mi pregunta es en general, no sobre la optimización específica de la que estoy hablando.

EDITAR: Tenga en cuenta que C ++ anuncia el principio de sobrecarga cero, y también haystd::sort ystd::stable_sort ordenar algoritmos.

EDIT2: La optimización sería algo como lo siguiente:

porremove_if:

bad_iter busca desde el principio aquellos elementos para los que el predicado devuelve true.good_iter busca desde el final aquellos elementos para los que el predicado devuelve false.

cuando ambos han encontrado lo que se espera, intercambian sus elementos. La terminación es a lasgood_iter <= bad_iter.

Si ayuda, considérelo como un iterador en un algoritmo de clasificación rápida, pero no los comparamos con un elemento especial, sino que usamos el predicado anterior.

EDIT3: Jugué y traté de encontrar el peor de los casos (el peor de los casosremove_if - note cuán raramente el predicado sería verdadero) y obtuve esto:

#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

Para otros usos, la partición es un poco más rápida, igual o más lenta. Coloréame desconcertado. :RE