[C++] iterator

iterator (반복자)

• 저장된 데이터를 순회(iterate)할 수 있는 기능을 제공하는 객체

• iterator는 포인터처럼 동작하지만 포인터가 아니라 클래스 객체이다.

사용자가 데이터 구조의 내부 구현을 알 필요 없이 데이터를 순회할 수 있도록 돕는 공통 인터페이스를 제공한다.

• 각 iterator는 자기가 구현되어있는 해당 자료구조에 맞게 동작한다.

구현되어있는 컨테이너만 다를 뿐, 이름은 동일하고 사용법도 같다.

• list의 경우 iterator는 노드의 주소를 저장하며, 연산자 오버로딩(`operator*`, `operator++`, `operator!=` 등)을 통해 데이터에 접근할 수 있도록 한다.

 

iterator가 필요한 이유

`std::vector`는 연속된 메모리 구조이므로 인덱스를 통해 데이터에 직접 접근할 수 있지만, `std::list`처럼 불연속적인 메모리 구조라면 특정 인덱스에 접근하는 함수를 제공하지 않는다.

list는 노드 기반의 데이터 구조로, 특정 데이터를 접근하려면 맨 처음 노드부터 순회하면서 다음 노드를 찾아가야 한다.

이런 과정을 프로그래머가 직접 구현하면 복잡해질 수 있기 때문에 C++ 표준 라이브러리는 편리하게 데이터를 순회할 수 있게 iterator를 제공해 준다.

중첩 클래스(Nested class) iterator

중첩 클래스(nested class)
• 클래스 내부에 다른 클래스를 정의하는 것

• iterator는 일반적으로 데이터 구조 클래스 내부에 정의된 중첩 클래스로 구현된다.

ex) `std::list<int>::iterator`는 `std::list<int>` 클래스 내부에 정의된 iterator 클래스이다.

iterator 역할

• 데이터 구조의 첫 번째 요소를 가리킨다.

std::list<int> listInt = {10, 20, 30};
std::list<int>::iterator iter = listInt.begin();  // 첫 번째 노드를 가리킨다.

`listInt.begin()`은 리스트의 첫 번째 노드의 iterator를 반환한다.

리스트는 특정 인덱스 접근이 비효율적인 자료구조라서 벡터처럼 특정 인덱스에 접근하는 것과 관련된 함수를 제공하지 않는다.
따라서 iterator로 하나씩 증가하면서 순차적으로 순회해야 한다.

• 데이터에 접근한다.

// iter가 가리키는 데이터를 반환한다.
int iData = *iter;  // 10
// *는 해당 자료구조 안에 있는 데이터를 가리키고 지칭하는 역할을 한다.
// 마치 포인터 역할을 하며, *를 operator로 역참조처럼 구현할 수 있다.

`*iter`는 `operator*()`가 iterator 클래스에 오버로딩되어 있기 때문에 iterator가 가리키는 데이터만 접근하여 반환한다.

`iter`가 마치 포인터처럼 동작한다.

`iter`가 리스트 안의 첫 번째 데이터를 받아오고 그것을 역참조하여 값을 확인한다.

※ 이때 `iter`는 포인터가 아니라 iterator 클래스의 객체이다.

• 다음 요소로 이동한다.

++iter;  // 다음 노드로 이동한다.
int nextData = *iter;  // 20

`++iter`는 iterator를 다음 노드로 이동시키는데, 이는 `operator++()`가 오버로딩되어 있기 때문이다.

• 끝까지 순회한다.

for (std::list<int>::iterator it = listInt.begin(); it != listInt.end(); ++it) {
    std::cout << *it << " ";  // 10 20 30
}

만약 end()가 마지막 요소의 다음이 아닌 마지막 요소라면?
• iterator가 마지막이 아니여야 반복되는데 마지막 데이터에서 같아지기 때문에 마지막 요소는 출력되지 않는 문제가 발생한다.

iterator 주요 특징

• 데이터 순회

list, vector, map 등 다양한 데이터 구조에서 사용할 수 있다.

• 포인터처럼 동작

`*`, `++` 등을 통해 데이터에 접근하거나 이동할 수 있다.

• 추상화 제공

프로그래머는 데이터 구조의 내부 구현을 몰라도 데이터를 다룰 수 있다.

 

▷ iterator 예시

#include <iostream>
#include <list>

int main() {
    std::list<int> numbers = {10, 20, 30};

    // iterator 선언
    std::list<int>::iterator iter = numbers.begin();

    // 데이터 순회
    while (iter != numbers.end()) {
        std::cout << *iter << " ";  // 10 20 30
        ++iter;  // 다음 노드로 이동
    }

    return 0;
}

---

▷ iterator 예시(vector, list)

#include <iostream>

#include <vector>
#include <list>

using std::cout;
using std::endl;

using std::vector;
using std::list;

int main()
{
	// ----------- vector ----------- //
	vector<int> vecInt;
	vecInt.push_back(10);
	vecInt.push_back(20);

	// 배열 버전 (마치 배열처럼 연산자를 사용하여 접근)
	vecInt[0] = 100;
	vecInt.at(1);  // vecInt[1];
    
    vector<int>::iterator veciter = vecInt.begin();
	*veciter = 100;  // vecInt[0];과 같다. (벡터 안에 넣어놓은 첫 번째 데이터에 접근)
	++veciter;  // 다음 데이터를 가리킨다.
	vecInt[0] = 100;

	// 벡터는 특정 인덱스에 접근하기 최적화되어있는 자료구조라서 iterator를 굳이 사용할 필요는 없다. (비효율적이다.)
	// 마냥 그렇지많은 않다.
		// 벡터도 넣어놓은 데이터를 삭제하고 싶을 수도 있다.
		// 특정 자리를 비웠다면 그 자리를 채우기 위해 뒤의 데이터들을 앞으로 땡겨와야 한다. (연속적인 구조)
			// 원래 데이터가 6개였는데 1개를 삭제하여 5개가 된 경우
				// 앞으로 땡기지 않고 데이터를 넣는다면(push_back()) 넣는 자리에 원래 있는 데이터를 덮어버린다.
	// 특정 위치에 있는 데이터를 삭제하는 경우
		// 몇 번째를 삭제하는지 알아야 한다.
		// 찾아보니 제거하는 함수로 erase()가 있다.
		// 그러나 해당 함수는 벡터에 구현되어있는 iterator를 요구한다.
	//vecInt.erase();
	// 삭제한 요소의 바로 다음 iterator를 반환한다.
		// 삭제하고 싶은 부분을 iterator로 가리켜서 해당 데이터를 주면 가리키는 곳을 삭제한다.
	
	// 이처럼 컨테이너마다 iterator를 이용한 설계가 공통적으로 적용되어있다.
    
    // 같은 자료구조여도 각 iterator는 전혀 다른 클래스이다.
	vector<float>::iterator;
	vector<short>::iterator;
	vector<int>::iterator;
    
	// ----------- list ----------- //
	list<int> listInt;
	listInt.push_back(10);
	listInt.push_back(100);

	list<int>::iterator iter = listInt.begin();  // 해당 리스트의 시작 부분을 가리킨다.
	int iData = *iter;  // 10
	++iter;  // 다음 데이터를 가리킨다. (= 다음 노드로 접근하여 그곳의 데이터 파트에 접근한다.)
	iData = *iter;

	//listInt.erase();
	// 리스트 안에 넣어놓은 데이터 중에 특정 위치를 가리키는 iterator를 받는다.
	// 해당 iterator가 가리키고 있는 데이터를 지운다.

	// 리스트 안에 넣어놓은 데이터 전체를 한 바퀴 순회하면서 출력
	for (iter = listInt.begin(); iter != listInt.end(); ++iter)
	{
		cout << *iter << endl;
	}

	return 0;
}