(C++) Mauvaise opération de suppression de carte et mécanisme d'implémentation sous-jacent des itérateurs de conteneurs en STL

1. Mauvaise opération de suppression de carte

Supposons qu'il y ait un conteneur de carte utilisé pour stocker le nombre d'étudiants correspondant à chaque province d'origine dans une classe universitaire, la clé est que la province est écrite en chinois complet et que la valeur est le nombre d'étudiants. Il nous faut maintenant supprimer l'enregistrement avec le nombre de personnes 0. Le code de suppression est le suivant :

map<string,int > countMap;for(map<string,int>::iterator it=countMap.begin();it!=countMap.end();++it)
{if(it->second==0)
{
        countMap.erase(it);
    }
}

À première vue, il n'y a pas de problème si vous regardez bien, il y a d'énormes fosses. Les principaux pièges cachés dans les opérations de suppression et d'insertion du conteneur STL sont les suivants. Deux éléments.
(1) Pour la suppression d'éléments dans des conteneurs de nœuds (carte, liste, ensemble), l'opération d'insertion rendra invalide l'itérateur pointant vers l'élément, et les autres itérateurs d'éléments ne seront pas affectés
(2 ; ) Pour les opérations séquentielles de suppression et d'insertion d'éléments conteneurs (vecteur, chaîne, deque), l'itérateur pointant vers cet élément et les éléments suivants deviendront invalides.

Ainsi, il n'y a aucun problème lors de la suppression d'un élément. C'est-à-dire :

for(map<string,int>::iterator it=countMap.begin();it!=countMap.end();++it)
{    if(it->second==0)
    {
        countMap.erase(it);        break;
    }
}

Cependant, lorsque plusieurs éléments sont supprimés, le programme plante. La raison en est que lorsqu'un élément spécifié est supprimé via un itérateur, l'itérateur pointant vers cet élément deviendra invalide. Si l'opération ++ est à nouveau effectuée sur l'itérateur invalide, un comportement indéfini se produira et le programme plantera. Il existe deux solutions. Prenons comme exemple le conteneur de carte ci-dessus. La mise en œuvre correcte de l'opération de suppression :

Méthode 1 : Lors de la suppression d'un élément avec une valeur spécifique, enregistrez l'actuel. valeur avant de supprimer l’élément Itérateur pour l’élément à côté de l’élément supprimé.

map<string,int >::iterator nextIt=countMap.begin();for(map<string,int>::iterator it=countMap.begin();;)
{    if(nextIt!=countMap.end())
    {
        ++nextIt;
    }    else
    { 
        break;
    }    if(it->second==0)
    {
        countMap.erase(it);
    }
    it=nextIt;
}

Comment mettre en œuvre cette méthode de manière plus concise ? L'implémentation spécifique de cette méthode dans le livre "Effective STL" est donnée ci-dessous :

for(map<string,int>::iterator it=countMap.begin();it!=countMap.end();)
{    if(it->second==0)
    {
        countMap.erase(it++);
    }    else
    {
        ++it;
    }
}

Cette implémentation profite des caractéristiques de l'opérateur post ++ Avant l'opération d'effacement, l'itérateur a déjà pointé. au suivant un élément.

De plus, map.erase() renvoie un itérateur pointant vers l'élément suivant immédiatement après l'élément supprimé, il peut donc être implémenté comme suit :

for(map<string,int>::iterator it=countMap.begin();it!=countMap.end();)
{    if(it->second==0)
    {
        it=countMap.erase(it);
    }   
    else
    {
        ++it;
    }
}

Méthode 2 : Lors de la suppression d'éléments qui remplissent certaines conditions, vous pouvez utiliser la méthode remove_copy_if & swap. Tout d'abord, utilisez le modèle de fonction remove_copy_if pour copier (copier) les éléments requis dans le conteneur temporaire selon les conditions. Les éléments restants qui n'ont pas été copiés sont équivalents à "supprimés", puis les éléments des deux conteneurs sont échangés. . ), vous pouvez appeler directement la fonction membre swap de map. Code de référence :

#include <iostream>#include <string>#include <map>#include <algorithm>#include <iterator>  using namespace std;map<string,int> mapCount;//不拷贝的条件bool notCopy(pair<string,int> key_value)
{    return key_value.second==0;
}int main()
{
    mapCount.insert(make_pair("tanwan",0));
    mapCount.insert(make_pair("anhui",1));
    mapCount.insert(make_pair("shanghai",0));
    mapCount.insert(make_pair("shandong",1));    map<string,int> mapCountTemp;//临时map容器
    //之所以要用迭代器适配器inserter函数模板是因为通过调用insert()成员函数来插入元素，并由用户指定插入位置
    remove_copy_if(mapCount.begin(),mapCount.end(),inserter(mapCountTemp,mapCountTemp.begin()),notCopy);

    mapCount.swap(mapCountTemp);//实现两个容器的交换

    cout<<mapCount.size()<<endl;     //输出2
    cout<<mapCountTemp.size()<<endl; //输出4

    for(map<string,int>::iterator it=mapCount.begin();it!=mapCount.end();++it)
    {        cout<<it->first<<" "<<it->second<<endl;
    }
}

Résultat de sortie du programme :

2
4
anhui 1
shandong 1

Inconvénients de cette méthode : Bien que la complexité temporelle de la réalisation de l'échange de deux cartes soit constante, en général, le temps système causée par la copie sera supérieure à la surcharge de temps liée à la suppression de l'élément spécifié, et le conteneur de carte temporaire augmente également la surcharge d'espace.

2. Le mécanisme sous-jacent d'implémentation des itérateurs dans les conteneurs en STL

Quand on parle de STL, il faut immédiatement penser à ses six composants principaux, à savoir : conteneur, itérateur, algorithme, foncteurs, Adaptateurs et répartiteurs d'espace, les itérateurs constituent un pont important reliant les conteneurs et les algorithmes.

L'essence des itérateurs de conteneurs en STL est un objet de classe, qui fonctionne comme un curseur dans une base de données. De plus, les itérateurs sont également un modèle de conception. On peut l'incrémenter (ou sélectionner le suivant) pour accéder aux éléments du conteneur sans savoir comment il est implémenté en interne. Il se comporte comme un pointeur et peut être utilisé pour accéder à des éléments spécifiés. Mais les deux sont des choses complètement différentes. Le pointeur représente l'adresse mémoire de l'élément, c'est-à-dire l'emplacement de stockage de l'objet en mémoire, tandis que l'itérateur représente la position relative de l'élément dans le conteneur.

Pour personnaliser un itérateur, vous devez surcharger certains opérateurs d'itérateur de base : * (déréférence), ++ (incrément), == (égal), != (pas égal), = (affectation) afin que il peut être utilisé dans une plage de déclaration. range for est une nouvelle instruction en C++11. Par exemple, lorsque nous utilisons l'instruction for (auto i: collection) sur une collection, sa signification est en fait :

for(auto __begin = collection.begin(),auto __end = collection.end();__begin!=__end;++__begin)
{ 
    i = *__begin;    ...//循环体
}

begin et end sont des ensembles. Fonction membre qui renvoie un itérateur. Si une classe peut avoir une plage pour fonctionner, elle doit remplir les conditions suivantes :
(1) Avoir des fonctions de début et de fin, qui renvoient toutes deux des itérateurs, où la fonction de fin renvoie un itérateur pointant vers la fin de l'ensemble, mais n'inclut pas l'élément de fin. La valeur est représentée par la plage de l'ensemble. La plage d'un itérateur est [début, fin), un intervalle fermé à gauche et ouvert à droite.
(2) Doit surcharger ++,! = et opérateur de déréférencement (*). L'itérateur ressemblera à un pointeur, mais ce n'est pas un pointeur. L'itérateur doit être finalement satisfait par ++ ! = condition, pour que la boucle puisse être terminée.

Le code d'implémentation le plus simple est donné ci-dessous. Nous définissons une classe CPPollection contenant un tableau de chaînes et nous lui permettons d'afficher chaque chaîne via une plage pour.

class CPPCollection 
{public:
    //迭代器类    class Iterator
    {    public:        int index;//元素下标
        CPPCollection& outer;
        Iterator(CPPCollection &o, int i):outer(o), index(i){}        void operator++()
        {
            index++;
        }
        std::string operator*() const
        {            return outer.str[index];
        }        bool operator!=(Iterator i)
        {            return i.index!=index;
        }
    };public:    CPPCollection()
    {        string strTemp[10]={"a", "b", "c", "d", "e", "f", "g", "h", "i", "j"};        int i=0;        for(auto strIt:strTemp)
        {
            str[i++]=strIt;
        }
    }

    Iterator begin()
    {        return Iterator(*this,0);
    }
    Iterator end()
    {        return Iterator(*this, 10);
    }private:
    std::string str[10];
};

Nous avons défini une classe imbriquée interne Iterator et surchargé ++, *, pour cela ! = opérateur. Étant donné que la classe imbriquée interne en C++ n'a aucun lien avec la classe externe, pour accéder à la valeur de l'objet de classe externe, nous devons transmettre une référence (ou un pointeur, dans ce cas, une référence). La méthode d'auto-incrémentation d'Iterator augmente en fait une valeur d'index interne. juge! La méthode = consiste à comparer avec un autre itérateur, qui est généralement la fin de la collection. Lorsque notre valeur d'index est égale à la valeur de l'index de fin, l'itérateur est considéré comme ayant atteint la fin. Dans la classe CPPollection, begin() et end() sont définis pour renvoyer respectivement les itérateurs de début et de fin, et appellent le code suivant :

　　CPPCollection cpc;
　　for (auto i : cpc)
　　{
    　　std::cout <<i<<std::endl;
　　}
　　//或者　　CPPCollection cpc;
　　for(CPPCollection::Iterator i= cpc.begin();i!=cpc.end();++i)
　　{        std::cout<<*i<<std::endl;
   }

即可遍历集合中的所有元素了。

在泛型算法中，为了对集合中的每一个元素进行操作，我们通常要传入集合的迭代器头、迭代器尾，以及谓词，例如std::find_if（vec.begin(),vec.end(),…），这种泛型算法其实就是在迭代器的首位反复迭代，然后运行相应的行为。

---

参考文献

[1]编写高质量代码：改善C++程序的150个建议.李健.机械工业出版社.

相关文章：

C# 2.0 Specification(迭代器)（二）

C#中使用迭代器处理等待任务_基础知识

C# 2.0 Specification(迭代器)（一）

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!