1. Wrong map deletion operation

Suppose there is a map container used to store the number of students corresponding to each hometown province in the university class, the key is The province is spelled out in full Chinese, and value is the number of students. Now we need to delete the record with the number of people 0. The deletion code is as follows:

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

Copy after login

At first glance, there is no problem. But after a closer look, there are huge pits. The main traps hidden in the deletion and insertion operations of the STL container are as follows: .
(1) For the deletion of elements in node containers (map, list, set), the insertion operation will cause the iterator pointing to the element to become invalid, and other element iterators will not be affected;
(2) For sequential Deletion and insertion operations of container (vector, string, deque) elements will cause the iterator pointing to this element and subsequent elements to become invalid.

So, there is no problem when deleting an element. That is:

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

Copy after login

However, when multiple elements are deleted, the program will crash. The reason is that when a specified element is deleted through an iterator, the iterator pointing to that element will become invalid. If the invalid iterator is operated again, undefined behavior will occur and the program will crash. There are two solutions. Let’s take the map container above as an example. The correct implementation of the deletion operation:

Method 1: When deleting an element with a specific value, save the current value before deleting the element. Iterator for the element next to the deleted element.

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

Copy after login

How to implement this method more concisely? The specific implementation of this method in the book "Effective STL" is given below:

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

Copy after login

This implementation takes advantage of the characteristics of the post operator. Before the erase operation, the iterator has already pointed to the next element.

Furthermore map.erase() returns an iterator pointing to the next element immediately following the deleted element, so it can be implemented as follows:

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

Copy after login

Method 2: When To delete elements that meet certain conditions, you can use the remove_copy_if & swap method. First, use the function template remove_copy_if to copy the required elements to the temporary container according to the conditions. The remaining elements that have not been copied are equivalent to being "removed", and then the elements in the two containers are swapped. ), you can directly call the member function swap of map. Reference code:

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

Copy after login

Program output result:

2
4
anhui 1
shandong 1

Copy after login

Disadvantages of this method: Although the time complexity of realizing the exchange of two maps is constant level, under normal circumstances, copying brings The time cost will be greater than the time cost of deleting the specified element, and the temporary map container also increases the space cost.

2. The underlying implementation mechanism of iterators in containers in STL

When it comes to STL, you must immediately think of its six main components, namely: container, iterator, algorithm, Functors, adapters and space allocators, iterators are an important bridge connecting containers and algorithms.

The essence of container iterators in STL is a class object, which functions similar to a cursor in a database. In addition, iterators are also a design pattern. We can increment it (or select the next one) to access the elements in the container without knowing how it is implemented internally. It behaves like a pointer and can be used to access specified elements. But the two are completely different things. The pointer represents the memory address of the element, that is, the storage location of the object in memory, while the iterator represents the relative position of the element in the container.

To customize an iterator, you need to overload some basic operators of the iterator: * (dereference), (increment), == (equal), != (not equal), = ( assignment) so that it can be used in a range for statement. range for is a new statement in C 11. For example, when we use the statement for (auto i: collection) on a collection, its meaning is actually:

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

Copy after login

begin and end are member functions of the collection. Returns an iterator. If a class can have a range for operation, it must meet the following conditions:
(1) Have begin and end functions, both of which return iterators, where the end function returns an iterator pointing to the end of the set, but does not include the end element The value is represented by the range of the set. The range of an iterator is [begin, end), a left-closed and right-open interval.
(2) Must be overloaded,! = and dereference (*) operator. The iterator will look like a pointer, but is not a pointer. The iterator must be passable and finally satisfied! = condition, so that the loop can be terminated.

The simplest implementation code is given below. We define a CPPCollection class with an array of strings in it, and we enable it to output each string through range for.

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

Copy after login

We defined an internal nested class Iterator and overloaded , *, for it! = operator. Since the inner nested class in C has no connection with the outer class, in order to access the value of the outer class object, we must pass in a reference (or pointer, in this case, a reference). The auto-increment method of Iterator actually increases an internal index value. judge! The = method is to compare with another iterator, which is usually the end of the collection. When our index value is equal to the end index value, the iterator is considered to have reached the end. In the CPPCollection class, begin() and end() are defined to return the beginning and end iterators respectively, and call the following code:

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

Copy after login

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

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

参考文献

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

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

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

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

The above is the detailed content of (C++) Wrong map deletion operation and the underlying implementation mechanism of container iterators in STL. For more information, please follow other related articles on the PHP Chinese website!