Utils

less

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

Node

template <typename T>
struct Node
{
	T		_data;
	Node	parent;
	Node	left;
	Node	right;

	Node(const T& data = T()) : _data(data), parent(nullptr), left(nullptr), right(nullptr) {}
	Node(const Node &other) : _data(other._data), parent(nullptr), left(nullptr), right(nullptr) {}
};

pair & make_pair

template <typename T1, typename T2>
struct Pair {
	typedef T1		first_type;
	typedef T2		second_type;

	T1 first;
	T2 second;

	Piar() : first(), second() {}
	Pair (T1 const &x1, T2 const &y) : first(x), second(y) {}

	Pair (Pair<T1, T2> const &other) : first(other.first), second(other.second) {}
	template< typename U1, typename U2>
	Pair (Pair<U1, U2> const &other) : first(other.first), second(other.second) {}

	Pair<T1, T2> &operator=(Pair<T1, T2> const &other) {
		this->first = other.first;
		this->second = other.second;
		return (*this);
	}
	Pair<T1, T2> &operator=(Pair<U1, U2> const &other) {
		this->first = other.first;
		this->second = other.second;
		return (*this);
	}
	~Pair() {}
};
template<typename T1, typename T2>
Pair<T1, T2> make_pair(T1 first, T2 second) {
	return (Pair<T1, T2>(first, second));
}

lexicographical_compare

template<class InputIt1, class InputIt2>
bool lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)
{
	for ( ; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2 ) {
		if (*first1 < *first2) return true;
		if (*first2 < *first1) return false;
	}
	return (first1 == last1) && (first2 != last2);
}

두 구간의 대응되는 요소를 차례대로 비교하는데 첫 번째 요소가 두 번째 요소보다 작으면 true를 리턴하고 크면 false를 리턴하며 즉시 종료한다. 만약 같다면 다음 요소를 똑같은 방식으로 계속 비교하기를 구간끝까지 반복한다. 디폴트 비교 함수 객체가 less이므로 첫 번째 구간이 두 번째 구간보다 작아야만 true를 리턴하며 같을 경우는 작지 않으므로 false가 리턴된다. 만약 첫 번째 구간이 먼저 끝나고 두 번째 구간은 아직 값이 남았으면 이 경우는 true를 리턴한다.