땡글이LAB
[C++] iterator (반복자) 정리 본문
# Iterator(반복자)
- 컨테이너에 저장되어있는 원소들을 공통적인 방법으로 하나씩 접근 가능하다.
- 모든 컨테이너들이 다 같은 방법으로 반복자 사용 가능.
- 각 타입에 ::iterator 또는 ::const_iterator 를 뒤에 붙여주면 사용이 가능하다.
- vector 컨테이너의 반복자
- vector<int>::iterator it;
- vector 컨테이너의 const한 반복자
- vector<int>::const_iterator it;
- vector 컨테이너의 반복자
- 포인터와 비슷하게 사용된다.
- 간접 참조 가능
- it = v.begin() + 2 에서 *it 간접 참조를 하면 세 번째 원소 값이 리턴된다.
- 간접 참조 가능
- iterator와 const_iterator의 차이
- const_iterator는 반복자가 가리키는 원소의 값을 변경하지 못한다.
- 반복자 값이 변경되지 못하는 게 아니고 반복자가 가리키는 원소의 값이 변경될 수 없다는 걸 의미한다.
- 일반 반복자는 포인터와 비슷하고 const 반복자는 const 포인터와 비슷하다. (간접참조로 값을 변경하지 못함)
- const_iterator는 반복자가 가리키는 원소의 값을 변경하지 못한다.
- 초기화 방법
- it = container.begin()
- 컨테이너이름.begin()하면 첫 번째 원소의 iterator를 리턴
- it = container.begin()
컨테이너에 저장되어있는 원소들을 공통적인 방법으로 하나씩 접근 가능하다.
각 타입에 ::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
(뒤에서 반복자의 종류에서 각 카테고리별로 설명하도록 한다)
#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
'Programming Language > C++' 카테고리의 다른 글
[C++] set, multiset, unordered_set 의 차이 (0) | 2022.02.12 |
---|---|
[C++] 문자열 자르기 (0) | 2022.01.20 |