reference:
- "전문가를 위한 C++" / 마크 그레고리
- "코딩 테스트를 위한 자료구조와 알고리즘 with C++" / 존 캐리, 셰리안 도시, 파야스 라잔
- http://soen.kr/lecture/ccpp/cpp4/39-1-1.htm(참고하기 좋은 사이트)
정리
- advance, next, prev 등 여러 반복자 관련 함수는 반복자의 종류에 따라 동작할 수도, 동작하지 않을 수도 있다. 반복자의 종류는 해당 반복자가 정의된 컨테이너 종류에 따라 다르다.
- 반복자 관련 함수의 동작 시간은 반복자 종류에 따라 다르다.
반복자(Iterator)
source: http://soen.kr/lecture/ccpp/cpp4/39-1-1.htm
컨테이너마다 원소에 대해 반복문을 수행할 방법이 담긴 특수한 스마트 포인터인 반복자가 정의되어 있다. 컨테이너의 종류가 달라도 반복자의 인터페이스는 모두 같다. 즉 구체적인 동작은 달라도 컨테이너 원소에 대해 반복문을 비슷한 방식으로 작성할 수 있도록 인터페이스가 통일되어있다.
배열에서 원소를 가리키는 포인터처럼 반복자도 operator++ 연산자를 이용하여 다음 원소로 이동할 수 있다. 또한 반복자로 원소의 필드나 원소 자체에 접근할 때 opeartor* 이나 oprator->를 사용할 수도 있다. 어떤 반복자는 operator= 이나 operator !=로 비교하거나 operator--로 이전 원소로 이동하는 기능도 제공한다.
reference: http://soen.kr/
컨테이너에 대해 어떤 작업을 하고 싶다면 먼저 이 컨테이너에 저장되어 있는 요소에 접근해야 하므로 순회가 꼭 필요하다. 알고리즘이란 컨테이너 자체에 대해 적용되는 것이 아니라 결국은 컨테이너의 요소들에 적용되는 것이므로 요소를 읽고 쓸 수 있어야 하는데 이를 위해 반복자가 사용된다. 알고리즘은 반복자를 통해 컨테이너의 요소를 읽고 변경하며 컨테이너는 알고리즘을 호출할 때 작업 대상 요소를 반복자로 지정한다. 그래서 반복자를 알고리즘과 컨테이너를 연결하는 매개체라고 한다.
..
..
동일한 코드로 작성되어 있는 알고리즘을 여러 개의 컨테이너에 똑같이 적용할 수 있다. 예를 들어 find는 지정한 구간을 순서대로 순회하며 값을 검색하는데 벡터나 리스트의 내부 구조가 완전히 다르지만 반복자가 연산자와 ++ 연산자, 비교 연산자 등만 잘 정의한다면 두 컨테이너를 동일한 방법으로 검색할 수 있는 것이다. 요소들이 어떤 모양을 가지든지 연산자로 읽을 수 있고 요소들간의 배치 관계에 상관없이 ++만 하면 다음 요소로 이동 가능하다.
임의 접근 반복자, 순방향 반복자
반복자는 포인터와 비슷하고, STL 컨테이너에 대해 공통의 인터페이스를 제공한다. 하지만 반복자를 이용한 연산은 어떤 컨테이너에서 정의된 반복자인지에 따라 결정된다.
벡터(std::vector)와 배열(std::array)에서 사용되는 반복자는 기능 면에서 가장 유연하다. 벡터와 배열은 연속된 자료 구조를 사용하기에 특정 위치의 원소에 곧바로 접근할 수 있다. 이러한 반복자를 임의 접근 반복자(random access iterator)라고 한다.
그러나 std::forward_list(연결 리스트형 컨테이너)의 경우 기본적으로 역방향으로 이동하는 기능(oprator--)을 제공하지 않으며, 바로 이전 노드로 이동하려면 맨 처음 노드부터 시작해서 찾아가야 한다. 따라서 std::forward_list에서는 증가 연산만 가능하며, 이러한 반복자를 순방향 반복자(forward_iterator)라고 한다.
advance(), next(), prev()
반복자 타입에 따라 사용할 수 있는 advance(), next(), prev() 함수가 있다.
advance() 함수는 반복자와 거리 값을 인자로 받고, 반복자를 거리 값만큼 증가시킨다. next()와 prev() 함수도 반복자와 거리 값을 인자로 받고, 해당 반복자에서 지정한 거리만큼 떨어진 위치의 반복자를 반환한다.
이들 함수는 해당 반복자가 지원할 경우에만 동작한다. 예를 들어 순방향 반복자에 대해 prev() 함수를 사용하면 에러가 발생한다.
또한 이들 함수의 동작 시간은 반복자 타입에 따라 결정된다.
- 임의 접근 반복자(ex, vector iterator)에서는 덧셈 또는 뺄셈이 상수 시간으로 동작하므로 next(), prev() 등의 함수도 상수 시간으로 동작.
- 나머지 타입의 반복자(ex, forward_list iterator)에서는 주어진 거리만큼 순방향 또는 역방향으로 이동해야 하기에 선형 시간이 소요된다.
다양한 반복자에서 이동
#include <iostream>
#include <forward_list>
#include <vector>
using namespace std;
int main(){
// vector를 이용하여 최근 경기 우승자 명단 작성
vector<string> vec = {
"Hamilton", "Hamilton", "Roseberg",
"Vettel", "Hamilton", "Vettel",
"Vettel", "Vettel", "Alonso"
};
auto it = vec.begin(); // 상수 시간
cout << "가장 최근 우승자: " << *it << '\n';
// => Hamilton
it += 8; // 상수 시간
cout << "8년전 우승자: " << *it << '\n';
// => Alonso
advance(it, -3); // 상수 시간
cout << "그 후 3년뒤 우승자: " << *it << '\n';
// => Vettel
// forward_list를 이용하여 같은 작업 수행하기
forward_list<string> fwd(vec.begin(), vec.end());
auto it1 = fwd.begin();
cout << "가장 최근 우승자: " << *it1 << '\n';
// => Hamilton
advance(it1, 5); // 선형 시간 O(n)
cout << "5년전 우승자: " << *it1 << '\n';
// => Vettel
//it1 += 5; // 에러
// no match for 'operator+='
// forward_list는 순방향으로만 이동할 수 있으므로
// advance(it1, -2); 는 에러가 발생함.
}다양한 반복자 사용 방법은 전체 데이터셋에서 특정 데이터에 접근할 때 매우 유용하게 사용할 수 있다.
벡터에서는 특정 원소에 즉각적으로 접근할 수 있으므로 벡터 반복자의 덧셈과 뺄셈 연산은 O(1)이다. 반면에 forward_list는 연속적인 순회를 통해서만 특정 원소에 접근할 수 있다. 그러므로 std::forward_list 반복자의 덧셈 연산 시간 복잡도는 O(n)이고, 여기서 n은 순회할 횟수를 나타낸다.
반복자 무효화
어떤 컨테이너든 원소 접근, 순회, 삽입, 삭제 등의 작업을 반복자를 사용하여 모두 같은 방식으로 처리한다. 반복자는 메모리 주소를 가리키는 포인터를 이용하여 구현되었기에 경우에 따라 컨테이너가 변경될 경우 제대로 동작하지 않을 수 있다. 그러므로 컨테이너가 변경되어 특정 노드 또는 원소의 메모리 주소가 바뀌면 사용하던 반복자가 무효화될 수 있고, 이 경우 예측할 수 없는 동작이 발생할 수 있다.
벡터에서 맨 뒤 원소를 추가하는 vector::push_back() 함수는 경우에 따라 새로 메모리 공간을 할당하고 기존의 모든 원소를 새 메모리 공간으로 복사하는 동작이 발생한다. 이 경우 기존에 사용하던 모든 반복자와 포인터, 참조는 모두 무효화된다.
마찬가지로 vector::insert() 함수를 수행할 때 메모리 재할당이 필요한 경우라면, 이 경우에도 기존의 반복자, 포인터, 참조는 모두 사용하면 안된다. 또한 메모리 재할당 없이 원소를 삽입하는 경우, 원소 삽입 위치 이후에 있는 모든 원소를 이동해야 하므로 이 위치를 가리키는 반복자는 모두 무효화된다.
벡터와 달리 연결 리스트에서는 삽입 또는 삭제 동작에서 원소를 이동할 필요가 없으므로 반복자가 무효화되지 않는다. 즉, std::list 또는 std::forward_list에서 삽입 동작은 반복자의 유효성에 영향을 미치지 않는다. 다만 특정 원소를 삭제하는 경우, 삭제되는 원소를 가리키던 반복자는 당연히 무효화되지만 나머지 원소를 가리키는 반복자는 그래도 사용할 수 있다.
std::vector<int> vec = {1, 2, 3, 4, 5};
auto v_it4 = vec.begin() + 4; // v_it4는 vec[4] 원소를 가리킨다.
vec.insert(vec.begin()+2, 0); // v_it4 반복자는 무효화된다.위 코드에서 마지막 문장이 수행되면 v_it4 반복자는 무효화되며, v_it4를 이용하여 원소에 접근하려고 하면 예상치 못한 에러가 발생할 수 있다.
std::list<int> lst = {1, 2, 3, 4, 5};
auto l_it4 = next(lst.begin(), 4);
lst.insert(next(lst,begin(), 2), 0); // l_it4 반복자는 여전히 유효하다. cf)
std::list는 size(), push_back(), pop_back() 등의 더 많은 함수를 제공하며, 이들 연산은 O(1) 시간 복잡도로 동작한다. 그러므로 std::forward_list보다 더 자주 사용된다.
std::forward_list는 데이터를 역방향으로 이동하며 접근하지 않아도 되는 경우에 메모리 또는 성능을 최적화하고 싶을 때에만 제한적으로 사용된다. 즉 대부분의 경우 std::list를 사용하는 것이 더 나은 선택이다.
