(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) 노드 컨테이너(map, list, set)에서 요소를 삭제하는 경우 삽입 작업으로 인해 해당 요소를 가리키는 반복자가 유효하지 않게 되고 다른 요소 반복자는 영향을 받지 않습니다.
(2) 순차의 경우; 컨테이너(벡터, 문자열의 삭제 및 삽입 작업, deque) 요소는 이 요소와 후속 요소를 가리키는 반복자가 유효하지 않게 됩니다.

그래서 요소를 삭제할 때 문제가 없습니다. 즉,

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

그러나 여러 요소가 삭제되면 프로그램이 충돌합니다. 그 이유는 지정된 요소가 반복자를 통해 삭제되면 해당 요소를 가리키는 반복자가 유효하지 않게 되기 때문입니다. 유효하지 않은 반복자에 대해 다시 ++ 연산을 수행하면 정의되지 않은 동작이 발생하고 프로그램이 중단됩니다. 위의 맵 컨테이너를 예로 들어 보겠습니다. 삭제 작업의 올바른 구현:

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

이 구현은 삭제 작업 전에 postfix ++ 연산자의 특성을 활용합니다. 반복자는 이미 다음 요소를 가리켰습니다.

게다가 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 및 스왑 방법. 먼저, Remove_copy_if 함수 템플릿을 사용하여 조건에 따라 필요한 요소를 임시 컨테이너에 복사(복사)합니다. 복사되지 않은 나머지 요소는 "제거"되는 것과 동일하며, 그런 다음 두 컨테이너의 요소가 교체됩니다. . ), map의 멤버 함수 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. STL의 컨테이너에 있는 반복자의 기본 구현 메커니즘

STL에 관해서는 즉시 6가지 주요 구성 요소, 즉 컨테이너, 반복자, 알고리즘, 펑터, 어댑터 및 공간 할당자를 생각해야 합니다. 컨테이너와 알고리즘을 연결하는 중요한 브리지입니다.

STL에서 컨테이너 반복자의 핵심은 데이터베이스의 커서와 유사한 기능을 하는 클래스 개체입니다. 또한 반복자도 디자인 패턴입니다. 내부적으로 어떻게 구현되는지 모르더라도 컨테이너의 요소에 액세스하기 위해 이를 증가(또는 다음 요소 선택)할 수 있습니다. 이는 포인터와 매우 유사하게 동작하며 지정된 요소에 액세스하는 데 사용할 수 있습니다. 그러나 둘은 완전히 다른 것입니다. 포인터는 요소의 메모리 주소, 즉 메모리에 있는 개체의 저장 위치를 ​​나타내고 반복자는 컨테이너에 있는 요소의 상대적 위치를 나타냅니다.

반복자를 사용자 정의하려면 *(역참조), ++(증가), ==(같음), !=(같지 않음), =(할당) 등 일부 기본 반복 연산자를 오버로드해야 합니다. 명령문의 범위에 사용됩니다. 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) 둘 다 반복자를 반환하는 시작 및 끝 함수가 있어야 합니다. 여기서 끝 함수는 집합의 끝을 가리키는 값을 반환하지만 끝 요소를 포함하지 않습니다. 즉, 컬렉션 범위로 표시되며 반복자의 범위는 왼쪽이 닫히고 오른쪽이 열리는 간격인 [시작, 끝)입니다.
(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 중국어 웹사이트의 기타 관련 기사를 참조하세요!