STL Container
STL
Standard Template Library
타입 독립적인 자료구조와 알고리즘을 사용하는 일반화 프로그래밍 (gerneric programming) 을 구현하기 위해 개발된 c++ 라이브러리.
크게 컨테이너, 반복자, 알고리즘 3가지로 구성되어 있다.
Container
vertor
헤더파일 에 정의되어 있는 순차 컨테이너의 한 종류. 각각의 원소들이 선형으로 배열되어 있다.
벡터 컨테이너는 동적 배열로 구현. 보통의 배열처럼 벡터 컨테이너들도 각각의 원소들이 메모리 상에서 연속적으로 존재한다. 따라서 벡터 컨테이너의 원소를 참조할 때 반복자(iterator)를 이용해 순차적으로 참조할 수 있고, 처음 원소부터의 상대적인 거리를 이용해 접근할 수도 있다.
보통의 배열과의 차이점은? 벡터 컨테이너는 스스로 공간을 할당하고, 크기를 확장 또는 축소 할 수 있음.
- 각각의 원소를 원소의 index값으로 바로 참조 가능
- 원소들에 임의의 순서로 접근 가능
- 벡터 끝에 새로운 원소를 추가하거나 제거 가능
다른 표준 순차 컨테이너(deque, list)와의 차이점은? 벡터는 원소에 접근하는 시간이나 컨테이너의 끝에 새로운 원소를 삽입/삭제하는 것이 매우 효울적.
하지만 중간에 사입하는 작업은 상대적으로 느리다.
벡터 컨테이너는 내부적으로 공간을 관리하기 위해 두 개의 변수를 사용한다.
- size : vector::size() 함수로 얻을 수 있는 값. 현재 벡터에 보관되어 있는 원소의 개수 의미.
- capacity : vector::capacity() 함수로 얻을 수 있는 값. 벡터에 할당된 공간의 크기 의미.
size가 capacity를 초과하면 capacity만큼의 공간이 추가로 할당된다.
deque
vertor와 흡사하지만 메모리 상에서 연속적인 공간으로 할당된다고 보장할 수 없다.
list
헤더파일 에 정의된 순차 컴테이너의 한 종류. 원소들이 메모리 상에 선형으로 배열되어 있다.
리스트 컨테이너는 보통 이중 연결 리스트로 구현. 이중 연결 리스트를 사용하기 때문에 메모리 상 임의의 위치에 원소가 저장돼있더라도 이전 원소와 다음 원소로 추적해 참조할 수 있다.
stack
순차(시퀀스) 컨테이너가 아닌 컨테이너 어댑터의 한 종류(컨테이너는 아님). 간결함과 명료성을 위해 인터페이스를 제한한 순차 혹은 연관 컨테이너의 변형이다. 반복자를 지원하지 않아, STL 알고리즘에서는 사용할 수 없음.
Iterator
(iterator는 클래스임) 컨테이너의 원소를 순회하는 방법을 추상화한 객체들. 배열을 순차적으로 접근하고 싶을 때 사용한다
컨테이너에 저장되어 있는 모든 원소들을 전체적으로 접근할 때 사용하는, 일종의 포인터와 비슷한 객체라고 할 수 있음.
