(C++) 間違ったマップ削除操作と STL のコンテナー反復子の基礎となる実装メカニズム

1. 間違ったマップ削除操作

大学のクラスで、出身地の各州に対応する学生の数を保存するために使用されるマップ コンテナがあるとします。重要なのは、州が完全な中国語で表記されていること、値が学生の数であることです。人数が0のレコードを削除する必要があります。削除コードは次のとおりです:

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

一見すると問題ありませんが、よく見ると大きな穴があります。 STL コンテナの削除および挿入操作に隠されたトラップは次のとおりです。
(1) ノード コンテナー (マップ、リスト、セット) 内の要素の削除の場合、挿入操作により、その要素を指す反復子が無効になり、他の要素の反復子は影響を受けません。 2) 順次の場合、コンテナー (vector、string、deque) 要素の削除および挿入操作により、この要素および後続の要素を指す反復子が無効になります。

したがって、要素を削除する場合は問題ありません。つまり:

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

ただし、複数の要素が削除されると、プログラムがクラッシュします。その理由は、イテレータを通じて指定された要素を削除すると、その要素を指すイテレータが無効になり、無効なイテレータを再度操作すると未定義の動作が発生し、プログラムがクラッシュするためです。解決策は 2 つあります。例として上記のマップ コンテナーを取り上げます。削除操作の正しい実装:

方法 1: 特定の値を持つ要素を削除するときは、現在のマップ コンテナーを保存します。要素を削除する前の値。削除された要素の次の要素のイテレータ。

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

このメソッドをより簡潔に実装するにはどうすればよいですか?書籍「Effective STL」でのこのメソッドの具体的な実装は次のとおりです:

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

この実装では、ポスト演算子の特性を利用しています。消去操作の前に、反復子はすでに次の要素を指しています。 。

さらに、map.erase() は、削除された要素の直後の次の要素を指す反復子を返すため、次のように実装できます。

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

方法 2: 特定の条件を満たす要素を削除するには、remove_copy_if & swap メソッドを使用できます。まず、関数テンプレートremove_copy_ifを使用して、必要な要素を条件に従って一時コンテナにコピーします。コピーされていない残りの要素は「削除」に相当し、その後、2つのコンテナ内の要素が交換されます。)、マップのメンバー関数 swap を直接呼び出すことができます。参照コード:

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

プログラム出力結果:

2
4
anhui 1
shandong 1

この方法の欠点: 2 つのマップの交換を実現するための時間量は一定レベルですが、通常の状況ではコピーによる時間コストが発生します。これは、指定された要素を削除する時間コストよりも大きくなり、一時マップ コンテナーによるスペース コストも増加します。

2. STL のコンテナーにおけるイテレーターの基礎となる実装メカニズム

STL に関して言えば、すぐにその 6 つの主要なコンポーネント、つまりコンテナー、イテレーター、アルゴリズム、ファンクター、アダプターとスペース アロケーター、イテレーターは、コンテナーとアルゴリズムを接続する重要なブリッジです。

STL のコンテナ イテレータの本質は、データベースのカーソルと同様に機能するクラス オブジェクトであり、さらに、イテレータは設計パターンでもあります。内部でどのように実装されているかを知らなくても、値をインクリメント (または次のものを選択) してコンテナ内の要素にアクセスできます。これはポインターのように動作し、指定された要素にアクセスするために使用できます。ただし、この 2 つはまったく別のもので、ポインタは要素のメモリ アドレス、つまりメモリ内のオブジェクトの格納場所を表し、イテレータはコンテナ内の要素の相対位置を表します。

イテレータをカスタマイズするには、イテレータのいくつかの基本演算子: * (逆参照)、(増分)、== (等しい)、!= (等しくない)、= (代入) をオーバーロードする必要があります。これは、for ステートメントの範囲内で使用できます。 range for は、C 11 の新しいステートメントです。たとえば、コレクションに対してステートメント for (auto i: collection) を使用する場合、その意味は実際には次のようになります。

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

begin と end はコレクションのメンバー関数です。 . イテレータを返します。クラスが操作の範囲を持つことができる場合、クラスは次の条件を満たしている必要があります。

(1) begin 関数と end 関数があり、どちらも反復子を返します。end 関数はセットの終わりを指す反復子を返します。ただし、終了要素は含まれません 値はセットの範囲で表されます イテレータの範囲は [begin, end)、つまり左が閉じて右が開いた間隔です。
(2) 過負荷になっているはずです! = および逆参照 (*) 演算子。イテレータはポインタのように見えますが、ポインタではありません。イテレータは合格可能であり、最終的には満足できるものでなければなりません。 = 条件を指定すると、ループを終了できます。

最も単純な実装コードを以下に示します。文字列の配列を含む CPPCollection クラスを定義し、範囲を介して各文字列を出力できるようにします。

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

内部のネストされたクラス Iterator を定義し、それに対して , * をオーバーロードしました。 = 演算子。 C の内部のネストされたクラスは外部クラスとの接続がないため、外部クラスのオブジェクトの値にアクセスするには、参照 (またはこの場合はポインター、参照) を渡す必要があります。 Iterator の自動インクリメント メソッドは、実際には内部インデックス値を増加させます。裁判官！ = メソッドは、通常はコレクションの最後である別の反復子と比較するためのもので、インデックス値が終了インデックス値と等しい場合、反復子は最後に到達したとみなされます。 CPPCollection クラスでは、begin() と end() がそれぞれ開始反復子と終了反復子を返し、次のコードを呼び出すように定義されています。

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

以上が(C++) 間違ったマップ削除操作と STL のコンテナー反復子の基礎となる実装メカニズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。