STL 연관 컨테이너 (2)

항목 22 : set과 multiset에 저장된 데이터 요소에 대해 키를 바꾸는 일은 피하자

잠깐만 생각해봐도 당연한 얘기다. 데이터가 삽입될 때 정렬되어서 관리되는데, 이미 삽입된 요소의 값을 바꾸면 정렬 상태가 무너진다.

다만 map과 다르게 const T가 아닌 그냥 T가 저장되기 때문에 정렬 기준과 상관없는 값을 바꿀수는 있다.

 

class Employee {
public:
    ...
    void setTitle(const std::string& title);
    int idNumber() const; // 정렬 기준
};

auto i = se.find(selectedID);
...
i->setTitle("Corporate Deity"); // 변경 가능

객체에 데이터가 여러개있고 일부 데이터만 정렬 기준(key)이 된다면 그 외의 데이터는 수정되어도 정렬 상태가 무너지지 않는다.

만약 set의 반복자 역참조가 T&가 아닌 const T&로 반환한다면, 캐스팅을 통해 참조자를 반환받은뒤에 값을 수정하면 된다.

 

map의 경우는 키값을 저장할때부터 상수화시키기 때문에 함부로 캐스팅을 통해 상수 성질을 없애지 않는것이 좋다

 

만약 저장된 요소를 바꾸고 싶다면 아래 단계를 순서대로 거치면 호환성과 안전성을 챙길 수 있다.

 

1. 변경하고자 하는 컨테이너 요소의 위치를 찾는다.
2. 해당 요소의 복사본을 만든다.
3. 원래 컨테이너에서 해당 요소를 삭제한다.
4. 복사본의 데이터를 수정한다.
5. 복사본을 컨테이너에 새로 삽입한다. 만약 새로 삽입되는 요소가 기존 요소와 위치가 같거나 바로 옆이라면 3번에서 삭제될 때의 반복자를 넘겨서 삽입 시간을 상수 시간으로 단축시킬 수 있다.

 

 

항목 23 : 연관 컨테이너 대신에 정렬된 vector를 쓰는 것이 좋을 때가 있다

데이터 셋업, 데이터 탐색, 데이터 재구성 순으로 자료 구조를 사용한다면 연관 컨테이너보다 벡터가 훨씬 나을 수 있다.

 

연관 컨테이너는 균형 이진 탐색(AVL) 트리를 사용하는데, 연속 메모리 구조가 아니라 트리 노드로 구현되어 있기 때문에 요소 하나 저장하는데 최소 세 개의 포인터를 사용하므로 오버헤드가 발생한다.

근데 벡터는 재할당이 이루어지지 않는 한 오버헤드가 없다.

 

만약 저장해야 하는 데이터의 수가 매우 많다고 할 때, 연관 컨테이너는 벡터와 같은 데이터의 양을 저장하더라도 오버헤드로 인해 사용 메모리가 많아지고, 페이지 하나당 저장되는 데이터 개수의 더 적기 때문에 캐시 적중률이 떨어지고, 페이지 부재도 더 빈번하게 발생할 수 있다.

 

그래서 정렬된 벡터에 한해서는 연관 컨테이너보다 더 나은 성능을 보여줄 가능성이 높다.

제약사항이 한가지 더 있긴 하다. 삽입, 삭제, 탐색이 빈번하지 않은 경우여야 한다는 점이다.

 

typedef std::pair<std::string, int> Data;

class DataCompare {
public:
    bool operator()(const Data& lhs, const Data& rhs) const { // 정렬용 비교 함수
        return keyLess(lhs.first, rhs.first);
    }
    bool operator()(const Data& lhs, const Data::first_type& k) const { // 탐색용 비교 함수1
        return keyLess(lhs.first, k);
    }
    bool operator()(const Data::first_type& k, const Data& rhs) const { // 탐색용 비교 함수2
        return keyLess(k, rhs.first);
    }
private:
    bool keyLess(const Data::first_type& k1, const Data::first_type& k2) const { // 실제 비교 함수
        return k1 < k2;
    }
};

덧붙여서 벡터를 써서 맵을 대신하려면 키값이 const여서는 안된다. 정렬될 때 각 요소의 값이 대입 연산을 통해 이동되기 때문이다. 만약 구현하게 된다면 정렬용 비교 함수 외에도 탐색용 비교 함수를 따로 만들어 두어야 한다.

 

 

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

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

std::map<int, Widget> m;
m[1] = 1.50; // == m.operator[](1)
m[2] = 3.67; // 만약 key에 2가 없다면?
...

맵은 key-value 페어로 이루어져 있다. 이미 존재하는 key라면 value의 참조자를 반환하여 value를 수정하고 없는 key라면 새로운 key-value 페어를 생성한다.

새로운 페어를 생성할 때, value_type의 기본 생성자를 이용해서 새로운 객체를 만들어낸다.

 

m[1] = 1.50;

/* 위의 코드는 아래로 풀이된다 */

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

키 검사->페어 생성->기본 생성자로 임시객체 생성->value에 복사->임시객체 소멸->value.operator=호출 순으로 이루어진다.

만약 기본 생성자 대신 원하는 값을 직접 매개변수에 넘겨주면 호출 횟수가 많이 줄어들 것이다.

 

m.insert(std::map<int, Widget>::value_type(1, 1.50));

 

만약 추가가 아닌 갱신이라면 오히려 insert보다 operator[]가 더 효율적이다.

 

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

하나의 함수로 추가와 갱신을 판단해서 각자 효율적인 동작을 선택하도록 구현해보면 대략적으로 위와 같다.

 

 

항목 25 : 현재는 표준이 아니지만, 해쉬 컨테이너에 대해 충분히 대비해 두자

(참고: 지금은 표준이다. unordered_map, unordered_set)

해쉬 컨테이너는 다른 연관 컨테이너와 다르게 비교 함수를 동등성 검사가 아닌 상등성 검사로 한다.

정렬 순서가 무의미하기 때문이다.