(C++) Falsche Kartenlöschoperation und der zugrunde liegende Implementierungsmechanismus von Container-Iteratoren in STL

1. Falscher Kartenlöschvorgang

Angenommen, es gibt einen Kartencontainer, der zum Speichern der Anzahl der Studenten verwendet wird, die jeder Heimatprovinz in einer Universitätsklasse entsprechen. Der Schlüssel ist: Die Provinz wird vollständig auf Chinesisch geschrieben, und der Wert ist die Anzahl der Studenten. Jetzt müssen wir den Datensatz mit der Personenzahl 0 löschen. Der Löschcode lautet wie folgt:

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

Auf den ersten Blick gibt es kein Problem. Wenn Sie genau hinschauen, gibt es zwei Die wichtigsten versteckten Fallen bei den Lösch- und Einfügevorgängen des STL-Containers: .
(1) Beim Löschen von Elementen in Knotencontainern (Karte, Liste, Satz) führt der Einfügevorgang dazu, dass der Iterator, der auf das Element verweist, ungültig wird und andere Elementiteratoren nicht betroffen sind.
( 2) Bei sequentiellen Lösch- und Einfügevorgängen von Containerelementen (Vektor, String, Deque) wird der Iterator, der auf dieses Element und nachfolgende Elemente verweist, ungültig.

Das Löschen eines Elements ist also kein Problem. Das heißt:

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

Wenn jedoch mehrere Elemente gelöscht werden, stürzt das Programm ab. Der Grund dafür ist, dass beim Löschen eines angegebenen Elements durch einen Iterator der Iterator, der auf dieses Element verweist, ungültig wird. Wenn die ++-Operation erneut für den ungültigen Iterator ausgeführt wird, tritt undefiniertes Verhalten auf und das Programm stürzt ab. Es gibt zwei Lösungen. Nehmen wir den Kartencontainer oben als Beispiel:

Methode 1: Speichern Sie beim Löschen eines Elements den aktuellen Wert vor dem Löschen des Elements.

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

Wie lässt sich diese Methode prägnanter umsetzen? Die spezifische Implementierung dieser Methode im Buch „Effective STL“ ist unten angegeben:

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

Diese Implementierung nutzt die Eigenschaften des Post++-Operators. Vor dem Löschvorgang hat der Iterator bereits darauf hingewiesen nächstes Element.

Darüber hinaus gibt map.erase() einen Iterator zurück, der auf das nächste Element zeigt, das unmittelbar auf das gelöschte Element folgt, sodass es wie folgt implementiert werden kann:

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

Methode 2: Wenn Sie Elemente löschen möchten, die bestimmte Bedingungen erfüllen, können Sie die Methode „remove_copy_if & swap“ verwenden. Verwenden Sie zunächst die Funktionsvorlage „remove_copy_if“, um die erforderlichen Elemente gemäß den Bedingungen in den temporären Container zu kopieren (kopieren). Die verbleibenden Elemente, die nicht kopiert wurden, entsprechen dem „Entfernen“, und dann werden die Elemente in den beiden Containern ausgetauscht . ), können Sie die Mitgliedsfunktion Swap von Map direkt aufrufen. Referenzcode:

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

Ergebnis der Programmausgabe:

2
4
anhui 1
shandong 1

Nachteile dieser Methode: Obwohl die Zeitkomplexität für die Realisierung des Austauschs zweier Karten konstant ist, bringt das Kopieren unter normalen Umständen Zeitkosten mit sich ist größer als der Zeitaufwand für das Löschen des angegebenen Elements, und der temporäre Kartencontainer erhöht auch die Speicherplatzkosten.

2. Der zugrunde liegende Implementierungsmechanismus von Iteratoren in Containern in STL

Wenn es um STL geht, müssen Sie sofort an seine sechs Hauptkomponenten denken, nämlich: Container, Iterator, Algorithmus, Funktoren, Adapter und Raumzuweiser, Iteratoren sind eine wichtige Brücke, die Container und Algorithmen verbindet.

Das Wesentliche an Container-Iteratoren in STL ist ein Klassenobjekt, das wie ein Cursor in einer Datenbank funktioniert. Darüber hinaus sind Iteratoren auch ein Entwurfsmuster. Wir können es erhöhen (oder das nächste auswählen), um auf die Elemente im Container zuzugreifen, ohne zu wissen, wie es intern implementiert ist. Es verhält sich ähnlich wie ein Zeiger und kann für den Zugriff auf bestimmte Elemente verwendet werden. Aber die beiden sind völlig unterschiedliche Dinge. Der Zeiger repräsentiert die Speicheradresse des Elements, also den Speicherort des Objekts im Speicher, während der Iterator die relative Position des Elements im Container darstellt.

Um einen Iterator anzupassen, müssen Sie einige grundlegende Iteratoroperatoren überladen: * (Dereferenzierung), ++ (Inkrement), == (gleich), != (ungleich), = (Zuweisung), damit Es kann in einem Bereich für die Anweisung verwendet werden. range for ist eine neue Anweisung in C++11. Wenn wir beispielsweise die Anweisung for (auto i:collection) für eine Sammlung verwenden, ist ihre Bedeutung tatsächlich:

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

begin und end sind Mitgliedsfunktionen von die Sammlung, die einen Iterator zurückgibt. Wenn eine Klasse einen Bereich für den Betrieb haben kann, muss sie die folgenden Bedingungen erfüllen:
(1) Sie verfügt über Anfangs- und Endfunktionen, die beide Iteratoren zurückgeben, wobei die Endfunktion einen Iterator zurückgibt, der auf das Ende der Menge zeigt. enthält jedoch nicht das Endelement. Der Wert wird durch den Bereich der Menge dargestellt. Der Bereich eines Iterators ist [Anfang, Ende), ein links geschlossenes und rechts offenes Intervall.
(2) Muss ++ überladen! = und Dereferenzierungsoperator (*). Der Iterator sieht aus wie ein Zeiger, ist aber kein Zeiger. Der Iterator muss schließlich mit ++ zufrieden sein! = Bedingung, damit die Schleife beendet werden kann.

Der einfachste Implementierungscode ist unten angegeben. Wir definieren eine CPPCollection-Klasse mit einem Array von Strings darin und ermöglichen ihr die Ausgabe jedes Strings über den gesamten Bereich.

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

Wir haben einen internen verschachtelten Klassen-Iterator definiert und ++, * dafür überladen! = Betreiber. Da die innere verschachtelte Klasse in C++ keine Verbindung zur äußeren Klasse hat, müssen wir eine Referenz (oder einen Zeiger, in diesem Fall eine Referenz) übergeben, um auf den Wert des äußeren Klassenobjekts zuzugreifen. Die automatische Inkrementierungsmethode von Iterator erhöht tatsächlich einen internen Indexwert. Richter! Die =-Methode dient zum Vergleich mit einem anderen Iterator, der normalerweise das Ende der Sammlung darstellt. Wenn unser Indexwert dem Endindexwert entspricht, wird davon ausgegangen, dass der Iterator das Ende erreicht hat. In der CPPCollection-Klasse sind begin() und end() so definiert, dass sie den Anfangs- bzw. End-Iterator zurückgeben und den folgenden Code aufrufen:

　　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(迭代器)（一）

Das obige ist der detaillierte Inhalt von(C++) Falsche Kartenlöschoperation und der zugrunde liegende Implementierungsmechanismus von Container-Iteratoren in STL. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!