References
- C++ Standard Library 2nd
Contents
- Iterator Traits
- User-Defined Iterators
Iterator Traits
반복자에는 위와 같이 다양한 카테고리가 있습니다. 이는 각각이 자신만의 특수한 기능이 있다는 것을 나타냅니다. 서로 다른 반복자 카테고리는 서로의 동작을 오버로딩할 수도 있고, 오버로딩될 수 있습니다. 이때, iterator tags와 iterator traits를 사용하여 이러한 오버로딩을 적용할 수 있습니다.
각 반복자 카테고리에서 C++ 표준 라이브러리는 iterator에 대한 "label"처럼 사용되는 iterator tag를 제공합니다.
실제 헤더 파일을 살펴보면 상속이 사용되었다는 것을 볼 수 있습니다. 따라서, forward_iterator_tag는 input_iterator_tag에 속하게 됩니다. output_iterator_tag를 상속하는 카테고리는 없는 것을 볼 수 있는데, 오직 mutable forward iterator만이 output iterator의 요구사항을 만족시킵니다. 다만, 이에 해당하는 카테고리가 존재하지는 않습니다.
만약 제너릭 코드를 작성한다면, 카테고리뿐만 아니라 반복자가 가리키는 요소의 데이터 타입 등이 필요할 수 있습니다. 따라서, C++ 표준 라이브러리는 iterator traits를 정의하는 특별한 템플릿 구조체를 제공합니다. 이 구조체에는 반복자에 필요한 정보가 있으며, 반복자가 가져야 하는 모든 데이터 타입(카테고리, 요소의 타입 등)에 대한 공통 인터페이스로 사용합니다.
template<typename _Iterator, typename = __void_t<>>
struct __iterator_traits { };
template<typename _Iterator>
struct __iterator_traits<_Iterator,
__void_t<typename _Iterator::iterator_category,
typename _Iterator::value_type,
typename _Iterator::difference_type,
typename _Iterator::pointer,
typename _Iterator::reference>>
{
typedef typename _Iterator::iterator_category iterator_category;
typedef typename _Iterator::value_type value_type;
typedef typename _Iterator::difference_type difference_type;
typedef typename _Iterator::pointer pointer;
typedef typename _Iterator::reference reference;
};위의 템플릿에서 _Iterator는 반복자의 데이터 타입을 나타내며, 어떤 반복자에서든 코드를 작성할 때 반복자의 카테고리, 요소의 데이터 타입 등을 사용할 수 있습니다. 예를 들어, 아래 표현식을 사용하여 반복자 타입 _Iterator의 값에 대한 데이터 타입을 알아낼 수 있습니다.
typename std::iterator_traits<_Iterator>::value_type위와 같은 구조에는 두 가지 장점이 있습니다.
- 반복자가 모든 데이터 타입 정의를 제공한다는 것을 보장
- 특수한 반복자에 대한 (부분) 특수화를 제공
위에서 두 번째 장점은 iterator로 사용될 수 있는 일반적인 포인터를 위한 것 입니다.
/// Partial specialization for pointer types.
template<typename _Tp>
struct iterator_traits<_Tp*>
{
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
/// Partial specialization for const pointer types.
template<typename _Tp>
struct iterator_traits<const _Tp*>
{
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef const _Tp* pointer;
typedef const _Tp& reference;
};
Writing Generic Functions for Iterators
Iterator tratis를 사용하면 반복자 카테고리에 따라 다른 코드를 구현하거나 타입 정의를 추론하는 제너릭 함수를 작성할 수 있습니다.
Using Iterator Types
Iterator tratis를 사용하는 간단한 예제로 요소에 대한 임시 변수가 필요한 경우를 생각해봅시다. 이때, 임시 값은 다음과 같이 간단히 선언됩니다.
typename std::iterator_traits<T>::value_type tmp;여기서 T는 반복자의 타입입니다.
또 다른 예시로 아래와 같은 요소를 shift하는 알고리즘이 있습니다.
template<typename ForwardIterator>
void shift_left(ForwardIterator beg, ForwardIterator end)
{
// temporary variable for first element
typedef typename std::iterator_traits<ForwardIterator>::value_type value_type;
if (beg != end) {
// save value of first element
value_type tmp(*beg);
// shift following values
...
}
}
Using Iterator Categories
다양한 반복자 카테고리에 따라 서로 다른 구현을 적용하려면 아래의 두 가지 단계를 따라야 합니다.
1. 함수 템플릿이 추가 인자로 반복자 카테고리를 받는 함수를 호출하도록 한다.
template<typename Iterator>
inline void foo(Iterator beg, Iterator end)
{
foo(beg, end, std::iterator_tratis<Iterator>::iterator_category());
}
2. 어떤 반복자 카테고리를 위한 다른 함수를 구현하여 특정 반복자 카테고리에 대해서만 제공하도록 한다.
// foo() for bidirectional iterators
template<typename BiIterator>
void foo(BiIterator beg, BiIterator end, std::bidirectional_iterator_tag)
{
...
}
// foo() for random-access iterators
template<typename RaIterator>
void foo(RaIterator beg, RaIterator end, std::random_access_iterator_tag)
{
...
}
Example : distance() 구현
바로 위에서 언급한 각 카테고리를 위한 템플릿 함수 구현의 예시로 반복자에 대한 보조 함수인 distance()를 들 수 있습니다. 이 함수는 두 반복자의 위치와 이들 요소 사이의 거리를 반환합니다. random-access iterators의 경우 단순히 - 연산자를 사용하여 구현할 수 있지만, 다른 모든 반복자에서는 범위의 끝에 도달하기 까지 증가한 숫자를 반환합니다.
// general distance()
template<typename Iterator>
typename std::iterator_traits<Iterator>::difference_type
distance(Iterator pos1, Iterator pos2)
{
return distance(pos1, pos2, std::iterator_traits<Iterator>::iterator_category());
}
// distance() for random-access iterators
template<typename RaIterator>
typename std::iterator_traits<RaIterator>::difference_type
distance(RaIterator pos1, RaIterator pos2,
std::random_access_iterator_tag)
{
return pos2 - pos1;
}
// distance() for input, forward, and bidirectional iterators
template<typename InIterator>
typename std::iterator_traits<InIterator>::difference_type
distance(InIterator pos1, InIterator pos2,
std::input_iterator_tag)
{
typename std::iterator_traits<InIterator>::difference_type d;
for (d=0; pos1 != pos2; ++pos1, ++d) {}
return d;
}여기서 반복자의 difference type이 반환형으로 사용되었습니다. 그리고 마지막 구현은 input iterator에 대한 태그를 사용했기 때문에 이 구현은 forward와 bidirectional iterators에서도 사용될 수 있습니다.
Writing User-Defined Iterators
Iterator Traits를 활용하여 사용자 정의 반복자를 구현해보도록 하겠습니다. 사용자 정의 반복자는 위에서 언급한 iterator tratis를 제공해야 하는데, 아래의 두 가지 방식 중 하나를 선택할 수 있습니다.
- 일반 iterator_traits 구조체를 위한 다섯 가지의 필수 데이터 타입을 제공
- iterator_tratis 구조체의 (부분) 특수화를 제공
첫 번째 방식을 위해서 C++ 표준 라이브러리에서는 데이터 타입을 정의하는 특별한 베이스 클래스, iterator<>를 제공합니다. 이를 사용하면 단순히 타입만 전달해주면 됩니다.
class MyIterator
: public std::iterator<std::bidirectional_iterator_tag,
type, std::ptrdiff_t, type*, type&> {
...
};위의 클래스 정의에서 첫 번째 템플릿 파라미터는 반복자의 카테고리를 정의하고, 두 번째는 type이라는 요소의 데이터 타입을 정의하고, 세 번째는 difference 타입, 네 번째는 pointer 타입, 다섯 번째는 reference 타입을 정의합니다. 마지막 3개의 인자는 optional이며, 기본값은 ptrdiff_t, type*, type& 입니다.
아래 예제 코드를 통해서 사용자 정의 반복자를 어떻게 정의하는지 살펴보도록 하겠습니다. 이 코드에서는 연관/비정렬 컨테이너를 위한 insert iterator를 정의합니다. C++ 표준 라이브러리에서 제공하는 insert iterator와는 달리 삽입하는 지점을 인자로 받지 않습니다.
#include <iterator>
template<typename Container>
class asso_insert_iterator
: public std::iterator<std::output_iterator_tag, typename Container::value_type>
{
protected:
Container& container; // container in which elements are inserted
public:
// constructor
explicit asso_insert_iterator(Container& c) : container(c) {}
// assignment operator - inserts a value into the container
asso_insert_iterator<Container>&
operator=(const typename Container::value_type& value) {
container.insert(value);
return *this;
}
// dereferencing is a no-op that returns the iterator itself
asso_insert_iterator<Container>& operator*() {
return *this;
}
// increment operation is a no-op that returns the iterator itself
asso_insert_iterator<Container>& operator++() {
return *this;
}
asso_insert_iterator<Container>& operator++(int) {
return *this;
}
};
// convenience function to create the inserter
template<typename Container>
inline asso_insert_iterator<Container> asso_inserter(Container& c)
{
return asso_insert_iterator<Container>(c);
}위 코드에서 asso_insert_iterator 클래스는 iterator 클래스로부터 파생되었고, 베이스 클래스에 대응되는 데이터 타입이 정의되어 있습니다. iterator 클래스에 전달된 첫 번째 템플릿 인자는 반복자 카테고리를 명시하는 output_iterator_tag 입니다. 두 번째 인자는 반복자가 참조하는 값의 데이터 타입으로 여기서는 컨테이너의 value_type 입니다. output iterator는 무언가를 write하는 데에만 사용될 수 있으므로 타입 정의가 필요하진 않지만, 위 코드처럼 값의 데이터 타입을 전달하면 어떠한 반복자 카테고리에서도 잘 동작합니다.
반복자를 생성할 때, 반복자는 container 멤버 변수에 자신의 컨테이너를 저장합니다. 할당되는 어떤 값이든지 이 컨테이너의 insert() 함수를 사용하여 값을 삽입합니다. *와 ++ 연산자는 아무런 동작도 수행하지 않고 단지 반복자 자체를 반환합니다.
마지막으로 inserter를 생성하고 초기화할 때 사용할 헬퍼 함수로 asso_inserter를 정의했습니다. 아래 코드는 이렇게 정의한 inserter를 사용해 unordered set에 요소를 삽입하는 예제를 보여줍니다.
int main()
{
std::unordered_set<int> coll;
// create inserter for coll (inconvenient way)
asso_insert_iterator<decltype(coll)> iter(coll);
// insert elements with the usual iterator interface
*iter = 1;
iter++;
*iter = 2;
iter++;
*iter = 3;
for (auto pos = coll.begin(); pos != coll.end(); ++pos) {
std::cout << *pos << " ";
}
std::cout << std::endl;
// create inserter for coll and insert elements (convenient way)
asso_inserter(coll) = 44;
asso_inserter(coll) = 55;
for (auto pos = coll.begin(); pos != coll.end(); ++pos) {
std::cout << *pos << " ";
}
std::cout << std::endl;
// use inserter with an algorithm
std::vector<int> vals = { 33, 67, -4, 13, 5, 2 };
std::copy(vals.begin(), vals.end(), asso_inserter(coll));
for (auto pos = coll.begin(); pos != coll.end(); ++pos) {
std::cout << *pos << " ";
}
std::cout << std::endl;
}
정의한 inserter는 연관 컨테이너에서도 사용될 수 있으며, unordered_set을 set으로 변경해도 프로그램은 잘 동작합니다.
'프로그래밍 > C & C++' 카테고리의 다른 글
| [C++] 스트림(stream) 클래스 (1) (0) | 2022.12.13 |
|---|---|
| [C++] 함수 객체 활용 (0) | 2022.12.12 |
| [C++] Clocks and Timers (0) | 2022.12.08 |
| [C++] Type Traits와 Type Utilities (0) | 2022.12.07 |
| [C++] Numeric Limits (0) | 2022.12.06 |
댓글