remove_if équivalent pour std :: map

Question

J'essayais d'effacer une série d'éléments de la carte en fonction de conditions particulières. Comment puis-je le faire en utilisant des algorithmes STL?

Initialement, je pensais utiliser remove_if mais cela n’est pas possible car remove_if ne fonctionne pas pour le conteneur associatif.

Y a-t-il des " remove_if " algorithme équivalent qui fonctionne pour la carte?

Comme une simple option, j’ai pensé faire une boucle sur la carte et l’effacer. Mais parcourir la carte et effacer est-il une option sûre (les itérateurs devenant invalides après l'effacement)

J'ai utilisé l'exemple suivant:

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

Presque.

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

Ce que vous aviez initialement incrémenterait l'itérateur deux fois si vous effaciez un élément de celui-ci; vous pouvez potentiellement ignorer les éléments à effacer.

C’est un algorithme commun que j’ai vu utilisé et documenté à de nombreux endroits.

[EDIT] Vous avez raison de dire que les itérateurs sont invalidés après un effacement, mais que seuls les itérateurs référençant l'élément qui est effacé, les autres itérateurs sont toujours valides. Par conséquent, utiliser iter ++ dans l'appel erase ().

Answer 2

erase_if pour std :: map (et autres conteneurs)

J'utilise le modèle suivant pour cette chose même.

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

Ceci ne renverra rien, mais supprimera les éléments de std :: map.

Exemple d'utilisation:

// '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 */;
});

Deuxième exemple (vous permet de transmettre une valeur de test):

// '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

J'ai obtenu cette documentation à partir de la excellente référence de SGL STL :

  

La carte a la propriété importante qui   insérer un nouvel élément dans une carte   n'invalide pas les itérateurs qui   pointez sur des éléments existants. Effacer un   élément d'une carte n'a pas non plus   invalider tous les itérateurs, sauf   Bien sûr, pour les itérateurs qui réellement   pointez sur l'élément qui est   effacé.

L’itérateur que vous avez et qui pointe sur l’élément à effacer sera bien sûr invalidé. Faites quelque chose comme ça:

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

Answer 4

Le code d'origine n'a qu'un problème:

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

Ici, le iter est incrémenté une fois dans la boucle for et une autre fois dans erase, ce qui aboutira probablement dans une boucle infinie.

Answer 5

Maintenant, std::experimental::erase_if est disponible dans l'en-tête <experimental/map>.

Voir: http://fr.cppreference.com/w/cpp / experimental / map / erase_if

Answer 6

À partir des notes de bas de:

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

un conteneur associatif de paires ne peut pas fournir d'itérateurs mutables (tels que définis dans les exigences de l'Itérateur trivial), car le type de valeur d'un itérateur mutable doit être Assignable et la paire n'est pas Assignable. Cependant, un conteneur associatif par paire peut fournir des itérateurs qui ne sont pas complètement constants: des itérateurs tels que l'expression (* i) .second = d est valide.

Answer 7

Premier

  

La carte a la propriété importante que l'insertion d'un nouvel élément dans une carte n'invalide pas les itérateurs qui pointent sur des éléments existants. L’effacement d’un élément d’une carte n’invalide pas non plus les itérateurs, à l’exception, bien entendu, des itérateurs qui pointent réellement sur l’élément en cours d’effacement.

Deuxièmement, le code suivant est bon

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

Lors de l'appel d'une fonction, les paramètres sont évalués avant l'appel de cette fonction.

Ainsi, lorsque iter ++ est évalué avant l'appel à effacer, l'opérateur ++ de l'itérateur renvoie l'élément en cours et pointe vers l'élément suivant après l'appel.

Answer 8

À mon humble avis, il n'y a pas remove_if() d'équivalent.
Vous ne pouvez pas réorganiser une carte.
Donc, erase() ne pouvez pas mettre vos paires d'intérêt à la fin sur lesquelles vous pouvez appeler <=>.

Answer 9

Basé sur la réponse d'Iron Savior pour ceux qui souhaitent proposer une gamme plus proche des itérateurs de prise de fonction standard .

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

Curieux de savoir s’il existe un moyen de perdre les éléments de ContainerT et de l’obtenir de l’itérateur.

Answer 10

La réponse de Steve Folly Je me sens plus efficace.

Voici une autre solution simple mais moins efficace :

La solution utilise remove_copy_if pour copier les valeurs souhaitées dans un nouveau conteneur, puis échange le contenu du conteneur d'origine avec ceux du nouveau:

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

Si vous souhaitez effacer tous les éléments dont la clé est supérieure à 2, la meilleure solution est

.

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

Ne fonctionne que pour les plages, pas pour les prédicats.

Answer 12

j'utilise comme ça

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