이번 시간에는 iterator와 range에 대해 살펴보겠습니다.

Iterator Basic

1. 핵심 정리

  • 반복자는 GoF 디자인 패턴에서 정의 : 복합 개체의 내부 구조에 상관 없이 순차적으로 요소에 접근하기 위한 방법을 제공 하는 것

  • STL에서의 정의 : 반복자 처럼 동작하는 모든 것은 반복자이다.(++ 연산 이동, * 연산자로 값에 접근 가능한 것)

  • STL에서는 디렉토리 내의 파일을 순회 하는 디렉토리 반복자 또한 제공함(C++17 이후)

#include <iostream>
#include <list>
#include <experimental/filesystem>
using namespace std;
using namespace std::experimental::filesystem;

int main()
{
	directory_iterator p("C:\\windows");

	cout << *p << endl;
	++p;
	cout << *p << endl;
}

2. 반복자를 다룰 때 std::begin, std::size를 사용 할 경우 배열 타입에서도 적용 가능한 범용적 코드 작성이 가능함

  • 주의 : end()로 얻는 반복자는 마지막 요소의 다음을 의미하므로 값을 꺼내 올 경우 크래시 발생
#include <iostream>
#include <list>   
#include <vector>
using namespace std;

int main()
{
	list<int> s = { 1,2,3,4,5 };
	//vector<int> s = { 1,2,3,4,5 };

	//int s[5] = { 1,2,3,4,5 };
	
	//list<int>::iterator p = s.begin();

	//auto p1 = s.begin(); //

	auto p1 = begin(s);
	int n = size(s); //  s.size();
	cout << n << endl;

	auto p2 = end(s);
	*p2 = 10; // 크래시 error;
}

3. 반복자 무효화 : 무효화 이후 접근시 크래시 발생!

  • 컨테이너의 내부 버퍼가 재할당 될 때
  • 반복자가 가르키던 요소가 제거 될 때
  • 컨테이너의 종류에 따라 무효화 조건이 다름
#include <iostream>
#include <list>   
#include <vector>
using namespace std;

int main()
{
	//vector<int> v = { 1,2,3,4,5 };
	list<int> v = { 1,2,3,4,5 };

	auto p = begin(v);

	v.resize(100); // vector는 무효화 발생, list는 발생하지 않음
				   //

	cout << *p << endl;
}

4. 반복자의 구간(Range)

  • first, last : 시작과 마지막 다음 요소를 가르키는 반복자의 쌍
  • 유효한 구간 : first부터 시작해서 ++ 연산으로 last에 도달 할 수 있는 구간
  • 빈 구간 : first == last인 경우, 빈 구간도 유효한 구간임
#include <iostream>
#include <list>
using namespace std;

int main()
{
	list<int> s1 = { 1,2,3 };
	list<int> s2 = { 4,5,6 };

	auto p1 = begin(s1);
	auto p2 = end(s1);

	// [p1, p2)

	while (p1 != p2)
	{
		++p1;
	}

	list<int> s3;
	if (s3.empty()) {}

	if (begin(s3) == end(s3)) {} // empty == true
}
  • STL의 copy 알고리즘
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

int main()
{
	int x[5] = { 1, 2, 3, 4, 5 };
	
	list<int> s2 = { 0,0,0,0,0 };

	copy(x, x + 5, begin(s2));

	for (auto& n : s2)
		cout << n << ", ";
}

Iterator Category

1. Iterator Category

  • vector는 sort 알고리즘 사용가능한데, list는 사용이 불가능한 이유?
    • 컨테이너의 종류에 따라 반복자에 적용할 수 있는 연산의 종류가 다름(– 연산이 불가능한 경우 등등)
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;

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

	list<int> v = { 1,3,5,7,9,2,4,6,8,10 };

	sort( begin(v), end(v) );

	for (auto& n : v)
		cout << n << ",";
}
  • 입력 vs 출력
    • 입력 : 반복자를 통해 요소를 읽어오는 것( = *i)
    • 출력 : 반복자를 통해 요소에 값을 쓰는 것( *i = )

2. multipass guarantee 개념

  • i1 == i2 라면 -> *i1 == *i2 혹은 ++i1 == ++i2 만족

  • 2개 이상의 반복자가 컨테이너의 요소에 동일하게 접근함을 보장

  • 컨테이너마다 지원 여부가 다름(list는 지원, stream / insert iterator는 지원 하지 않음)

#include <iostream>
#include <list>
using namespace std;

int main()
{
	list<int> s1 = { 1,2,3 };

	auto i1 = begin(s1);
	auto i2 = i1;

	if (i1 == i2)
	{
		cout << (*i1 == *i2) << endl;
		cout << (++i1 == ++i2) << endl;
	}
}

3. 반복자 카테고리 개념을 알아야 하는 이유

#include <iostream>
#include <vector>
#include <list>
#include <forward_list>
#include <algorithm>
using namespace std;

int main()
{
	vector<int> v = { 1,2,3,4,5,6,7,8,9,10 };

	// find의 1, 2 인자의 최소 요구 조건? : 입력 반복자
	auto p = find(begin(v), end(v), 5);

	reverse(begin(v), end(v));// reverse의 요구조건 : 양방향 반복자

	sort(begin(v), end(v)); // stl의 sort는 quick sort
							// sort의 요구조건 : 임의 접근 반복자.

	forward_list<int> s = { 1,2,3 };
	reverse(begin(s), end(s)); // error


	list<int> s2 = { 1,2,3 };
	sort(begin(s2), end(s2)); // error

	s2.sort(); // ok.

	vector<int> v = { 1,2,3 };

	v.sort();  // 멤버 함수 sort()가 있을까 ?
				// 없다.  일반 함수(알고리즘) 
				// sort()를 사용하면 된다.

	for (auto& n : v)
		cout << n << ", ";
}

4. tag dispatching

  • advance 구현 해보기( tag dispatching 활용 : 반복자의 카테고리에 따라 다르게 동작하도록(최적화) )
    • 모든 컨테이너는 멤버 변수에 iterator_category을 제공함
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
using namespace std;

template<typename T>
void eadvance_imp(T& p, int n, 
				  random_access_iterator_tag)
{
	cout << "random 버전" << endl;
	p = p + n;
}

template<typename T>
void eadvance_imp(T& p, int n,
				  input_iterator_tag)
{
	cout << "input 버전" << endl;
	while (n--)	++p;
}

template<typename T>
void eadvance(T& p, int n)
{
	// 반복자의 종류에 따라서 다른 함수를 선택
	eadvance_imp(p, n,
			typename T::iterator_category() );
}


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

	auto p = begin(s);

	eadvance(p, 5);

	cout << *p << endl;
}
  • 최신 문법을 활용 하면 더욱 간결하게 표현 가능함
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
using namespace std;

// 1. 함수 인자를 사용한 오버로딩.
/*
template<typename T> void eadvance_imp(T& p, int n, random_access_iterator_tag)
{
	p = p + n;
}
template<typename T> void eadvance_imp(T& p, int n, input_iterator_tag)
{
	while (n--)	++p;
}
template<typename T> void eadvance(T& p, int n)
{
	eadvance_imp(p, n, typename T::iterator_category());
}
*/

// 2. C++17 if constexpr 사용.
#include <type_traits>

/*
template<typename T> void eadvance(T& p, int n)
{
	if constexpr (is_same< typename T::iterator_category, random_access_iterator_tag>::value)
	{
		p = p + n;
	}
	else
		while (n--) ++p;
}
*/
// 3. enable_if 를 사용..   SFINAE 개념 사용.

template<typename T> 
typename enable_if<is_same<typename T::iterator_category,random_access_iterator_tag>::value>::type
eadvance(T& p, int n)
{
	p = p + n;
}

template<typename T> 
typename enable_if<! is_same<typename T::iterator_category, random_access_iterator_tag>::value>::type
eadvance(T& p, int n)
{
	while (n--) ++p;
}

int main()
{
	list<int> s = { 1,2,3,4,5,6,7,8,9,10 };

	auto p = begin(s);

	eadvance(p, 5);

	cout << *p << endl;
}

Iterator traits

1. 반복자가 가르키는 타입을 찾아서 리턴하는 방법

#include <iostream>
#include <list>
#include <vector>
using namespace std;
#include <iterator>

template<typename T>
typename iterator_traits<T>::value_type
sum(T first, T last)
{
	typename iterator_traits<T>::value_type s = 0;

	while (first != last)
	{
		s = s + *first;
		++first;
	}
	return s;
}

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

	int s[10] = { 1,2,3,4,5,6,7,8,9,10 };

	int n = sum(begin(s), end(s));

	cout << n << endl;
}
  • C++11 이후 문법(타입 추론)을 활용한 방법(auto와 decltype)
#include <iostream>
#include <list>
#include <vector>
#include <iterator>
using namespace std;


template<typename T>
typename iterator_traits<T>::value_type
sum(T first, T last)
{
	typename 
	remove_reference<decltype(*first)>::type s = 0;

	while (first != last)
	{
		s = s + *first;
		++first;
	}
	return s;
}

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

	int s[10] = { 1,2,3,4,5,6,7,8,9,10 };

	int n = sum(begin(s), end(s));

	cout << n << endl;
}

Insert iterator

1. back insert iterator : 반복문 없이 한방에 여러 데이터 삽입 가능

#include <iostream>
#include <list>
#include <iterator>
using namespace std;

int main(int argc, char** argv)
{
	list<int> s = { 1, 2, 3, 4, 5};

	s.push_back(10);

	back_insert_iterator< list<int> > p( s );
	*p = 20; // s.push_back(20);

	int x[5] = { 10,20,30,40,50 };
	copy(x, x + 5, p);

	for ( auto& n : s )
		cout << n << endl; 
}

int main(int argc, char** argv)
{
	int x[5] = { 10,20,30,40,50 };
	list<int> s = { 1, 2, 3, 4, 5 };

	copy(x, x + 5, back_inserter( s) );

	for (auto& n : s)
		cout << n << endl; 
}

Iterator adapter : 기존 기능을 변경

1. reverse_iterator

int main()
{
	list<int> s = { 1,2,3,4,5,6,7,3,9,10};

	auto p1 = begin(s);
	auto p2 = end(s);

	reverse_iterator< list<int>::iterator> p3( p2 ); // p3와 p2는
													// 다른 객체
	reverse_iterator< list<int>::iterator> p4( p1 );

	auto ret1 = find(p1, p2, 3); //
	auto ret2 = find(p3, p4, 3); //

	//++p3; // --p2 처럼 동작

	cout << *p3 << endl; // 10
	++p3;
	cout << *p3 << endl; // 9
	++p3;
	cout << *p3 << endl; // 3
	--p2;
	cout << *p2 << endl; // 10
}

2. move iterator

  • 반복자 전달시 이동 생성자 호출 지원
#include <iostream>
#include <iterator>
#include <vector>
#include "People.h"
using namespace std;

int main()
{
    vector<People> v;
    v.push_back(People("A"));
    v.push_back(People("B"));
    v.push_back(People("C"));
    v.push_back(People("D"));

    cout << "------------------------" << endl;

    vector<People> v2(make_move_iterator(begin(v)),
                      make_move_iterator(end(v)));
}

Iterator helper

next, advance, distance

#include <iostream>
#include <iterator>
#include <forward_list>
using namespace std;

int main()
{
    int x[10] = { 1,2,3,4,5,6,7,8,9,10};

    forward_list<int> s = { 1,2,3,4,5,6,7,8,9,10};

    auto p1 = next(begin(s));

    advance(p1, 3); // p1 + 3;

    cout << *p1 << endl; // 5

    cout << distance( begin(s), p1) << endl; // p1 - begin(s)

    iter_swap(p1, begin(s));

    cout << *p1 << endl; // 1
}