[C++] 이터레이터와 STL

👨‍💻 개인 공부 기록용 블로그 입니다.
💡 틀린 내용이나 오타는 댓글, 메일로 제보해주시면 감사하겠습니다!! (__)

42 Cursus - Cpp Module을 진행하기 위해 정리했었던 C++98 기본 개념들로, C++11, C++14와 다른 내용이 있을 수 있습니다.
각 개념은 정리한 시간 순으로 배치되어 있으며, 한 포스트에 배치된 개념이 크게 관련이 없을 수 있습니다.

이터레이터 (Iterator)

💡 지시자, 반복자와 같이 번역하는 경우도 많이 보았는데, 어감이 이상하기도 하고, 본래의 의미를 잘 못살린다는 생각이 들어서 그냥 이터레이터로 적기로 했다. C++의 이터레이터에 대해서만 기술한다.

• 이터레이터 (Iterator) 는 C++의 다양한 구조에서 균일한 방식으로 작업할 수 있도록 도와주는 포인터의 일반화된 형태이다.

Input Iterator

• 컨테이너로부터 데이터를 순차적으로 읽기 위한 이터레이터
• ++it (이터레이터 증가연산), *it (이터레이터 참조), ==, !=(두 이터레이터가 같은지 비교 하는 연산) 등이 이에 속한다.
• 스트림으로부터 데이터를 읽거나, 범위에 대해 한 번만 수행하면 되는 연산에 쓰인다.

Output Iterator

• 데이터를 순차적으로 쓰는 출력 작업에 사용되는 이터레이터
• *it = something (쓰기 위한 이터레이터 참조), it++ (이터레이터 증가연산) 등이 이에 속한다.
• 스트림에 데이터를 쓰거나, 컨테이너 맨 뒤에 원소를 삽입하는 연산에 쓰인다.

Forward Iterator

• Input Iterator + Output Iterator
• 순차적인 데이터 읽기 쓰기 작업에 사용됨

Bidirectional Iterator

• Forward Iterator + 역방향 연산
• 양방향으로 데이터 읽기 쓰기가 가능함. → --it (이터레이터 감소연산) 가능
• 양방향 연결리스트와 같이 일정 범위 내 양방향 순회가 가능함
• list, set, map이 양방향 이터레이터를 지원함 → 이터레이터 끼리의 산술 연산(덧셈, 뺼셈)이 불가능함.

Random Access Iterator

• Bidirectional Iterator + 이터레이터에 대한 산술 연산
• 덧셈 뺄셈과 같은 산술 연산에 더불어, 상대적인 비교연산 (<, >, <=, >=) 가능
• 원소 랜덤 접근이 가능한 컨테이너(vector, array)는 모두 지원

Writing Custom Iterators

• 컨테이너 클래스 내부에 이터레이터 클래스를 추가적으로 정의 및 구현
• 구현하고자 하는 이터레이터의 카테고리를 결정한 후, 그에 맞는 연산자 오버로딩 구현 (*, ++, --, ==, != 등)
• 랜덤 접근 이터레이터의 경우에는 +, -, [] 연산도 구현해야 함.
• 필수 사항은 아니지만, begin(), end() 또한 구현하면 좋다.
• const_iterator, reverse_iterator, const_reverse_iterator 도 재구현한다.

STL (Standard Template Library)

• 표준 템플릿 라이브러리 STL (Standard Template Library) 은 템플릿을 통해 구현되어 프로그래머로 하여금 기본적인 자료구조들을 추가 구현없이 사용할 수 있게 만든 라이브러리
• 크게 세 종류 (컨테이너와 알고리즘, 이터레이터)로 구분된다.
  • 컨테이너 : 임의 타입의 객체 보관
  • 이터레이터 : 컨테이너에 보관된 원소에 접근
  • 알고리즘 : 이터레이터를 통한 일련의 작업 수행
• 이터레이터 같은 경우는 위에 서술. 컨테이너는 종류별로 구분하여 대표적인 것을 서술하고, 알고리즘은 자주 사용될 법 한 것만 따로 정리
• C++11 버전에서 유효한 것은 바탕색을 회색으로 처리함.

Containers

Sequence Container

• Vector : 연속적인 동적 배열
  • 배열의 크기와 관련된 메모리 관리를 사용자가 아닌 배열 스스로 관리
  • 연속적인 메모리 공간에 고정된 크기를 우선 할당한 뒤, 필요할 경우 추가 할당함.
  • C++에서는 메모리 할당/해제 연산이 비싼 축에 속하기 때문에, 파이썬 처럼 원소를 제거한 후 일부 메모리를 해제하는 연산은 이뤄지지 않고, 오직 소멸자가 호출될 때만 메모리를 해제함.
  • 연속적인 메모리를 사용하기 때문에 사용성에 있어서 효율적이지만, 덱과 비교하여 재할당이 자주 일어남
  • 끝단에서의 삽입 및 삭제와 원소 랜덤 접근은 \( O(1) \)에 이뤄지지만, 특정 위치에서의 삽입 및 삭제는 \( O(N) \)이 소요됨
  • vector의 경우, 메모리 공간을 최적화하기 위하여 템플릿 특수화를 통해 구현됨.
  • 자주 쓰이는 멤버 함수 : push_back, pop_back, insert, erase, size, capacity, reserve
• Deque : 양 끝에서 삽입/제거가 가능한 큐
  • 벡터와 비슷하지만, 양 끝단에서의 삽입/제거 연산에 좀 더 최적화된 자료구조
  • 벡터와 같이 \( O(1) \)에 랜덤 접근이 가능하며, 같은 시간에 양 끝단에서의 삽입/제거가 가능함.
  • chunks 단위로 메모리를 할당하여 관리하기 때문에, 벡터보다는 일반적으로 메모리를 더 사용함.
  • 자주 쓰이는 멤버 함수 : push_back, push_front, pop_back, pop_front, insert, erase, size
• List : 양방향 연결 리스트
  • 어디서든 삽입/제거 연산을 효율적으로 수행하기 위한 자료구조
  • 인덱스를 통한 원소 랜덤 접근이 불가능하다. 반드시 순차적으로 접근해야만 한다.
  • 재할당 및 복사 없이 크기를 동적으로 조절할 수 있다.
  • 원소와 이전 원소에 대한 포인터, 다음 원소에 대한 포인터를 함께 저장하기 때문에, 어디서든 삽입 제거가 효율적이지만 일반적으로 더 많은 메모리를 사용한다.
  • 자주 쓰이는 멤버함수 : push_back, push_front, pop_back, pop_front, insert, erase, size

• Array
  • 벡터와 달리, 컴파일 타임에 크기가 고정되는 배열
  • 힙 메모리가 아닌 스택에 할당되기 때문에 빠르며, \( O(1) \)에 랜덤 접근이 가능하다.
  • 자주 쓰이는 멤버함수 : begin, end, size, fill, swap
• Forward_list
  • list와 달리, 단방향 연결 리스트를 통해 구현됨
  • 어디서든 삽입/제거 연산을 효율적으로 수행할 수 있음.
  • list의 특징을 대부분 가지지만, 양방향 이터레이터를 지원하지 않으며, 더 좋은 메모리 효율성을 가짐.
  • 자주 쓰이는 멤버변수 : insert_after, erase_after, push_front, pop_front, push_back, pop_back

Associative Container

• Set : key로 정렬되는 유니크한 key들의 집합
  • 원소들이 항상 key를 기준으로 오름차순 정렬되어 있음
  • 중복되는 원소들을 담을 수 없으며, 크기가 동적으로 관리됨.
  • \( O(logN) \)에 삽입/삭제/탐색이 가능함.
  • 자주 사용되는 멤버함수 : insert, erase, find, count, begin, end, size
• Map : 유니크한 key로 정렬되는 key-value쌍의 집합
  • 원소들이 key-value 쌍의 형태를 띄고 있으며, 항상 key에 대해 오름차순 정렬됨
  • 중복되는 key를 담을 수 없으며, 크기가 동적으로 관리됨.
  • \( O(logN) \)에 삽입/삭제/탐색이 가능함.
  • 자주 사용되는 멤버함수 : insert, erase, find, count, begin, end, size
• Mulitset : set과 유사하지만, 다중 key를 허용함
• Mulitmap : map과 유사하지만, 다중 key-value쌍(중복되는 key)을 허용함

Unordered Associative Container

• 아래는 모두 C++11에서 소개된 자료구조로, 연관 컨테이너와 비슷하지만 내부적으로 정렬을 수행하지 않음.
• 그러나 해시테이블을 통해 빠른 접근이 가능하도록 함.

• Unordered_set
  • set과 비슷한 특징을 갖지만, 정렬을 수행하지 않고 해싱(hashing)을 통해 원소를 관리함.
  • 원소 삽입/접근/삭제에 대해 평균 \( O(1) \)의 복잡도로 수행 가능함. 해싱의 특성 상, 최악의 경우 \( O(N) \)까지 소요될 수 있음.
  • 자주 쓰이는 멤버 함수 : insert, erase, find, begin, end, size
• Unordered_map
  • map과 비슷한 특징을 갖지만, 정렬을 수행하지 않고 해싱(hashing)을 통해 원소를 관리함.
  • 원소 삽입/접근/삭제에 대해 평균 \( O(1) \)의 복잡도로 수행 가능함. 해싱의 특성 상, 최악의 경우 \( O(N) \)까지 소요될 수 있음.
  • 자주 쓰이는 멤버 함수 : insert, erase, find, begin, end, size
• Unordered_multiset : Unordered_set과 유사하지만, 다중 key를 허용함
• Unordered_multimap : Unordered_map과 유사하지만, 다중 key-value쌍(중복되는 key)을 허용함

Container Adapter

• Sequential 컨테이너에 대해 다른 인터페이스를 제공. 데이터 구조를 가지지 않고, 다른 컨테이너를 통해 원소를 저장함.
• Stack : 컨테이너가 스택 구조를 띄도록 조정
  • LIFO(Last In, First Out)구조를 띔.
  • 최상단에서만 접근/추가/삭제가 가능하며, 기본적으로 deque를 사용함. 물론 list나 vector를 사용하는 것도 가능함.
  • 자주 사용되는 멤버함수 : push, pop, top, size, empty
• Queue : 컨테이너가 큐 구조를 띄도록 조정
  • FIFO(First In, First Out)구조를 띔.
  • 양 끝단에서만 접근/추가/삭제가 가능하며, 기본적으로 deque를 사용함. list또한 사용 가능함.
  • 자주 사용되는 멤버함수 : push, pop, front, back, size, empty
• Priority_queue : 컨테이너가 우선순위 큐 구조를 띄도록 조정
  • 원소들이 삽입 순서가 아닌 우선순위에 따라 정렬되어 있음.
  • 가장 우선순위가 높은 원소에만 접근이 가능함.
  • 기본적으로 vector를 사용하며, deque또한 사용 가능함.
  • 우선순위 설정을 위한 비교 함수 사용자화를 할 수 있음
  • 자주 쓰이는 멤버함수 : push, pop, top, size, empty

Algorithms

• 컨테이너의 이터레이터를 인자로 받아서 처리하며, 원소 검색, 정렬, 계산, 조작 등 다양한 목적을 위한 다양한 함수가 포함된 알고리즘 라이브러리

Non-modifying Sequence Operations

• 컨테이너의 원소들을 변경하지 않는 연산들
• **find(first, last, value)** : [first, last)에 대해 value를 탐색
• **count(first, last, value)** : [first, last)에 대해 value의 개수를 세는 함수
• **mismatch(first1, last1, first2)** : [first1, last1) 과 [first2, first2 + (last1 - first1)) 두 범위를 비교하여 첫 번째로 달라지는 원소 쌍의 이터레이터를 반환함
• **equal(first1, last1, first2)** : [first1, last1) 과 [first2, first2 + (last1 - first1)) 두 범위가 같은지 비교
• **adjacent_find(first, last)** : [first, last) 인접한 두 원소가 같은 이터레이터를 반환
• **search(first, last, s_first, s_last)** : [first, last) 범위 내에서, 서브시퀀스 [s_first, s_last)의 첫 등장을 탐색

Modifying Sequence Operations

• 컨테이너의 원소들을 직접적으로 변경하게 되는 연산들
• copy(first, last, result): [first, last) 범위의 원소들을 result로 시작하는 다른 범위로 복사
• replace(first, last, old_value, new_value): [first, last) 범위에 존재하는 원소들에 대해, old_value를 new_value로 바꿈
• remove(first, last, value):[first, last)범위에서value 를 찾아 삭제하고, 뒤 원소들을 앞으로 당김
• swap_ranges(first1, last1, first2): [first1, last1) 범위 내 원소들을 first2로 시작하는 다른 범위와 swap
• reverse(first, last): [first, last)범위의 원소들을 뒤집음

Sorting Operations

• 컨테이너의 원소들을 정렬하는데에 쓰이는 연산들
• sort(first, last): [first, last) 범위의 원소들을 오름차순으로 정렬
• stable_sort(first, last): [first, last) 범위의 원소들을 오름차순으로 안정정렬(같은 원소에 대해 순서의 무결성 보장)
• partial_sort(first, middle, last): [first, middle) 범위의 원소들을 오름차순 정렬
• nth_element(first, nth, last): nth 원소를 고정한채로, [first, nth), (nth, last) 범위를 부분정렬함.

Binary Search Operations

• 정렬된 컨테이너의 원소들을 효율적으로 검색하기 위한 이진 탐색 연산들
• lower_bound(first, last, value): [first, last) 범위의 원소들을 탐색하여, value보다 크거나 같은 첫번째 원소를 반환함.
• upper_bound(first, last, value): [first, last) 범위의 원소들을 탐색하여, value보다 큰 첫번째 원소를 반환함.
• equal_range(first, last, value): (lower_bound, upperbound)의 std::pair객체를 반환함.
• binary_search(first, last, value): 범위 내 특정 원소가 존재하는지 판단함.

Set Operations

• 정렬된 컨테이너의 원소들에 대한 집합 연산들
• set_union(first1, last1, first2, last2, result): 각 두 범위에 해당하는 집합의 합집합을 result에 구축함.
• set_intersection(first1, last1, first2, last2, result): 각 두 범위에 해당하는 집합의 교집합을 result에 구축함.
• set_difference(first1, last1, first2, last2, result): 각 두 범위에 해당하는 집합의 차집합을 result에 구축함.
• set_symmetric_difference(first1, last1, first2, last2, result): 각 두 범위에 해당하는 집합의 대칭차집합(\( (A-B) + (B - A) = (A \cup B) - (A \cap B) \) )을 result에 구축함.

Heap Operations

• 최대 힙을 만들고 조작하기 위한 연산들
• make_heap(first, last): [first, last) 범위를 힙 구조를 띄도록 재정렬함.
• push_heap(first, last): [first, last-1) 범위로 정의된 힙에 원소를 삽입함.
• pop_heap(first, last): 힙 컨테이너에서 최댓값(루트노드)을 맨 마지막 자식노드와 교환하고, 루트 노드를 재정렬함. (pop_back()은 사용자가 직접 호출해야함.)
• sort_heap(first, last): [first, last) 범위의 힙 컨테이너를 재정렬함

Min/Max Operations

• 최댓값 최솟값을 찾기 위한 연산들
• min(a, b): a와 b중 작은 것을 반환함.
• max(a, b): a와 b중 큰 것을 반환함.
• min_element(first, last): [first, last)범위 중 가장 작은 원소를 반환함.
• max_element(first, last): [first, last)범위 중 가장 큰 원소를 반환함.

Numeric Operations

• 수학적인 연산들
• accumulate(first, last, init): [first, last)범위의 누적합을 계산. (누적합 = init + 범위 내 모든 원소)
• inner_product(first1, last1, first2, init): [first, last)범위와 first2로 시작하는 범위에 대해 내적을 계산. (내적 = init + 두 범위에 대한 순차적인 곱의 누적합)
• partial_sum(first, last, d_first): [first, last)범위에 대한 부분합을 순차적으로 계산하여 d_first 로 시작하는 범위에 씀. ([0] = [0], [1] = [0:1], [2] = [0:2] … )
• adjacent_difference(first, last, result): [first, last) 범위에서, 인접 원소에 대한 차이를 result 로 시작하는 범위에 씀. ([0] = [0], [1] = [1] - [0], [2] = [2] - [1] … )

Reference

CPP 레퍼런스 (이터레이터)

CPP 레퍼런스 (std::iterator)

CPP 레퍼런스 (컨테이너)

CPP 레퍼런스 (알고리즘)