41-1-라.동등성 조건

디폴트 비교 함수 객체인 less는 키 비교를 위해 < 연산자를 사용하며 greater로 바꿀 경우는 > 연산자가 필요하다. 비교 함수 객체를 직접 만들 때도 크다 또는 작다 둘 중의 하나로 전후 관계를 분명히 판별하는 식으로 작성해야 한다. 정렬을 위한 위치를 판별하는데 == 연산자는 별반 쓸모가 없다. 왜냐하면 이분 검색이 가능하기 위해서는 상등 비교가 아닌 대소 비교를 여러 번 해야 하기 때문이다. 정렬이란 상대적인 순서를 정하는 연산이므로 같다는 조건은 필요가 없다.

비슷한 이유로 >=, <= 같은 조건도 사용할 수 없다. 이 두 조건은 실제로는 두 조건의 OR 결합이기 때문에 키의 분명한 전후 관계를 판별하는데는 쓸 수 없기 때문이다. <=연산자로 키를 비교해서 true라는 결과가 나왔다 하더라도 같아서 ture인지 작아서 true인지를 알 수 없으므로 애매모호한 것이다. <= 연산을 정렬 조건으로 주면 어떤 결과가 나오는지 테스트해 보자.

 

: setlessequal

#include <Turboc.h>

#include <iostream>

#include <set>

using namespace std;

 

template<typename C> void dump(const char *desc, C c) { cout.width(12);cout << left << desc << "==> ";

      copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," ")); cout << endl; }

 

void main()

{

     randomize();

     set<int, less_equal<int> > s;

     for (int i=0;i<20;i++) {

          s.insert(random(30));

     }

     dump("결과",s);

}

 

정수형 셋에 20개의 난수를 마구 집어 넣어 보았다. 실행 결과는 매번 다르겠지만 대충 다음과 같이 나온다.

 

결과        ==> 1 2 5 5 8 9 11 14 15 18 18 18 19 20 22 23 23 24 26 27

 

<= 연산은 확정적이지 못하므로 셋이 정신을 못차리고 엉뚱한 비교를 해 대며 그러다 보니 같은 값도 다르다고 판단하여 중복 삽입되는 것이다. 그래서 셋은 < 아니면 > 두 연산자 중 하나로만 비교해야 한다. 둘 중 어떤 것을 쓰나 상관은 없는데 사람들은 보통 오름차순을 더 좋아하므로 디폴트 비교 객체는 less로 선택되어 있다.

그런데 이분 검색중에 범위를 좁혀 나갈 때는 < 미만 비교 연산자만으로도 충분하지만 검색을 할 때는 정확하게 같은 것이 있는지 조사해야 하므로 == 연산이 필요하다. 그러나 셋은 == 연산을 요구하지 않으며 대신 < 연산의 조합으로 검색할 키를 찾는다. 여기서 동일성과 동등성의 개념이 나누어진다.

 

동일성(equality) : 두 값이 완전히 같은지 검사한다. 객체의 경우 모든 멤버가 일치해야 동일하며 주로 == 연산자를 사용한다.

동등성(equivalance) : 두 값이 같은 값으로 인정되는지 검사한다. 키에 해당하는 값만 비교하며 < 연산자의 조합으로 정의된다.

 

동일성은 두 값이 완전히 같다는 뜻이고 동등성은 두 값이 집합의 기준에서 볼 때 같다고 인정된다는 뜻이다. STL에서 두 키 a와 b의 동등성은 다음 조건으로 점검한다.

 

!(a < b) && !(b < a)

 

a가 b보다 작지 않고 b가 a보다 작지 않으면 두 키가 동등하다고 인정하는 것이다. 좀 어려워 보이는 수식이지만 쉽게 얘기하면 어느 쪽도 크다고 말할 수 없을 때 두 키가 같다고 판단한다. 동등성을 표현하는 이 조건은 비교 객체가 디폴트인 less일 때의 얘기이고 좀 더 일반적으로 얘기하자면 비교 객체가 Comp일 때 다음 조건을 만족해야 두 키가 동등하다고 한다.

 

!Comp(a,b) && !Comp(b,a)

 

순서를 바꿔가며 비교해 봐도 둘 다 거짓일 때만 동등하다. 셋의 insert 함수는 삽입 위치를 결정하기 위해 동등성의 개념을 사용한다. 이 동등성의 개념이 왜 중요한지 다음 예제를 통해 알아보자.

 

: President

#include <iostream>

#include <set>

#include <string>

#include <algorithm>

using namespace std;

 

class President

{

public:

     int Id;

     string Name;

     string Addr;

 

     President(int aId,char *aName, char *aAddr)

          : Id(aId), Name(aName), Addr(aAddr) { }

     void OutPresident() {

          printf("Id:%d, 이름:%s, 주소:%s\n",Id,Name.c_str(),Addr.c_str());

     }

     bool operator<(const President &Other) const {

          return Id < Other.Id;

     }

     bool operator==(const President &Other) {

          return (Id==Other.Id && Name==Other.Name && Addr==Other.Addr);

     }

};

 

void main()

{

     set<President> King;

     King.insert(President(516,"박정희","동작동"));

     King.insert(President(1212,"전두환","연희동"));

     King.insert(President(629,"노태우","강북"));

     King.insert(President(3030,"김영삼","상도동"));

     King.insert(President(1234,"김대중","강남"));

 

     set<President>::iterator it;

     for (it=King.begin();it!=King.end();it++) {

          (*it).OutPresident();

     }

     President ZeroThree(3030,"아무개","아무데나");

     it=King.find(ZeroThree);

     if (it != King.end()) {

          cout << "검색되었음" << endl;

          (*it).OutPresident();

     }

     it=find(King.begin(),King.end(),ZeroThree);

     if (it != King.end()) {

          cout << "검색되었음" << endl;

          (*it).OutPresident();

     }

}

 

President 클래스는 높으신 어른들을 표현하는데 일반적인 인물 정보라고 생각하면 될 것이다. 멤버로는 유일한 값을 보장하는 Id와 이름, 주소 등이 포함되어 있다. 실무에 사용하는 클래스라면 생년월일, 성별, 본적, 주민등록번호, 전화 번호 등등 온갖 상세한 정보들이 포함되어야 할 것이다. President는 < 연산자와 == 연산자를 제공하는데 < 연산자는 Id만으로 우선 순위를 판별하는 동등성 점검을 하고 == 연산자는 모든 멤버를 다 비교하는 동일성 검사를 하고 있다.

main에서는 President의 셋 King을 선언하고 다섯 개의 요소를 삽입한다. 별다른 비교 함수 객체를 지정하지 않았으므로 디폴트 비교 함수 객체인 less가 사용되며 따라서 실제 비교에는 객체의 < 연산자가 사용된다. < 연산자가 Id로 비교를 수행하므로 Id의 오름차순으로 정렬되며 같은 Id를 가지는 요소는 삽입이 거부된다. 일단 실행 결과를 보자.

 

Id:516, 이름:박정희, 주소:동작동

Id:629, 이름:노태우, 주소:강북

Id:1212, 이름:전두환, 주소:연희동

Id:1234, 이름:김대중, 주소:강남

Id:3030, 이름:김영삼, 주소:상도동

검색되었음

Id:3030, 이름:김영삼, 주소:상도동

 

순서를 아무렇게나 삽입했지만 Id순으로 정렬되어 들어감을 확인할 수 있다. 요소들을 전부 삽입한 후 find 멤버 함수로 3030 Id를 가지는 "아무데나"에 사는 "아무개"를 검색해 보았다. 이런 정보를 가지는 객체는 셋에 포함되어 있지 않지만 결과는 검색되었다고 나온다. 왜 이런 결과가 나오는가 하면 find 멤버 함수가 이분 검색을 하면서 < 연산자만을 사용하여 동등성을 비교하기 때문이다.

< 연산자는 Id만을 비교하므로 3030과 크지도 않고 작지도 않으면 같은 것으로 취급한다. 이름이나 주소는 아무런 고려 대상이 되지 못한다. set이 삽입이나 검색을 위해 동일성이 아닌 동등성의 개념을 사용한다는 것을 분명히 확인할 수 있다. President 클래스에 == 연산자를 빼 버려도 이 셋은 잘 동작하는 것을 보면 셋은 == 연산을 전혀 사용하지 않음을 알 수 있다.

반면 전역 find 함수는 구현 코드를 보면 알겠지만 == 연산자로 동일한 요소를 검색한다. King 셋에는 아무데나에 사는 아무개라는 인물이 없으므로 find 전역 함수는 아무 것도 찾지 못할 뿐만 아니라 == 연산자가 없으면 제대로 컴파일되지도 않는다.

이 예제에서 Id는 요소의 키로 사용되는데 키는 중복되지 않는 성질을 가져야 한다. 사람에 대한 정보라면 주민등록번호가 키로 사용될 것이고 서적 정보라면 ISBN이 키로 사용될 것이다. 객체들은 키만 일치하면 동등한 것으로 판단하는 것이 상식적이며 나머지 요소들은 전혀 비교의 대상이 아니다. 그래서 셋은 키만을 비교하는 동등성의 개념을 사용하는 것이다.

동등성은 동일성 조건의 일부만을 칭하는 개념인데 셋에 포함되는 객체가 멤버 전체를 키로 사용하지 않을 수 있으므로 동일성이 아닌 동등성으로 정렬을 하는 것이 논리적으로 합당하다. int나 double같은 타입은 객체 전체가 키이므로 동등성이 동일성과 같으며 이 둘을 같이 사용해도 별 상관이 없다. 사실 find 멤버 함수나 이분 검색의 최종 일치 점검을 위해 동등성보다는 동일성이 더 편리하다. 그러나 이렇게 할 경우 < 연산자와 == 연산자가 비교의 대상을 다른 것으로 정의하면 엄청난 혼란을 야기하게 된다. 그래서 하나의 조건만으로 모든 것을 처리할 수 있는 정책을 취하는 것이 옳다.

키 변경 불가 원칙

셋은 요소를 정렬할 때 항상 키값을 기준으로 하며 검색할 때도 키값의 대소를 판별하여 이분 검색한다. 객체의 어떤 멤버가 키인가는 객체마다 다를 수 있는데 동등성 비교에 사용되는 모든 멤버가 키라고 할 수 있다. 키는 셋이 요소의 순서를 정하기 위해 사용하는 중요한 값이므로 셋에 이미 들어가 있는 키를 변경해서는 안된다. 다음 예제를 보자.

 

: KeyChange

#include <iostream>

#include <set>

using namespace std;

 

template<typename C> void dump(const char *desc, C c) { cout.width(12);cout << left << desc << "==> ";

      copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," ")); cout << endl; }

 

void main()

{

     int ar[]={1,3,2,6,4,5};

     int i;

     set<int> s;

     for (i=0;i<sizeof(ar)/sizeof(ar[0]);i++) {

          s.insert(ar[i]);

     }

     dump("최초",s);

     set<int>::iterator it;

     it=s.begin();it++;it++;it++;

     *it=99;

     dump("수정후",s);

     it=s.find(5);

     if (it!=s.end()) {

          cout << *it << endl;

     } else {

          cout << "찾는 키가 없습니다." << endl;

     }

}

 

정수형 셋 s에 1~6까지의 정수를 삽입했는데 배열에는 엉망으로 초기화되어 있지만 셋에 들어가면서 알아서 정렬될 것이다. 이 상태에서 3번째 키에 대한 반복자를 얻은 후 이 반복자 위치의 키를 99로 변경했다. 그리고 셋에 5가 있는지 검색해 보았다. 실행 결과는 다음과 같다.

 

최초        ==> 1 2 3 4 5 6

수정후      ==> 1 2 3 99 5 6

찾는 키가 없습니다.

 

삽입 직후에는 제대로 정렬되어 있지만 반복자로 키의 값을 강제로 바꾼 후에는 정렬 상태가 깨져 버렸다. 셋은 요소들이 항상 정렬되어 있다고 가정하고 동작하며 삽입할 때 스스로 정렬된 위치에 삽입한다. 그러나 이 예제처럼 키를 강제로 바꿔 버리면 셋은 무결성이 깨져 버려 이후의 어떠한 동작도 보장하지 못한다.

5가 분명히 있음에도 불구하고 없다고 오판하는 이유는 이분 검색 중에 5앞에 99를 먼저 보게 되고 99 뒤쪽에는 절대로 5가 있을 수 없다고 판단해 버리기 때문이다. 검색뿐만 아니라 이후의 삽입도 완전 엉망이 되고 만다. 한 번 무결성이 깨져 버리면 셋은 그야말로 쓰레기통이 되어 버리는 것이다.

그렇다면 셋은 이런 위험한 동작에 대해 왜 방어를 하지 못하는 것일까? begin이나 find 등 반복자를 리턴하는 멤버 함수들이 const_iterator를 리턴한다면 컴파일 중에 키값을 변경하는 것을 막을 수 있을 것이다. 그러나 이 함수들이 상수 반복자를 리턴하지 못하는 이유는 객체의 모든 값이 키가 아니기 때문이다. President예제에 다음 코드를 작성하는 것은 완전히 합법적이다.

 

it->Addr="제주도";

 

검색 결과 찾은 객체의 주소가 제주도로 바뀌는 것은 셋의 무결성을 전혀 해치지 않는다. 뭐 살다 보면 이사를 간다거나 이름을 바꿀 수도 있는 노릇 아니겠는가? 이런 동작이 허용되어야 하므로 반복자 자체는 상수가 될 수 없는 것이다. 따라서 셋의 반복자를 사용할 때는 가급적이면 iterator 타입보다는 const_iterator 타입을 사용하는 것이 바람직하며 불가피하게 iterator 타입을 써야 한다면 키의 값을 바꾸지 않도록 알아서 조심하는 수밖에 없다. 반면 키와 값이 분리되어 있는 맵은 이 문제에 대해 확실한 안전 장치를 제공한다.

만약 키를 꼭 바꾸고 싶다면 어떻게 해야 할까? 이때는 원하는 요소를 일단 삭제하고 키를 변경한 후 다시 삽입하는 방법밖에 없다. 그래야 insert 함수가 변경된 키 위치에 맞게 정렬된 위치를 찾아 제대로 삽입하며 셋은 계속 무결성을 유지할 수 있다. 요점은 셋에 이미 들어가 있는 요소의 키는 절대 바꾸어서는 안된다는 것이다.