반복자

반복자

반복자는 어떤 컨테이너의 원소를 가리키는 객체입니다.

반복자는 포인터 개념을 추상화한 것입니다. 포인터가 순차적인 데이터(배열)에서만 동작하는 반면, 반복자는 연결 리스트나 탐색 트리 같은 어떤 컨테이너에서도 동작하며, 게다가 일관된 문법으로 동작하므로 라이브러리 개발자가 코드 중복을 피하는 데 큰 도움이 됩니다.

#문법

반복자 it이 가리키는 원소를 얻으려면 역참조 연산자 *it을 사용해야 합니다. 다음 원소로 이동하려면 증가 연산자 ++it을 사용해야 합니다(반복자에는 후위 증가 연산자가 없습니다).

모든 컨테이너에는 어떤 첫 번째 원소와 마지막 원소가 있습니다. 첫 번째 원소를 가리키는 반복자는 a.begin()으로 얻을 수 있고, a.end()로는 마지막 원소 다음에 오는 어떤 가상의 원소를 가리키는 반복자를 얻을 수 있습니다. 따라서 a.begin()부터 a.end() 직전까지 순회하면 컨테이너의 모든 원소를 순회하게 됩니다.

vector<int> a = {1, 2, 3, 4, 5};

// в типе итератора должна содержаться информация о контейнере
// поэтому в случае вектора интов это "vector<int>::iterator"
for (vector<int>::iterator it = a.begin(); it != a.end(); ++it)
    cout << *it << endl;

// в современном C++ можно вместо него использовать "auto"
for (auto it = a.begin(); it != a.end(); ++it)
    cout << *it << endl;

// также если нужно пройтись по всему массиву, можно сжать до такого
for (int x : a)
    cout << x << endl;

// если нужно как-то изменить элемент, его можно передать по ссылке
for (int &x : a)
    x *= 2;

for (x : a)
    cout << x << endl;

for (const int &x : a)
    cout << x << endl;

// (также можно вместо int писать auto)

// the initializer may be a braced-init-list
for (int x : {1, 2, 3, 4, 5})
    cout << x << endl;

// the initializer may be an array
int b[] = {1, 2, 3, 4, 5};
for (int x : b)
    cout << x << endl;

array<int, 5> c = {1, 2, 3, 4, 5};
for (int x : c)
    cout << x << endl;

#반복자의 범주

반복자는 컨테이너 인터페이스에서 매우 중요한 부분입니다. 반복자는 표준 라이브러리의 다양한 알고리즘에 전달할 수 있습니다. 이러한 알고리즘은 컨테이너의 내부 구조를 알 필요는 없지만, 어떤 데이터 접근 패턴이 가능한지는 알아야 합니다.

따라서 컨테이너의 반복자는 내부 구조에 따라 서로 다른 수준의 보장을 제공하는 여러 추상 클래스 중 하나에 해당할 수 있습니다.

  • input_iterator는 역참조와 증가 연산만 지원하며, 심지어 증가 연산을 수행한 후에 이전 값들이 유효하게 남아 있다는 보장조차 없습니다. 이름에서 짐작할 수 있듯이, 스트림 입력에 사용됩니다.

  • forward_iterator는 앞의 기능에 더해, 특정 원소를 가리키는 반복자를 사라질 염려 없이 원하는 만큼 몇 번이든 증가시킬 수 있음을 보장합니다(따라서 데이터를 여러 번 순회하는 알고리즘에 사용할 수 있습니다).

  • bidirectional_iterator: 앞의 것에 더해 감소(it--), 즉 이전 원소로 이동하는 기능을 지원합니다.

  • random_access_iterator는 앞의 기능에 더해 어떤 거리 $k$만큼 떨어진 원소로 이동하는 기능(it + k, it - k, it += k, it -= k)과 두 반복자가 가리키는 위치 사이의 거리를 구하는 기능을 지원합니다. 예를 들어 a - b라는 식은 반복자 a와 b에 해당하는 컬렉션의 두 원소 사이의 거리를 정수로 반환합니다.

#STL의 알고리즘

예를 들어, std::vector의 반복자는 random_access_iterator에 속하며, 표준 라이브러리의 lower_bound 함수를 호출하면 원소들에 대해 이진 탐색을 수행합니다(원소들이 비내림차순으로 정렬되어 있다고 가정합니다):

vector<int> a = {1, 2, 3, 5, 8, 13};

// вернет 8
cout << *lower_bound(a.begin(), a.end(), 7) << endl;

lower_bound 함수는 주어진 값보다 작지 않은 첫 번째 원소를 가리키는 반복자를 반환합니다. 또한 주어진 값보다 엄격하게 큰 첫 번째 원소를 반환하는 upper_bound도 있습니다(int의 경우 이는 x + 1에 대한 lower_bound를 찾는 것과 같습니다).

벡터의 반복자가 임의 접근을 지원한다는 것을 알고 있으므로 이진 탐색은 $O(n \log n)$에 동작하지만, 다른 자료 구조에서는 그렇지 않을 수도 있습니다.

또한 이러한 이유로 C 스타일 배열 대신 std::array를 사용하는 것이 합리적인 경우가 많습니다. std::array는 완전히 동일한 고정 길이 배열이지만, 반복자를 지원하며 그와 함께 모든 STL 알고리즘도 지원합니다:

array<int, 3> a = {4, 2, 1, 3};

// вернет 1
cout << *min_element(a.begin(), a.end()) << endl;