[C++] STL(Standard Template Library)이란?

STL이란?

표준 C++ 라이브러리(Standard Template Library)로

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

 

C++은 template라는 걸 통해서 한 가지 타입에 특정되지 않고, 여러 타입에 일반적인 문법을 사용할 수 있게 된 데다 STL을 통해서 타입 / 컨테이너 / 알고리즘을 분리해 하나씩만 구현해도 여러 조합의 경우를 포괄할 수 있는 언어가 되었다.

 

STL = 컨테이너 + 반복자 + 알고리즘

컨테이너(Container)

특정한 타입의 원소들을 담아 다루기 위한 객체

 

Vector 

 - 동적 배열이므로 배열의 크기를 변경할 수 있다.

 - 임의 접근이 가능하며, 뒤에서의 삽입이 빠르다.

 - 삽입, 삭제, 탐색 O(n), 임의 원소 접근 O(1) 보장

list

 - 연결리스트이므로 데이터를 순차적으로 접근하고 관리할 때 유용하다.

 - 위치에 상관없이 삽입과 삭제가 빠르다.

 - 삽입, 삭제 O(1), 탐색, 임의 원소 접근 O(n) 보장

deque

 - 덱, 데크라고 한다.

 - 임의 접근이 가능하며 앞과 뒤에서의 삽입이 빠르다.

 - 삽입, 삭제, 탐색 O(1), 임의 원소 접근 O(n) 보장

map

 - 특정 키(key)로 데이터를 접근하고 관리할 수 있다.

 - 키로 값에 접근하며 삽입과 삭제가 빠르다.

 - 삽입, 삭제, 탐색 모두 O(log n) 보장

set

 - 원소들을 순서대로 관리하며 소속 검사와 삽입, 삭제가 빠르다.

 - 중복된 원소를 허용하지 않는다. (map과 set의 차이점, set은 값이 곧 키가 됩니다.)

 - 삽입, 삭제, 탐색 모두 O(log n) 보장

stack

 - top에서만 삽입과 삭제가 가능하다.

 - LIFO(Last In First Out) 방식으로 데이터를 삽입, 삭제 한다.

 - 삽입, 삭제 O(1) 보장

queue

 - 삽입은 뒤쪽에서, 삭제는 앞쪽에서 수행한다.

 - FIFO(First In First Out) 방식으로 데이터를 삽입, 삭제한다.

 - 삽입, 삭제 O(1) 보장

 

더 자세하게 보면 아래와 같이 분리가 된다.

 

• 순차 컨테이너

  • 배열(array)

  • 동적 배열(vector)

  • 양방향 큐(deque)

  • 단방향 리스트(forward_list)

  • 양방향 리스트(list)

• 연관 컨테이너

  • 정렬된 유일 key 집합(set)

  • 정렬된 유일 key와 value의 집합(map) - 별명은 dictionary다. 사전처럼 쓰면 좋다.

  • 정렬된 중복허용 key 집합(multiset)

  • 정렬된 중복허용 key와 value의 집합(multimap)

• 비정렬 연관 컨테이너(ordered는 sorted와 같은 비슷한 의미다.)

  • 유일 key 해시(unordered set)

  • 유일 key와 value의 해시(unordered map)

  • 중복허용 key 해시(unordered multiset)

  • 중복허용 key와 value의 해시(unordered multimap)

• 그밖에.

  • 스택(stack)

  • 큐(queue)

  • 우선순위큐(priority_queue)

 

반복자(iterator)

컨테이너에서 보유하는 내부 데이터를 순회할수 있는 객체이고, 컨테이너의 특정 위치를 나타낸다.

요즘 객체지향 언어에서는 딱히 생각하지 않아도 될만큼 간편하게 자료구조가 제공되지만,

C++에서는 아직 자료를 포인터 단위로 관리하기 때문에 해당 자료의 위치에서 데이터에 접근하고 사용하기 위해서는 그 위치에 저장된 자료구조를 읽는데 필요한 읽기 전용 '도구'가 필요하다.

바로 반복자가 그 역할을 한다.

 

출처 : https://wiserloner.tistory.com/435

알고리즘(algorithm)

컨테이너 객체의 원소를 다루기 위한 여러 알고리즘으로 검색, 정렬, 수정 등의 역할을 수행한다.

 

binary_search

 - 정렬되어 있는 범위 내의 원소에서 이진 검색을 수행한다.

find

 - 범위 내에서 특정 값을 갖는 원소를 검색한다.

for_each

 - 주어진 범위 내에서 각 원소에 대해 함수 객체를 적용한다.

max

 - 두 객체 중 큰 값을 구한다.

min

 - 두 객체 중 작은 값을 구한다.

remove

 - 범위 내에서 특정 값을 갖는 원소를 제거한다.

replace

 - 범위 내에서 특정 값을 갖는 원소를 찾아 값을 변경한다.

sort

 - 범위 내의 값을 오름차순으로 정렬한다.

 

 

 

출처: https://wonjayk.tistory.com/208 [배고파서 까먹고 만든 블로그]

출처: https://boycoding.tistory.com/124 [소년코딩]