remove_if equivalente para std :: map

Eu estava tentando apagar uma série de elementos do mapa com base em uma condição particular. Como faço isso usando algoritmos STL?

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

Existe algum algoritmo equivalente "remove_if" que funciona para o mapa?

Como uma opção simples, pensei em percorrer o mapa e apagar. Mas repetir o mapa e apagar é uma opção segura? (Já que os iteradores ficam inválidos após o apagamento)

Usei o seguinte exemplo:

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;
}

Quase.

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

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

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

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

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

Eu uso o seguinte modelo para isso.

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 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
});

Agora, std::experimental::erase_ifestá disponível no cabeçalho <experimental/map>.

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

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

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

Portanto, o iterador que você possui que está apontando para o elemento a ser apagado, obviamente, 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, o que provavelmente terminará em algum loop infinito.

Aqui está uma solução elegante.

for (auto it = map.begin(); it != map.end();)
{   
    (SomeCondition) ? map.erase(it++) : (++it);
}

Das notas de fundo de:

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

um Container Associativo de Par 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 Atribuível e o par não é Atribuível. No entanto, um Container Associativo de Par pode fornecer iteradores que não são completamente constantes: iteradores de forma que a expressão (* i) .second = d seja válida.

Primeiro

Map tem a propriedade importante de que inserir um novo elemento em um mapa não invalida os iteradores que apontam para os elementos existentes. Apagar um elemento de um mapa também não invalida nenhum iterador, exceto, é claro, para iteradores que realmente 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 função, os parâmetros são avaliados antes da chamada dessa função.

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.

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

Baseado na resposta do Iron Savior Para aqueles que gostariam de fornecer uma gama mais próxima das linhas de iteradores de tomadas funcionais padrão.

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 ContainerTitens e obtê-los do iterador.

A resposta de Steve Folly Eu me sinto mais eficiente.

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

A solução usa remove_copy_ifpara copiar os valores que queremos em um novo contêiner e, em seguida, trocar o conteúdo do contêiner original pelo 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);

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

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

Porém, funciona apenas para intervalos, não para qualquer predicado.

Eu uso assim

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