C++ 주요 알고리즘과 연산자 용법

 

 

 

C++ 주요 자료구조(set, vector 등) 및 연산자 용법

 

C++을 공부하면서 주요 자료구조에 대해 정리가 필요하여 아래와 같이 정리해보았습니다.

티스토리 포스팅 가로 간격 제한으로 인해 아래와 같이 쪼개져 있음을 감안하고 보시길 바랍니다.

 

---

1. 주요 자료구조

자료구조	헤더 파일	선언 방법	초기화 방법
set	<set>	std::set<T> s;	std::set<T> s = {1, 2, 3};
multiset	<set>	std::multiset<T> ms;	std::multiset<T> ms = {1, 2, 3};
unordered_set	<unordered_set>	std::unordered_set<T> us;	std::unordered_set<T> us = {1, 2, 3};
map	<map>	std::map<Key, T> m;	std::map<Key, T> m = {{1, "a"}, {2, "b"}};
unordered_map	<unordered_map>	std::unordered_map<Key, T> um;	std::unordered_map<Key, T> um = {{1, "a"}, {2, "b"}};
queue	<queue>	std::queue<T> q;	std::queue<T> q(std::deque<T>{1, 2, 3});
deque	<deque>	std::deque<T> dq;	std::deque<T> dq = {1, 2, 3};
stack	<stack>	std::stack<T> st;	std::stack<T> st(std::deque<T>{1, 2, 3});
vector	<vector>	std::vector<T> v;	std::vector<T> v = {1, 2, 3};
array	<array>	std::array<T, N> arr;	std::array<T, N> arr = {1, 2, 3};
list	<list>	std::list<T> lst;	std::list<T> lst = {1, 2, 3};

 

 

 

자료구조	삽입	삭제	탐색
set	s.insert(value);	s.erase(value);	s.find(value);
multiset	ms.insert(value);	ms.erase(value);	ms.find(value);
unordered_set	us.insert(value);	us.erase(value);	us.find(value);
map	m.insert({key, value});	m.erase(key);	m.find(key);
unordered_map	um.insert({key, value});	um.erase(key);	um.find(key);
queue	q.push(value);	q.pop();	q.front();
deque	dq.push_back(value); dq.push_front(value);	dq.pop_back(); dq.pop_front();	dq.at(index); dq[index];
stack	st.push(value);	st.pop();	st.top();
vector	v.push_back(value);	v.erase(it);	v.at(index); v[index];
array	arr[index] = value;	arr[index] = T();	arr.at(index); arr[index];
list	lst.push_back(value);	lst.erase(it);	std::find(lst.begin(), lst.end(), value);

 

 

자료구조	크기	공백 여부 확인	시간복잡도
			삽입	삭제	탐색
set	s.size();	s.empty();	O(log n)	O(log n)	O(log n)
multiset	ms.size();	ms.empty();	O(log n)	O(log n)	O(log n)
unordered_set	us.size();	us.empty();	O(1) (평균) / O(n) (최악)	O(1) (평균) / O(n) (최악)	O(1) (평균) / O(n) (최악)
map	m.size();	m.empty();	O(log n)	O(log n)	O(log n)
unordered_map	um.size();	um.empty();	O(1) (평균) / O(n) (최악)	O(1) (평균) / O(n) (최악)	O(1) (평균) / O(n) (최악)
queue	q.size();	q.empty();	O(1)	O(1)	O(1)
deque	dq.size();	dq.empty();	O(1)	O(1)	O(1)
stack	st.size();	st.empty();	O(1)	O(1)	O(1)
vector	v.size();	v.empty();	O(1) (평균) / O(n) (최악)	O(n)	O(1)
array	arr.size();	arr.empty(); (없음, 항상 false)	O(1)	O(1)	O(1)
list	lst.size();	lst.empty();	O(1)	O(1)	O(n)

 

 

2. 주요 알고리즘 및 연산자

알고리즘/연산자	기능	시간 복잡도
unique	연속된 중복 요소를 제거하고, 새로운 끝을 반환	O(n)
sort	범위 [first, last)를 정렬	O(n log n)
count	범위 [first, last)에서 value의 개수를 반환	O(n)
iterator	컨테이너 요소를 순회할 수 있는 반복자 생성	O(1)
find	범위 [first, last)에서 value를 찾고, 반복자를 반환	O(n)
binary_search	정렬된 범위에서 이진 검색으로 value가 있는지 확인	O(log n)
reverse	범위 [first, last)의 요소 순서를 반대로 뒤집음	O(n)
next_permutation	범위 [first, last)를 다음 순열로 변경	O(n)
prev_permutation	범위 [first, last)를 이전 순열로 변경	O(n)
accumulate	범위 [first, last)의 요소를 초기값 init에 더함	O(n)
distance	두 반복자 first와 last 사이의 거리 반환	O(1) (랜덤 접근) / O(n) (기타)
copy	범위 [first, last)의 요소를 d_first로 복사	O(n)
remove	범위 [first, last)에서 value와 같은 요소 제거	O(n)
lower_bound	정렬된 범위에서 value 이상 첫 위치 반환	O(log n)
upper_bound	정렬된 범위에서 value 초과 첫 위치 반환	O(log n)
equal_range	정렬된 범위에서 value의 하한과 상한 범위 반환	O(log n)
merge	두 정렬된 범위를 병합하여 d_first로 저장	O(n)
includes	정렬된 범위1이 범위2의 모든 요소를 포함하는지 확인	O(n)

 

알고리즘/연산자	헤더 파일	선언 방법	사용 방법
unique	<algorithm>	std::unique	std::unique(first, last);
sort	<algorithm>	std::sort	std::sort(first, last);
count	<algorithm>	std::count	std::count(first, last, value);
iterator	<iterator>	std::iterator	auto it = container.begin();
find	<algorithm>	std::find	std::find(first, last, value);
binary_search	<algorithm>	std::binary_search	std::binary_search(first, last, value);
reverse	<algorithm>	std::reverse	std::reverse(first, last);
next_permutation	<algorithm>	std::next_permutation	std::next_permutation(first, last);
prev_permutation	<algorithm>	std::prev_permutation	std::prev_permutation(first, last);
accumulate	<numeric>	std::accumulate	std::accumulate(first, last, init);
distance	<iterator>	std::distance	std::distance(first, last);
copy	<algorithm>	std::copy	std::copy(first, last, d_first);
remove	<algorithm>	std::remove	std::remove(first, last, value);
lower_bound	<algorithm>	std::lower_bound	std::lower_bound(first, last, value);
upper_bound	<algorithm>	std::upper_bound	std::upper_bound(first, last, value);
equal_range	<algorithm>	std::equal_range	std::equal_range(first, last, value);
merge	<algorithm>	std::merge	std::merge(first1, last1, first2, last2, d_first);
includes	<algorithm>	std::includes	std::includes(first1, last1, first2, last2);