remove_if equivalente para std :: map

Question

Eu estava tentando apagar um intervalo de elementos do mapa com base em determinada condição. Como posso fazer isso usando algoritmos STL?

Inicialmente eu pensei em usar remove_if mas não é possível, como remove_if não funciona para recipiente associativo.

Existe alguma "remove_if" algoritmo equivalente que funciona por mapa?

Como uma opção simples, pensei em loop através do mapa e apagar. Mas é looping através do mapa e apagar uma opção segura? (Como iteradores ficar inválido após apagar)

Eu usei o exemplo seguinte:

bool predicate(const std::pair<int,std::string>& x)
{
    return x.first > 2;
}

int main(void) 
{

    std::map<int, std::string> aMap;

    aMap[2] = "two";
    aMap[3] = "three";
    aMap[4] = "four";
    aMap[5] = "five";
    aMap[6] = "six";

//      does not work, an error
//  std::remove_if(aMap.begin(), aMap.end(), predicate);

    std::map<int, std::string>::iterator iter = aMap.begin();
    std::map<int, std::string>::iterator endIter = aMap.end();

    for(; iter != endIter; ++iter)
    {
            if(Some Condition)
            {
                            // is it safe ?
                aMap.erase(iter++);
            }
    }

    return 0;
}

Answer 1

Quase.

for(; iter != endIter; ) {
            if (Some Condition) {
                    aMap.erase(iter++);
            } else {
                    ++iter;
            }
}

O que você tinha originalmente iria incrementar o iterador duas vezes se você apagou um elemento a partir dele; você poderia pular elementos que precisavam ser apagados.

Este é um algoritmo comum que eu vi usado e documentado em muitos lugares.

[EDIT] Está certo que iteradores são invalidadas após um apagamento, mas apenas iterators referenciando o elemento que é apagado, outros iterators ainda são válidos. Daí usando iter ++ na chamada apagar ().

Answer 2

erase_if para std :: map (e outros recipientes)

Eu uso o seguinte modelo para isso mesmo.

namespace stuff {
  template< typename ContainerT, typename PredicateT >
  void erase_if( ContainerT& items, const PredicateT& predicate ) {
    for( auto it = items.begin(); it != items.end(); ) {
      if( predicate(*it) ) it = items.erase(it);
      else ++it;
    }
  }
}

Isso não vai retornar nada, mas ele irá remover os itens da std :: map.

Exemplo de uso:

// 'container' could be a std::map
// 'item_type' is what you might store in your container
using stuff::erase_if;
erase_if(container, []( item_type& item ) {
  return /* insert appropriate test */;
});

Segundo exemplo (permite que você passe em um valor de teste):

// 'test_value' is value that you might inject into your predicate.
// 'property' is just used to provide a stand-in test
using stuff::erase_if;
int test_value = 4;  // or use whatever appropriate type and value
erase_if(container, [&test_value]( item_type& item ) {
  return item.property < test_value;  // or whatever appropriate test
});

Answer 3

Eu tenho essa documentação do excelente SGI STL referência :

Mapa tem a propriedade importante que a inserção de um novo elemento para um mapa não invalida iteradores que apontam para elementos existentes. apagar uma elemento de um mapa também não invalida qualquer iteradores, exceto, Claro que, para iteradores que realmente apontar para o elemento que está sendo apagados.

Assim, o iterador você tem que está apontando para o elemento a ser apagada vontade, naturalmente, ser invalidada. Fazer algo como isto:

if (some condition)
{
  iterator here=iter++;
  aMap.erase(here)
}

Answer 4

O código original tem apenas um problema:

for(; iter != endIter; ++iter)
{
    if(Some Condition)
    {
        // is it safe ?
        aMap.erase(iter++);
    }
}

Aqui a iter é incrementado uma vez no loop for e outra vez em apagar, o que provavelmente vai acabar em algum loop infinito.

Answer 5

Agora, std::experimental::erase_if está disponível em <experimental/map> cabeçalho.

Veja: http://en.cppreference.com/w/cpp / experimental / map / erase_if

Answer 6

A partir das notas de fundo de:

http://www.sgi.com/tech/stl/PairAssociativeContainer.html

um par associativa do recipiente não pode fornecer iterators mutáveis ??(como definido nos requisitos Trivial Iterator), porque o tipo de valor de uma iteração mutável deve ser atribuíveis, e o par não pode ser atribuído. No entanto, um par associativa recipiente pode fornecer iterators que não são completamente constantes: iterators de tal modo que a expressão (* i) .segunda = d é válido.

Answer 7

Primeiro

Mapa tem a propriedade importante que inserir um novo elemento em um mapa não invalida iteradores que apontam para elementos existentes. Apagar um elemento de um mapa também não invalida qualquer iteradores, exceto, é claro, para iteradores que realmente apontam para o elemento que está sendo apagado.

Em segundo lugar, o seguinte código é bom

for(; iter != endIter; )
{
    if(Some Condition)
    {
        aMap.erase(iter++);
    }
    else
    {
        ++iter;
    }
}

Ao chamar uma função, os parâmetros são avaliados antes da chamada para essa função.

Assim, quando iter ++ é avaliado antes da chamada para apagar, o operador ++ do iterador irá devolver o item atual e irá apontar para o item seguinte após a chamada.

Answer 8

IMHO não há remove_if() equivalente.
Você não pode reordenar um mapa.
Então remove_if() não pode colocar seus pares de juros no final em que você pode chamar erase().

Answer 9

Com base na resposta do Iron Savior Para aqueles que gostariam de fornecer uma gama mais ao longo das linhas de DST iterators tomada funcionais .

template< typename ContainerT, class _FwdIt, class _Pr >
void erase_if(ContainerT& items, _FwdIt it, _FwdIt _Last, _Pr _Pred) {
    for (; it != _Last; ) {
        if (_Pred(*it)) it = items.erase(it);
        else ++it;
    }
}

curioso para saber se há alguma maneira de perder os itens ContainerT e conseguir que a partir do iterator.

Answer 10

A resposta de Steve Folly eu sinto o mais eficiente.

Aqui é outra fácil, mas menos eficiente solução :

Os usos solução remove_copy_if para copiar os valores que queremos em um novo recipiente, troca então o conteúdo da embalagem original com os do novo:

std::map<int, std::string> aMap;

...
//Temporary map to hold the unremoved elements
std::map<int, std::string> aTempMap;

//copy unremoved values from aMap to aTempMap
std::remove_copy_if(aMap.begin(), aMap.end(), 
                    inserter(aTempMap, aTempMap.end()),
                    predicate);

//Swap the contents of aMap and aTempMap
aMap.swap(aTempMap);

Answer 11

Se você quiser apagar todos os elementos com maior chave que 2, então a melhor maneira é

map.erase(map.upper_bound(2), map.end());

só funciona para faixas, porém, não para qualquer predicado.

Answer 12

Eu uso como esta

 std::map<int, std::string> users;    
 for(auto it = users.begin(); it <= users.end()) {
    if(<condition>){
      it = users.erase(it);
    } else {
    ++it;
    }
 }