[C++] iterator (반복자) 정리

# Iterator(반복자)

• 컨테이너에 저장되어있는 원소들을 공통적인 방법으로 하나씩 접근 가능하다.
  • 모든 컨테이너들이 다 같은 방법으로 반복자 사용 가능.
• 각 타입에 ::iterator 또는 ::const_iterator 를 뒤에 붙여주면 사용이 가능하다.
  • vector 컨테이너의 반복자
    • vector<int>::iterator it;
  • vector 컨테이너의 const한 반복자
    • vector<int>::const_iterator it;
• 포인터와 비슷하게 사용된다.
  • 간접 참조 가능
    • it = v.begin() + 2 에서 *it 간접 참조를 하면 세 번째 원소 값이 리턴된다.
• iterator와 const_iterator의 차이
  • const_iterator는 반복자가 가리키는 원소의 값을 변경하지 못한다.
    • 반복자 값이 변경되지 못하는 게 아니고 반복자가 가리키는 원소의 값이 변경될 수 없다는 걸 의미한다.
  • 일반 반복자는 포인터와 비슷하고 const 반복자는 const 포인터와 비슷하다. (간접참조로 값을 변경하지 못함)
• 초기화 방법
  • it = container.begin()
    • 컨테이너이름.begin()하면 첫 번째 원소의 iterator를 리턴

 

컨테이너에 저장되어있는 원소들을 공통적인 방법으로 하나씩 접근 가능하다.

각 타입에 ::iterator 또는 ::const_iterator 를 뒤에 붙여주면 사용이 가능하다.

 

 

STL(Standard Template Library)은 반복자의 5가지 종류를 구현한다(밑의 반복자의 내부 구현과 Category 인자를 보면 알 수 있다).

 

# Iterator 내부 구현

[반복자의 내부 구현]

template <class Category, class T, class Distance = ptrdiff_t,
          class Pointer = T*, class Reference = T&>
  struct iterator {
    typedef T         value_type;
    typedef Distance  difference_type;
    typedef Pointer   pointer;
    typedef Reference reference;
    typedef Category  iterator_category;
  };

 

 

[template parameters 설명]

#1-1. Category

Iterator tag	Category of iterators
input_iterator_tag	Input Iterator
output_iterator_tag	Output Iterator
forward_iterator_tag	Forward Iterator
bidirectional_iterator_tag	Bidirectional Iterator
random_access_iterator_tag	Random-access Iterator

(뒤에서 반복자의 종류에서 각 카테고리별로 설명하도록 한다)

 

#1-2. T

Type of elements pointed by the iterator.

 

#1-3. Distance

Type to represent the difference between two iterators.

 

#1-4. Pointer

Type to represent a pointer to an element pointed by the iterator.

 

#1-5. Reference

Type to represent a reference to an element pointed by the iterator.

 

 

 

# Iterator 종류

반복자에는 5가지 종류가 있다. 

1. 입력 반복자(input iterator)

• Read 및 접근 가능
• Write 불가능
• 산술 연산 : ++ 연산만 가능
• 비교 연산 : ==, != 가능

2. 출력 반복자(output iterator)

• Read 및 접근 불가능
• Write만 가능
• 산술 연산 : ++ 연산만 가능
• 비교 연산 : 불가능

3. 순방향 반복자(forward iterator)

• 읽기, 쓰기, 접근 다 가능하다.
• 산술연산 : ++ 연산만 가능
• 비교 연산 : ==, != 가능

4. 양방향 반복자(bidirectional iterator)

• 읽기, 쓰기 접근 다 가능하다.
• 산술연산 : ++, -- 만 가능
• 비교 연산 : ==, != 만 가능

list, set, map은 이 반복자를 지원한다. (그래서 set의 반복자끼리 뺄셈을 하려 했을 때 불가능했던 것)

이 양방향 반복자를 지원하지 않는 컨테이너는 알고리즘 헤더의 reverse() 함수를 사용할 수 없다. 
reverse 함수는 이 양방향 반복자를 사용하기 때문이다. 이처럼 함수, 연산에 따라 사용할 수 있는 반복자가 정해져있다는 것을 꼭 알아두자!

5. 임의접근 반복자(random access iterator)

• 읽기, 쓰기 접근 다 가능하다.
• 산술연산 : ++, --, +, -, +=, -= 가능
• 비교 연산 : ==, !=, >, <, >=, <= 가능
• 첨자 연산자 사용 가능 : []
  • it[n] : *(it + n) 과 같다.

vector, deque는 이 반복자를 지원한다. 그래서 반복자끼리 사칙 연산을 해야한다면, vector 사용해야 한다.

+, - 산술 연산이 가능한건 “임의 접근 반복자”를 가지는 vector, deque 밖에 없다.

 

 

# Iterator 사용 예제 : insert, erase

 iterator 사용 예제로 erase를 중점적으로 다루겠다. 가장 실수가 많이 일어나는 부분이라 생각되기에 짚고 넘어갈 필요가 있다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
	vector<int> vec;

	for (int i = 1; i <= 10; i++)
		vec.push_back(i);

	//6번째 값 삭제
	auto iter = vec.erase(vec.begin() + 5);

	cout << "6번째 값 삭제 이후 vector : ";
	for (auto element : vec)
		cout << element << ' ';
	cout << '\n';


	//2 ~ 4번째 구간 삭제
	iter = vec.erase(vec.begin() + 1, vec.begin() + 4);

	cout << "2 ~ 4번째 구간 삭제 이후 vector : ";
	for (auto element : vec)
		cout << element << ' ';

	cout << '\n';
}

 vec.begin() + 5 는 vec에서 6번째 값을 가리키는 iterator 이므로 erase 해주면 6번째 값이 삭제된다. 매우 간단한 vector 사용 예제다.

 구간을 삭제할 때 erase는 첫 번째 인자는 포함시켜서 삭제하지만 두 번째 인자는 포함시키지 않고 구간을 삭제한다. 즉 삭제되는 구간 범위가 [ 첫 번째 인자 , 두 번째 인자 ) 로 설정된다.

 

그런데 만약, for문 안에서 6번째 값을 지우려고 한다면 어떻게 될까??

#include <iostream>
#include <vector>

using namespace std;

int main() {
	vector<int> vec;

	//1부터 10까지 push
	for (int i = 1; i <= 10; i++)
		vec.push_back(i);

	auto iter = vec.begin();

	while (iter != vec.end()) {
		if (iter == vec.begin() + 5) {
			//6번째 값 삭제
			iter = vec.erase(vec.begin() + 5);
			continue;
		}

		cout << *iter << ' ';
		iter++;
	}

	cout << '\n';
}

결과가 뭔가 잘못됐다. 이유는 이 글을 보고 있는 모두가 알겠지만 코딩테스트에서 간혹 실수로 이런 것을 놓친다면 디버깅하는데 많은 시간이 할애된다... 이유는 간단하다. 6번째 값이 지워졌으니 그 다음 값도 vector 내에서 6번째 값이 돼서 vec.begin() + 5 랑 같아진다. 그래서 7 ~ 10 은 출력이 안되고 1 ~ 5 만 출력이 되는 것을 확인할 수 있다.

해결 방법으로는 반복문 바깥에 bool 형 변수를 둬서 한 번 지워진다면 그 이후에는 지워지지 않도록 if 문을 두는 방법도 있을 것이다. 확실한 건 반복문 안에서 erase는 정말 조심히 사용하거나 반복문 바깥에서 erase를 사용해야 좀 더 안전한 코드를 작성할 수 있다는 점이다.

 

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> myvector(3, 100);
    vector<int>::iterator it;

    // 처음 위치에 200 삽입
    it = myvector.begin();
    it = myvector.insert(it, 200);

    // 300 2번 삽입 (200이 삽입된 위치의 앞에)
    myvector.insert(it, 2, 300);

    it = myvector.begin();

    // 다른 vector랑 합치기 (myvector의 3번째 위치에)
    vector<int> anothervector(2, 400);
    myvector.insert(it + 2, anothervector.begin(), anothervector.end());

    // 배열 삽입 (myvector의 맨 앞에)
    int myarray[] = { 501,502,503 };
    myvector.insert(myvector.begin(), myarray, myarray + 3);

    cout << "myvector contains:";
    for (it = myvector.begin(); it < myvector.end(); it++)
        cout << ' ' << *it;
    cout << '\n';

    return 0;
}

위의 코드는 insert 예제이다. 주석에 설명을 남겨놨으니 참고하면 될 것이다.

 

# insert, erase 시간 복잡도

vector의 insert 및 erase는 시간 복잡도가 O(N)이 된다. vector는 결국 우리가 편하게 쓰게끔 만들어진 라이브러리에 불과하다. 즉 중간에 어떤 값을 지우게 되면 그 vector의 크기만큼 지워진 부분의 뒤 부분을 앞으로 한 칸씩 혹은 여러 칸 땡겨와야하므로 O(N)이 된다.

 

하지만 list의 경우는 다르다(C++의 list는 연결리스트로 구현되어있다). list는 insert와 erase가 O(1)에 가능하다. 하지만 탐색에는 O(N)이 걸리는 단점이 있다. 그러므로 코드를 짤 때 항상 시간복잡도를 생각해서 상황에 맞는 컨테이너를 사용하는 것이 좋다. 

 

 

 

 

Reference 

• C++ Reference
• 위키백과 - STL
• https://ansohxxn.github.io/stl/chapter16-2/