STL(Standard Template Library)
STL은 C++ 표준 라이브러리의 일부로 자주 사용되는 컨테이너와 알고리즘을 템플릿 기반으로 제공하는 라이브러리이다.
STL의 구성요소는 컨테이너, 알고리즘, 반복자로 크게 3가지로 나눌 수 있다.
컨테이너 : 데이터를 저장하고 관리하는 객체(벡터, 맵, 리스트 등)
알고리즘 : 컨테이너에 저장된 데이터를 처리하는 다양함 함수를 제공(sort, next_permutation 등)
반복자 : 컨테이너의 요소들을 순회하고 접근하는 방법을 제공(포인터처럼 동작함)
반복자는 컨테이너 요소에 순회하고 접근하는 수단이며 알고리즘은 반복자를 통해 컨테이너 내부 데이터를 처리한다.
반복자
순방향 반복자
컨테이너의 요소들을 앞에서부터 차례로 순회하며 각 원소에 접근할 수 있는 반복자다.
맨 처음 위치는 begin(), 마지막 원소 다음 위치는 end()로 접근할 수 있다.
반복자가 가리키는 곳을 읽거나 수정할 수 있다.
++연산자는 지원하고 -- 연산자는 지원하지 않아 한방향으로만 이동할 수 있다.
역방향 반복자
컨테이너의 요소를 뒤에서부터 순회하며 각 원소에 접근할 수 있는 반복자다.
rbegin()은 마지막 요소를, rend()는 첫 번째 요소 바로 앞 위치를 가리킨다.
반복자가 가리키는 곳을 읽거나 수정할 수 있다.
++와 -- 연산자 모두 지원하여 양방향으로 이동할 수 있다.
컨테이너
벡터
배열과 매우 유사하지만 크기를 동적으로 조절할 수 있다.
데이터를 순차적으로 저장하며 인덱스를 통해 특정 위치의 원소에 쉽게 접근할 수 있다.
<vector> 헤더 파일을 포함해야 한다.
선언 및 초기화
vector<DataType> name 으로 선언한다. 이때 벡터의 크기는 0이다
vector<DataType> name = {1, 2, 3} 선언과 동시에 초기값을 직접 지정하는 방법
vector<DataType> name2 = name1 기존 벡터의 모든 요소를 복사하는 방법.
vector<DataType> name(5,10) 10으로 초기화 된 크기가 5인 벡터를 생성하는 방법.(모든 원소가 10)
삽입과 삭제
push_back() : 가장 마지막에 새 원소를 추가하는 메서드, 시간복잡도는 O(1)이다.
pop_back() : 가장 마지막에 있는 원소를 삭제하는 메서드, 시간복잡도는 O(1)이다.
insert() : 중간에 원소를 삽입하는 메서드, 삽입 지점 이후 모든 원소를 뒤로 이동시키므로 시간 복잡도는 O(N)이다.
erase() : 중간에 원소를 삭제하는 메서드, 삭제 지점 이후 모든 원소를 앞으로 당겨야하므로 시간 복잡도는 O(N)이다.
clear() : 모든 원소를 지우는 메서도, 시간 복잡도는 O(N)이다.
주의할 점
1. 중간 삽입이나 삭제가 빈번하게 발생한다면 deque 사용을 고려해야한다.
2. 벡터는 원소 개수가 내부 용량을 넘으면 메모리 재할당을 하고 이 과정의 시간 복잡도는 O(N)이다.
따라서 원소의 최대 개수를 예측할 수 있다면 reverse() 메서드를 활용해서 미리 메모리를 확보하여 재할당이 발생하지 않도록 하는게 좋다.
// 벡터의 메모리 재할당 발생 확인 예제
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vec;
for (int i = 0; i < 10; ++i) {
vec.push_back(i);
cout << "size: " << vec.size() << ", capacity: " << vec.capacity() << endl;
}
return 0;
}
/*
출력결과 예시 (capacity는 환경마다 다를 수 있음)
size: 1, capacity: 1
size: 2, capacity: 2
size: 3, capacity: 4
size: 4, capacity: 4
size: 5, capacity: 8
...
유의사항: 용량(capacity)을 초과하면 2배씩 재할당 → 이 과정은 O(N)
*/// reserve를 사용하여 메모리 재할당을 방지하는 예제
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vec;
vec.reserve(10); // 최대 10개의 원소를 넣을 예정이므로 미리 메모리 확보
for (int i = 0; i < 10; ++i) {
vec.push_back(i);
cout << "size: " << vec.size() << ", capacity: " << vec.capacity() << endl;
}
return 0;
}
/*
출력결과:
size: 1, capacity: 10
size: 2, capacity: 10
...
size: 10, capacity: 10
*/set
중복되지 않는 원소들을 정렬된 상태로 저장하는 컨테이너다.
<set> 헤더 파일을 포함해야 한다.
선언 및 초기화
set<DataType> name 으로 선언한다.
set<DataType> name으로 빈 set을 선언할 수 있다.
set<DataType> name = {3,1,4,1,5,9,2,6,} 초기화 리스트를 사용할 수 있다.
단 set은 중복된 값을 허용하지 않고 원소들이 자동으로 오름차 순으로 정렬되므로 {1, 2, 3, 4, 5, 6, 9} 원소를 갖는다.
set<DataType> name2 = name1 기존 set을 복사해서 새로운 set을 만들 수 있다.
삽입과 삭제
insert() : 원소를 삽입하는 메서드, 삽입할 때 마다 정렬된 상태를 유지한다.
erase() : 원소를 삭제하는 메서드, 삭제할 때 마다 정렬된 상태를 유지한다.
clear() : 모든 원소를 삭제하는 메서드 O(N)
set은 내부적으로 데이터를 정렬할 때 레드 블랙 트리를 사용한다. 따라서 삽입, 삭제시 시간 복잡도는 O(logN)이다.
셋은 정렬 상태를 유지하는 특성 상 원소를 바로 수정할 수는 없다.
원소를 변경하려면 기존 원소를 삭제하고 새로운 값을 삽입하는 방식으로 처리해야 한다.
삽입과 삭제 모두 O(logN)이므로 전체 변경 연산의 시간 복잡도는 O(logN)이 된다.
주의할 점
1. set은 중복된 원소를 허용하지 않는다. 정렬된 상태를 유지하면서 중복된 값을 저장하려면 multiset을 사용해야 한다.
2. 원소의 정렬이 필요하지 않고 빠른 탐색이 중요한 경우에는 해시 기반의 unordered_set을 사용하는 것이 더 적합하다.
3. set은 삽입과 동시에 자동 정렬되기 때문에 원소의 삽입 순서가 유지되지 않는다.
삽입 순서를 그대로 유지하려면 vector나 list를 사용하는 것이 더 적합하다.
4. set은 인덱스를 지원하지 않으므로 인덱스로 원소에 접근해야 하는 경우 vector를 사용하는 것이 더 적합하다.
map
키와 값을 쌍으로 갖는 연관 컨테이너다.
중복 키를 허용하지 않으며 키를 기준으로 데이터가 자동으로 오름차순 정렬된다.
<map> 헤더 파일을 포함해야 한다.
선언 및 초기화
map<keyType, valueType> name으로 선언한다.
map<keyType, valueType> name = {{key1, value1}, {key2,value2}}으로 키와 값을 갖는 맵을 생성할 수 있다.
map<keyType, valueType> name2 = name1 으로 기존 맵을 복사할 수 있다.
원소 변경
1. [ ] 연산자를 활용해서 맵의 값을 변경할 수 있다. 만약 해당 키가 없다면 새로운 키 - 값 쌍을 만든다.
2. at() 메서드를 사용해서 맵의 값을 변경할 수 있다. 단 [ ] 연산자와 달리 존재하지 않는 키로 접근하면 out_of_range 예외가 발생한다.
삽입과 삭제
insert() : 존재하는 키를 삽입하려 하면 삽입은 무시되고 반환값으로는 삽입된 위치의 반복자와 함께 삽입 성공 여부를 나타내는 false가 반환된다.
// insert()를 이용한 삽입 및 중복 키 처리 결과 확인
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, string> myMap;
auto result1 = myMap.insert({1, "Apple"});
auto result2 = myMap.insert({2, "Banana"});
auto result3 = myMap.insert({1, "Cherry"}); // 중복 키
cout << "삽입 1 성공 여부: " << result1.second << endl; // true
cout << "삽입 2 성공 여부: " << result2.second << endl; // true
cout << "삽입 3 (중복) 성공 여부: " << result3.second << endl; // false
for (auto& p : myMap) {
cout << p.first << ": " << p.second << endl;
}
return 0;
}
// 출력결과:
// 삽입 1 성공 여부: 1
// 삽입 2 성공 여부: 1
// 삽입 3 (중복) 성공 여부: 0
// 1: Apple
// 2: Bananaerase() : 특정 키를 이용해 원소를 삭제할 수 있으며 이 경우 시간 복잡도는 O(logN)이다.
반복자를 통해 특정 위치의 원소를 삭제할 수도 있으며 이 경우 시간 복잡도는 일반적으로 O(1)이다.
// erase()를 사용하여 키 또는 반복자를 통해 원소 삭제
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, string> myMap = {
{1, "Apple"}, {2, "Banana"}, {3, "Cherry"}
};
myMap.erase(2); // 키 2 삭제
auto it = myMap.find(3); // 키 3의 반복자 찾기
if (it != myMap.end()) {
myMap.erase(it); // 반복자를 통한 삭제
}
for (auto& p : myMap) {
cout << p.first << ": " << p.second << endl;
}
return 0;
}
// 출력결과:
// 1: Apple
// 키 기반 삭제는 O(logN), 반복자 삭제는 평균 O(1)clear() : 모든 원소를 삭제하는 메서드. O(N)
주의할 점
1. 단순히 키만 필요하고 값이 필요하지 않는 경우 set를 사용
2. 만약 원소의 삽입 순서를 유지해야 한다면 vector 사용
3. 키는 명확해야 한다. 부동 소수점을 키로 사용하는 것은 적합하지 않다.
알고리즘
sort
sort(first, last, comp), comp 함수가 없으면 오름차순이 기본
기본적으로 오름차순으로 범위 [first, last)에 있는 원소들을 정렬한다. [는 포함O, )는 포함X (fisrt <= x < last)
<algorithm> 헤더 파일을 포함해야 한다.
시간복잡도는 평균적으로 O(N logN이다)
// 문자열 벡터를 길이 기준으로 정렬하는 사용자 정의 comp 함수 사용
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compareByLength(const string& a, const string& b) {
return a.length() < b.length(); // 짧은 문자열이 앞에 오도록 정렬
}
int main() {
vector<string> names = {"Alice", "Bob", "Christina", "Dan"};
sort(names.begin(), names.end(), compareByLength);
for (const string& name : names) {
cout << name << " ";
}
return 0;
}
// 출력결과: Bob Dan Alice Christinafind
find(first, last, value)
범위 [fisrt, last) 내에서 특정 값과 일치하는 첫 번째 원소를 선형 탐색한다.
일치하는 값이 있으면 해당 원소를 가리키는 반복자를 반환하고 없으면 last 반복자를 반환한다.
시간 복잡도는 O(N)이다.
// find()로 특정 값을 찾고 위치를 출력하는 예제
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> vec = {10, 20, 30, 40, 50};
auto it = find(vec.begin(), vec.end(), 30);
if (it != vec.end()) {
cout << "찾은 값: " << *it << endl; // *을 붙여야 값이 나옴 안붙이면 인덱스 2가 출력
}
return 0;
}
// 출력결과: 찾은 값: 30
// find는 처음 발견된 30의 위치 반복자를 반환count
count(first, last, value)
범위 [first, last] 내에서 특정 값이 몇 번 등장하는지를 계산하여 반환한다.
시간 복잡도는 O(N)이다.
// 벡터에서 값 5가 몇 번 등장하는지 세는 예제
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {1, 5, 2, 5, 3, 4};
int result = count(v.begin(), v.end(), 5);
cout << "5의 개수: " << result << endl;
return 0;
}
// 출력결과: 5의 개수: 2
// count는 범위 내에서 5가 몇 번 등장했는지 반환 (O(N))unique
unique(first, last)
범위 [first, last) 내에서 연속된 중복 요소를 제거한다.
실제로 컨테이너에서 원소가 삭제되는 것은 아니며 각 원소의 첫 번째 발생만 유지되도록 원소들을 앞쪽으로 덮어 씌워 재배열한다.
그 이후의 영역은 남아있으므로 보통 erase와 함께 사용하여 완전히 제거한다.
시간 복잡도는 O(N)이다.
함수는 중복 제거 후 마지막 고유 원소의 다음 위치를 가리키는 반복자를 반환한다.
중복된 값 처리
// unique()는 연속된 중복 요소만 제거 (재배열만 함)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {1, 1, 2, 2, 2, 3, 1, 1};
auto newEnd = unique(v.begin(), v.end());
for (auto it = v.begin(); it != newEnd; ++it) // newEnd가 되면 종료
{
cout << *it << " ";
}
return 0;
}
// 출력결과: 1 2 3 1
// 주의: 실제 컨테이너 크기는 그대로이고, 중복 제거된 결과는 앞쪽에만 있음unique 수행 후 erase를 수행하지 않는 경우
// unique()만 호출하고 erase()를 하지 않으면 쓰레기 값이 남아있을 수 있음
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {1, 1, 2, 2, 3, 3, 3};
unique(v.begin(), v.end());
for (int val : v) {
cout << val << " ";
}
return 0;
}
// 출력결과: 1 2 3 2 3 3 3 (이후 값이 남아있음)
// ⚠원소가 "논리적으로"만 제거됨. 실제 삭제된 건 아님.unique 수행 후 erase를 수행
// unique()와 erase()를 조합해 실제로 중복 원소 삭제
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {1, 1, 2, 2, 3, 3, 3};
v.erase(unique(v.begin(), v.end()), v.end());
for (int val : v) {
cout << val << " ";
}
return 0;
}
// 출력결과: 1 2 3
// erase–remove idiom을 통해 연속된 중복 요소가 완전히 제거됨'코딩테스트 공부' 카테고리의 다른 글
| 재귀 함수 (0) | 2025.09.30 |
|---|---|
| 효율적인 코드 구현하기(벡터vs덱, 정렬이 필요없는데 정렬하는 경우, 특정 원소 찾기, 문자열 결합하기, auto& vs auto) (0) | 2025.09.29 |
| 입력값 처리(숫자 반올림, 올림, 내림, 문자열 스트림, 진법 변환) (0) | 2025.09.29 |
| 자주 하는 실수(단락 평가, off by one, 0으로 나누기, 중간 값의 오버플로) (0) | 2025.09.26 |
| 문자열 메서드(find, append, replace, substr 등) (0) | 2025.09.26 |
