Iterator

Iterator란? link

C++에서 반복자는 ++ 연산으로 이동하고 * 연산으로 값에 접근할 수 있는 객체. raw pointer도 반복자.

객체가 반복자 요구 조건을 만족하는지 확인하려면 input_or_output_iterator<T> 같은 concept을 사용하면 됨.

컨테이너 반복자 사용 시 주의점 link

컨테이너의 반복자 타입을 직접 쓰면 코드가 복잡해지고 컨테이너가 바뀔 때마다 타입도 바뀌어야 하므로 auto 사용 권장.

• c.begin() vs std::begin()

  • std::begin()은 raw array도 처리 가능
  • 구현은 컨테이너용과 배열용 따로 작성

  template<typename C>
constexpr auto mybegin(C& c) noexcept(noexcept(c.begin())) -> decltype(c.begin())
{ return c.begin(); }

template<typename T, std::size_t SZ>
constexpr T* mybegin(T(&arr)[SZ]) noexcept
{ return arr; }
  

Iterator invalidation link

반복자를 얻은 후에 컨테이너가 재할당되거나 수정되면 그 반복자는 더 이상 유효하지 않음.

Passing Iterator link

반복자는 크기가 작고 복사 비용이 적기 때문에 함수 인자로 전달할 때 보통 값 전달(call by value)을 사용

• Cheap-to-copy types의 경우 pass by value 시 copy가 일어난다. 즉 value를 받아서 function call을 위한 stack에 넣음. 그런데 pass by reference의 경우 memory address to the stack을 push하고 called function이 그 주소에 있는 것을 fetch해야 함. 그래서 둘을 비교해보면 Cheapto-cpoy types는 그냥 pass by value로 쓰면 됨
• iterator를 참조로 받으면 dereference를 해서 iterator를 얻고 또 dereference를 해서 값에 접근하는 과정이 superfluous
• StackOverflow 논의

std::ranges::begin link

std::ranges::begin은 기존 std::begin보다 안전하다.

이유는 아래와 같다

1. 반환 타입 검사

   • std::begin(c)를 하면 c가 begin함수를 가지고 있고 그걸 부르는 것
   • 그런데 c가 begin을 Iterator말고 이상한 걸 리턴해도 에러가 안남
   • std::ranges::begin은 반환 타입이 무조건 반복자여야한다는 조건이 있음

2. value category 검사

   • rvalue라면 기존 begin const iterator를 반환하는데 이거는 dangling이라 undefined 동작 발생
   • ranges::begin은 rvalue넣으면 에러

Range와 View link

• Range: begin, end로 반복자 꺼낼 수 있는 타입
• View: 실제 컨테이너를 복사하지 않고 가공된 형태로 보여주는 것 (ex: string_view, filter_view 등)

반복자가 가리키는 타입 얻기 link

• C++20: std::iter_value_t<T>
• C++98~17: typename T::value_type 또는 typename iterator_traits<T>::value_type 사용

Iterator category link

반복자는 계층 구조를 가짐 (in/output, forward, bidirectional, random access, contiguous)

STL 알고리즘은 반복자의에 대한 요구 조건이 있음

  template<typename BidirIt>
void reverse(BidirIt first, BidirIt last); // -- 연산 가능한 반복자 필요
  

그래서 reverse를 보면 iterator category를 이용한 타입 이름을 지음

• multiple pass: *it1 == *it2일 때 ++it1, ++it2 후에도 같아야 함

istream_iterator link

* 연산 시 스트림에서 값을 꺼내고 해당 값을 소비함.

Iterator operation: advance / distance / next / prev link

• advance: 반복자를 특정 거리만큼 이동
• distance: 반복자 간 거리 계산
• std::next(iter, n, last): 최대 범위 제한 가능

++c.begin() vs std::next(c.begin()) link

++c.begin()은 rvalue에 대해 불가능. std::next(c.begin())는 함수 인자로 넘겨지면서 lvalue가 되어 가능.

한편 vector, list의 반복자는 ++c.begin이 된다.

rvalue는 ++연산은 불가능하나 멤버함수 호출은 가능한 원리를 이용해서 아래와 같이 구성하여 iterator를 사용하게 되면 ++이 가능

  class myiterator {
 int* current;
public:
 myiterator(int* p = nullptr) : current{p} {}
 myiterator& operator++() { ++current; return *this; }
 int& operator*() { return *current; }
};
  

Copy Container link

1. 대입연산자/Assign: 기존 요소 완전히 제거 후 복사
2. 반복문: list는 지원 안됨. list는 operator[]가 없어서.
3. copy: 기존 요소에 덮어쓰기

• copy: 반복자만 인자로 받아서 덮어씀
• ranges::copy: 반복자 또는 컨테이너 자체 전달 가능

reverse_iterator link

• 생성자 또는 make_reverse_iterator(it)로 생성 가능
• rbegin() / rend()는 내부적으로 std::make_reverse_iterator(v.end()) 호출
• 어떤 코드를 반대로 동작시키고 싶을 때 반복자만 반대로 설정해주면 됨.

insert_iterator link

• 후방 삽입: back_insert_iterator, ex) std::back_inserter(v)
• 전방 삽입: front_insert_iterator
• 중간 삽입: insert_iterator

  std::vector v {1, 2, 3, 4, 5};
std::list s1{0, 0, 0, 0, 0};
std::list s2{0, 0, 0, 0, 0};

copy(v, std::front_inserter(s1));
copy(v, std::inserter(s2, s2.begin()));
  

• vector는 push_front 불가능. front_inserter 사용 불가

counted_iterator (C++20) link

• 반복자에 횟수 제한 기능 추가
• std::counted_iterator it{base_iter, 5}
• 범위 끝에는 std::default_sentinel 사용

  std::counted_iterator ci{it, 5};
while (ci != std::default_sentinel) {
 std::println("{}", *ci++);
}
  

• legacy 함수에 사용하려면 std::common_iterator<I, S> 사용
• sentinel_for concept으로 조건 검사 가능