Como excluir um elemento de um std :: vector de std :: pair com base no valor .first?

Question

Ok, então eu tenho uma classificação std::vector<std::pair<int,double>>. O que não consigo descobrir é como posso excluir uma entrada do vetor com base no valor do "primeiro" elemento do std :: pair (int). Irei potencialmente fazer isso várias vezes no meu algoritmo, então prefiro não iterar por meio do vetor todas as vezes (que pode conter até um milhão de entradas). Eu sei que podemos facilmente remover elementos com base no índice usando std :: erase ou remove, mas há uma maneira de fazer isso com base no valor do primeiro elemento do par? Ou podemos obter o índice desse elemento e, em seguida, usar std :: erase?

Nota: o valor do primeiro elemento do std :: pair é único para o vetor. Dadas as restrições do programa, preciso usar o vetor (ou seja, não posso usar mapa ou contêiner diferente).

Exemplo: eu tenho um contêiner como este:

std::vector<std::pair<int,double>> vec = { {20, 60.3}, ... {10, -20.2}, {1020, -80.9}};

Quero remover rapidamente o elemento com o primeiro elemento == 10 do vetor, mas não sei em qual índice do vetor ele está localizado.

Answer 1

Seu vetor é classificado, então você pode (e deve) usar std::lower_bounde std::upper_bound.

Eles fornecem um intervalo que corresponde a algum critério (desde que a ordem de classificação do contêiner torne isso significativo) e faz isso por meio de uma boa pesquisa binária.

Fornece um comparador personalizado que examina apenas o primeiro item de cada par.

---

#include <utility>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<std::pair<int,double>> data = { {20, 60.3}, {10, -20.2}, {1020, -80.9}};
    
    const int intToSearchFor = 10;
    
    const auto lower = std::lower_bound(
       data.begin(),
       data.end(),
       intToSearchFor,
       [](const std::pair<int, double>& el, const int i)
       {
          return el.first < i;
       }
    );
    
    const auto upper = std::upper_bound(
       data.begin(),
       data.end(),
       intToSearchFor,
       [](const int i, const std::pair<int, double>& el)
       {
          return i < el.first;
       }
    );
    
    data.erase(lower, upper);
}

Se os seus ints são únicos, você não precisa da verificação do limite superior e pode simplesmente apagar o elemento na posição lower... mas primeiro você terá que garantir que é realmente igual a i(pode ser maior que), e também que não é data.end().

---

Este algoritmo implementa basicamente std::map::erase(ou std::multimap::erase), mas com dados classificados em armazenamento contíguo. É ótimo para pesquisa rápida de conjuntos de dados relativamente pequenos; infelizmente, você está preso ao custo de reduzir os elementos subsequentes após um apagamento . Os mapas evitam isso armazenando dados indiretamente. Um deque pode ser um bom meio-termo para você. Só você pode saber, com base em seus dados normais e padrões de acesso.

Você também pode descobrir que, como o tipo de elemento é apenas a pair<int, double>, seu compilador pode trocar um monte de operator=chamadas por um simples agradável memmove, que é muito rápido na escala de que você está falando hoje em dia.