게임 프로그래머

map::operator[]는 AddOrUpdate 기능을 수행하도록 설계되어 키를 점검하여 들어있지 않은 경우에 pair가 추가되고, 들어있는 경우에는 value가 업데이트하고 값에 대한 참조자를 반환

키가 있지 않은 경우에 값 타입의 기본 생성자를 사용하여 pair 객체를 새로 생성한 후 operator=를 통해 복사되므로 불필요한 기본 생성자와 대입 연산이 이루어짐

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

map<int, Widget> m;
m[1] = 1.50;

불필요한 기본 생성자와 대입 연산 제거되므로 추가를 하고 싶다면 operator[] 보다는 insert를 쓰는 것이 좋음

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

insert를 호출할 때 pair의 생성자와 소멸자, Widget의 생성자와 소멸자가 반드시 호출됨

반면 키가 이미 존재할 때에 operator[]는 pair의 생성자와 소멸자, Widget의 생성자와 소멸자의 비용이 들지 않음

결론

map에 추가할 경우 insert가 효율적으로 좋고, 갱신할 경우 operator[]이 효율적으로 좋음

추가와 갱신을 한번에 효율을 잡을 수 있는 함수 구현

k의 위치 혹은 삽입 위치를 찾기 위해 lower_bound 호출하고 동등성 검사

단축 정보(hint) : iterator가 k와 동등한 키를 가진 새 요소의 위치를 정확히 가리킴

표준안에 의하면 단축 정보가 제대로 세팅되어 있으면 insert의 수행 시간은 상수 시간

template<typename MapType, typename KeyArgType, typename ValueArgType>
typename MapType::iterator efficientAddOrUpdate(MapType& m, const KeyArgType& k, const ValueArgType& v)
{
    typename MapType::iterator iterator = m.lower_bound(k);
    
    if(iterator != m.end() && !(m.key_comp()(k, iterator->first)))
    {
        iterator->second = v;
        return iterator;
    }
    else
    {
        return m.insert(iterator, typename MapType::value_type(k, v)));
    }
}

KeyArgType과 ValueArgType이 맵에 저장된 타입으로 변환될 수만 있다면(Widget의 경우 operator=) 다른 타입이어도 됨

KeyArgType과 ValueArgType 대신에 MapType::key_type과 MapType::mapped_type을 사용한다면 타입의 불필요한 생성자, 소멸자 비용을 추가로 지불할 수 있음

(Widget의 경우 Widget(double Widget))

efficientAddOrUpdate(m, 1, 1.5);

빠른 데이터 검색을 지원하는 자료구조를 사용할 때 연관 컨테이너를 주로 사용

하지만 탐색 속도가 정말 중요하다면 해쉬 컨테이너(상수 시간 빠른 탐색)를 사용하는 것이 대부분 좋음

(해쉬 함수가 이상하거나 테이블 크기가 너무 작으면 느리지만 거의 드뭄)

표준 연관 컨테이너는 균형 이진 탐색 트리로 구현됨

균형 이진 탐색 트리는 노드의 삽입, 삭제, 탐색이 일정한 순서를 따르지 않으며, 다음 동작이 예측할 수 없는 상황에 적합하도록 구현된 자료 구조

하지만 많은 프로그램이 극단적으로 혼란스럽게 자료구조를 사용하지 않고 보통 3단계로 압축되는 순서를 따름

데이터 셋업

많은 데이터 요소를 넣는 과정으로, 주로 삽입/삭제가 대부분

데이터 탐색

셋업이 끝난 자료 구조를 원하는 정보가 들어있는지 탐색

데이터 재구성

자료구조에 있는 데이터를 변경

보통 기존 데이터를 모두 지우고 새 데이터를 삽입하므로 데이터 셋업과 비슷하며 데이터 탐색 단계로 진입

위의 3단계 방식으로 자료 구조를 사용한다면 vector가 표준 연관 컨테이너보다 나은 수행 성능(수행시간과 메모리 공간 모두)을 제공할 가능성이 높음

벡터가 반드시 정렬돼있어야 binary_search, lower_bound, equal_range 등 탐색 알고리즘을 제대로 적용하여 나은 수행 성능을 보임

첫 번째 이유는 메모리 크기 문제

표준 연관 컨테이너는 균형 이진 탐색 트리 구조로 되어 있어 트리 노드가 포인터로 연결된 구조

각 트리 노드에는 왼쪽/오른쪽 자식 노드 포인터들과 부모 노드 포인터를 저장하므로 메모리 증가

두 번째 이유는 메모리 참조 지역성 문제

컨테이너의 데이터 타입의 Widget이 12바이트이고, 포인터의 크기가 4바이트, 메모리 페이지의 하나가 4K 바이트라고 가정할 때,

vector에 저장하는 경우는 한 페이지에 341개의 Widget이 들어가고 연관 컨테이너는 170개의 Widget이 들어감

가상 메모리 시스템까지 고려했을 때 연관 컨테이너는 불연속적으로 노드를 할당하기 때문에 필요한 메모리 페이지는 더 필요하고, 페이지 폴트도 증가하여 속도가 느려짐

vector로 map/multimap을 흉내내는 방법

vector를 써서 map/multimap을 흉내내려면 pair<const Key, Value>가 아닌 pair<Key, Value>를 사용해야 함

요소 재배치/정렬 과정에서 const Key는 이동, 복사, 대입 연산이 불가능하기 때문

pair에 기본적으로 제공되는 operator<는 pair의 두 멤버를 모두 고려하기 때문에 정렬에 사용하는 비교 함수를 만들어야 함

키 값만 가지고 탐색이 이루어지므로 탐색용 비교 함수도 구현해야 하는데, 첫 번째 매개 변수로 들어가는 데이터가 키인지 페어 객체인지 알 수 없기 때문에 모두 고려해야 함

using Data = pair<string, int>;

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
    {
        return keyLess(lhs.first, k);
    }

    bool operator(const Data::first_type& k, const Data& rhs) const
    {
        return keyLess(k, rhs.first);
    }

private:
    bool keyLess(const Data::first_type& k1, const Data::first_type& k2) const
    {
        return k1 < k2;
    }
};

vector<Data> vd;
...
sort(vd.begin(), vd.end(), DataCompare());

lower_bound(vd.begin(), vd.end(), DataCompare());

모든 표준 연관 컨테이너는 내부에 저장되는 데이터 요소를 정렬해서 관리하며, 컨테이너의 정상적인 동작은 요소들이 정렬된 상태에서만 가능

연관 컨테이너에 들어있는 요소의 값을 바꾼다면 제대로 된 위치에 있을 가능성이 적으므로 컨테이너의 정렬 상태가 무너짐

map<K, V> 혹은 multimap<K, V> 타입의 객체에 저장되는 요소는 pair<const K, V>이기 때문에 map과 multiset은 키 값을 변경하는 것이 불가능

(const_cast를 사용하면 가능하지만 비권장)

map<int, string> m;

m.begin()->first = 100; // 에러

set과 multiset은 set<T> 혹은 multiset<T> 타입의 객체는 데이터 요소의 타입이 T이므로 직접적인 키 변경이 가능

키 변경이 가능하게 구현된 이유는 ID를 실질적인 키로 사용하여 키를 제외한 다른 데이터를 수정하는 경우(setTitle)가 있음

따라서 키가 아닌 데이터를 수정하기 때문에 set 객체를 훼손시키지 않음

class Employee
{
public:
    int getIDNumber() const;
    void setTitle(const string& title);

private:
    int id;
    string title;
};

struct IDNumberLess
{
    bool operator()(const Employee& lhs, const Employee& rhs) const
    {
        return lhs.getIDNumber() < rhs.getIDNumber();
    }
};

using EmpIDSet = set<Employee, IDNumberLess>;
EmpIDSet employeeSet;

EmpIDSet::iterator iterator = employeeSet.find(selectedID);
if(iterator != employeeSet.end())
{
    iterator->setTitle("Corporate Deity");
}

map과 multimap에도 동일한 법칙이 적용될 수 있을 생각이 있겠지만 표준화 위원회에서 map/multimap의 키는 const이어야 하고, set/multiset의 값은 const이면 안된다고 결정

set/multiset의 값은 const가 아니기 때문에 값을 바꾸어도 컴파일 에러가 발생하지 않기 때문에 컨테이너가 정상적으로 작동하기 위해 키에 해당하는 데이터를 변경해서는 안됨

set과 multiset의 요소가 const가 아니어도 데이터 요소의 변경을 막기 위해 iterator의 operator*/operator->를 const T&/const T*를 반환하도록 구현될 수 있음

(C++20에서는 const를 반환)

키 부분이 아닌 데이터의 변경을 위해 const가 아닌 참조자로 캐스팅

EmpIDSet::iterator iterator = employeeSet.find(selectedID);
if(iterator != employeeSet.end())
{
    const_cast<Employee&>(*iterator).setTitle("Corporate Deity");
}

참조자로 캐스팅하지 않는 경우 발생하는 문제

해당 캐스팅의 결과는 *i의 사본인 임시 객체이며 setTitle은 임시 객체에서 호출되므로 set의 객체를 변경하지 않는 오동작 발생

EmpIDSet::iterator iterator = employeeSet.find(selectedID);
if(iterator != employeeSet.end())
{
    static_cast<Employee>(*iterator).setTitle("Corporate Deity");
    ((Employee)(*i)).setTitle("Corporate Deity");
}

캐스팅을 사용하지 않고 안전하게 변경하는 방법

EmpIDSet::iterator iterator = employeeSet.find(selectedID);
if(iterator != employeeSet.end())
{
    EmpIDSet e(*i);
    employeeSet.erase(i++); // 반복자를 후위 증가하여 반복자 무효화 방지
    
    e.setTitle("Corporate Deity");
    employeeSet.insert(i, e);
}

set<int, less_equal<int>> s;
s.insert(10);
s.insert(10);

연관 컨테이너는 동등성을 체크하므로 set은 같은 값이 있는지 체크할 때 동등성을 체크

비교 타입이 less_equal이므로 operator<=가 비교 함수로 쓰이는데, 동일한 값이 동등하지 않다는 결론으로 set에 동일한 값이 추가되어 비정상 컨테이너가 됨

!(10 <= 10) && !(10 <= 10) // 결과는 false

multiset이나 multimap은 중복 객체를 담을 수 있지만 비교 함수는 같은 값에 대해 false로 반환해야 함

equal_range 알고리즘에서 상등한 값의 범위를 식별하는 것이 아닌 동등한 값의 범위를 식별하므로 두 개의 10이 범위에 동시에 들어갈 일이 생기지 않는 오류 발생

multiset<int, less_equal<int>> s;
s.insert(10);
s.insert(10);

따라서 비교 함수가 같은 값에 대해 항상 false를 반환하지 않으면 모든 연관 컨테이너가 정상적으로 동작하지 않음

알파벳 순서대로 출력되길 기대하겠지만 포인터를 담고 있기 때문에 string의 16진수 포인터 값이 출력되므로 루프를 직접 만들지 말라는 좋은 예제

물론 **iterator를 사용하면 알파벳이 출력되지만 포인터 값으로 정렬되기 때문에 정렬을 기대하면 안됨

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

for(set<string*>::const_iterator iterator = ssp.begin(); iterator != ssp.end(); ++iterator)
{
    cout << *iterator << endl;
}

ostream_iterator에 스트림으로 출력해 보낼 객체의 타입을 string으로 정했는데 ssp에 들어있는 것은 string*이므로 컴파일 에러 발생

copy(ssp.begin(), ssp.end(), ostream_iterator<string>(cout, "\n"));

string*를 매개변수로 받아 string끼리 비교 함수자 구현하여 정렬 지원

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

using StringPtrSet = set<string*, DereferencePtrLess>
StringPtrSet ssp;

루프를 직접 만들지 않고 알고리즘을 통한 순회

for_each(ssp.begin(), ssp.end(), [](const string* ps){ cout << *ps << std::endl;});

transform(ssp.begin(), ssp.end(), ostream_iterator<string>(cout, "\n"), Dereference());

set 템플릿에 들어가는 매개 변수는 타입이어야 하므로 비교 함수를 넣을 경우 컴파일되지 않음

bool stringPtrLess(const string* ps1, const string* ps2)
{
    return *ps1 < *ps2;
}

set<string, stringPtrLess> ssp; // 컴파일 에러

포인터 뿐만 아니라 포인터처럼 동작하는 객체(스마트 포인터, 반복자 등)에도 적용되는 내용

상등성

operator==

x==y에서 x와 y가 같다고 해서 모든 데이터가 같은 값이 아닐 수 있고 operator==을 어떻게 정의하냐에 따라 다름

class Widget
{
public:
    bool operator==(const Widget& rhs)
    {
        // lastAccessed를 비교하지 않아도됨
    }

private:
    bool lastAccessed;
};

동등성

operator<, less

STL 모든 연관 컨테이너(set, multiset, map, multimap)가 내부 데이터 요소를 관리할 때 사용하는 정렬 순서

x, y 모두가 c의 정렬 순서에 대해 서로의 앞에 오지 않으면 동등

key_comp는 비교용 함수 혹은 함수 객체를 반환하는 함수

(x < y == false) && (y < x == false)
s.key_comp()(x,y) == false && s.key_comp()(y,x) == false;

연관 컨테이너의 비교 함수

연관 컨테이너의 기본 비교 함수는 less

동등성은 비교 함수의 동작 원리에 따라 정해지므로 컨테이너를 인스턴스화할 때 비교 함수를 하나만 지정

template <class _Kty, class _Pr = less<_Kty>, class _Alloc = allocator<_Kty>>
class set : public _Tree<_Tset_traits<_Kty, _Pr, _Alloc, false>>

연관 컨테이너의 커스텀 비교 함수(comparison function)를 설정하는 예제

커스텀 비교 함수를 사용할 경우 멤버 함수 find는 동등성을 사용하지만 알고리즘 find는 상등성을 사용하므로 둘의 결과가 다를 수 있으므로 멤버 함수를 선호해야 함

struct CIStringCompare
{
    bool operator()(const string& lhs, const string& rhs) const
    {
        // 구현
    }
};

set<string, CIStringCompare> setStringCompare;

만약 정렬 기준이 상등성이었다면 정렬용 비교 함수 말고 값이 같은지 비교하는 함수가 기본 비교 함수로 하나 더 필요했음

만약 insert에서 동등성을 검사하고 find에서 상등성을 검사한다면 "persephone"은 추가되지 않아 if 문이 false가 됨

따라서 두 개의 비교 함수를 사용하게 되면 규칙을 정확히 지키지 않는 이상 컨테이너 혹은 함수의 값이 복잡해질 수 있음

set2CF<string, CIStringCompare, equal_to<string>> s;
s.insert("Persephone");
s.insert("persephone");

if(s.find("persephone") != s.end())

상등성이 필요하다면 equal_to 혹은 operator==을 사용