STL

STL이란?

C++에 내장된 템플릿 기반의 라이브러리이며, 크게 컨테이너, 반복자, 그리고 알고리즘으로 구성되어 있다.

• 컨테이너(Container) : 데이터를 저장, 관리하는 구조체(자료구조)들의 집합.
• 반복자(Iterator) : 컨테이너 내 데이터를 순회(Navigation)할 수 있도록 도와주는 일종의 '포인터' 역할
• 알고리즘 (Algorithm) : 정렬, 탐색, 삽입, 삭제 등과 같은 로직을 매우 효율적이고 제네릭하게 제공.

 

Vector

• 동적 배열로 구현된 컨테이너
• 연속적인 메모리 블록을 사용해서 랜덤 접근이 빠른 편
• 원소를 추가/삭제 할 때 마지막 원소에 대해 가장 효율적
• 중간에 삽입/삭제 시 비효율적.
• 주요 함수
  • push_back(value) : 맨 뒤에 원소 추가
  • pop_back() : 맨 뒤 원소 제거
  • size() : 원소 개수 반환
  • capity() : 현재 할당된 메모리 크기
    • 메모리 크기가 증가할 수록 재할당과 복사가 발생해서 reserve()로 미리 공간 확보도 가능.
  • at(index) : 지정된 인덱스의 원소 반환 (범위 초과 시 예외 발생)
  • front() : 첫 번째 원소 반환
  • back() : 마지막 원소 반환
  • clear() : 모든 원소 제거
  • insert(iterator, value) : 지정된 위치에 원소 삽입
  • erase(iterator) : 지정된 위치의 원소 제거
  • data() : 내부 배열 포인터 반환

List

• 이중 링크드 리스트로 구현된 컨테이너
• 앞/뒤로 자유롭게 탐색이 되고 삭제가 매우 효율적
• 메모리가 연속적이지 않으며, 랜덤 접근은 느리다.
• 중간 삽입 / 삭제가 매우 효율적
• 순차적 데이터 추가/삭제 적합
• 주요 함수
  • push_back(value) : 맨 뒤에 원소 추가
  • push_front(value) : 맨 앞에 원소 추가
  • pop_back() : 맨 뒤 원소 제거
  • pop_front() : 맨 앞 원소 제거
  • insert(iterator, value) : 지정된 위치에 원소 삽입
  • erase(iterator) : 지정된 위치의 원소 제거

Deque

• 양방향으로 동적 배열처럼 동작하는 컨테이너
• 임의 접근이 가능하며, 양쪽 끝에서의 삽입/삭제가 빠르다
• 중간 삽입/삭제는 비효율적
• 스택이나 큐와 같은 동작이 필요한 경우 유용

그래서 무엇을 많이 사용할까?

중간 삽입 삭제가 자주 일어나는 경우 -> list 추천

양쪽 끝에서 추가 / 삭제를 빈번하게 처리 -> deque 추천

시간 복잡도로 접근하면? -> vector를 추천

 

Map

• 키(key)와 값(value)을 한 쌍으로 묶어서 관리
• 키는 유일해야 하며, 검색, 삽입, 삭제가 평균
• 키는 자동으로 정렬이 가능하다.
• 내부적으로 레드 - 블랙 트리로 구현
• 주요 함수
  • insert(pair) : 키-값 쌍 삽입
  • erase(key) : 키로 요소 제거
  • find(key) : 키로 요소 검색 (iterator 반환)
    • key가 있으면 해당 key의 iterator 반환하나 없으면 end() 리턴.
  • operator[key] : 키로 값에 접근 또는 삽입
  • size() : 요소 개수 반환

Set

• 중복되지 않는 유일한 값을 저장
• 요소는 자동으로 정렬
• 내부적으로 map과 동일하게 레드- 블랙 트리 구현
• 주요 함수
  • insert(value) : 요소 추가
  • erase(value) : 요소 제거
  • find(value) : 요소 검색
  • size() : 요소 개수 반환
  • lower_bound(value) : 지정된 값 이상의 첫 번째 요소를 반환
  • upper_bound(value) : 지정된 값보다 큰 첫 번째 요소 반환

multimap

• 같은 키를 중복해서 저장할 수 있는 map
• 하나의 키 -> 여러 개의 value가 들어갈 수 있다.
• 주요 함수
  • map과 동일하게 삽입, 제거, 검색
  • equal_range(key) : 동일한 키의 요소 범위를 반환

multiset

• 동일 값(키) 중복을 허용하는 set
• 주요 함수
  • 요소 추가, 요소 제거, 요소 검색은 set과 동일

Sort

• 정렬 알고리즘.
• 기본 정렬 방식은 오름차순이다.
• sort(v.begin(), b.end(), greater<>()) 은 내림차순을 구현한 것이다.
• 정렬하고 싶은 함수의 첫번째 값과, 마지막 값, 그리고 어떻게 정렬하고 싶은지 함수를 넣으면 된다.

nth_element

• K번째 값을 찾는 알고리즘
• n번째로 작은 원소를 배열의 n번째 위치로 보낸 뒤, 그 왼쪽은 n번째보다 작은 원소들, 오른쪽은 n번째보다 큰 원소들로 반 정렬을 해준다.