STL

STL은 C++의 표준 라이브러리의 일부로, 컨테이너, 알고리즘, 반복자 등의 템플릿 기반 구성요소를 포함한다. STL을 활용하면 다양한 자료구조와 알고리즘을 직접 구현하지 않고도, 사용할 수 있다.

1. 컨테이너(Containers)

데이터를 담는 자료구조

1-1. 시퀀스 컨테이너(Sequence Containers)

데이터를 선형적인 순서로 저장하며, 요소의 삽입 순서가 유지된다.

Vector

동적 배열로 구현되었다.
특징
1. 연속된 메모리 공간
2. 랜덤 접근 : O(1)
3. 끝에 데이터 삽입/삭제 : O(1)
4. 중간에 데이터 삽입/삭제 : O(n)
참고 - [C/C++] vector

1-2. 연관 컨테이너(Associative Containers)

키(Key)를 바탕으로 데이터를 자동 정렬하여 저장하며, 빠른 검색을 목적으로 합니다.

• Map

  키(key)와 값(value)의 쌍으로 저장하며, 키를 기준으로 정렬한다.

특징
1. 키로 자동 정렬
2. 키 중복 불가
3. 검색/삽입/삭제 : O(log n)
참고 - [C/C++] map

1-3. 정렬되지 않은 연관 컨테이너 (Unordered Containers)

해시 테이블(Hash Table)을 사용하여 순서에 상관없이 매우 빠른 검색 속도를 제공한다.

특징
1. 정렬되지 않음
2. 검색/삽입/삭제 : O(1) 평균

2. 반복자(Iterators)

반복자는 컨테이너의 요소를 순회하고 접근하는 일반화된 포인터이다.
반복자의 장점은 다양한 컨테이너에 동일한 방식으로 접근이 되고 순회가 가능하다.

반복자의 종류

1. Input Iterator (입력 반복자)
   특징 : 읽기 전용 , 한 방향 이동 (++) , 한 번만 순회 가능
2. Output Iterator (출력 반복자)
   특징 : 쓰기 전용 , 한 방향 이동 , (++)대입 연산만 가능
3. Forward Iterator (전방 반복자)
   특징 : 읽기/쓰기 , 가능앞으로만 이동 , (++)여러 번 순회 가능
4. Bidirectional Iterator (양방향 반복자)
   특징 : 읽기/쓰기 가능 , 양방향 이동 (++, --) , list, set, map에서 사용
5. Random Access Iterator (임의 접근 반복자)
   특징:읽기/쓰기 가능 , 임의 위치 접근 ([], +, -, +=, -=) , 반복자 간 거리 계산 가능 , vector, deque, array에서 사용

참고 - [C/C++] Iterator(반복자)

3. 알고리즘(Algorithms)

알고리즘은 STL 컨테이너의 요소를 처리하는 템플릿 함수들의 모음이다.

참고 - [C/C++] STL Algorithm