Recentemente (de um comentário SO), aprendi questd::remove estd:remove_if são estáveis. Estou errado em pensar que essa é uma péssima escolha de design, já que ela impede certas otimizações?

Imagine remover o primeiro e quinto elementos de um 1Mstd::vector. Por causa da estabilidade, não podemos implementarremove com swap. Em vez disso, devemos mudar todos os elementos restantes. :(

Se não estivéssemos limitados pela estabilidade, poderíamos (para RA e BD iter) praticamente ter 2 iters, um da frente, o segundo de trás, e depois usar o swap para trazer itens a serem removidos para o final. Tenho certeza que pessoas inteligentes talvez fiquem ainda melhores. Minha pergunta é, em geral, não sobre otimização específica da qual estou falando.

EDITAR: por favor, note que C ++ anuncia o princípio de sobrecarga zero, e também existemstd::sort estd::stable_sort classificar algoritmos.

EDIT2: otimização seria algo como o seguinte:

Pararemove_if:

bad_iter olha desde o início para os elementos para os quais o predicado retorna verdadeiro.good_iter olha do final para os elementos para os quais o predicado retorna falso.

quando ambos encontraram o que é esperado, eles trocam seus elementos. A rescisão é emgood_iter <= bad_iter.

Se isso ajudar, pense nisso como um algoritmo de ordenação rápida, mas não os comparamos a um elemento especial, mas usamos o predicado acima.

EDIT3: Eu brinquei e tentei encontrar o pior caso (pior caso pararemove_if - perceba como raramente o predicado seria verdade) e eu entendi:

#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 outros usos, a partição é um pouco mais rápida, igual ou mais lenta. Colora-me intrigado. : D