advance 의 구현으로 배우는 테크닉

• container 안의 item을 증가시키고 싶을때
  • ++ 등을 사용하는 것보다 advance를 사용하면, container가 달라도 같은 구현을 유지할 수 있어서 좋다.
•  std::advance(it, N)
  • 반복자 it를 N만큼 이동하는 알고리즘
  • <iterator>
  • 반복자의 종류(category) 에 따라 +또는 ++ 연산자 사용
• advance 구현방법
  • tag_dispatching : C++98
  • enable_if : C++11
  • if constexpr : C++17
  • concept & requires clauses : C++20

#include<iostream>
#include<vector>
#include<list>
#include<iterator>

int main()
{
//	std::vector<int> c = { 1,2,3,4,5,6,7,8,9,10 };
	std::list<int> c = { 1,2,3,4,5,6,7,8,9,10 };

	auto p = std::begin(c);
	
	// 반복자를 5칸 전진하고 싶다
	// p=p+5
	// ++p; ++p; ++p; ++p; ++p;

	std::advance(p, 5);

	std::cout << *p << std::endl;
}

 

• Tag dispatching 으로 구현
  1. empty class를 사용해서 반복자의 종류를 나타내는 타입 설계
  2. iterator 설계시 "using iterator_category=종류" 를 멤버타입으로 제공
  3. 반복자의 종류에 따라 다르게 구현된 advance_imp( it, sz, 종류(category) ) 함수 제공
  4. advance() 함수에서 "T::iterator_category"에 따라 적절한 advance_imp() 호출
• 1,2 번은 이미 STL 에 구현이 되어있어서 없어도 무방

// 1. empty class를 사용해서 반복자의 종류(category) 를 타입화한다.
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : input_iterator_tag {};
struct bidirectional_iterator_tag : forward_iterator_tag {};
struct random_access_iterator_tag : bidirectional_iterator_tag {};

// 2. 각 컨테이너의 반복자설계시 해당 반복자가 어떤 종류(category)인지
// 약속된 형태(iterator_category)로 외부에 알려준다
template<typename T>
class vector_iterator
{
	using iterator_category = random_access_iterator_tag;
};

template<typename T>
class list_iterator
{
	using iterator_category = input_iterator_tag;
};

// 3. 반복자의 종류에 따라 다르게 동작하는 advance_imp() 함수 제공
template<typename T>
void advance_imp(T& it, std::size_t sz, std::random_access_iterator_tag)
{
	it = it + sz;
	std::cout << "using +" << std::endl;
}

template<typename T>
void advance_imp(T& it, std::size_t sz, std::input_iterator_tag)
{
	while (--sz)
		++it;
	std::cout << "using ++" << std::endl;
}

// 4. advance() 함수에서 전달된 반복자 안의 "iterator_category" 에 따라 tag_dispatching
template<typename T>
void xadvance(T& it, std::size_t sz)
{
	advance_imp(it, sz, typename T::iterator_category());
}

int main()
{
//	std::vector<int> c = { 1,2,3,4,5,6,7,8,9,10 };
	std::list<int> c= { 1,2,3,4,5,6,7,8,9,10 };

	auto p = std::begin(c);

	xadvance(p, 5);
	std::cout << *p << std::endl;
}

 

• Tag dispatching 버전의 개선 - 일반 array 도 가능하게 할 수 있을까?
  • advance_imp를 호출할때, iterator_category 를iterator_traits<T> 로 감싸주고
  • iterator_traits<T>를 이용해서 template 부분특수화를 사용한다

#include<iostream>
#include<vector>
#include<list>

template<typename T>
struct iterator_traits
{
	typedef typename T::iterator_category iterator_category;
};

template<typename T>
struct iterator_traits<T*>
{
	typedef std::random_access_iterator_tag iterator_category;
};

// 3. 반복자의 종류에 따라 다르게 동작하는 advance_imp() 함수 제공
template<typename T>
void advance_imp(T& it, std::size_t sz, std::random_access_iterator_tag)
{
	it = it + sz;
}

template<typename T>
void advance_imp(T& it, std::size_t sz, std::input_iterator_tag)
{
	while (--sz) ++it;
}

// 4. advance() 함수에서 전달된 반복자 안의 "iterator_category" 에 따라 tag_dispatching
template<typename T>
void xadvance(T& it, std::size_t sz)
{
//				int*::iterator_category
//	advance_imp(it, sz, typename T::iterator_category());
	advance_imp(it, sz, typename iterator_traits<T>::iterator_category());
}

int main()
{
//	std::vector<int> c = { 1,2,3,4,5,6,7,8,9,10 };
//	std::list<int> c= { 1,2,3,4,5,6,7,8,9,10 };
	int c[10]= { 1,2,3,4,5,6,7,8,9,10 };

	auto p = std::begin(c);		// p 는 int*

	xadvance(p, 5);
	std::cout << *p << std::endl;
}

 

• size_t 대신, stl container의 size에 따라서 변경가능한 변수를 사용하자
  • T::difference_type
  • 이것 역시 iterator_traits<T> 를 사용해서, std::iterator_traits<T>::difference_type

#include<iostream>
#include<vector>
#include<list>

template<typename T>
struct iterator_traits
{
	typedef typename T::iterator_category iterator_category;
};

template<typename T>
struct iterator_traits<T*>
{
	typedef std::random_access_iterator_tag iterator_category;
};

template<typename T>
void advance_imp(T& it, typename std::iterator_traits<T>::difference_type sz, std::random_access_iterator_tag)
{
	it = it + sz;
	std::cout << "using +" << std::endl;
}

template<typename T>
void advance_imp(T& it, typename std::iterator_traits<T>::difference_type sz, std::input_iterator_tag)
{
	while (--sz)
		++it;
	std::cout << "using ++" << std::endl;
}

// size_t 대신 STL container에 맞게 정의된 size type을 사용하자
//  T::difference_type -> std::iterator_traits<T>::difference_type
template<typename T>
void xadvance(T& it, typename std::iterator_traits<T>::difference_type sz)
{
//					int*::iterator_category
//	advance_imp(it, sz, typename T::iterator_category());
	advance_imp(it, sz, typename iterator_traits<T>::iterator_category());
}

// tag_dispatching 버전의 개선 - 컨테이너(c)가 일반 array 일때도 동작하게 하고싶다
// iterator_traits<T> 로 감싸주고 iterator_traits<T>를 이용해서 template 부분특수화를 사용한다
int main()
{
//	std::vector<int> c = { 1,2,3,4,5,6,7,8,9,10 };
//	std::list<int> c= { 1,2,3,4,5,6,7,8,9,10 };
	int c[10]= { 1,2,3,4,5,6,7,8,9,10 };

	auto p = std::begin(c);		// p 는 int*

	xadvance(p, 5);
	std::cout << *p << std::endl;
}

 

• C++11 부터는 enable_if_t<> 를 사용해서 코드를 조금 더 간략하게 만들 수 있다.
  • +와 ++로 구현된 동일한 이름의 2개의 템플릿을 제공
  • 조건(반복자의 종류)에 따라 다른 템플릿을 선택하기 위해서 enable_if 를 사용한다

template<typename t>
std::enable_if_t<조건, 함수반환값>
xadvance(...)
{
}

1. 템플릿 함수의 반환값 자리에 놓임
2. 조건이 참인경우 함수 반환값을 사용
3. 조건이 거짓인 경우 함수 템플릿을 사용하지 않음

• std::is_same_v<A, B> : 같은 타입일때는 참

#include<iostream>
#include<vector>
#include<list>

template<typename T>
std::enable_if_t< std::is_same_v< std::random_access_iterator_tag, typename std::iterator_traits<T>::iterator_category>, void>
 xadvance(T& it, typename std::iterator_traits<T>::difference_type sz)
{
	it = it + sz;
	std::cout << "using +" << std::endl;

}

template<typename T>
std::enable_if_t< std::is_same_v< std::input_iterator_tag, typename std::iterator_traits<T>::iterator_category>, void>
xadvance(T& it, typename std::iterator_traits<T>::difference_type sz)
{
	while (--sz)
		++it;
	std::cout << "using ++" << std::endl;
}

int main()
{
//	std::vector<int> c = { 1,2,3,4,5,6,7,8,9,10 };
//	std::list<int> c= { 1,2,3,4,5,6,7,8,9,10 };
	int c[10]= { 1,2,3,4,5,6,7,8,9,10 };

	auto p = std::begin(c);		// p 는 int*

	xadvance(p, 5);
	std::cout << *p << std::endl;
}

 

• C++17 에서는 if constexpr 을 사용해서 구현할 수 있다.
  • 간단하게 생각해봤을때, xadvance 안에서 타입을 검사해서 되는쪽으로 분기하면 된다.
  • 하지만 if를 사용하면, 작동하지 않는 타입의 경우에도 if 문 아래의 code가 template으로 부터 생성되므로, 오류가 발생
  • 그래서 나온 것이 if constexpr - 거짓이면 code 조차 생성하지 않는다

#include<iostream>
#include<vector>
#include<list>

template<typename T>
void xadvance(T& it, typename std::iterator_traits<T>::difference_type sz)
{
	// if를 사용하면, 작동하지 않는 타입의 경우에도 if 문 아래의 code가 template으로 부터 생성되므로, 오류가 발생
	// if constexpr - 거짓이면 code 조차 생성하지 않는다
	if constexpr (std::is_same_v< std::random_access_iterator_tag, typename std::iterator_traits<T>::iterator_category>)
	{
		it = it + sz;
		std::cout << "using +" << std::endl;
	}
	else
	{
		while (sz--)
			++it;
		std::cout << "using ++" << std::endl;
	}
}

int main()
{
	std::vector<int> c = { 1,2,3,4,5,6,7,8,9,10 };
	std::list<int> c2= { 1,2,3,4,5,6,7,8,9,10 };
	int c3[10]= { 1,2,3,4,5,6,7,8,9,10 };

	auto p = std::begin(c);
	xadvance(p, 5);
	auto p2 = std::begin(c2);		
	xadvance(p2, 5);
	auto p3 = std::begin(c3);
	xadvance(p3, 5);

	std::cout << *p << std::endl<< *p2 <<std::endl<<*p3 << std::endl;
}

 

• C++20 부터는 concept 으로 구현 가능
  • enable_if 가 template 함수의 return 값 부분에 삽입해서, 조건에 따라 template 코드를 생성하지 않는 것이었는데, 코드가 좀 억지스럽게 느껴진다
  • concept을 이용하면, 조금 더 나은 방향으로 개선 가능

#include<iostream>
#include<vector>
#include<list>
// enable_if 가 좀 코드가 지저분하니, C++20 부터는 concept으로 하면 조금더 나은 코드로 변경가능
template<typename T>
requires std::is_same_v< std::random_access_iterator_tag, typename std::iterator_traits<T>::iterator_category>
void xadvance(T& it, typename std::iterator_traits<T>::difference_type sz)
{
	it = it + sz;
	std::cout << "using +" << std::endl;
}

template<typename T>
	requires (! std::is_same_v< std::random_access_iterator_tag, typename std::iterator_traits<T>::iterator_category>)
void xadvance(T& it, typename std::iterator_traits<T>::difference_type sz)
{
	while (sz--)
		++it;
	std::cout << "using ++" << std::endl;
}

int main()
{
	std::vector<int> c = { 1,2,3,4,5,6,7,8,9,10 };
	std::list<int> c2 = { 1,2,3,4,5,6,7,8,9,10 };
	int c3[10] = { 1,2,3,4,5,6,7,8,9,10 };

	auto p = std::begin(c);
	xadvance(p, 5);
	auto p2 = std::begin(c2);
	xadvance(p2, 5);
	auto p3 = std::begin(c3);
	xadvance(p3, 5);

	std::cout << *p << std::endl << *p2 << std::endl << *p3 << std::endl;
}

• 이 버전도 여전히 복잡하다.
• C++20에 추가된 random_access_iterator 라는 concept을 이용하면 조금 더 심플하게 할 수 있다.

#include<iostream>
#include<vector>
#include<list>
//random_access_iterator concept으로 하면 조금더 나은 코드로 변경가능
template<typename T>
requires std::random_access_iterator<T>
void xadvance(T& it, typename std::iterator_traits<T>::difference_type sz)
{
	it = it + sz;
	std::cout << "using +" << std::endl;
}

template<typename T> 
requires (! std::random_access_iterator<T> )
void xadvance(T& it, typename std::iterator_traits<T>::difference_type sz)
{
	while (sz--)
		++it;
	std::cout << "using ++" << std::endl;
}

int main()
{
	std::vector<int> c = { 1,2,3,4,5,6,7,8,9,10 };
	std::list<int> c2 = { 1,2,3,4,5,6,7,8,9,10 };
	int c3[10] = { 1,2,3,4,5,6,7,8,9,10 };

	auto p = std::begin(c);
	xadvance(p, 5);
	auto p2 = std::begin(c2);
	xadvance(p2, 5);
	auto p3 = std::begin(c3);
	xadvance(p3, 5);

	std::cout << *p << std::endl << *p2 << std::endl << *p3 << std::endl;
}