[Effective STL] 24. map::operator[] vs map::insert

항목 24. map::operator[]나 map::insert는 효율 문제에 주의하여 선택하자

 

 

 

operator[] 대신 insert를 써야할 때

class Widget
{
public:
    Widget();
    Widget(double weight);
    Widget& operator=(double weight);
    ...
};

map<int, Widget> m;
m[1] = 1.50;
m[2] = 3.67;
m[3] = 10.5;
m[4] = 45.8;
m[5] = 0.0003; // 심각한 수행 성능 저하!

• map::operator[]는 추가 혹은 갱신(add or update) 기능을 수행하도록 설계되었다.
• 즉, m[k] = v; 시
  1. 해당 맵에 키 k가 있는지 점검
  2. 없다면 k와 v가 페어로 묶여서 맵에 새로 추가
  3. 있다면 k와 매핑된 값(value)이 v로 갱신
• 즉, operator[]는 pair에 대한 참조자를 반환하도록 되어 있고, v는 페어의 second 멤버 데이터에 대입된다.
  • 갱신일 때는 간편하지만..
  • 추가일 때는 참조하는 값 객체를 '새로 생성하고' 참조자를 반환하게 될 것이다.

map<int, Widget> m;

// 즉 아래의 코드는
m[1] = 1.50;
// 이처럼 풀어쓸 수 있을 것이다.
// result의 타입은 pair< map<int, Widget>::iterator, bool >
auto result = m.insert(map<int, Widget>::value_type(1, Widget()));
// 1.50을 넣어서 바로 생성할 수 있는 생성자가 존재하지만..
// 빈 Widget을 먼저 생성하는 불필요한 오버헤드가 발생한다.
result.first->second = 1.50; // 값 변경

// 아래 코드가, 사실 최적의 동작일 것이다.
// 함수 호출을 세 개나 줄였다.
// 1. Widget 기본 생성자 함수
// 2. Widget 소멸자 함수
// 3. Widget 대입 연산자 함수
m.insert(map<int, Widget>::value_type(1, 1.50));

• 즉, 요소 추가에는 operator[] 보다는 insert를 쓰는 것이 낫다.

 

 

 

insert 대신 operator[]를 써야할 때

• 요소 갱신이 필요할 때는(즉, 동등한(equivalent) 키(항목 19 참조)가 이미 있는 경우)는 상황이 달라진다.

// operator[]를 사용하여 갱신
m[k] = v;

// isnert를 사용하여 갱신
m.insert(map<int, Widget>::value_type(k, v)).first->second = v;
// insert 갱신의 경우
// 1. pair<int, Widget>(즉, map<int, Widget>::value_type)의 생성자, 소멸자가 호출된다.
// 2. pair 안의 Widget의 생성자, 소멸자가 덩달아 호출된다.
// 더군다나 operator[]가 훨씬 보기 좋다.

 

 

 

둘을 신경쓰지 않고 사용할 함수 작성

// operator[]나 insert를 신경쓰지 않고 쓸 efficientAddOrUpdate 함수
template<typename MapType, typename KeyArgType, typename ValueArgType>
typename MapType::iterator efficientAddOrUpdate(MapType& m,
                                                const KeyArgType& k,
                                                const ValueArgType& v)
{
    typename MapType::iterator lb = m.lower_bound(k); // k의 위치나 삽입 위치를 찾는다.
    
    if(lb != m.end() && !(m.key_comp()(k, lb->first))) // 동등성 검사
    {
        // k가 존재하면
        lb->second = v; // 갱신 후
        return lb; // 반복자 반환
    }
    else
    {
        return m.insert(lb, typename MapType::value_type(k, v)); // 없으면 insert 후 반복자 반환
    }
}

auto affectedPair = efficientAddOrUpdate(m, k, v); // 이렇게 쉽게 사용 가능하다.

• lower_bound(항목 45 참조)
• typename을 사용한 이유(EC++ 항목 42 참조)
• 재미있는 점! KeyArgType과 ValueArgType은 맵에 저장된 타입일 필요가 없다.
  • 맵에 저장된 타입으로 변환될 수만 있으면(convertible) 된다.
• KeyArgType과 ValueArgType 템플릿 매개변수를 제거할 수도 있을 것이다.

// KeyArgType, ValueArgType을 제거한 버전
template<typename MapType>
typename MapType::iterator efficientAddOrUpdate(MapType& m,
                                                const typename MapType::key_type& k,
                                                const typename MapType::mapped_type& v)
{
    typename MapType::iterator lb = m.lower_bound(k);
    
    if(lb != m.end() && !(m.key_comp()(k, lb->first)))
    {
        lb->second = v; // 갱신 후
        return lb; // 반복자 반환
    }
    else
    {
        return m.insert(lb, typename MapType::value_type(k, v)); // 없으면 insert 후 반복자 반환
    }
}

class Widget
{
public:
    ...
    Widget& operator=(double weight);
    ...
};
map<int, Widget> m;

efficientAddOrUpdate(m, 10, 1.5); // 이렇게 호출한다면?
// ValueArgType 버전에서는 double로 판정하고 전달되지만,
// MapType::mapped_type 버전에서는 Widget 객체로 변환되어 전달된다!(쓸데없는 객체 생성 비용)