[C++] 컨테이너별 iterator

hwhyeons·2025년 2월 12일

C++로 알고리즘을 준비하다보면,
배열을 정렬할 때는 sort(arr.begin(), arr.end())등의 문법을
많이 사용하게 된다.

여기서 begin(), end()는 모두 iterator()을 반환한다.

C++로 알고리즘 및 코딩테스트를 공부할 때는 반복기 사용을 잘 알아두면 헷갈리지 않고 잘 사용할 수 있다.

C++의 iterator은 크게

(출처 : 링크)
이 정도로 나눠볼 수 있다.

이터레이터 종류에 따라 할 수 있는 연산이 다르다.

iterator 종류 알아보기

위 표에 여러가지 종류의 iterator가 있지만,
알고리즘 문제를 풀기 위해 공부하는 거라면 random_access_iterator인지
아닌지만 구별하면 된다.

왜냐면 가장 간단한 예시로,
std::sort()로 정렬을 사용하기 위해서는 random access iterator을
인자로 전달해야하기 때문이다.

또 이분탐색을 직접 구현하지 않고 algorithm 헤더를 이용해서
lower_bound(), upper_bound(), binary_search() 등을 이용할 때도
random_access_iterator을 전달해야한다.

radom access iterator

한국어로 표현하면 임의 접근 반복기, 임의 접근 반복자 등으로 부를 수 있다.
임의 접근이라는 것은, 인덱스를 이용해서 읽고 쓸 수 있는 반복자를 의미한다.

그 외에도 여러가지 특징이 있지만, PS에서 중요한건
반복자에 ++,-- 등의 증감연산과 산술연산이 가능하다는 것이다.

또 operator[]을 이용해서 마치 배열의 인덱스에 접근하듯 접근할 수 있다.

STL의 vector는 임의 접근 반복자를 제공한다.

vector<int> v1 = {10,20,30,40};
cout << *(v1.begin()+2) << endl;

(참고로 반복자는 * 을 이용해서 포인터처럼 역참조 할 수 있다)

하지만, STL의 list (연결리스트)는 임의 접근 반복자가 아니다.
따라서 순차적으로 이동은 가능하나, 인덱스로 접근이 불가능하다.

list<int> l1 = {10,20,30,40};
cout << *(l1.begin()+2) << endl; // compile error

STL Container별 iterator 종류 구별법

vector

iterator 종류를 구분해야 어느 상황에서 사용할 수 있는지 없는지를 구분할 수 있다.
이를 외우는 것은 자료구조의 특성을 알고 있으면 크게 어렵지가 않다.

해당 자료구조의 메모리 구조를 알고 있으면 충분히 유추가 가능하다.

예를들어, vector의 경우 내부가 배열로 구성되어있다.
배열은 메모리를 순차적으로 차지하며, 자료형의 크기와 배열의 시작 주소를 알면
몇번째 원소가 어느 메모리 주소에 위치해있는지 안다.
그렇기 때문에 연결 리스트와 다르게 어떠한 위치에 있든 접근하는 상황에서는
O(1)의 시간복잡도를 가진다고 배웠을 것이다.

반복자를 포인터처럼 생각하면 조금 쉬운데, 포인터는 주소를 가리킨다.
근데 배열(벡터)는 N번째 원소의 메모리 주소가 바로 계산이 가능하다.
-> random_access_iterator을 제공한다

list
STL list는 연결리스트다 (linked list)
연결리스트의 특징은 한 원소가 그 다음 원소를 가리키고,
또 다음 원소는 그 다음 원소를 가리키는 방식이다.
따라서 연결리스트는 어레이리스트(벡터)나 배열처럼
N번째 원소의 주소를 바로 알 수가 없다.
-> random access iterator가 아니다

아까 처음에 std::sort()를 이용하기 위해서는 random access iterator가 필요하다고 했는데, list의 경우 std::sort를 이용한 정렬이 불가능하다.
```
list<int> l1 = {10,20,30,40};
 sort(l1.begin(), l1.end());
```
IDE에는 오류가 안잡힐 수 있는데 컴파일 하면 오류발생한다.

하지만 list는 시퀀스 컨테이너이고 중간 원소들도 접근이 가능한데,
정렬 기능을 사용하지 못한다는 것은 이상하다.
이런 이유로 C++ 연결리스트는 자체적으로 멤버에 sort()가 존재한다.
l1.sort()와 같이 정렬을 제공하므로, std::sort()가 아닌
list자체의 sort()를 이용해서 정렬해야한다

stack / queue
스택과 큐는 C++에서 반복자를 제공하지 않는다.
반복자를 제공할 이유도 없고 반복자가 있으면 오히려 더 의도치 않은 행동을
할 가능성이 있다.

스택과 큐는 맨 앞의 원소만 접근하는 용도인데, 굳이 iterator을 이용해서
중간 원소를 확인할 필요가 없기 때문이고 이런 용도라면
vector나 deque 등의 다른 컨테이너를 선택해야한다.

deque
덱은 큐, 스택과 비슷하지만 다르다.
맨 앞과 맨 뒤 둘다 삽입, 제거가 가능하고
중간 원소 접근도 가능하다.
따라서 deque은 iterator을 제공한다.

그러면 deque에서는 임의 접근 반복자를 제공할까?
-> 제공한다.

이 내용은 링크에 예전에 따로 정리해두었다.

이를 통해 deque의 메모리 구조를 확인하면 왜 random access iterator가
제공되는지 알 수 있다.

즉, random access iterator가 제공되기 때문에,
alogorithm 헤더에서 제공하는 sort, binary_search 등을
deque에서도 사용할 수 있다.

set / map
C++의 set은 TreeSet(이진탐색트리)를 의미한다.
따라서, random_access_iterator을 제공하기에는 구조적으로 힘들다.

treeset은 원소들이 정렬되어 추가되며, 그 원리는
이진 탐색 트리에 있다.

특정 값을 가진 원소를 찾는 것은 O(logN)이 소요되며,
N번째 원소를 찾는 것도 마찬가지다.

아까 std::binary_search를 사용하기 위해서는 random access iterator가 필요하다고 했다.

따라서 set의 iterator로는 std::binary_search가 불가능하지만
다행히 set에서는 set 자체적으로 lower_bound(), upper_bound()를
제공하기 때문에 이분탐색이 가능하다.

만약 어떤 원소가 존재하는지만 체크하고 싶다면,
C++ 20 이후에는 contains()를, 그 이전에는 find()를 이용하면 된다.
이 역시 내부적으로 이분탐색을 진행한다.

unordered_set / unordered_map
해시셋은 당연히 random_access_iterator을 제공할 수 없다.
특정 원소가 존재하는지는 해시값을 이용해 매우 빠르게 찾을 수 있지만,
구조 특성상 N번째 원소라는 개념이 없다.
특정원소를 빠르게 찾으면서 동시에 N번째라는 순서를 도입하고 싶으면
set을 사용해야한다 (단, unordered_set처럼 O(1)은 아니고 O(logN))

priority_queue
우선순위큐는 힙 구조를 이용한다.
물론 힙을 저장하고 표현하기 위한 구조로는 배열,벡터,deque등의
임의 접근이 가능한 자료구조를 사용한다.

그래서 priority_queue를 이용하는 문제에서
```
priority_queue<int, vector<int>,greater<int>> pq;
```
이렇게 중간에 vector<int>등을 굳이 넣는 것을 해봤을 수 있다.
이게 우선순위 큐 원소를 저장할 컨테이너를 결정하는 것이다.
```
priority_queue<int, deque<int>,greater<int>> pq1;
priority_queue<int, vector<int>,greater<int>> pq2;
priority_queue<int, list<int>,greater<int>> pq3;
pq1.push(10);
pq2.push(20);
pq3.push(30); // compile error
```
임의 접근 반복자를 제공하지 않는 list는 내부 컨테이너로 사용이 불가능하다.
컴파일 할 때 알아서 잡아준다.

어쨋든 결론은 랜덤 엑세스 이터레이터를 제공이 불가능하다
(애초에 우선순위 큐는 반복자를 제공하지 않는다)