STL이란?
STL은 C++에 내장된 템플릿 기반의 라이브러리이며, 크게 컨테이너, 반복자(Iterator), 그리고 알고리즘으로 구성되어 있다!
- 컨테이너(Container): 데이터를 저장·관리하는 구조체(자료구조)들의 집합
- 반복자(Iterator): 컨테이너 내 데이터를 순회(Navigation)할 수 있도록 도와주는 일종의 '포인터' 역할
- 알고리즘(Algorithm): 정렬, 탐색, 삽입, 삭제 등과 같은 로직을 매우 효율적이고 제네릭하게 제공
컨테이너
- vector ****동적 배열
- 동적 배열로 구현된 컨테이너이다
- 연속적인 메모리 블록을 사용해서 랜덤 접근이 빠른 편이다.
- 원소를 추가/삭제할 때 마지막 원소에 대해 가장 효율적이다다.
- 중간에 삽입/삭제 시 비효율적이다. → 데이터 이동 발생!
- 주요 함수
push_back(value): 맨 뒤에 원소 추가pop_back(): 맨 뒤 원소 제거size(): 원소 개수 반환capacity(): 현재 할당된 메모리 크기- 다만, 이게 증가할 수록 재할당과 복사가 발생해서
reserve()로 미리 공간 확보도 가능
- 다만, 이게 증가할 수록 재할당과 복사가 발생해서
at(index): 지정된 인덱스의 원소 반환 (범위 초과 시 예외 발생)front(): 첫 번째 원소 반환back(): 마지막 원소 반환clear(): 모든 원소 제거insert(iterator, value): 지정된 위치에 원소 삽입erase(iterator): 지정된 위치의 원소 제거data(): 내부 배열 포인터 반환
벡터에 대해서는 STL 기초에서 더 자세하게 다뤘으니 거기서 확인하자.
- List 이중 링크드 리스트
- 이중 링크드 리스트(링크드 리스트가 2개!)로 구현된 컨테이너이다.
- 이중 링크드 리스트는 앞/뒤로 자유롭게 탐색이 되고 삭제가 매우 효율적!
단일 연결 리스트: 1 -> 2 -> 3 -> 4 : 3을 삭제하려면 2까지 이동해서 2의 링크를 4로 바꿔야 했다. 이중 연결 리스트: 1 <-> 2 <-> 3 <-> 4 : 3을 삭제할 때, 3의 이전(prev)과 다음(next)을 연결만 하면 됨 2 <-> 4
- 이중 링크드 리스트는 앞/뒤로 자유롭게 탐색이 되고 삭제가 매우 효율적!
- 메모리가 연속적이지 않으며 랜덤 접근은 느리다.
- 중간 삽입/삭제가 매우 효율적이다.
- 순차적 데이터 추가/삭제에 적합하다.
- 주요 함수
push_back(value): 맨 뒤에 원소 추가push_front(value): 맨 앞에 원소 추가pop_back(): 맨 뒤 원소 제거pop_front(): 맨 앞 원소 제거insert(iterator, value): 지정된 위치에 원소 삽입erase(iterator): 지정된 위치의 원소 제거
- 이중 링크드 리스트(링크드 리스트가 2개!)로 구현된 컨테이너이다.
#include <iostream>
#include <list>
int main() {
std::list<int> lst;
// 원소 추가
lst.push_back(30);
lst.push_back(31);
lst.push_front(32);
for (int elem : lst) {
std::cout << elem << " "; // 32 30 31
}
std::cout << std::endl;
// 중간에 원소 삽입
auto it = lst.begin(); // begin은 head, rbegin은 tail처럼 동작!
++it; // 두 번째 위치로 이동
lst.insert(it, 15);
for (int elem : lst) {
std::cout << elem << " "; // 32 15 30 31
}
std::cout << std::endl;
}- Deque (데크라고 발음)
- 양방향으로 동적 배열처럼 동작하는 컨테이너이다.
- 임의 접근이 가능하며, 양쪽 끝에서의 삽입/삭제가 빠르니다.
- 중간 삽입/삭제는 비효율적이다.
- 스택이나 큐와 같은 동작이 필요한 경우 유용하다.
- 주요 함수
push_back(value): 맨 뒤에 원소 추가push_front(value): 맨 앞에 원소 추가pop_back(): 맨 뒤 원소 제거pop_front(): 맨 앞 원소 제거at(index): 지정된 인덱스의 원소 반환 (범위 초과 시 예외 발생)front(): 첫 번째 원소 반환back(): 마지막 원소 반환clear(): 모든 원소 제거insert(iterator, value): 지정된 위치에 원소 삽입erase(iterator): 지정된 위치의 원소 제거
반복자
반복자는 데이터의 집합체(예: 리스트, 튜플, 딕셔너리 등)에서 요소들을 순차적으로 접근할 수 있는 객체를 의미한다. 파이썬에서는 for 루프와 함께 자주 사용되며, 반복 가능한 객체(iterable)에서 요소를 하나씩 꺼낼 수 있도록 도와준다.
- 역방향 반복자 (reverse_iterator)
- 컨테이너를 역순으로 순회할 때
rbegin()과rend()를 사용한다.
- 컨테이너를 역순으로 순회할 때
for (std::vector<int>::reverse_iterator rit = vec.rbegin(); rit != vec.rend(); ++rit) {
std::cout << *rit << " ";
}- 상수 반복자 (const_iterator)
- 컨테이너의 데이터를 수정할 수 없는 반복자에요. read-only 용도로 쓰면 좋다
for (std::vector<int>::const_iterator it = vec.cbegin(); it != vec.cend(); ++it) {
std::cout << *it << " ";
}- 삽입 반복자
- 컨테이너에 새로운 원소를 삽입할 때 사용한다.
std::vector<int> vec = {1, 2, 3}; std::vector<int> vec2 = {4, 5, 6}; // vec 뒤에 vec2를 삽입 => vec {1,2,3,4,5,6} std::copy(vec2.begin(), vec2.end(), std::back_inserter(vec));- back_inserter외에 front_inserter, inserter(원하는 위치에 삽입)가 있다.
앞에서는 소개를 하기위해 std::vector<int>::const_iterator it이런식으로 전부 선언하였지만 요즘엔 auto키워드를 사용하여
for (auto it = vec.cbegin(); it != vec.cend(); ++it) {
std::cout << *it << " ";
}
for (int val : vec) {
std::cout << val << std::endl;
}와 같이 사용하면 된다.
알고리즘
- 정렬 관련:
sort,partial_sort,stable_sort,nth_element… - 탐색 관련:
find,binary_search,lower_bound,upper_bound… - 수치 관련:
accumulate,inner_product,adjacent_difference… - 수정 관련:
fill,replace,remove_if,unique…
등등 알고리즘의 종류가 매우 많다.
예시코드
#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;
int main() {
vector<int> v = {5, 2, 9, 1, 7};
// 정렬
sort(v.begin(), v.end());
// 탐색
if (binary_search(v.begin(), v.end(), 9)) {
cout << "9가 벡터에 있습니다!" << endl;
}
// 누적 합
int sum = accumulate(v.begin(), v.end(), 0);
cout << "벡터 원소들의 합 = " << sum << endl; // 24
// 특정 값 치환
replace(v.begin(), v.end(), 1, 100); // 이제 1이 있던 자리가 100으로 바뀜
sum = accumulate(v.begin(), v.end(), 0);
cout << "벡터 원소들의 합2 = " << sum << endl; // 123
}위의 코드처럼 알고리즘을 자유자재로 쓰다 보면 코딩 테스트 문제 해결 속도가 엄청나게 빨라진다.
