[STL] 컨테이너, 반복자

[STL] STL

Standard Template Library

프로그램에 필요한 자료구조와 알고리즘을 템플릿으로 제공하는 라이브러리.

자료구조와 알고리즘은 서로 반복자라는 구성 요소를 통해 연결한다.

STL의 구성 요소

* 컨테이너 (Container) : 객체를 저장하는 객체로 컬렉션 혹은 자료구조라도 한다.

* 반복자 (Iterator) : 포인터와 비슷한 개념으로 컨테이너의 원소를 가리키고, 

가리키는 원소에 접근하여 다음 원소를 가리키게 하는 기능을 한다.

* 알고리즘 (Algorithm) : 정렬, 삭제, 검색, 연산 등을 해결하는 일반화된 방법을 제공하는 함수 템플릿이다.

* 함수 객체 (Function Object) : 함수처럼 동작하는 객체로 operator() 연산자를 오버로딩한 객체이다. 

컨테이너와 알고리즘 등에 클라이언트 정책을 반영하게 한다.

* 어댑터 (Adaptor) : 구성 요소의 인터페이스를 변경해 새로운 인터페이스를 갖는 구성요소로 변경한다. 

(새로운 구성요소처럼 보인다.)

* 할당기 (Allocator) : 컨테이너의 메모리 할당 정책을 캡슐화한 클래스 객체로 

모든 컨테이너는 자신만의 기본 할당기를 가지고 있다.

ㅁ 컨테이너

컨테이너는 같은 타입을 저장, 관리할 목적으로 만들어진 클래스이다.

컨테이너는 두가지 타입으로 나눌 수 있다. (총 7가지 컨테이너를 제공)

* 표준 시퀀스 컨테이터 (Standard sequence container) 

컨테이너 원소가 자신만의 삽입 위치(순서)를 가지는 컨테이너

-> vector, deque, list  : 선형적

* 표준 연관 컨테이너 (Standard associative container)

저장 원소가 삽입 순서와 다르게 특정 정렬 기준에 의해 자동 정렬되는 컨테이너 

-> set, multiset, map, multimap  : 비선형적

(string은 시퀀스 컨테이너의 일종이나 문자만을 저장하는 컨테이너로 표준 컨테이너에 해당되지 않는다.)

(근사 컨테이너)

컨테이너의 데이터를 저장하는 방식에 따라 두 가지로 나눌 수 있다.

* 배열 기반 컨테이너 : 데이터 여러 개가 하나의 메모리 단위에 저장

-> vector, deque

* 노드 기반 컨테이너 : 데이터 하나를 하나의 메모리 단위에 저장

-> list, set, multiset, map, multimap

ㅁ 반복자

반복자는 포인터와 비슷하게 동작한다.

반복자는 컨테이너에 저장된 원소를 순회하고 접근하는 일반화된 방법을 제공한다.

반복자는 컨테이너와 알고리즘이 하나로 동작하게 묶어주는 인터페이스 역할을 하여 반복자로 인해 알고리즘이 특정 컨테이너에 종속되지 않고 독립적이면서도 컨테이너와 결합하여 동작할 수 있게 해준다.

반복자는 컨테이너 내부의 원소를 가리키고 접근할 수 있어야 한다.

또한 반복자는 다음 원소로 이동하고 모든 원소를 순회할 수 있어야 한다.

STL의 모든 컨테이너는 자신만의 반복자를 제공한다.

멤버 함수 begin()과 end()는 순차열의 시작과 끝을 가리키는 반복자를 반환하는 함수이다.

순차열의 시작과 끝은 begin()과 end()인데, 여기서 end()는 마지막 원소의 다음을 가리킨다.

즉, [begin, end)인 반개구간이다.

또한 순차열의 한 원소를 가리키는 iterator가 있다면

그 구간은 [begin, iterator), [iterator, end)로 구간을 나눌 수 있다.

(또한 [p, q)구간에서 p와 q가 같은 곳을 보고 있다면 이는 순차열의 원소가 존재하지 않는 것이다.)

반복자는 ++연산자로 다음 원소로 이동할 수 있고, ==과 != 연산자로 begin, end와 비교할 수 있다.

 - begin()         : 컨테이너의 시작 원소를 가리키는 반복자를 반환

 - end()            : 컨테이너의 끝 표시 반복자를 반환 (끝 원소 다음)

 - ++iterator     : 반복자를 다음 원소를 가리키도록 이동

 - *iterator       : 반복자가 가리키는 원소(객체)를 반환 (역참조)

vector, deque는 임의 접근 반복자를 지원

 - iterator[i]      : iterator + i번째 원소에 접근

 - iterator += n : iterator를 n만큼 이동

 - iterator -= n  : iterator를 -n한 만큼 이동