C++ STL 정리

STL (Standard Template Library)

:  C++의 템플릿을 사용해 표준으로 정리된 라이브러리로

일반적인 알고리즘에 대한 효율적인 구현을 제공하는 것을 목표로 함

 

컨테이너, 반복자, 알고리즘 등의 라이브러리로 구성됨

---

▶ 컨테이너 (Container)

: 자료를 저장하는 클래스 템플릿의 집합

기본 자료형과 유저가 정의한 자료형을 담는 일종의 자료구조

 

종류

1. 시퀀스 컨테이너
일반적인 자료구조와 동일한 형태 ( vector(가변 배열), list(연결 리스트), string, deque, ...  )

임의의 위치에 삽입, 삭제가 가능하고 데이터를 순차적으로 저장함

자료를 입력한 순서대로 저장하기 때문에 저장, 탐색 알고리즘에 불리함

∴ 적은 양의 자료나 검색 속도가 중요하지 않은 경우에 사용함

 

2. 연관 컨테이너

일정한 규칙에 따라 자료를 조직화해 저장 ( set, map, multiset, multimap, ... )

자료를 정렬 / 해시 등을 이용해 저장하기 때문에 탐색에 유리함

∴ 많은 양의 자료나 검색 속도가 중요한 경우에 사용함

 

3. 어댑터 컨테이너

데이터를 미리 정해진 방식에 따라 관리 ( stack(LIFO), queue(FIFO), ... )

시퀀스 컨테이너를  변형시켜 스택, 큐, 우선순위 큐 형태로 저장함

---

 

• pair: 간단한 연관 컨테이너로 순서에 따라 first, second로 불리는 객체로 구성되어 배치, 복사, 비교될 수 있음. first 요소는 컨테이너 내 유니크 키로 작동하며 pair는 map이나 hash_map(C++11이후 unordered_map)에 기본값으로 쓰임

pair의 쓰임

2 개의 데이터를 저장할 수 있는 변수. 비교 연산시 1순위를 first / 2순위를 second로 판별

#include <iostream>
#include <utility>
using namespace std;
int main(){
	//int, int 자료형을 저장하는 변수 선언
	pair<int, int=""> p;
	//(4, 5)를 p에 저장
	p=make_pair(4, 5);
	//c++11부터 가능
	p={4, 5};
	return 0;
}

 

 

• vector: C의 배열과 거의 비슷하게 사용할 수 있는 시퀀스 컨테이너(동적 배열). 끝 위치에 원소를 삽입과 삭제, 랜덤 위치 참조시 O(1)로 매우 효율적임. 하지만, 삽입하고 삭제하는 부분이 끝 부분이 아니라면 O(n)의 시간 복잡도

vector의 쓰임

동적 배열로 임의의 위치에 있는 원소 접근과 뒤에 원소를 추가하는 연산은 O(1)을 보장함

#include <iostream>
#include <vector>
using namespace std;
int main(){
	//int 자료형을 저장하는 동적배열
	vector<int> vec1;
	//double 자료형을 저장하는 동적배열
	vector<double> vec2;
	//사용자가 정의한 Node 구조체를 저장하는 동적배열
	vector<node> vec3;
	//벡터의 초기 크기를 n으로 설정
	vector<int> vec4(n);
	//벡터의 초기 크기를 n으로 설정하고 1로 초기화
	vector<int> vec5(n, 1);
	//크기가 n*m인 2차원 벡터를 선언하고 0으로 초기화
	vector<vector<int> > vec6(n, vector<int>(m, 0));
	//벡터의 맨 뒤에 원소(5) 추가
	vec1.push_back(5);
	//벡터의 맨 뒤 원소 삭제
	vec1.pop_back();
	//벡터의 크기 출력
	printf("%d\n", vec1.size());
	//벡터의 크기를 n으로 재설정
	vec1.resize(n);
	//벡터의 모든 원소 삭제
	vec1.clear();
	//벡터의 첫 원소의 주소, 마지막 원소의 다음 주소 리턴
	vec1.begin();
	vec1.end();
	//[a, b) 주소 구간에 해당하는 원소 삭제
	vec1.erase(vec1.begin(), vec1.end());//모든 원소 삭제
	//vec7은 vec1의 2번째 원소부터 마지막 원소까지 복사하여 생성
	vector<int> vec7=vector<int>(vec1.begin()+2, vec1.end());
	return 0;
}

 

 

• array: vector와 달리 고정 길이의 배열을 표현할 때 사용하는 시퀀스 컨테이너. 기존 배열과 마찬가지로 스택에 저장됨. 적은 양의 자료에 유리하지만 고정된 길이라는 한계 때문에 크기 변경이 불가능

 

 

• stack: LIFO형식(후입선출)으로 구성된 자료구조로 마지막으로 삽입된 요소가 top에 존재

stack의 쓰임

#include <iostream>
#include <stack>
using namespace std;
int main(){
	//int자료형을 저장하는 스택 생성
	stack<int> st;
	//원소(4) 삽입
	st.push(4);
	//맨 위 원소 팝
	st.pop();
	//맨 위 원소 값 출력
	printf("%d\n", st.top());
	//스택이 비어있다면 1 아니면 0
	printf("%d\n", st.empty());
	//스택에 저장되어 있는 원소의 수 출력
	printf("%d\n", st.size());
	return 0;
}

 

 

• queue: FIFO형식(선입선출)으로 구성된 자료구조

queue의 쓰임

#include <iostream>
#include <queue>
using namespace std;
int main(){
	//int자료형을 저장하는 큐 생성
	queue<int> q;
	//원소(4) 삽입
	q.push(4);
	//맨 위 원소 팝
	q.pop();
	//맨 위 원소 값 출력
	printf("%d\n", q.front());
	//큐가 비어있다면 1 아니면 0
	printf("%d\n", q.empty());
	//큐에 저장되어 있는 원소의 수 출력
	printf("%d\n", q.size());
	return 0;
}

• priority_queue: 우선순위 queue로 높은 우선순위를 가진 요소가 상위에 위치함(값이 크면 top에 위치)

 

 

• deque: 맨 앞, 맨 뒤에서 모두 O(1)로 삽입 및 삭제가 가능함 (동적 배열). 다만, 메모리 상에서 연속적으로 저장하지 않기 때문에 반복자(Iterator)를 사용할 때 유효성을 보장하지 않음

deque의 쓰임

#include <iostream>
#include <deque>
using namespace std;
int main(){
	//int 자료형을 저장하는 동적배열 생성
	deque<int> dq;
	//배열 맨 앞에 원소(5) 추가
	dq.push_front(5);
	//배열 맨 뒤에 원소(5) 추가
	dq.push_back(5);
	//배열 맨 앞의 원소 삭제
	dq.pop_front();
	//배열 맨 뒤의 원소 삭제
	dq.pop_back();
	//나머지는 vector와 동일하다.
	return 0;
}

 

 

• list (양방향) / forward_list (단방향): 연결 리스트로 탐색과 접근에 있어서 느리지만 위치를 안다면 빠르게 삽입 및 삭제할 수 있음. forward_list는 단방향 연결 리스트로 탐색을 할 때 후진이 불가능함

list의 쓰임

#include <iostream>
#include <list>
using namespace std;
int main(){
	list<int> l;
	// push_back
	l.push_back(5);
	l.push_back(6);
	l.push_back(7);
	l.push_back(8);
	l.push_back(9);
	l.push_back(10);
	// pop_back
	l.pop_back();
	// push_front
	l.push_front(4);
	l.push_front(3);
	l.push_front(1);
	l.push_front(0);
	// pop_front
	l.pop_front();
	// back and front
	cout << "list front value : " << l.front() << '\n';
	cout << "list end value : " << l.back() << '\n';
	// size
	cout << "list size : " << l.size() << '\n';
	// empty
	cout << "Is it empty? : " << (l.empty() ? "Yes" : "No") << '\n';
	// iterator
	list<int>::iterator begin_iter = l.begin(); // auto begin_iter = l.begin()도 가능
	list<int>::iterator end_iter = l.end(); // auto end_iter = l.end()도 가능
	// insert
	begin_iter++; // 2번째를 가리키는 iterator
	l.insert(begin_iter, 2);
	// erase
	end_iter--; // 마지막 원소를 가리키는 iterator
	l.erase(end_iter);
	// *iterator : 원소 접근
	cout << "list "<< distance(l.begin(), begin_iter)+ 1 << " element : " << *begin_iter << '\n';
	return 0;
}

 

 

• set / multiset: 이진 탐색 트리를 기반으로 삽입할 때부터 자동으로 정렬이 됨. 각종 집합 연산이 가능하고 set의 경우 정렬시 사용되는 값이 유일해야 함(key만 저장하기 때문), multiset은 정렬 시 사용되는 값이 유일하지 않아도 됨(key값이 중복될 수 있음)

set의 쓰임

균형잡힌 이진트리, 원소 삽입과 삭제, 탐색 등의 연산은 O(log n)을 보장

#include <iostream>
#include <set>
using namespace std;
int main(){
	//int 자료형을 저장하는 균형잡힌 이진트리 생성
	set<int> s;
	//원소(5) 삽입
	s.insert(5);
	//6값을 가지는 원소를 찾음 있다면 해당 원소의 주소값,  없다면 s.end()리턴
	if(s.find(6)!=s.end())
		printf("존재합니다.\n");
	else
		printf("없습니다.\n");
	//저장된 원소의 수를 리턴
	printf("%d\n", s.size());
	//모든 원소 삭제
	s.clear();
	//해당 주소의 원소 삭제
	//2번째 원소 삭제
	s.erase(++s.begin());
	return 0;
}

 

 

• map / multimap: set과 유사하게 이진 탐색 트리 기반으로 자동 정렬이 되지만 key만 저장되는 set과 달리 key-value값으로 구성(pair형태)됨. key값은 유일해야 하지만 value값은 유일하지 않아도 됨 (multimap에서 key값은 유일하지 않아도 됨)

map의 쓰임

딕셔너리 자료구조로 원소 삽입과 삭제, 탐색 등의 연산은 O(log n)을 보장함

#include <iostream>
#include <map>
using namespace std;
int main(){
	//int 자료형을 key로 int 자료형을 데이터로 저장하는 딕셔너리 자료구조 생성
	map<int, int=""> m;
	//(4, 5)원소 삽입
	m.insert(make_pair(4, 5));
	//또는
	m[4]=5;
	//key와 연관된 원소를 pair<키 자료형, 데이터 자료형> 형태로 리턴함
	printf("%d\n", m.find(4).second);
	//key와 연관된 원소의 개수를 리턴함
	printf("%d\n", m.count(4));
	//저장된 원소의 수를 리턴함
	printf("%d\n", m.size());
	//모든 원소 삭제
	m.clear();
	//해당 주소의 원소 삭제
	m.erase(++m.begin());
	return 0;
}

 

• unordered_set / unordered_map / unordered_multiset / unordered_multimap: set, map의 개념적으로는 동일하지만 트리 대신 hash를 이용해 구현된 컨테이너. 삽입, 삭제, 탐색시 트리의 시간복잡도를 따르지 않고 해시의 특성을 따름 (삽입, 삭제, 탐색시 최적 O(1) / 최악 O(n))

---

▶  반복자 (Iterator)

: 컨테이너 원소를 순회하는 방법을 추상화한 객체

반복자를 이용하면 STL 내부의 자료에 접근하는 방법을 표준화 할 수 있음

즉, 반복자를 사용해 컨테이너 내 원소들에 접근할 수 있음

---

• input iterator (입력 반복자) : 현 위치의 원소를 한 번만 읽을("read") 수 있는 반복자를 말함 (ex. istream)
• output iterator (출력 반복자) : 현 위치의 원소를 한 번만 쓸("write") 수 있는 반복자를 말함 (ex. ostream)
• forward iterator (순방향 반복자) : 입출력 반복자 기능과 순방향으로 이동이 가능하고 재할당될 수 있는 반복자
• bidirectional iterator (양방향 반복자) : 순방향 반복자 기능과 역방향까지 이동이 가능한 반복자
  • list, set, multiset, map, multimap

 

• random access iteraotr (임의 접근 반복자) : 양방향 반복자 기능에 +, -, +=, -=, [] 연산까지 가능한 반복자
  • vector, deque

 

 

---

▶  알고리즘 (algorithm)

: 정렬, 삭제, 탐색 연산 등의 활동을 수행하는 작업을 정의해 놓은 템플릿 함수

---

• sort: 정렬하는 함수
• find: 검색하는 함수
• transform: 변경하는 함수
• for_each: first부터 last까지 각각의 원소들에 대해 함수를 실행하는 함수
• generate: 생성하는 함수
• binary_search: 이진 탐색법으로 탐색하는 함수

 

algorithm의 쓰임

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(const int a, const int b){
	return a>b;
}

int main(){

	int arr1[100000];
	vector<int> arr2[100000];
	int n=100000;

	//sort
	//첫 원소의 주소와 마지막 원소의 다음 주소를 인자로 넘겨준다.
	sort(arr1, arr1+n);
	sort(arr2.begin(), arr2.end());
	//비교 함수도 만들어서 같이 넘겨줄 수 있다.
	sort(arr1, arr1+n, cmp);

	//stable_sort
	//사용법은 같다.
	stable_sort(arr1, arr1+n);

	//lower_bound
	//첫 원소의 주소와 마지막 원소의 다음 주소와 비교할 원소를 넘겨준다.
	//구간내의 원소들은 정렬되어 있어야한다.
	//리턴 값은 해당 원소의 주소값이다. 없다면 arr1+n을 리턴한다.
	//또는 arr2.end()를 리턴한다.
	int idx=lower_bound(arr1, arr1+n, 42)-arr1;
	printf("%d\n", idx);

	//upper_bound
	//사용법은 같다.
	vector<int>::iterator it=upper_bound(arr2.begin(), arr2.end(), 54);
	if(it!=arr2.end())
		printf("%d\n", *it);

	//max_element
	//첫 원소의 주소와 마지막 원소의 다음 주소를 인자로 넘겨준다.
	//구간내의 최대값을 가지는 원소의 주소를 리턴한다.
	printf("%d\n", *max_element(arr1, arr1+n));

	//min_element
	//사용법은 같다.
	printf("%d\n", *min_element(arr2.begin(), arr2.end()));

	//unique
	//첫 원소의 주소와 마지막 원소의 다음 주소를 인자로 넘겨준다.
	//구간내의 중복된 원소를 구간의 끝부분으로 밀어주고 마지막 원소의 다음 주소를 리턴한다.
	//구간내의 원소들은 정렬되어 있어야한다.
	//보통 erase와 함께 중복된 원소를 제거하는 방법으로 사용한다.
	arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());

	//next_permutation
	//첫 원소의 주소와 마지막 원소의 다음 주소를 인자로 넘겨준다.
	//구간내의 원소들의 다음 순열을 생성하고 true를 리턴한다.
	//다음 순열이 없다면 false를 리턴한다.
	//구간내의 원소들은 정렬되어 있어야한다.
	int arr[10];
	for(int i=0;i<10;i++)
		arr[i]=i;
	do{
		for(int i=0;i<10;i++)
			printf("%d ", arr[i]);
		printf("\n");
	}while(next_permutaion(arr, arr+10));

	return 0;
}

 

 

 

---

※ 참고 1: https://eehoeskrap.tistory.com/246
※ 참고 2: https://ssocoit.tistory.com/24
※ 참고 3: C++ 기초플러스 6판 (저자: Stephen Prata)