STL 연관 컨테이너 (1)

연관 컨테이너는 시퀀스 컨테이너와 다르게 상등성이 아닌 동등성의 관점으로 요소를 처리한다.

또한 자동으로 요소가 정리된다.

 

항목 19 : 상등 관계(equality)와 동등 관계(equivalence)의 차이를 파악하자

find 알고리즘과 set의 insert는 기본적으로 "두 값이 같은가?"를 알아내는것은 같지만 동작 방식은 다르다.

"같다"의 정의는 find는 상등성, insert는 동등성에 두고있다.

조금 더 쉽게 얘기하면 상등성은 operator==(같다, 틀리다), 동등성은 operator<(크다, 작다)로 판별한다.

 

◾ 상등성

개념적 뿌리는 operator==에 두고있다.

x==y가 참이면 x, y는 같다. 하지만 x, y가 같다고 해서 모든 데이터 멤버가 같다는 보장은 없다.

 

class Widget {
...
private:
    TimeStamp lastAccessed;
};

bool operator==(const Widget& lhs, const Widget& rhs)
{
    // lastAccessed 필드 고려 X
}

lastAccessed 필드를 고려하지 않았기 때문에 lastAccessed 값이 다르더라도 다른 데이터 멤버가 동일하면 두 객체는 같다는 판정을 내린다.

 

◾ 동등성

정렬된 범위 안에 있는 개체들의 상대적인 순서로 판단한다.

객체 x, y가 있을 때, x, y 모두가 서로의 앞에 오지만 않으면 동등하다고 본다.

 

!(w1 < w2) && !(w2 < w1)

이 식이 성립하면 동등하다고 본다. 서로의 값이 서로의 앞에 오지 않으면 두 값은 특정한 정렬 기준에 대해서 동등한 것이다.

 

실제로 연관 컨테이너에 사용되는 비교 함수는 operator<가 아니라 기본적으로 less 이다.

 

!c.key_comp()(x,y) && !c.key_comp()(y,x)

c.key_comp는 비교용 함수를 반환해준다.

 

대소문자를 구분하지 않는 set에서 문자열 "STL"과 "stL"은 상등 관계가 아니지만 동등 관계이다.

표준 연관 컨테이너가 상등성이 아닌 동등성에 기반을 두고 만들어진 이유는 비교 함수를 딱 하나만 지정해주기 위해서이다. 만약 상등성에 기반을 두었다면 정렬용 비교 함수 말고도 값이 같은지를 알아내는 함수가 하나 더 필요하다.

 

연관 컨테이너에 값을 넣을때는 동등 관계로 넣고 값을 찾을때는 상등 관계로 찾는다.

 

 

항목 20 : 포인터를 저장하는 연관 컨테이너에 대해서는 적합한 비교(비교 함수자) 타입을 정해주자

연관 컨테이너는 요소를 삽입할 때 자동으로 정렬이 된다.

만약 타입이 포인터라면 포인터 값을 기준으로 정렬을 하기 때문에 별도의 비교 함수를 정해주어야 한다.

 

std::set<string*> ssp;
ssp.insert(new std::string("Anteater"));
...

auto i = ssp.begin();
*i; // 포인터 값
**i; // 데이터

역참조를 두번 하면 데이터에 접근할 수 있지만 애초에 정렬 기준이 데이터가 아니라서 저장 순서도 뒤죽박죽이다.

 

struct StringPtrLess : public std::binary_function<const std::string*, const std::string*, bool> {
    bool operator()(const std::string* ps1, const std::string* ps2) const {
        return *ps1 < *ps2;
    }
};

기본으로 지정되는 비교 함수자 대신에 포인터가 가리키는 요소를 비교하는 임의의 비교 함수 객체를 만들어서 선언시 지정해주면 된다.

 

typedef std::set<std::string*, StringPtrLess> StringPtrSet;

StringPtrSet ssp;
ssp.insert(new std::string("Anteater"));
...

string의 포인터를 저장하기 때문에 여전히 데이터에 접근하려면 두 번의 역참조가 이뤄져야 하지만 정렬 기준은 의도한대로 데이터를 기준으로 정렬된다.

 

struct DereferenceLess {
    template<typename PtrType>
    bool operator()(PtrType pT1, PtrType pT2) const {
        return *pT1 < *pT2;
    }
};

std::set<std::string*, DereferenceLess> ssp;

멤버 함수를 템플릿으로 만들면 각 포인터의 타입별로 함수 객체를 만들 필요 없이 범용적으로 사용이 가능하다.

 

꼭 원시 포인터가 아니더라도 포인터처럼 동작하는 스마트 포인터나 반복자 역시 동일하게 적용해야한다.

 

 

항목 21 : 연관 컨테이너용 비교 함수는 같은 값에 대해 false를 반환해야 한다

항목 19 내용의 연장선이다.

set의 비교 함수는 기본적으로 less이다. 만약 less_equal일때의 상황을 가정해보자.

 

std::set<int, std::less_equal<int>> s;
s.insert(10);
s.insert(10); // 중복 값 삽입 시도

 

!(10A <= 10B) && !(10B <= 10A)
// !true && !true => false

중복된 값의 삽입 시도를 했음에도 둘의 값은 동등하지 않다는 결론을 내리고 삽입을 하게된다.

 

연관 컨테이너의 비교 함수는 같은 값에 대해 항상 false를 반환해야 구조가 무너지지 않는다.

관련 정보(strict weak ordering) : https://panty.run/strict-weak-ordering/