반복자

yun·2024년 2월 9일

C++

목록 보기

34/41

Iterator

벡터와 배열에서 사용되는 반복자가 기능 면에서 가장 유연
random access iterator (임의 접근 반복자) : 벡터와 배열은 연속된 자료 구조를 사용하기 때문에 특정 위치의 원소에 곧바로 접근할 수 있다
forward iterator (순방향 반복자) : std::forward_list에서는 증가 연산만 가능

반복자 타입에 따라 사용할 수 있는 함수

advance()

반복자와 거리 값을 인자로 받고, 반복자를 거리 값만큼 증가

C++ 11 ~ C++ 17

template< class InputIt, class Distance >
 void advance( InputIt& it, Distance n );```

C++ 17 ~
- ```
template< class InputIt, class Distance >
 constexpr void advance( InputIt& it, Distance n );```
```
- constexpr: 상수를 만드는 키워드, constexpr를 리턴함으로써 advance의 결과값을 다른 함수에서 사용할 수 있게 됨 (참고: https://stackoverflow.com/questions/66002533/for-what-reason-would-a-function-with-void-return-type-be-constexpr)

next(), prev()

반복자와 거리 값을 인자로 받고, 해당 반복자에서 지정한 거리만큼 떨어진 위치의 반복자를 반환

C++ 11 ~ C++ 17

template< class InputIt >
 InputIt next( InputIt it, typename std::iterator_traits<InputIt>::difference_type n = 1 );```

template< class BidirIt >
 BidirIt prev( BidirIt it, typename std::iterator_traits<BidirIt>::difference_type n = 1 );```

C++ 17

template< class InputIt >
 constexpr InputIt next( InputIt it, typename std::iterator_traits<InputIt>::difference_type n = 1 );```

template< class BidirIt >
 constexpr BidirIt prev( BidirIt it, typename std::iterator_traits<BidirIt>::difference_type n = 1 );```

C++ 20 ~

template< std::input_or_output_iterator I >
 constexpr I next( I i, std::iter_difference_t<I> n );

template< std::bidirectional_iterator I >
 constexpr I prev( I i, std::iter_difference_t<I> n );

참고

위 함수들은 해당 반복자가 지원할 경우에만 동작
순방향으로만 이동 가능한 순방향 반복자에 대해 prev() 함수를 사용하면 에러 발생
동작 시간도 반복자 타입에 따라 결정
- next(), prev()
  - 임의 접근 반복자에서는 덧셈 또는 뺄셈이 상수 시간으로 동작하므로 상수 시간으로 동작
  - 나머지 타입의 반복자에서는 주어진 거리만큼 순방향 또는 역방향으로 이동해야 하기 때문에 선형 시간 소요

연습문제

반복자를 사용하여 F1 그랑프리 수상자 명단에서 정보를 검색하기

#include <iostream>
#include <forward_list>
#include <vector>

using namespace std;

int main()
{
  // 벡터로 최근 경기 우승자 명단 작성
  vector<string> vec = {
  	"Lewis Hamilton", "Lewis Hamilton", "Nico Roseberg",
    "Sebastian Vettel", "Lewis Hamilton", "Sebastian Vettel",
    "Sebastian Vettel", "Sebastian Vettel", "Fernando Alonso"
  };
  
  auto it = vec.begin();  // 상수 시간 = O(1)
  cout << "가장 최근 우승자: " << *it << endl;
  
  it += 8;  // 상수 시간
  cout << "8년 전 우승자: " << *it << endl;
  
  advance(it, -3);  // 상수 시간
  cout << "그후 3년 뒤 우승자: " << *it << endl;
  
  // forward_list로 같은 작업 수행
  forward_list<string> fwd(vec.begin(), vec.end());
  
  auto it1 = fwd.begin();
  cout << "가장 최근 우승자: " << *it1 << endl;
  
  advance(it1, 5);  // 선형 시간 = O(n)
  cout << "5년 전 우승자: " << *it1 << endl;
  
  // forward_list는 순방향으로만 이동할 수 있음
  // 런타임 에러 발생
  // advance(it1, -2);
  
  // forward_list의 iterator는 += 연산자가 정의되어 있지 않음
  // 컴파일 에러 발생
  // it1 += 2;
}