remove_if equivalente para std :: map

Eu estava tentando apagar uma gama de elementos do mapa com base em condições particulares. Como faço isso usando algoritmos STL?

Inicialmente, pensei em usar remove_if mas não é possível, pois remove_if não funciona para o container associativo.

Existe algum algoritmo equivalente “remove_if” que funcione para o mapa?

Como uma opção simples, pensei em percorrer o mapa e apagar. Mas está percorrendo o mapa e apagando uma opção segura (como os iteradores ficam inválidos depois de apagados)

Eu usei o seguinte exemplo:

 bool predicate(const std::pair& x) { return x.first > 2; } int main(void) { std::map 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::iterator iter = aMap.begin(); std::map::iterator endIter = aMap.end(); for(; iter != endIter; ++iter) { if(Some Condition) { // is it safe ? aMap.erase(iter++); } } return 0; } 

Quase.

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

O que você tinha originalmente incrementaria o iterador duas vezes se você apagasse um elemento dele; você poderia pular os elementos que precisavam ser apagados.

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

[EDITAR] Você está correto que os iteradores são invalidados após um apagamento, mas apenas os iteradores que fazem referência ao elemento que é apagado, outros iteradores ainda são válidos. Portanto, usando o iter ++ na chamada erase ().

erase_if para std :: map (e outros contêineres)

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 retornará nada, mas removerá os itens do 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 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 }); 

Eu recebi esta documentação da excelente referência SGI STL :

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

Assim, o iterador que você está apontando para o elemento a ser apagado naturalmente será invalidado. Faça algo assim:

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

O código original tem apenas um problema:

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

Aqui, o iter é incrementado uma vez no loop for e outra vez no erase, que provavelmente terminará em algum loop infinito.

Das notas de fundo de:

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

Um Par Associative Container não pode fornecer iteradores mutáveis ​​(conforme definido nos requisitos do Trivial Iterator), porque o tipo de valor de um iterador mutável deve ser Assignable e o par não é Assignable. No entanto, um Contêiner Associativo em Par pode fornecer iteradores que não são completamente constantes: iteradores tais que a expressão (* i) .segundo = d é válida.

Primeiro

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

Em segundo lugar, o código a seguir é bom

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

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

Portanto, quando o iter ++ é avaliado antes da chamada para apagar, o operador ++ do iterador retornará o item atual e apontará para o próximo item após a chamada.

Com base na resposta do Iron Savior Para aqueles que gostariam de fornecer um intervalo mais ao longo das linhas de iteradores std 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 se houver alguma maneira de perder os itens ContainerT e obter isso do iterador.

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

A resposta de Steve Folly me sinto mais eficiente.

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

A solução usa remove_copy_if para copiar os valores que desejamos em um novo contêiner e, em seguida, troca o conteúdo do contêiner original pelos novos:

 std::map aMap; ... //Temporary map to hold the unremoved elements std::map 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); 

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

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

Funciona apenas para intervalos, não para qualquer predicado.

Agora, std::experimental::erase_if está disponível no header .

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