[C++/STL] Operator Overloading & Functor

개요

STL을 사용하게 되면 컨테이너 내 요소들의 순서 또는 key를 비교하기 위한 기준이 필요하다.
일반 primitive type의 경우 기본 연산자 (less, greater, equal_to 등)을 제공해서 생략할 수 있지만
custom data type을 사용하거나 sort, unique 기준이 일반적이지 않은 경우
연산자 오버로딩(Operator Overloading) 또는 함수 객체(Function Object, Functor)를 사용해서 기준을 잡아줘야 한다.

 

Function Object (Functor)

클래스의 함수 호출 연산자 (function call operator)를 오버로딩하면 그 클래스의 객체를 함수 포인터처럼 사용할 수 있다.
이렇게 사용하는 객체를 함수 객체 (Function Object) 또는 Functor라고 부른다.
STL Container는 Functor를 인자로 받아 sort, key를 비교하는 기준으로 사용한다.

ex) set<T, Compare> / unordered_set<T, Hash, KeyEqual>

 

Predefined Functor

c++은 사전 정의된 Functor를 제공하는데 STL Container 사용 시 사용하는 대상들을 보자.

 

Comparision Operator

비교 연산자에 대해 사전 정의된 Functor로는 less, greater, equal_to 등이 있다.

• set, map, priority_queue 등은 요소들의 순서를 결정하는 기준이 필요하고 less, greater functor를 default로 사용한다.
• unordered_set, unordered_map은 요소들의 key를 결정하는 기준이 필요하고 equal_to functor를 default로 사용한다.

사전 정의된 Functor에서는 각각 ==, <, > 등의 operator를 사용하고 있기 때문에
data type에 각각 operator==, operator<, operator>가 정의되어 있어야 한다.

그래서, Custom Data Type을 사용하는 경우

1) Functor를 재정의해서 사용하거나,
2) 연산자 오버로딩을 통해 기준을 잡아줘야 한다.

template<class T>
struct equal_to {
    bool operator()(const T& lhs, const T& rhs) const {
        return lhs == rhs;
    }
}

template<class T>
struct less {
    bool operator()(const T& lhs, const T& rhs) const {
        return lhs < rhs;
    }
}

template<class T>
struct greater {
    bool operator()(const T& lhs, const T& rhs) const {
        return lhs > rhs;
    }
}

 

hash Operator

unordered_map, unordered_set은 hash 값을 연산하는 기준이 필요하다.
c++(14)은 primitive type과 string에 대한 사전 정의된 Hash Operator를 제공하기 때문에,
기본 타입을 사용하는 경우 hash operator를 따로 정의해줄 필요가 없다.

Custom Data Type을 사용하는 경우 hash operator를 따로 지정해줘야 한다.

• key 값에 대해 size_t type의 hash 값을 반환 (size_t == unsigned long long)

 

Hash Operator Format

template<class T>
struct hash {
    size_t operator()(const Key& key) const {
        return (hash value);
    }
}

 

예시

struct MyHash {
    size_t operator()(const pii& key) const {
        return (size_t)key.first * n + key.second;
    }
};

 

 

Member Function Overloading (Operator Overloading)

custom data type은 Comparision Operator(==, <, >, () 등)를 사용하려면 연산자 오버로딩을 통해 기능을 재정의해야 한다.
STL Container는 Predifined Functor를 통해 정렬, key 기준을 결정하는데, 각 Functor에서 사용하는 Operator를 재정의하는 방식으로 이를 이용할 수 있다.

예시

struct Data {
    int a, b;
    bool operator<(const Data& r) const {
        if (a == b) return b < r.b;
        else        return a < r.a;
    }
}