set, lower_bound(), upper_bound()에 사용자 지정 타입 사용

 

set 자료구조나 lower_bound(), upper_bound() 함수에 사용자 정의 타입을 사용하기 위해서는 < 연산자를 오버로드 해주어야 한다.

• 하지만, 각 경우에 따라 오버로드 함수의 시그니처가 다르다.

 

struct Item
{
    int data;

    // set
    friend bool operator < (const Item& A, const Item& B) { return A.data < B.data; }
    // lower_bound
    friend bool operator < (const Item& left, int right)  { return left.data < right; }
    // upper_bound
    friend bool operator < (int left, const Item& right)  { return left < right.data; }
};

 

Item을 data에 따라 정렬하여 set에 저장하고, vector로 변환하여 lower_bound()와 upper_bound() 함수를 사용하는 예시다.

 

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

void main()
{
    set<Item> st;

    st.insert({1});
    st.insert({10});
    st.insert({100});
    st.insert({1000});

    vector<Item> v(st.begin(), st.end());

    int index = lower_bound(v.begin(), v.end(), 10) - v.begin();
    cout << "[" << index << "] " << v[index].data << endl;

    index = upper_bound(v.begin(), v.end(), 10) - v.begin();
    cout << "[" << index << "] " << v[index].data << endl;
}

 

출력

[1] 10
[2] 100