Iterator(반복자)

컨테이너의 요소에 접근하고 순회하는 객체

반복자 종류

1. Input Iterator(입력 반복자)

#include <string>
#include <iostream>
#include <istream>
#include <sstream>

int main()
{
	// ============================================
	// Input Iterator (입력 반복자)
	// ============================================
	// - 읽기 전용(read-only) 반복자
	// - 순차적으로 앞으로만 이동 가능
	// - 요소를 읽을 수만 있고, 쓸 수는 없음
	// - 각 위치에 한 번만 읽기 가능 (single-pass)
	// ============================================

	std::string line;
	std::getline(std::cin, line);

	std::istringstream str(line);
	std::istream_iterator<std::string> input(str);
	std::istream_iterator<std::string> end2;

	while (input != end2)
	{
		std::cout << *input++ << std::endl;
	}
	std::istream_iterator<std::string> input2 = input;

	std::cout << "\n=== 지원 연산 ===" << std::endl;
	std::cout << "value = *input     // 역참조 (읽기)" << std::endl;
	std::cout << "++input, input++   // 증가 연산" << std::endl;
	std::cout << "input2 = input1    // 복사" << std::endl;
	std::cout << "input1 == input2   // 비교 (==, !=)" << std::endl;

	std::cout << "\n=== 제약 사항 ===" << std::endl;
	std::cout << "*input = value     // ❌ 쓰기 불가" << std::endl;
	std::cout << "--input            // ❌ 감소 불가" << std::endl;
	std::cout << "input + n          // ❌ 임의 접근 불가" << std::endl;
	std::cout << "input[n]           // ❌ 인덱스 접근 불가" << std::endl;

	return 0;
}

2. Output Iterator(출력 반복자)

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <list>

int main()
{
	// ============================================
	// Output Iterator (출력 반복자)
	// ============================================
	// - 쓰기 전용(write-only) 반복자
	// - 순차적으로 앞으로만 이동 가능
	// - 요소를 쓸 수만 있고, 읽을 수는 없음
	// - 각 위치에 한 번만 쓰기 가능 (single-pass)
	// ============================================

	// 1. ostream_iterator
	std::ostream_iterator<int> output(std::cout, ", ");

	*output++ = 10;
	*output++ = 20;
	*output++ = 30;
	std::cout << std::endl;

	// 2. back_inserter - 끝에 요소 추가
	std::vector<int> v1 = { 2,3,5,7 };
	std::vector<int> v2;
	std::vector<int> v3;

	// 수동으로 back_inserter 사용
	std::back_insert_iterator<std::vector<int>> backit1 = std::back_inserter(v2);
	for (auto val : v1)
	{
		*backit1++ = val;  // v2 : 2,3,5,7
	}

	// 알고리즘과 함께 사용
	std::copy(v2.begin(), v2.end(), std::back_inserter(v3)); // v3 : 2, 3, 5, 7

	// 3. front_inserter - 앞에 요소 추가
	std::list<int> v4 = { 111,222,333,444 };
	std::list<int> v5;
	std::list <int> v6;

	// 수동으로 front_inserter 사용
	std::front_insert_iterator < std::list <int >> frontit1 = std::front_inserter(v5);
	for (auto val : v4)
	{					  
		*frontit1++ = val; // 역순 v5 : 444, 333, 222, 111
	}

	// 알고리즘과 함께 사용                                      
	std::copy(v5.begin(), v5.end(), std::front_inserter(v6)); // 다시 역순 v6 111, 222, 333, 444

	//// 4. inserter - 특정 위치에 추가
	std::vector<int> v7 = { 111,222,333,444 };
	std::vector<int>::iterator it = v7.begin();

	// it + 2 위치(333 앞)에 삽입
	std::insert_iterator<std::vector<int>> inserterit1 = std::inserter(v7, it+2);

	// 첫 삽입: 666이 it+2 위치에 들어감
	// 두번째 삽입: 555가 666 뒤(새로운 it+3)에 들어감

	*inserterit1++ = 666; // v7 : 111, 222, 666, 333, 444
	*inserterit1++ = 555; // v7 : 111, 222, 666, 555, 333, 444

	std::cout << "\n=== 지원 연산 ===" << std::endl;
	std::cout << "*output = value    // 역참조 (쓰기)" << std::endl;
	std::cout << "++output, output++ // 증가 연산" << std::endl;
	std::cout << "output2 = output1  // 복사" << std::endl;

	std::cout << "\n=== 제약 사항 ===" << std::endl;
	std::cout << "value = *output    // ❌ 읽기 불가" << std::endl;
	std::cout << "output1 == output2 // ❌ 비교 불가" << std::endl;
	std::cout << "--output           // ❌ 감소 불가" << std::endl;
	std::cout << "output + n         // ❌ 임의 접근 불가" << std::endl;
	std::cout << "output[n]          // ❌ 인덱스 접근 불가" << std::endl;

	return 0;
}

3. Forward Iterator(전방 반복자)

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <forward_list>

int main()
{
	// ============================================
	//	 Forward Iterator (전방 반복자)
	// ============================================
	// - 읽기와 쓰기 모두 가능(Input Iterator + Output Iterator)
	// - 단방향(forward-only) 이동
	// - 다중 패스 (Multi-pass) - 같은 위치를 여러 번 읽거나 쓸 수 있음, 같은 범위를 여러 번 순회 가능
	// - 반복자 비교 가능(동등 비교 (==, !=) 지원)
	// ============================================

	// 1. forward_list
	std::cout << "=== 1. forward_list 기본 사용 ===" << std::endl;
	// 읽기
	std::forward_list<int> fl1 = { 1,2,5,76,8 };
	std::cout << "초기값: ";
	for (std::forward_list<int>::iterator it = fl1.begin(); it != fl1.end(); ++it)
	{
		std::cout << *it << " "; // fl1 : 1, 2, 5, 76, 8 
	}
	std::cout << std::endl;

	// 쓰기
	for (std::forward_list<int>::iterator it = fl1.begin(); it != fl1.end(); ++it)
	{
		*it *= 2; // f1 : 1, 2, 5, 76, 8 -> 2, 4, 10, 152, 16
	}

	// 다시 읽기 - 다중 패스 (Multi-pass)
	std::cout << "2배 후: ";
	for (std::forward_list<int>::iterator it = fl1.begin(); it != fl1.end(); ++it)
	{
		std::cout << *it << " "; // fl1 : 1, 2, 5, 76, 8 
	}
	std::cout << std::endl;

	std::cout << "\n=== 2. 반복자 비교 ===" << std::endl;
	std::forward_list<int>::iterator it2 = fl1.begin();
	it2++; it2++; // it2 -> 10

	std::cout << "it2가 가리키는 값: " << *it2 << std::endl;
	std::cout << "순회하면서 it2와 같은 위치 찾기: ";

	for (std::forward_list<int>::iterator it = fl1.begin(); it != fl1.end(); ++it)
	{
		if (it2 == it)
		{
			std::cout << *it << " (찾음!)" << std::endl;
		}
	}

	std::cout << "\n=== 3. 독립적인 반복자(다중 패스) ===" << std::endl;
	std::forward_list<int>::iterator it3 = fl1.begin();
	std::forward_list<int>::iterator it4 = fl1.begin();
	it3++; it3++;
	std::cout << "it3: " << *it3 << std::endl; // 10
	std::cout << "it4: " << *it4 << std::endl; // 2 (독립적!)

	// forward_list 요소 추가,삭제
	std::cout << "\n=== 4. forward_list 요소 추가 (insert_after) ===" << std::endl;
	// it2는 여전히 10을 가리킴
	std::cout << "it2 위치(10) 다음에 15 삽입" << std::endl;
	fl1.insert_after(it2,15); // f1 : 2, 4, 10, 15, 152, 16
	std::cout << "it2 위치(10) 다음에 25 삽입 (15 앞에 들어감)" << std::endl;
	fl1.insert_after(it2,25); // f1 : 2, 4, 10, 25, 15, 152, 16

	for (std::forward_list<int>::iterator it = fl1.begin(); it != fl1.end(); ++it)
	{
		std::cout << *it << std::endl; // f1 : 2, 4, 10, 152, 16
	}

	std::cout << "\n=== 지원 연산 ===" << std::endl;
	std::cout << "*it = value    // 역참조 (쓰기)" << std::endl;
	std::cout << "value = *it    // 역참조 (읽기)" << std::endl;
	std::cout << "++it, it++     // 증가 연산" << std::endl;
	std::cout << "it1 = it2      // 복사" << std::endl;
	std::cout << "it2 == it1     // 비교(==,!=)" << std::endl;
	std::cout << "iterator it;   // 기본 생성자" << std::endl;

	std::cout << "\n=== 제약 사항 ===" << std::endl;
	std::cout << "--it           // ❌ 감소 불가" << std::endl;
	std::cout << "it + n,it - n  // ❌ 임의 접근 불가" << std::endl;
	std::cout << "it[n]          // ❌ 인덱스 접근 불가" << std::endl;
	std::cout << "it1 < it2      // ❌ 대소 비교 불가" << std::endl;

	return 0;
}

4. Bidirectional Iterator(양방향 반복자)

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <list>
#include <set>
#include <map>
#include <iterator>

int main()
{
	// ============================================
	//	 Bidirectional Iterator (양방향 반복자)
	// ============================================
	// - 읽기, 쓰기 (Input Iterator + Output Iterator) + 다중 패스 (Multi-pass)
	// - 양방향 이동 가능 (역방향 이동 가능)
	// - 반복자 비교 가능(동등 비교 (==, !=) 지원)
	// ============================================

	// 1. std::list의 반복자
	std::list<int> list1 = { 1, 5, 7, 8, 23, 121 };

	std::cout << "=== std::list - 정방향 순회 ===" << std::endl;
	std::cout << "list1 : ";
	for (std::list<int>::iterator it1 = list1.begin(); it1 != list1.end(); ++it1)
	{
		std::cout << *it1 << " ";
	}
	std::cout << std::endl;

	std::cout << "\n=== std::list - 역방향 순회 ===" << std::endl;
	std::cout << "list1 : ";
	std::list<int>::iterator it2 = list1.end();
	--it2;
	for (; it2 != list1.begin(); --it2)
	{
		std::cout << *it2 << " ";
	}
	std::cout << *it2 << std::endl;

	// 양방향 이동 예제
	std::cout << "\n=== 양방향 이동 ===" << std::endl;
	std::list<int>::iterator it_move = list1.begin();
	++it_move; ++it_move;  // 7을 가리킴
	std::cout << "현재: " << *it_move << std::endl;

	++it_move;  // 앞으로
	std::cout << "앞으로 이동: " << *it_move << std::endl;

	--it_move; --it_move;  // 뒤로
	std::cout << "뒤로 이동: " << *it_move << std::endl;

	// 2. std::set의 반복자
	std::set<int> s1 = { 2, 6, 8, 10 };

	std::cout << "\n=== std::set - 정방향 순회 ===" << std::endl;
	std::cout << "s1 : ";
	for (std::set<int>::iterator it1 = s1.begin(); it1 != s1.end(); ++it1)
	{
		std::cout << *it1 << " ";
	}
	std::cout << std::endl;

	std::cout << "\n=== std::set - 역방향 순회 ===" << std::endl;
	std::cout << "s1 : ";
	std::set<int>::iterator it3 = s1.end();
	--it3;
	for (; it3 != s1.begin(); --it3)
	{
		std::cout << *it3 << " ";
	}
	std::cout << *it3 << std::endl;

	// 3. std::map도 마찬가지
	std::map<int, std::string> m1 = { {1, "one"}, {2, "two"}, {3, "three"} };

	std::cout << "\n=== std::map - 역방향 순회 ===" << std::endl;
	std::map<int, std::string>::iterator it_map = m1.end();
	--it_map;
	for (; it_map != m1.begin(); --it_map)
	{
		std::cout << it_map->first << ":" << it_map->second << " ";
	}
	std::cout << it_map->first << ":" << it_map->second << std::endl;

	// 4. 역방향 반복자 (reverse_iterator)
	std::list<int> list2 = { 6, 3, 412, 4 };

	std::cout << "\n=== std::list - 역방향 반복자 순회 ===" << std::endl;
	std::cout << "list2 : ";
	for (std::list<int>::reverse_iterator rit = list2.rbegin(); rit != list2.rend(); ++rit)
	{
		std::cout << *rit << " ";
	}
	std::cout << std::endl;

	// 5. std::advance 사용
	std::cout << "\n=== std::advance 사용 ===" << std::endl;
	std::list<int>::iterator it_adv = list1.begin();
	std::advance(it_adv, 3);
	std::cout << "3칸 앞으로: " << *it_adv << std::endl;

	std::advance(it_adv, -2);
	std::cout << "2칸 뒤로: " << *it_adv << std::endl;

	// 6. std::distance 사용 
	std::cout << "\n=== std::distance 사용 ===" << std::endl;
	std::list<int>::iterator begin = list1.begin();
	std::list<int>::iterator end = list1.end();
	std::cout << "list1 시작과 끝의 거리 : " << std::distance(begin, end) << std::endl;

	// std::advance + std::distance - 중간 지점 거리 계산
	std::list<int>::iterator mid = list1.begin();
	std::advance(mid, 3);
	std::cout << "시작부터 3번째 요소까지 거리 : " << std::distance(begin, mid) << std::endl;
	std::cout << "3번째 요소부터 끝까지 거리 : " << std::distance(mid, end) << std::endl;

	std::cout << "\n=== 지원 연산 ===" << std::endl;
	std::cout << "*it = value        // 역참조 (쓰기)" << std::endl;
	std::cout << "value = *it        // 역참조 (읽기)" << std::endl;
	std::cout << "++it, it++         // 증가 연산" << std::endl;
	std::cout << "--it, it--         // 감소 연산 (추가!)" << std::endl;
	std::cout << "it2 == it1         // 비교(==,!=)" << std::endl;
	std::cout << "iterator it1;      // 기본 생성자" << std::endl;
	std::cout << "iterator it2 = it1 // 복사" << std::endl;

	std::cout << "\n=== 제약 사항 ===" << std::endl;
	std::cout << "it + n, it - n // ❌ 임의 접근 불가" << std::endl;
	std::cout << "it[n]          // ❌ 인덱스 접근 불가" << std::endl;
	std::cout << "it1 < it2      // ❌ 대소 비교 불가" << std::endl;

	return 0;
}

5. Random Access Iterator(임의 접근 반복자)

#include <string>
#include <iostream>
#include <vector>
#include <deque>
#include <array>

int main()
{
	// ============================================
	//	 Random Access Iterator (임의 접근 반복자)
	// ============================================
	// - Bidirectional Iterator의 모든 기능
	// - 임의 접근 가능 - 포인터 처럼 동작, 산술 연산, 인덱스 접근, 대소 비교지원
	// - O(1) 시간 복잡도 - 임의의 위치 접근이 상수 시간
	// ============================================

	// 1. std::vector의 반복자
	std::cout << "=== std::vector ===" << std::endl;
	std::vector<int> v1 = { 2, 6, 8, 10, 223 };

	std::vector<int>::iterator it = v1.begin();

	// 임의 접근
	std::cout << "it[0]: " << it[0] << std::endl;  // 2
	std::cout << "it[2]: " << it[2] << std::endl;  // 8
	std::cout << "it[4]: " << it[4] << std::endl;  // 223

	// 산술 연산
	std::vector<int>::iterator it2 = v1.begin() + 3;
	std::cout << "it2 + 3 : " << *it2 << std::endl;
	it2 -= 2;
	std::cout << "it2 -= 2 : " << *it2 << std::endl;

	// 거리 계산
	std::cout << "it2 - it : " << it2 - it << std::endl;

	// 2. std::deque의 반복자
	std::cout << "\n=== std::deque ===" << std::endl;
	std::deque<int> d1 = { 55, 77, 324, 2, 3321 };

	std::deque<int>::iterator it3 = d1.begin();

	// 임의 접근
	std::cout << "it3[0]: " << it3[0] << std::endl;  // 55
	std::cout << "it3[2]: " << it3[2] << std::endl;  // 324
	std::cout << "it3[4]: " << it3[4] << std::endl;  // 3321

	// 산술 연산
	std::deque<int>::iterator it4 = d1.begin() + 3;
	std::cout << "it4 + 3 : " << *it4 << std::endl;
	it4 -= 2;
	std::cout << "it4 -= 2 : " << *it4 << std::endl;

	// 거리 계산
	std::cout << "it4 - it3 : " << it4 - it3 << std::endl;

	// 3. std::array의 반복자 마찬가지
	std::cout << "\n=== std::array ===" << std::endl;
	std::array<int, 5> arr1 = { 100, 200, 300, 400, 500 };

	std::array<int, 5>::iterator it5 = arr1.begin();
	std::cout << "it5[0]: " << it5[0] << std::endl;
	std::cout << "it5[3]: " << it5[3] << std::endl;

	// 4. 대소 비교
	std::cout << "\n=== 대소 비교 ===" << std::endl;
	std::vector<int>::iterator it_a = v1.begin();
	std::vector<int>::iterator it_b = v1.begin() + 3;

	if (it_a < it_b) {
		std::cout << "it_a < it_b" << std::endl;
	}
	if (it_b > it_a) {
		std::cout << "it_b > it_a" << std::endl;
	}

	// 5. 일반 포인터 (Random Access Iterator)
	std::cout << "\n=== 일반 포인터 (Random Access Iterator) ===" << std::endl;
	int arr[] = { 10, 20, 30, 40, 50 };
	int* ptr = arr;

	std::cout << "ptr[0]: " << ptr[0] << std::endl;
	std::cout << "ptr[3]: " << ptr[3] << std::endl;
	std::cout << "*(ptr + 2): " << *(ptr + 2) << std::endl;

	std::cout << "\n=== 지원 연산 ===" << std::endl;
	std::cout << "*it = value           // 역참조 (쓰기)" << std::endl;
	std::cout << "value = *it           // 역참조 (읽기)" << std::endl;
	std::cout << "++it, it++            // 증가 연산" << std::endl;
	std::cout << "--it, it--            // 감소 연산" << std::endl;
	std::cout << "it2 == it1            // 비교(==,!=)" << std::endl;
	std::cout << "iterator it1;         // 기본 생성자" << std::endl;
	std::cout << "iterator it2 = it1    // 복사" << std::endl;
	std::cout << "it + n, it - n        // 임의 접근(산술 연산 : +, -, -=, +=)" << std::endl;
	std::cout << "it[n]                 // 인덱스 접근" << std::endl;
	std::cout << "it1 < it2             // 대소 비교(<,<=,>,>=)" << std::endl;
	std::cout << "it1 - it2             // 두 반복자 사이 거리" << std::endl;

	return 0;
}