C++ 알고리즘용 STL 정리

0. array

c언어의 배열을 사용해도 되지만, c++에서의 array 컨테이너도 있다.

at 메서드를 지원하므로 try catch문으로 경계값 검사를 실행할 수 있다.

또한 STL의 다른 컨테이너와 함수들과 호환이 된다.

template < class T, size_t N > 
class array;

생성자

커스텀 생성자는 없다.

그냥 std::array<int, 3> arr; 로 사용한다.

메서드

// <capacity>
size_type size();
bool empty();

// <element access>
reference operator[](size_type n);
reference at ( size_type n ); // out_of_range exception
reference back();
reference front();

// <iterator access>
iterator begin();
iterator end();
reverse_iterator rbegin();
reverse_iterator rend();

// <fill>
void fill (const value_type& val);

주의

다른 컨테이너와 달리 operator= 오버로딩이 없으므로 array 객체간에 대입이 불가능하다.

1. string

생성자

// 1. default
string();

// 2. copy
string(const string& str);

// 3. substring
string(const string& str, size_t pos, size_t len = npos);

// 4. fill
string(size_t n, char c);

// 5. range
template<class InputIterator> 
string(InputIterator first, InputIterator last);

타입 변환

// 문자열에서 다른 타입으로
// 예외 발생하니 주의
int stoi(const string& str);
long stol(const string& str);
long long stoll(const string& str);
unsigned long stoul(const string& str);
unsigned long long stoull(const string& str);
double stod(const string& str);
long double stold(const string& str);

// 다른 타입에서 문자열로
string to_string(int val);
string to_string(long val);
string to_string(long long val);
string to_string(unsigned val);
string to_string(unsigned long val);
string to_string(unsigned long long val);
string to_string(double val);
string to_string(long double val);

메서드

// <capacity>
size_t size() const
bool empty() const

// <element access>
char& operator[](size_t pos);
char& at(size_t pos); // out_of_range exception
char& back();
char& front();

// <iterator access>
iterator begin();
iterator end();
reverse_iterator rbegin();
reverse_iterator rend();

// <삽입>
string& operator+=(const string& str);
string& operator+=(const char* s);
string& operator+=(char c);
string& insert(size_t pos, const string& str);
string& insert(size_t pos, const char* s);

// <삭제>
// sequence 삭제, 반환값: *this
string& erase(size_t pos = 0, size_t len = npos);
// charater 삭제
// 반환값은 삭제된 첫 글자의 위치를 차지하는 문자의 iterator, 없으면 string::end
iterator erase(const_iterator p);
// range 삭제
iterator erase(const_iterator first, const_iterator last);
// 맨 뒤 문자 삭제
void pop_back();
// 전체 삭제
void clear();

// <치환>
string& replace(size_t pos, size_t len, const string& str);
string& replace(size_t pos, size_t len, const char* s);
string& replace(const_iterator i1, const_interator i2, const string& str);
string& replace(const_iterator i1, const_interator i2, const char* s);
template <class InputIterator> 
string& replace(const_iterator i1, const_iterator i2, InputIterator first, InputIterator last);

// <c문자열로 변환>
const char* c_str() const;

// <검색>
// 없을 시 string::npos 반환
size_t find(const string& str, size_t pos = 0) const;
size_t find(const char* s, size_t pos = 0) const;
size_t find(char c, size_t pos = 0) const;

// <부분 문자열>
string substr(size_t pos = 0, size_t len = npos) const;

// <비교>
// ==, !=, <, <=, >, >=

// <입력>
// 구분문자(기본은 줄바꿈) 또는 파일끝에 도달하면 추출 중지.
// 구분문자는 추출되어 삭제.
istream& getline(istream& is, string& str, char delim);
istream& getline(istream& is, string& str);

// <새 값으로 할당>
string& operator=(const string& str);
string& operator=(const char* s);
string& operator=(char c);

2. vector

template < class T, class Alloc = allocator<T> > 
class vector;

생성자

// 1. default
vector();

// 2. fill, 
// allocator_type()는 std의 기본 메모리 할당자.
// 해당 매개변수는 생략해도 됨.
vector(size_type n, const allocator_type& alloc = allocator_type());
vector(size_type n, const value_type& val, const allocator_type& alloc = allocator_type());

// 3. range
template<class InputIterator> 
vector(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());

// 4. copy
vector(const vector& x)

메서드

// <capacity>
size_type size() const
bool empty() const

// <element access>
reference at(size_type n); // out_of_range exception
reference operator[](size_type n); 
reference back();
reference front();

// <iterator access>
iterator begin();
iterator end();
reverse_iterator rbegin();
reverse_iterator rend();

// <삽입>
void push_back(const value_type& val);
// single element
// 반환값은 새로 삽입된 요소 중 첫 번째 요소를 가리키는 반복자
iterator insert(const_iterator position, const value_type& val);
// fill
iterator insert(const_iterator position, size_type n, const value_type& val);
// range
templacte<class InputIterator>
iterator insert(const_iterator position, InputIterator first, InputIterator last);


// <삭제>
void pop_back();
// 반환값은 삭제된 마지막 요소의 다음에 오는 요소의 새 위치
// 시퀀스의 마지막요소가 삭제된 경우 컨테이너의 끝
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
// 전체 삭제
void clear();

// <비교>
// ==, !=, >, >=, <, <=

// <새 값으로 할당>
// 현재 콘텐츠를 대체하고 크기도 적절히 조정됨
vector& operator=(const vector& x);

3. list

template < class T, class Alloc = allocator<T> > 
class list;

생성자

// 1. default
list();

// 2. fill
list(size_type n, const allocator_type& alloc = allocator_type());
list(size_type n, const value_type& val, const allocator_type& alloc = allocator_type());

// 3. range
template<class InputIterator> list(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());

// 4. copy
list(const list& x);

메서드

vector 메서드와 동일하다고 생각하자.

list 만의 메서드가 존재하지만 STL 함수를 이용하면 되기때문에 코딩테스트 목적이면 굳이 알 필요가 없다.

단, vector의 인덱스 접근 연산자는 없다.

당연하다. Linked List의 특징을 생각해보자.

3. stack

template <class T, class Container = deque<T> > 
class stack;

생성자

stack (const container_type& ctnr);

메서드

size_type size();
bool empty();
void push(const value_type& val);
void pop();
reference top();

4. queue

template <class T, class Container = deque<T> > 
class queue;

생성자

queue (const container_type& ctnr);

메서드

size_type size();
bool empty();
void push (const value_type& val)
void pop();
reference front(); 
reference back();

5. deque

template < class T, class Alloc = allocator<T> > 
class deque;

생성자

// 1. default
deque(const allocator_type& alloc = allocator_type());

// 2. fill
deque(size_type n);
deque(size_type n, const value_type& val, const allocator_type& alloc = allocator_type());

// 3. range
template <class InputIterator>  
deque (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());

// 4. copy
deque (const deque& x);

메서드

deque만의 특징을 살린 메서드는 다음과 같다.

void pop_back();
void pop_front();
void push_back (const value_type& val);
void push_front (const value_type& val);

나머지는 vector와 동일하다고 생각하자.

6. priority_queue

template <class T, class Container = vector<T>,  class Compare = less<typename Container::value_type> > 
class priority_queue;

생성자

// 1. initialize
priority_queue (const Compare& comp, const Container& ctnr);

// 2. range
template <class InputIterator>  
priority_queue (InputIterator first, InputIterator last, const Compare& comp, const Container& ctnr);

메서드

size_type size();
bool empty();
void push (const value_type& val);
void pop();
const_reference top();

커스텀 비교

struct myLess{
    bool operator()(const int& a, const int& b){ return a < b;}
};
priority_queue<int, vector<int>, myLess> pq;

priority_queue의 마지막 타입인수는 구조체(클래스) 타입이다.

해당 구조체는 ()연산자를 오버로딩하는 메서드가 있어야 한다.

이 메서드는 비교할 두 요소를 const 매개변수로 받고 bool을 반환한다.

7. map

레드블랙트리 기반이다.

template <
    class Key,                              // 키 타입
    class T,                                // 값 타입
    class Compare = less<Key>,              // 키 비교 함수 (기본: 오름차순)
    class Alloc = allocator<pair<const Key, T>> // 메모리 할당자
>
class map;

생성자

// 1. emtpy
map();
map(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());

// 2. range
template <class InputIterator> 
map(InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());

// 3. copy
map(const map& x);

메서드

// <capacity>
size_type size();
bool empty();

// <조회>
// 개수 조회 (0 또는 1)
size_type count (const key_type& k);
// 범위 조회 
// lowerbound, upperbound의 쌍 (마찬가지로 범위의 요소 개수는 0또는 1)
pair<iterator,iterator> equal_range (const key_type& k);
// 값 위치 조회
// 없으면 map::end 를 반환한다.
iterator find (const key_type& k);
// lowerbound, 해당안되면 map::end을 반환한다.
iterator lower_bound (const key_type& k);
// upperbound
iterator upper_bound (const key_type& k);

// <element access>
mapped_type& at (const key_type& k); // out_of_range exception
// 없으면 자동할당을 해버리니 주의
mapped_type& operator[](const key_type& k);

// <iterator access>
iterator begin();
iterator end();

// <삽입>
// single element
// 멤버 유형 value_type은 컨테이너의 요소 유형으로, map에서 pair<const key_type,mapped_type>으로 정의된다
// 성공시에 {해당 요소의 위치, true} 를 반환한다.
// 실패시에 {해당 키를 갖는 요소의 위치, false}를 반환한다.
pair<iterator, bool> insert(const value_type& val);
// range
template <class InputIterator>  
void insert (InputIterator first, InputIterator last);

// <삭제>
// 삭제된 요소 개수를 반환한다.
size_type erase(const key_type& k);
// 삭제된 요소 다음의 위치에 해당하는 요소에 대한 반복자를 반환한다.
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
// 전체 삭제
void clear();

// <비교>
// begin()부터 end()까지 pair<key, value>의 비교 알고리즘으로 비교
==, !=, <, <=, >, >= 

// <할당>
map& operator= (const map& x);

8. set

레드블랙트리 기반이다.

template <
    class T,                             // 집합의 원소 타입 (key와 value가 동일)
    class Compare = std::less<T>,        // 정렬 기준 (기본: 오름차순)
    class Alloc = std::allocator<T>      // 메모리 할당자
>
class set;

생성자

// 1. emtpy
set();
set(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());

// 2. range
template <class InputIterator> 
set(InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());

// 3. copy
set(const set& x);

메서드

map의 메서드에서 key대신 val만 바뀔뿐 나머지는 동일하다.

insert같은 경우는 매개변수에 pair가 아닌 val이 전달된다.

9. multimap, multiset

중복값도 허용한다는 점을 제외하고 map과 set과 같다.

10. unordered_map

해시테이블 기반이다.

template <
    class Key,                              // 키 타입
    class T,                                // 값 타입
    class Hash = std::hash<Key>,            // 해시 함수 객체
    class Pred = std::equal_to<Key>,        // 키 비교 함수 (동등성 판단)
    class Alloc = std::allocator<std::pair<const Key, T>> // 메모리 할당자
>
class unordered_map;

생성자

// 1. empty
unordered_map();
unordered_map( size_type n, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type());

// 2.copy
unordered_map ( const unordered_map& ump );

메서드

map은 레드블랙트리이고, unordered_map은 해시테이블이므로 내부 자료구조를 조정하는 전용 메서드들이 따로 있지만, 코딩테스트를 위해서는 그런 메서드들은 알 필요가 없다.

• count
• find
• operator[]
• insert
• erase
• clear
• size

정도만 사용되는데 이는 map과 같다.

11. unordered_set

대충 느낌오니까 생략

12. 정렬

정렬

// 기본
template <class RandomAccessIterator>  
void sort (RandomAccessIterator first, RandomAccessIterator last);

// 커스텀
template <class RandomAccessIterator, class Compare>  
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

커스텀 정렬에서 마지막 매개변수를 보면 Compare comp이다.

이는 class 타입이 아니고 해당 클래스로부터 생성된 인스턴스 타입이다.

struct myCompare{
    bool operator()(const int& a, const int& b){
        return a < b;
    }
};
sort(v.begin(), v.end(), myCompare());

안정 정렬

// 기본
template <class RandomAccessIterator>  
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last);

// 커스텀
template <class RandomAccessIterator, class Compare>  
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

순열

STL을 변경해가며 상태유지를 하므로 시작전에 꼭 미리 오름차순 정렬되어야 한다.

template <class BidirectionalIterator>  
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

선택 알고리즘

퀵 소트 할때 선택 알고리즘이 이용된다.

해당 값을 기준으로 작은 값을은 앞쪽, 큰 값들은 뒤쪽으로 보내는 알고리즘이다.

원래 구현해야하는데 C++은 STL로 지원한다.

template <class RandomAccessIterator>  
void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

13. 탐색

find

못찾으면 last 반환

template <class InputIterator, class T>   
InputIterator find (InputIterator first, InputIterator last, const T& val);

binary_search

범위내에 값이 존재하는지를 판단한다.

어느 위치에 있는지는 모른다.

당연히 사전에 정렬이 되어있어야 한다.

template <class ForwardIterator, class T>  
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val);

lower_bound, upper_bound

당연히 사전에 정렬이 되어 있어야 한다.

{1, 1, 2, 2, 2, 3, 3} 라는 컨테이너가 있다고 치자

/	1	1	2	2	2	3	3
위치	0	1	2	3	4	5	6

lower_bound(2)는 값이 2이상인 인덱스 중 첫 번째 인덱스를 반환한다.

upper_bound(2)는 값이 2초과인 인덱스 중 첫 번째 인덱스를 반환한다.

template <class ForwardIterator, class T>  
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);

template <class ForwardIterator, class T>  
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);

equal_range

template <class ForwardIterator, class T>
pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val);

14. 집계

반환타입인 iterator_traits<InputIterator>::difference_type 는 부호있는 정수 타입이다.

template <class InputIterator, class T>  
typename iterator_traits<InputIterator>::difference_type count (InputIterator first, InputIterator last, const T& val);

15. 제거 및 유니크 처리

컨테이너의 erase 메서드와 같이 사용해야 "진짜" 삭제가 된다.

아래의 remove는 "가짜" 삭제이다.

remove

val을 제일 뒤로 보냄.

고로 실제로 삭제되는건 아님.

반환값은 제거되지 않은 마지막 요소의 다음 번째 위치이다.

template <class ForwardIterator, class T>  
ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val);

unique

중복 값들을 제거한다.

단, 사전에 오름차순으로 정렬되어 있어야 한다.

반환값은 제거되지 않은 마지막 요소의 다음 번째 위치이다.

template <class ForwardIterator>  
ForwardIterator unique (ForwardIterator first, ForwardIterator last);

16. 최소/최대

min_element

// default
template <class ForwardIterator>  
ForwardIterator min_element (ForwardIterator first, ForwardIterator last);

// custom
template <class ForwardIterator, class Compare>  
ForwardIterator min_element (ForwardIterator first, ForwardIterator last, Compare comp);

max_element

// default
template <class ForwardIterator>  
ForwardIterator max_element (ForwardIterator first, ForwardIterator last);

// custom
template <class ForwardIterator, class Compare>  
ForwardIterator max_element (ForwardIterator first, ForwardIterator last, Compare comp);

minmax_element

// default
template <class ForwardIterator>
pair<ForwardIterator,ForwardIterator> minmax_element (ForwardIterator first, ForwardIterator last);

// custom
template <class ForwardIterator, class Compare>
pair<ForwardIterator,ForwardIterator> minmax_element (ForwardIterator first, ForwardIterator last, Compare comp);

min

// default
template <class T> 
const T& min (const T& a, const T& b);

// custom
template <class T, class Compare>  
const T& min (const T& a, const T& b, Compare comp);

// initializer list 
template <class T> 
T min (initializer_list<T> il);
template <class T, class Compare>  
T min (initializer_list<T> il, Compare comp);

initializer_list는 C++에서 복사 및 할당할때 암묵적으로 생성되는 const T 유형의 요소를 갖는 C++의 초기화 목록이다.

auto il = { 10, 20, 30 } 처럼 사용하면 된다.

max

// default
template <class T> 
const T& max (const T& a, const T& b);

// custom
template <class T, class Compare>  
const T& max (const T& a, const T& b, Compare comp);

// initializer list 
template <class T> 
T max (initializer_list<T> il);
template <class T, class Compare>  
T max (initializer_list<T> il, Compare comp);

17. 순서변경 및 복사

reverse

내부적으로 swap 메서드를 이용하므로 컨테이너 내부에 swap이 정의되어 있어야 한다.

template <class BidirectionalIterator>  
void reverse (BidirectionalIterator first, BidirectionalIterator last);

copy

원본과 범위가 겹치면 안된다.

복사한 값들을 집어넣을 컨테이너의 공간이 부족하면 안된다.

template <class InputIterator, class OutputIterator>  
OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result);

fill

template <class ForwardIterator, class T>  
void fill (ForwardIterator first, ForwardIterator last, const T& val);

rotate

내부적으로 swap이 정의되어 있어야 한다.

template <class ForwardIterator>  
ForwardIterator rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last);

{1, 2, 3, middle, 8, 9} 가 있다고 가정하자.

결과는

{middle, 8, 9, 1, 2, 3} 이 된다.

반환 값은 이전에 first가 가리켰던 값을 가리키는 반복자이다.

이터레이터 제어

STL에서 사용되는 이터레이터를 직접 제어할 수 있다.

이터레이터 이동 함수 요약

<함수 이름>	<방향>	<원본 변경 여부>	<반환값>
next(it, n)	앞	NO	이터레이터
prev(it, n)	뒤	NO	이터레이터
it++ / ++it	앞	YES	이터레이터
it-- / --it	뒤	YES	이터레이터
advance(it, n)	양방향	YES	X
distance(it1, it2)	계산용	NO	정수

단항 연산자와 컨테이너별 이터레이터 종류

<컨테이너>	<이터레이터 종류>
vector	Random Access Iterator
deque	Random Access Iterator
list	Bidirectional Iterator
array	Random Access Iterator
map / set	Bidirectional Iterator
forward_list	Forward Iterator

함수별 적용 가능 여부 요약

<함수 이름>	<적용 가능 컨테이너>
++it / --it	대부분 가능 (단, --it은 Forward Iterator에서 ❌)
next	모든 이터레이터
prev	Bidirectional 이상만 가능
advance	모든 이터레이터에서 사용 가능
distance	모든 이터레이터에서 사용 가능
it + n	Random Access만 가능

실전 팁

• vector, deque, array는 Random Access ➡️ 모든 연산 가능
• map, set은 Bidirectional Iterator ➡️ it + n 빼고 모두 OK
• unordered_map, unordered_set, forward_list는 Forward Iterator ➡️ 앞으로만 가는 이터레이터라서 --, prev 가 불가능, it + n도 불가능

기억법

이터레이터의 종류가 곧 연산의 한계다.

STL 컨테이너마다 이터레이터가 다르기 때문에, 연산 가능 여부는 컨테이너가 아니라 이터레이터 타입에 따라 결정된다.