[effective STL] 항목 24 : map에서 []나 insert는 효율 문제에 주의하자.

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

double 값을 이용하여 widget을 초기화 할 수 있다.

이렇게 자료구조가 있을 때 두 가지 정도 작업이 있을 수 있다.

1. map에 값을 넣으며 초기화.

2. map에 들어가 있는 값을 변경하는 작업.

보통은 둘 다 이렇게 사용한다.

mW[1] = 1.50;

map의 operator[] 연산자의 특징

추가 아니면 갱신(add or update) 기능을 수행하도록 설계되어 있다.

mW[k] = v;

키 값 k가 들어 있는지 점검 -> 그렇지 않다면 k와 v를 페어로 묶어 맵에 새로 추가한다.

만약 k가 있다면 -> k와 맵핑된 value 값을 v로 갱신한다.

map에 값을 넣으면 초기화 할 때

mW[1] = 1.50;

이것을 풀어 쓰게 되면 이렇게 된다고 한다.

typedef map<int, Widget> IntWidgetMap;
 
pair<IntWidgetMap::iterator, bool> result = 
    mW.insert(IntWidgetMap::value_type(1, Widget()));
 
result.first->second = 1.50;

Widget의 기본 생성자를 호출하여 만들고 이것을 대입하는 형태가 된다.

이렇게 하지 말고 아예 Widget 객체를 원하는 값을 생성자 매개 변수에 넣어 바로 만들어 넣는것이 효율적이다.

m.insert(IntWidgetMap::value_type(1,1.50));

이렇게 하면 임시로 만드는 기본생성자와 대입 연산자가 호출되지 않으므로 비용을 크게 줄일 수 있다.

map에 들어가 있는 값을 변경 할 때

m[k] = v; // 1
 
m.insert(IntWidgetMap::value_type(k,v)).first->second = v; // 2

key가 이미 있기 때문에 operator[]는 pair 객체를 생성하지 않는다.

효율적으로나 미적으로나 // 1이 낫다.

결론

"추가"를 할 경우는 insert가 효율적이다. "갱신"을 할 경우는 operator[]가 효율적이다.

EfficientAddOrUpdate 만들기

그럼 insert와 []를 구분하여 서로 다르게 동작하는 함수를 만들면 될 것이다.

https://github.com/ElementalKiss/Cpp/blob/master/Example/EfficientAddOrUpdate.cpp

#include <iostream>
#include <map>
 
using namespace std;
 
class Widget
{
public:
    Widget() : m_weight(0) { };
    Widget(double weight) : m_weight(weight) { };
    Widget& operator=(double weight) { 
        this->m_weight = weight; 
        return *this; 
    };
 
private:
    double m_weight;
};
 
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);
 
    if (lb != m.end() && !(m.key_comp()(k,lb->first))) {
        lb->second = v;
        return lb;
    }
    else {
        typedef typename MapType::value_type MVT;
        return m.insert(lb, MVT(k,v));
    }
}
 
int main(int argc, const char* argv[])
{
    map<int, Widget> mW;
 
    mW[1] = 1.5;
    
    // goto insert
    efficientAddOrUpdate(mW, 2, 1.6);
    // goto []
    efficientAddOrUpdate(mW, 1, 1.2);
 
    return 0;
}