표준 템플릿 라이브러리, STL은 C++ 언어가 제공하는 템플릿을 바탕으로 만든 컨테이너 클래스를 제공하는 라이브러리이다. 템플릿을 사용해 구현된 컨테이너들의 집합이다.
벡터, 리스트, 큐 그리고 스택 등의 클래스 템플릿과 그 안에 저장된 데이터를 검색하고 정렬하는 등의 처리를 위한 함수들이 제공된다.
STL의 목적은 프로그래머들이 많이 사용하는 공통적인 컨테이너 클래스를 제공하는 것이다.
STL의 구성요소
컨테이너: 객체 또는 기본 데이터 타입의 집합으로 각 컨테이너는 관련된 헤더 파일 포함 필요
반복자: 컨테이너 요소들에 대한 순회 및 접근
알고리즘: 컨테이너의 요소들을 다루기 위한 알고리즘(find, max, count, accumulate, sort, ...)
컨테이너
컨테이너는 데이터를 저장하는 것으로, 저장하는 데이터는 int나 float와 같은 기본 자료형의 값일 수도 있고 사용자가 정의한 클래스의 객체들이 될 수도 있다.
C++에서 제공하는 배열 역시 컨테이너와 같은 역할을 한다.
그러나 배열은 프로그램을 구현할 때 크기가 미리 정해져야 하며,
중간에 새로운 값을 삽입한다거나 삭제할 때 해당 위치 이후의 값들을 모두 앞으로(또는 뒤로) 이동시키는 작업을 일일이 프로그래밍해야 한다.
STL에서 제공하는 컨테이너들을 사용하게 되면 각각의 용도에 따라 효과적인 알고리즘을 제공받을 수 있어 편리하고 효율적이다.
컨테이너 종류
순차 컨테이너 : 동일한 자료형의 객체들을 선형적인 구조로 저장하는 것이다. 컨테이너 요소들의 삽입 순서를 유지하는 컨테이너다.
종류
특징
vector
1. 크기의 확장이 가능한 배열 2. [] 연산자로 지정한 첨자를 이용하여 빠른 접근 가능 3. 끝에 삽입 또는 삭제하는 것은 빠르나 그 외의 위치에 삽입 또는 삭제하는 것은 느리다.
list
1. 이중 연결 리스트 2. 어느 위치든지 삽입 또는 삭제가 효율적이다. 3. 직접 접근은 비효율적이므로 제공하지 않는다.
deque
vector와 list의 혼합 형태로, 이들의 특성이 모두 필요할 때 사용할 수 있으나, 성능이 좋지 못하다.
연상 컨테이너 : 컨테이너 요소들의 삽입 순서를 유지하지 않고 탐색 트리와 같은 인덱스 구조를 이용하는 컨테이너로서, 키를 이용한 검색 기능을 제공한다.
종류
특징
set
1. 키 객체만 저장 2. 키 값이 중복되지 않음
map
1. 키 객체를 값 객체와 연결한 쌍을 저장 2. 키 값이 중복되지 않음
multiset
1. 키 객체만 저장 2. 키 값이 중복 가능
multimap
1.키 객체를 값 객체와 연결한 쌍을 저장 2. 키 값이 중복 가능
무순서 연상 컨테이너: 연상 컨테이너처럼 키를 이용한 검색 기능을 제공하지만 탐색 트리와 같은 인덱스 구조를 이용하는 것이 아닌 해시함수를 이용함으로써 데이터 검색 시간이 데이터 수에 관계없이 일정하다.
연상 컨테이너와 마찬가지로 컨테이너 요소들의 삽입 순서가 유지되지 않지만 대신 해시함수에 따라 요소들이 저장된다.
종류
특징
unordered_set
set과 동일하나 해시함수를 이용하여 요소 저장
unordered_map
map과 동일하나 해시함수를 이용하여 요소 저장
unordered_multiset
multiset과 동일하나 해시함수를 이용하여 요소 저장
unordered_multimap
multimap과 동일하나 해시함수를 이용하여 요소 저장
연상 컨테이너와 무순서 연상 컨테이너 비교
항목
연상 컨테이너 (Associative Containers)
무순서 연상 컨테이너 (Unordered Associative Containers)
컨테이너 종류
std::set, std::map, std::multiset, std::multimapstd::unordered_set, std::unordered_map, std::unordered_multiset, std::unordered_multimap
내부 구조
균형 이진 탐색 트리 (보통 Red-Black Tree) 해시 테이블 (Hash Table)
키 정렬 여부
✅ 자동으로 정렬됨 (오름차순 기본)
❌ 정렬되지 않음 (해시 분산에 따라 저장)
삽입 순서 보존
❌ 정렬 순서 우선 → 삽입 순서와 다름
❌ 삽입 순서 보장 안 됨
검색/삽입/삭제 평균 시간
O(log n)
O(1) (평균), O(n) (최악)
커스터마이징 기준
std::less<Key> 등 비교 함수 (Compare)std::hash<Key> + == 연산자
연산 가능한 키 요구사항
요소 정렬을 위한 < 연산 필요 (Compare 개념)
== 연산과 해시함수 필요
* std::map은 자동 정렬
std::map<int, std::string> m;
m[3] = "three";
m[1] = "one";
m[2] = "two";
for (const auto& [k, v] : m)
std::cout << k << ": " << v << "\n";
// 출력: 1: one 2: two 3: three
std::unordered_map은 정렬 안 됨 , 삽입 순서도 아님
std::unordered_map<int, std::string> um;
um[3] = "three";
um[1] = "one";
um[2] = "two";
for (const auto& [k, v] : um)
std::cout << k << ": " << v << "\n";
// 출력 순서 예시: 2: two 1: one 3: three (환경마다 다름)
컨테이너 어댑터: 기본적인 일반 컨테이너를 기반으로 특정 용도에 맞게 유도된 컨테이너다.
종류
특징
queue
FIFO 구조
priority_queue
우선순위에 따라 데이터를 액세스할 수 있는 구조
stack
LIFO 구조
컨테이너 어댑터와 일반 컨테이너 비교
항목
컨테이너 어댑터 (stack, queue, priority_queue)
일반 컨테이너 (vector, deque, list, map 등)
직접 요소 접근 (iterator 등) ❌ 불가 (begin(), end() 없음)
✅ 가능
용도 특화 인터페이스 제공 ✅ 제한적 (push, pop, top 등만 제공)
❌ 일반적 (insert, erase, at, [] 등)
내부 컨테이너 설정 가능 ✅ 가능 (템플릿 인자로 선택 가능)
-
복잡한 자료구조 제공 여부 ❌ (단순 스택/큐/힙)
✅ (트리 기반 map/set, hash 기반 unordered map 등)
알고리즘 호환 (std::sort, std::find 등) ❌ 불가능
✅ 가능 (iterator 지원 때문에)
표준 컨테이너인가? ✅ 표준이지만 어댑터 클래스
✅ STL 핵심 컨테이너
stack : 요소 접근은 top()만 가능, s[0], s.begin() 등의 사용은 불가
std::stack<int> s;
s.push(1);
s.push(2);
s.pop(); // 2 제거
std::cout << s.top(); // 1
vector : 임의 접근(indexing, iterator) 가능, 알고리즘 적용 가능
std::vector<int> v = {1, 2, 3};
v.push_back(4);
std::cout << v[2]; // 3
std::sort(v.begin(), v.end());
컨테이너 어댑터와 일반 컨테이너의 철학적 차이
컨테이너 어댑터
일반 컨테이너
동작(행위)을 제한 해 안정성과 용도 특화 제공유연성과 범용성 에 초점
내부 컨테이너를 감추고 추상화함
내부 구현에 대한 접근이 가능함
자료구조적 특성(LIFO/FIFO/Heap 등)에 집중
범용 자료 저장에 집중
std::stack<int, std::vector<int>> s1; // vector 기반 스택
std::stack<int, std::list<int>> s2; // list 기반 스택일반 컨테이너의 공통 기능
Function
Description
기본 생성자
빈 컨테이너 초기화
재정의된 생성자
다른 속성들과 함께 초기화
복사 생성자
다른 컨테이너를 복사본을 생성하여 초기화
이동 생성자
기존 컨테이너를 다른 컨테이너로 이동시키면서 초기화
소멸자
컨테이너 객체를 소멸시킴
대입 연산자 operator=
하나의 컨테이너를 다른 컨테이너로 복사
이동 대입 연산자 operator=
하나의 컨테이너를 다른 컨테이너로 이동시킴
size()
컨테이너의 요소 개수를 반환
empty()
컨테이너의 요소가 비어있는지 여부를 반환
insert()
컨테이너에 요소 삽입
operator< and operator<=
두 컨테이너의 요소들을 비교하여 대소 여부를 반환
operator> and operator>=
두 컨테이너의 요소들을 비교하여 대소 여부를 반환
operator== and operator!=
두 컨테이너의 요소들의 동등성 여부를 반환
swap()
두 컨테이너의 요소들을 swap
erase()
컨테이너의 특정 요소들을 삭제
clear()
컨테이너의 모든 요소들을 삭제
begin and end
컨테이너의 시작 이터레이터, 종료 이터레이터 반환
rbegin and rend
컨테이너의 역순 시작 인터레이터, 역순 종료 이터레이터 반환
cbegin and cend
컨테이너의 const 시작 이터레이터, const 종료 이터레이터 반환
crbegin and crend
컨테이너의 const 역순 시작 이터레이터, const 역순 종료 이터레이터 반환
컨테이너 요소에 대한 요구사항
컨테이너의 요소는 복사되어 컨테이너에 저장된다. => 컨테이너에 저장하려는 요소가 사용자 정의 자료형인 경우 해당 사용자 정의 자료형은 복사가 가능하고 대입이 가능해야 한다.
즉, 복사 생성자와 대입 연산자가 정의돼 있어야 한다.
특히, Associative(연산) 컨테이너의 경우엔 순서 정렬을 위한 비교 연산을 수행할 수 있어야 한다.
즉, 비교 연산자에 대한 다중 정의가 필요하다.
결국, 컨테이너의 템플릿 인자로 전달되는 타입의 클래스에선 opearator<, operator== 연산자 다중정의가 필요하다.
반복자
컨테이너 요소에 대해 추상적인 접근을 가능하게 하는 기능이다.
즉, 컨테이너의 종류가 무엇이고 컨테이너가 어떻게 구현됐는지는 몰라도 된다.
반복자는 포인터의 개념이 일반화된 것 으로, 컨테이너에 저장된 원소들을 액세스하는 공통적인 방법으로 사용된다.컨테이너의 유형에 따라 서로 다른 형태의 반복자가 사용된다.
순방향 반복자는 컨테이너의 앞쪽으로만 움직일 수 있으며, ++ 연산자가 이를 위해 사용된다.
양방향 반복자는 앞과 뒤로 움직일 수 있으며, 이를 위해 ++, -- 연산자가 정의돼 있다.
랜덤 액세스 반복자는 양방향 반복자의 기능과 함께 임의의 위치로 이동할 수 있다.
stack과 queue를 제외한 대부분의 컨테이너는 반복자를 사용해 순환 가능 하다.
반복자의 선언 : 반복자가 사용될 컨테이너 타입을 명시
std::vector<int>::iterator it1;
std::list<string>::iterater it2;
std::map<string, string>::iterator it3;
std::set<char>::iterator it4;std::vector<int> vec {1, 2, 3};
컨테이너의 end 함수는 컨테이너의 마지막 요소가 저장된 위치의 다음 위치를 가리키는 이터레이터를 반환한다.
std::set<char> ch {'A', 'E', 'D', 'B'};
set은 삽입 순서를 유지하지 않으므로 인덱싱으로 접근이 불가하다.
반복자의 사용
for 문과 반복자를 사용한 vector 순환
#include <iostream> #include <vector> int main() { std::vector<int> vec{ 1, 2, 3}; for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); it++) { std::cout << *it << std::endl; } }while문과 반복자를 사용한 set 순환
#include <iostream> #include <set> int main() { std::set<char> ch{'A', 'E', 'D', 'B'}; std::set<char>::iterator it = ch.begin(); while(it != ch.end()) { std::cout << *it << " "; ++it; } }
auto 키워드
자동으로 타입을 추정해주는 키워드
타입이 길어질 경우 사용하면 편리하다.
#include <iostream>
#include <vector>
int main()
{
std::vector<int> vec{ 1, 2, 3};
for (auto it = vec.begin(); it != vec.end(); it++)
{
std::cout << *it << std::endl;
}
}#include <iostream>
#include <set>
int main()
{
std::set<char> ch{'A', 'E', 'D', 'B'};
auto it = ch.begin();
while(it != ch.end())
{
std::cout << *it << " ";
++it;
}
}
반복자의 연산자(포인터와 비슷하게 동작한다.)
#include <iostream>
#include <vector>
#include <set>
int main()
{
std::vector<int> vec{ 1, 4, 7};
auto it = vec.begin();
it += 2;
std::cout << *it <<std::endl; // 7
}
역반복자
역순으로 동작
마지막 요소가 첫 요소가 되는 반복자
++ 및 -- 가 역방향으로 작용
#include <iostream>
#include <vector>
int main()
{
std::vector<int> vec { 1, 2, 3};
std::vector<int>::reverse_iterator it = vec.rbegin();
while(it != vec.rend())
{
std::cout << *it << " ";
++it; // 이터레이터가 역방향으로 이동
}
// 3 2 1
}
기타 반복자들
const_iterator => cbegin() / cend()
const_ reverse_iterator => crbegin() / crend()
const 이터레이터로 접근한 요소는 상태를 변경할 수 없다.
#include <iostream>
#include <vector>
int main(){
std::vector<int> vec {1, 2, 3};
for(auto it = vec.cbegin(); it != vec.cend() ; it++)
{
*it = 5; // Error: const 요소의 상태를 변경할 수 없다.
}
for(auto it = vec.begin(); it != vec.end() ; it++)
{
*it = 5; // OK
}
}STL 알고리즘
STL 알고리즘들은 컨테이너의 반복자를 사용하여 컨테이너의 원소에 대해 적용할 수 있는 여러 가지 연산을 제공한다.
알고리즘에는 컨테이너의 반복자가 인수로 전달되어 그 알고리즘이 어떤 객체 또는 범위에 대해 동작할 것인지를 지정한다.
컨테이너의 반복자에 의해 지정된 요소 집합에 대해서 알고리즘이 수행된다.
매우 다양한 알고리즘이 구현돼 있다.
알고리즘을 사용하기 위해 함수를 알고리즘 파라미터의 인자로 전달해야 하는 경우가 존재한다.
알고리즘
목적
search
주어진 값과 동일한 첫 번째 원소를 반환
count
주어진 값을 갖는 원소의 수를 반환
swap
컨테이너 안의 값을 교환
sort
컨테이너의 값들을 지정된 순서에 따라 정렬
merge
두 정렬된 영역의 원소들을 합병
reverse
list의 원소들을 역순으로 나열
remove
컨테이너에서 주어진 값을 제거
replace
주어진 값을 다른 값으로 대체
unique
인접 위치에 있는 중복값을 제거
for_each
주어진 함수를 컨테이너의 모든 원소에 적용
알고리즘과 반복자
#include <algorithm>컨테이너에 따라 적용할 수 있는 알고리즘이 다르다.
모든 알고리즘은 반복자를 인자로 필요로 한다.
반복자의 유효성
반복자가 유효하지 않을 수 있다.
반복자 iterator가 가리키고 있는 요소가 삭제된다면 iterator가 유효하지 않다.
find 알고리즘
find 알고리즘은 컨테이너 내 어떤 요소가 첫 번째로 나타나는 지점을 찾아준다.
해당 지점을 가리키는 반복자를 반환하거나 컨테이너의 end 함수가 반환하는 마지막 반복자를 반환 => end 함수가 반환하는 반복자를 반환하는 경우, 해당 요소가 컨테이너에 없다는 뜻이다.
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> vec{ 1, 3, 7, 4, 8, 10}; auto location = std::find(vec.begin(), vec.end(), 3); if(location == vec.end()){ std::cout << "cannot find" << std::endl; }else { std::cout << "found" << std::endl; std::cout << *location << std::endl; } return 0; }find 알고리즘의 사용을 위해서는 요소들을 비교할 수 있어야 한다.
operator==가 사용되므로, 찾고자하는 요소의 타입이 클래스인 경우 오버로딩이 필요하다.#include <iostream> #include <string> #include <vector> #include <algorithm> class Player { std::string name; int health; int xp; public: bool operator==(const &Player p) const { if(name == p.name) // C++ string은 값 비교를 하도록 ==를 오버로딩 해놓음 return true; return false; } }; int main() { std::vector<int> team{ ... }; Player p{"Hero", 100, 12}; auto location = std::find(team.begin(), team.end(), p); if(location == vec.end()){ std::cout << "cannot find" << std::endl; }else { std::cout << "found" << std::endl; std::cout << *location << std::endl; } return 0; }
Functor, Function Pointer, Lamda expression
for_each 알고리즘
for_each 알고리즘은 컨테이너 내 각 요소를 인자로 하는 함수를 호출
함수를 인자로써 전달하는 방법
Functor
Function Pointer
Lamda expression
Functor의 사용
함수처럼 사용 가능한 객체 => () 연산자의 오버로딩
struct Square_Functor // Functor 선언과 구현
{
void oprerator() (int x) // () 연산자 오버로딩
{
cout << x*x << " ";
}
}
Square_Functor square; // Functor 객체
vector<int> vec {1, 2, 3, 4};
for_each(vec.begin(),vec.end(), square);Function Pointer의 사용
함수의 주소값을 알고리즘의 인자로 전달
함수명은 함수의 주소값을 뜻한다.
void square(int x)
{
cout << x*x << " ";
}
Square_Functor square; // Functor 객체
vector<int> vec {1, 2, 3, 4};
for_each(vec.begin(),vec.end(), square);
//1 4 9 16
```
* Lamda expression의 사용
* 익명 함수
* 함수에 이름을 부여하지 않고 한 번만 사용하는 일회성 함수 구현에 사용
* `[]` => 캡처 절, scope 외부 변수를 값 또는 참조로 접근하는지를 명시
```
vector<int> vec {1, 2, 3, 4};
for_each(vec.begin(), vec.end(), [](int x) {cout << x*x << " "};);
```Array
고정 크기 배열 컨테이너 기존의 정적 배열과 거의 유사하나, STL이므로 반복자를 이용할 수 있고 알고리즘에 전달될 수 있다.
배열과 같이 요소에 대한 직접 접근이 가능하다.
#include <iostream>
#include <algorithm>
#include <array>
int main() {
std::array<int, 5> arr1{1, 2, 3, 4, 5};
std::array<std::string, 3> arr2{"Kim", "Lee", "Park"};
std::cout << arr1.size() << std::endl;
std::cout << arr1[0] << std::endl; // 1
std::cout << arr1.at(2) << std::endl; // 3
}Vector
std::vector#include <vector>Array와 달리 가변 크기 배열 컨테이너
요소에 대한 직접 접근 가능
요소의 끝 위치 삽입(push_back) 및 제거(pop_back) (constant time)
임의의 위치에 요소 삽입 및 제거(linear time)
반복자가 유효하지 않을 수 있다.
#include <iostream>
#include <vector>
int main() {
std::vector vec {1, 2, 3, 4, 5};
std::cout << vec.size() << std::endl;
std::cout << vec.capacity() << std::endl;
std::cout << vec[0] << std::endl;
std::cout << vec[1] << std::endl;
std::cout << vec.at(3) << std::endl;
std::cout << vec[-1] << std::endl;// Runtime Error
std::cout << vec.at(-1) << std::endl; // Exception
std::cout << vec.front() << std::endl;
std::cout << vec.back() << std::endl;
}#include <iostream>
#include <vector>
int main() {
std::vector vec {1, 2, 3, 4, 5};
std::cout << vec.size() << std::endl;
std::cout << vec.capacity() << std::endl; // 5
std::cout << vec.data() << std::endl; // 첫 번째 요소가 저장된 메모리 주소 반환
vec.push_back(10);
std::cout << vec.size() << std::endl;
std::cout << vec.capacity() << std::endl; // 7
std::cout << vec.data() << std::endl;
// push_back으로 인해 새로운 메모리 할당받아 push_back 이전과 달라진다.
}
push_back과 emplace_back의 차이
#include <iostream>
#include <string>
#include <vector>
class Person {
std::string name;
public:
Person(std::string name)
:name{name}
{
std::cout << "constructor called" << std::endl;
}
}
int main() {
std::vector<Person> vec;
vec.push_back(Person("Kim")); // 임시 객체를 생성해서 복사하여 저장
vec.emplace_back(Person("Lee")); // 임시 객체 생성없이 해당 객체를 직접 저장
}#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec{1, 2, 3, 4, 5};
auto it = find(vec.begin(), vec.end(), 4);
vec.insert(it, 7);
std::cout << vec[3] << std::endl;
}List
순차 컨테이너
연속된 메모리 공간에 저장되지 않는다.
요소에 대한 직접 접근 불가(at 함수와 [] 연산자로 접근 불가)
요소의 위치가 결정되면, 삽입과 삭제가 매우 효율적
요소 탐색은 Array와 Vector에 비해 비효율적
양방향 연결리스트로, 크기가 가변적, 가변 컨테이너
반복자의 유효성 보장 안 됨
#include <list>
#include <algorithm>
int main() {
std::list<int> myList{1, 2, 3, 4, 5};
auto it = std::find(myList.begin(), myList.end(), 3);
myList.insert(it, 10);
myList.erase(it); // 반복자가 더 이상 유효하지 않다.
}Set
집합과 유사하다
key에 따라 정렬
요소에 대한 직접 접근 불가
반복자가 유효하지 않을 수 있다.
#include <iostream>
#include <set>
#include <algorithm>
template <typename T>
void PrintContainer(T myContainer) {
for(auto it = myContainer.begin(); it != myContainer.end(); it++) {
std::cout << *it << " ";
}
std::cout << std::endl;
}
int main() {
std::list<int> l{ 3, 1, 5, 4, 2 };
PrintContainer<std::list<int>>(l); // 초기화 순서대로 출력
std::set<int> s{ 3, 1, 5, 4, 2 };
PrintContainer<std::set<int>>(s); // 정렬되어 출력
}
순차 컨테이너와 달리 연상 컨테이너는 front 함수와 back 함수가 없다.(삽입하는 순서가 없기 때문이다.)
정렬을 위해 operator< 오버로딩 필요
insert 함수의 결과로 pair<iterator, bool> 타입의 객체 반환
class Person {
std::string name;
int age;
public:
bool operator<(const Person& p) const {
if(this.age < p.age) {
return true;
}
return false;
}
};
Person p1 {"kim", 20};
Person p2 {"lee", 21};
set<Person> persons;
persons.insert(p1);
auto result = persons.insert(p2);
multiset
unordered_set
unordered_multiset
Map
dictionary(사전)과 유사
요소가 key-value 쌍으로 저장
Key 값에 따라 정렬
Key는 유일한 값으로 중복 불가
Key를 통한 직접 접근 가능
반복자가 유효하지 않을 수 있다.
#include <map>
int main() {
std::map<std::string, int> m1 {
{"Kim", 20},
{"Lee", 21}
};
std::cout << m1["Kim"] <<std::endl;
m1["Kim"] = 22;
m1["Park"] = 25; // m1 map에 새로운 pair<std::string, int> 객체 추가, insert
m1.insert(std::make_pair("Choi", 20));
}
multimap
unordered_map
undordered_multimap
