#36. STL (Standard Template Library) 정의

#STL (Standard Template Library)

STL은 표준에 등록된 템플릿들의 모음이다.

STL은 컨테이너, 알고리즘, 함수 객체, 반복자 로 구성되어 있다.

 

 

컨테이너는 데이터를 저장하는 객체이다.

이 컨테이너는

배열기반의 vector

노드기반의 list, map

의 종류가 있다.

 

배열 기반은 연속된 메모리를 사용하여 저장한다.

노드 기반은 비 연속된 메모리에 저장을 하지만 포인터로 서로 연결해 두는 것이다.

 

여기서 vector와 list는 표준 시퀀스 컨테이너로, 선형적인 구조를 가지고 있다.

map은 표준 연관 컨테이너로, 비선형적인 구조를 가지고 있다.

구분	Vector	List	Map
컨테이너의 종류	동적배열 기반	노드 기반	트리 기반
메모리 저장 방식	배열	노드	노드
원소 배치방법	표준 시퀀스 컨테이너(선형)	표준 시퀀스 컨테이너(선형)	표준 연관 컨테이너(비선형)

 

 

알고리즘이란

->컨테이너 내에서 정렬, 삭제, 탐색 등을 위한 일반화된 방법을 제공하는 함수 템플릿이다.

대부분의 알고리즘은 전역에 정의되어 있으며, 자주 사용하는 알고리즘은 algorithm 파일에 있다.

#include <algorithm> 을 통해 사용 할 수 있다.

 

 

함수 객체는 함수 호출 연산자를 연산자 오버로딩하여 사용하는 것을 뜻한다.

 

 

반복자는 객체이다.

객체이지만 포인터를 사용 하듯이 사용할 수 있다.

 

---

구분	Vector	List	Map
특징	1. 동적배열 기반으로 인덱스 접근이 가능 -> 탐색에 좋다. 2. 맨 끝에서 부터 삽입 및 삭제 해 나간다 (맨 앞에서는 불가능 하다) 3. 맨 뒤 삭제 및 삽입은 자유롭기 때문에 상수 시간이 소요된다. 하지만, 중간 삽입 및 삭제는 삭제후 뒤의 자료를 앞으로 이동시켜야 하므로 선형 시간이 소요된다. 4. 동적 배열 기반으로 배열 크기가 넘어 설 경우, 재할당 및 기존 자료들의 복사가 필요하므로 삽입 삭제 보단 탐색에서 주로 사용된다.	1.  노드기반으로 더블링크드 리스트로 구현되어 있어, 앞뒤 노드의 삽입 및 삭제가 가능하다. 2. 각 노드는 연속된 메모리에 나열된 것이 아니라 비 연속적인 메모리 공간에 저장되어 있지만 포인터로 각 노드를 연결하여 연속된 것 처럼 보인다. 3. 인덱스 접근이 불가하므로 탐색이 불리하다. 4. 탐색시 순차 접근을 통해 원하는 원소가 나올때까지 순회해야 하므로 선형시간이 소요된다. 5. 중간삽입 및 삭제시에는 포인터 연결을 해제 및 재 연결만 하면 되므로 상수시간이 소요된다. 6. 한정된 메모리가 아니므로 원하는 만큼 런타임 시에도 노드의 추가가 가능	1. 원소들은 key값와 value값으로 한 쌍을 이루며, 원소들은 key값에 따라 자동정렬 된다. 2. key값에 따라 정렬되기 때문에 반복자를 통한 탐색이 가능하다. 3. 따라서 노드 기반이지만 key값을 통해 임의 접근이 가능하다.