2. 훑어보기

1. 맛보기

   다음은 가장 많이 사용되는 컨테이너 vector와 vector의 이터레이터를 통한 값의 접근, 이터레이터(iterator)를 사용하는 정렬 알고리즘 sort()에 대한 간단한 예시 코드이다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	vector<int> v1;         // int를 보관하는 vector 컨테이너 생성

	v1.push_back(3);        // 컨테이너에 원소 삽입
	v1.push_back(1);        // 3 1
	v1.push_back(9);        // 3 1 9
	v1.push_back(4);        // 3 1 9 4
	v1.push_back(5);        // 3 1 9 4 5

	// []연산자를 통한 원소 접근
	v1[2] = 8;						// 9 -> 8
	for (size_t i = 0; i < v1.size(); i++) {
		cout << v1[i] << ' ';		// 3 1 8 4 5
	}
	cout << endl;
	

	// 이터레이터를 통한 원소 접근
	vector<int>::iterator vIter;	// vector<int>의 이터레이터1
	vIter = v1.begin() + 3;			// 3번째 원소를 가리키는 이터레이터 
	*vIter = 7;						// 4 -> 7

	// v1의 시작점에서 마지막까지 순회
	for (auto iter = v1.begin(); iter != v1.end(); iter++) {
		cout << (*iter) << ' ';		// 3 1 8 7 5
	}
	cout << endl;


	// 정렬 알고리즘 (오름차순)
	sort(v1.begin(), v1.end());


	// 범위 기반 for loop
	for (auto& v : v1) {
		cout << v << ' ';			// 1 3 5 7 8
	}
	return 0;
}

2. Containers

   컨테이너란 유명한 자료구조와 이를 처리하는 연산을 쉽게 구현할 수 있도록 미리 만들어서 제공하는 컬렉션 객체다. 컨테이너에서 제공하는 메서드와 이터레이터를 통해서 원하는 값을 삽입, 접근, 수정, 삭제할 수 있으며, 각 컨테이너 내부의 원소들은 컨테이너의 종류에 따라 다양한 방법으로 보관된다. 위 예제의 vector가 대표적인 컨테이너이다.

보관할 수 있는 데이터 타입

   컨테이너는 템플릿을 사용해 자료구조에 보관될 타입을 설정할 수 있다. 일반적으로 컨테이너에 보관할 수 있는 데이터 타입은 복사가 가능한 모든 데이터 타입이다. set과 같은 일부 컨테이너는 데이터 타입의 추가적인 연산을 요구할 수 있다. 한 번 정해진 타입을 바꿀 수는 없다. 따라서, 하나의 컨테이너에 다른 여러 타입을 동시에 사용할 수는 없다.

vector<int> v1;             // int형 vector 컨테이너 생성
vector<string> v2;          // string형 vector 컨테이너
vector<unique_ptr<int>> v3; // 포인터를 저장하는 컨테이너

v1.push_back(10);           // (O) int형 컨테이너에 int 값 삽입 메서드
v1.push_back("hello~~");    // (X) int형 컨테이너에 string형 삽입 불가능

종류

   컨테이너는 구조에 따라서 크게 3가지로 분류할 수 있으며, 그 외에 컨테이너를 활용해 추가적인 자료구조를 구현한 Adapters가 존재한다.

• Sequence Container
  • 삽입된 순서가 유지되며, 이를 순서대로(순차적으로) 접근할 수 있는 컨테이너
  • array - 정적 배열 (유일한 정적 컨테이너)
  • vector - 동적 배열
  • deque - 이중 큐 (스택 + 큐)
  • list - 이중 연결리스트
  • forward_list - 단일 연결 리스트
• Associative Containers
  • 이진 탐색 트리로 구현되어 정해진 우선순위에 의해 정렬된 상태를 유지하는 컨테이너
  • set - 집합
  • multiset - 중복을 포함하는 집합
  • map - 맵 (딕셔너리)
  • multimap - 중복을 포함하는 맵
• Unordered Associative Containers
  • hash table로 구현되어 우선순위가 없지만 그 외에는 Associative 컨테이너와 같은 연산을 제공하는 컨테이너
  • unordered_set - 해시 집합
  • unordered_multiset - 해시 집합 (중복을 포함)
  • unordered_map - 해시 맵
  • unordered_multimap - 해시 맵 (중복을 포함)
• Container Adapters
  • 컨테이너를 활용해 구현한 추가적인 자료구조
  • stack - 스택
  • queue - 큐
  • priority_queue - 우선순위 큐

메서드

   각 컨테이너에서 제공하는 메서드는 거의 비슷한 역할과 이름을 가졌다. 이를 살펴보고 세부적인 컨테이너 각각의 메서드를 공부하는 것이 전반적으로 이해하기 쉽다. 각 메서드는 역할에 따라 분류할 수 있는데, 특정 컨테이너에서만 존재하는 메서드를 제외하면 대략 5개 정도로 분류할 수 있다.

• Iterators
  • 컨테이너 내부 요소에 접근할 수 있는 이터레이터를 반환하는 메서드로 보통 시작과 끝의 다음 이터레이터를 반환

• Element access
  • 원소 접근을 위한 메서드 (연산자 포함)

• Capacity
  • 크기와 할당 용량과 관련된 메서드

• Modifiers
  • 원소 추가/삭제에 관련된 메서드

• Lookup
  • (association containers에서) 원소 탐색과 관련된 메서드

3. Iterators

   이터레이터는 자료구조를 공통된 방법으로 접근하는 일종의 약속이다. 일반화된 포인터 오브젝트라고 생각하면 된다. 따라서, 대부분의 연산이 포인터 연산과 유사하다.

   <algorithm>은 자료구조를 접근하기 위해 이터레이터만을 사용한다. 이터레이터라는 공통된 자료 접근 인터페이스는 이터레이터를 구현한 모든 자료구조는 <algorithm>을 사용할 수 있도록 알고리즘과 자료구조간의 의존성을 제거한다. 모든 컨테이너는 이터레이터 형태의 인터페이스를 제공한다.

4. Algorithm

   <algorithm>은 탐색, 정렬, 카운팅과 같은 범용적으로 많이 사용하는 알고리즘들을 사용하기 쉽도록 미리 구현한 함수들을 말한다. 이터레이터를 사용해 어떤 데이터 타입이든 상관 없이 범용적으로 사용할 수 있도록 만들어졌다. 해당 함수들을 사용하면, JS나 java stream처럼 선언형으로 프로그래밍하는 느낌을 받을 수 있다.
 

제공되는 알고리즘 종류

• 원본을 수정하지 않는 순차 연산
  • 탐색
  • 조건 검색
  • 카운팅
• 원본을 수정하는 순차 연산
  • 복사 및 이동
  • 채우기
  • 회전(뒤집기)
  • 중복 제거
  • 자리 변경
  • 쉬프트
  • 변형
• 분할과 합치기(merge)
• 정렬
• 이진 탐색
• 집합 연산
• 힙 연산
• 최대/최소와 자르기
• 비교
• 순열과 조합
• 그 외 <numeric> 헤더 함수들