STL(Standard Template Library)
- 표준 템플릿 라이브러리. 컨테이너와 알고리즘으로 구성됨.
STL 순차 컨테이너
vector
- 메모리에서 연속적으로 위치함.
#include <vector>생성자
vector<int> v1;
vector<int> v2(10, -1); // -1이 10개인 배열
vector<int> v3 {1, 2, 3, 4, 5};- 생성한 배열의 크기와 같은 capacity를 가진다.
assign
- 선언한 vector 객체를 재사용할 때 사용.
vector<int> intVector(10, 0);
intVector.assign(5, 100);
intVector.assign({1, 2, 3, 4});항목 룩업
- 인덱스 연산을 통해 접근 시 유효 범위를 벗어나면 에러를 발생시킨다.
- at() 메서드 사용 시에는 out_of_range exception을 발생시킨다.
vector<int> v {1, 2, 3, 4, 5};
v[2] = 0;
v.at(3) = -1;
v.front() = 2;
v.back() = -3;반복자
vector의 항목이 삽입되어 capacity가 변경되는 경우 댕글링 포인터 버그가 발생한다.
vector<int> intVector(10, 0);
auto it = intVector.begin();
//vector<int>::iterator it = intVector.begin();
it += 5;
--it;
*it = 4;
vector<int> v1(10), v2(10);
for(auto it = v1.begin(); it != v1.end(); ++it)
{
}
for(auto& item : v1)
{
}
항목 삽입
vector<int> v;
v.reserve(5);
for(int i = 0; i < 5; i++)
{
v.push_back(10);
}
vector<int> v2;
v2.reserve(10);
for(int i = 0; i < 5; i++)
{
v.push_back(1);
}
v.insert(v.begin(), 2); // 0 위치에 2 삽입
v.insert(v.begin() + 2, 2, 3); // 2 위치에 3을 2번 삽입.
v.insert(v.end(), {4, 5}); // 맨 뒤에 4, 5 삽입.- emplace_back과 emplace는 push_back, insert와 같은 결과를 가져오지만 항목을 생성한 뒤 인자로 전달하는 대신 항목에 필요한 인자들을 직접 전달하기 때문에 좀 더 효율적이다.
struct point {int x, y;};
vector<point> v;
v.reserve(2);
v.emplace_back(1, 2);
v.emplace(v.begin(), 3, 4);항목 삭제
vector<int> v {1, 2, 3, 4, 5};
v.pop_back();
v.erase(v.begin() + 1); // 1번 위치 값 삭제
v.erase(v.begin(), v.end() - 1); // 0번 위치부터 맨 뒤 한자리 앞까지 모두 삭제
v.clear() // 전체 삭제.- 특정 조건 항목만을 삭제해야 한다면 remove, remove_if 사용.
vector<int> v1 = {1, 2, 3, 1, 1, 1};
auto it = remove_if(v1.begin(), v1.end(), [](int num){ return num == 1; })
v1.erase(it, v1.end());
// v1 = {2, 3}비교 연산
==, !=, <, >, <=, >= 연산자 사용 가능.
list
- 메모리에서 연속적으로 위치하지 않음. 연결형리스트
#include <list>생성자
- vector와 거의 같다.
list<string> lst = {"String1", "String2", "String3"};항목 룩업
- front()
- back()
반복자
- 양방향 반복자. ++, -- 만을 사용.
항목 삽입/삭제
- push_front, push_back, emplace_front, emplace_back, insert, emplace
- pop_front, pop_back, erase, clear, remove, remove_if
유용한 메서드
- size(), empty()
- resize() : size 재설정. 기존의 항목이 사라지거나 새로운 항목이 추가됨.
- splice() : 다른 list를 삽입.
list<int> list1 {1, 4 ,5}, list2 {2, 3};
auto splicePos = next(list1.begin(), 1);
list1.splice(splicePos, list2); // list1 = {1, 2, 3, 4, 5}- unique() : 중복된 항목 제거.
- merge() : 두 list를 정렬을 유지하며 병합.
- sort() : stable sort.
- reverse() : 역순으로 재배치.
deque
#include <deque>STL 컨테이너 어댑터
queue
#include <queue>생성 및 비교
- deque(=default), list중 하나를 바탕 컨테이너로 사용해야한다.
#include <deque>
#include <list>
queue<int> q1;
deque<int> dq{ 1, 2, 3, 4, 5 };
queue<int> q2{ dq };
list<int> l{ 1, 2, 3, 4, 5 };
queue<int, list<int>> q3{ l };룩업
- front(), back()
삽입
- push(), emplace()
삭제
- pop()
priority_queue
#include <queue>생성
priority_queue<int> pq1; // max heap
priority_queue<int, vector<int>, greater<int>> pq2(data.begin(), data.end()); // min heap
// 비교함수를 직접 전달.
auto cmp = [](int left, right) {return (left ^ 1) < (right ^ 1);}
priority_queue<int, vector<int>, decltype(cmp)> pq3(cmp);
메소드
- top(), pop(), push()
stack
#include <stack>- 바탕 컨테이너로 vector, list, deque 모두 가능.
- 인터페이스는 priority_queue와 동일.
STL 알고리즘
STL 유틸리티 알고리즘
- min, max, minmax 등..
STL 검색 알고리즘
- find, find_if
auto ptr = find(arr, arr + 10, 7);
auto it = find_if(v.begin(), v.end(), [](int a){ return a > 10; })
// 찾지 못하면 v.end() 반환.- min_element, max_element, minmax_element
auto min_it = min_element(v.begin(), v.end());
auto minmax_it = minmax_element(v.begin(), v.end());
// minmax_it.first, minmax_it.second정렬된 항목열에 적용 가능
- binary_search -> bool: 특정 값이 있는지 없는지 여부.
- lower_bound -> iterator : 주어진 값보다 작지 않은 첫 번째 항목 리턴.
- upper_bound -> iterator : 주어진 값보다 큰 첫 번째 항목 리턴.
- equal_range -> pair<iter, iter> : lower, upper를 함께 리턴.
#include <algorithm>
sort(v.begin(), v.end());
bool check = binary_search(v.begin(), v.end(), 77); // 77이 있는 지 없는 지
auto range = equal_range(v.begin(), v.end(), 77);
// range.first, range.second STL 변경 알고리즘
- find한 뒤 값을 바꾸는 함수.
replace, replace_if
replace(v.begin(), v.end(), a, b); // a를 b로 replace
replace_if(v.begin(), v.end(), [lower](int i) {return i < lower;}, lower);
unique
- 중복되는 값들을 뒤쪽으로 분리하고 경계위치를 리턴.
- 연속적으로 중복되는 값만을 처리하기 때문에 이산적인 중복 값을 처리하기 위해서는 정렬을 한 뒤에 사용.
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end(), v.end()));
next_permutation, prev_permutation
항목들의 다음 순열 조합, 이전 순열 조합으로 변환.
마지막 조합에 도달한 경우 false, 이외에는 true 리턴.
string s = "aba";
sort(s.begin(), s.end());
