PS 하면서 알면 좋은 STL들

Range Iteration(범위 반복)

C++의 모든 container들은 range iteration을 통해 간편하게 container를 순회할 수 있다.
 - sequence container : vector, deque, list
 - container adapter : stack, queue, prority_queue
 - associate container : set, unordered_set, multiset, map, unordered_map, multimap, bitset

for(auto i : container)
    ...

 

입/출력 관련 STL

소수점 아래 n자리 출력

아래 예시는 고정시켜서 10개를 출력하는 함수이다.

cout << fixed;
cout.precision(10);

 

round, ceil, floor

cmath header를 include해 쓰는 함수들이다.
round : 반올림 함수, ceil : 올림 함수, floor : 내림 함수이다.

#include <cmath>

double x = 3.14;
round(x); // 3
ceil(x); // 4
floor(x); // 3

 

상수 관련 STL

상수 PI 사용

_USE_MATH_DEFINES를 define하고 cmath header를 include하면 M_PI로 pi 값을 쓸 수 있다.

#define _USE_MATH_DEFINES // 제일 위에 올려야 함.
#include <cmath>

M_PI; // pi 값

 

MAX / MIN 사용

<limits.h>를 include하고 INT_MAX, INT_MIN, LLONG_MAX, LLONG_MIN 등을 쓸 수 있다.

#include <limits.h>

cout<<INT_MAX<<endl; // int 중 max 값
cout<<INT_MIN,<<endl; // int 중 min 값
cout<<LLONG_MAX,<<endl; // long long 중 max 값
cout<<LLONG_MIN<<endl; // long long 중 min 값

 

자료형 관련 STL

자료형 변환

숫자 -> string : to_string(숫자) 함수
string -> 숫자 -> stol(문자열) 함수 이용

 

 

자료형 검사

isdigit, isalpha 함수

#include 

char을 인수로 받는다.
isdigit는 char이 숫자가 아니면 0을, 숫자면 1을 리턴한다.
isalpha 함수는 char이 알파벳이 아니면 0을, 알파벳이면 0이 아닌 수를 리턴한다.

#include <cctype>

char c = 'a';
isdigit(c); // 0
isalpha(c); // 1

 

tolower, toupper 함수

char을 인수로 받는다. 영어 문자가 아닌 경우 해당 문자를 그대로 리턴, tolower는 소문자를, toupper는 대문자를 리턴한다.

#include <cctype>

char A = 'A', b = 'b';
tolower(A); // a
toupper(b); // B

 

Container

Vector

copy

vector.copy(arr.begin(), arr.begin()+n) 이렇게 잘라낼 수 있다.

 

accumulate

numeric header를 include한 후, accumulate(arr.begin(), arr.end(), 'sum 초기값')으로 배열 합을 구할 수 있다. 이 때 'sum 초기값'을 0으로 지정할 시 int로 지정되므로 0LL로 지정해야 좋을 것이다.

#include <numeric>

vector<int> v = {1, 2, 3, 4, 5};
accumulate(v.begin(), v.end(), 0LL);

 

erase​

arr.erase(arr.iterator)를 하면 해당 iterator의 값을 삭제할 수 있다.

 

중복제거

 <vector의 중복제거>는 unique라는 함수를 이용해 가능하다. unique 함수는 arr.begin()부터 arr.end()까지 '연속해서 중복으로 나오는 것'들을 vector의 제일 뒷자리로 미뤄주는 기능이다. 아래 코드에서 erase(iter1, iter2) 이렇게 되어있는데 이건 iter1부터 iter2까지 지운다는 것이고, iter1자리에 unique 함수가 들어가 있으므로 '연속으로 중복되어 나오는 것은 지우고, 제일 뒷자리로 미룬 쓰레기값들을 모두 삭제하는 코드'이다. 만약 vector 전체에서 unique하게 만들고 싶다면 sort 이후 unique, erase를 쓰면 될 것이다.(아니면 pq나 map같은거 써도 되고)

arr.erase(unique(arr.begin(), arr.end()),arr.end());

 

find

 #include <algorithm> header에 있는 find 함수를 이용해서 vector 내부에 value라는 값이 있는지 확인할 수 있다. 이 때 리 턴값이 arr.end()라면 값이 없는 것이다.

find(arr.begin(), arr.end(), value)

 

vector의 정렬

sort(arr.begin(), arr.end(), less<int>()); // 오름차순
sort(arr.begin(), arr.end(), greater<int>()); // 내림차순

 

Priority Queue

자동 정렬해주는 자료구조. 우선순위가 높은 것을 top에 올려주는 queue이다. 기본적으로 queue와 동일하게 동작하기 때문에 push, front, pop만 알고 있으면 된다.

#include <queue>

priority_queue<int> pq;
pq.push(1);
pq.front(); // pq에서 우선순위가 제일 높은 것
pq.pop(); // pq.front()가 pop됨.

 

 default는 less<>이고, greater<>을 쓰면 오름차순으로 top()에 올려준다.

priority_queue<int> q; // default는 less. 큰 숫자가 top.
priority_queue<int, vector<int>, less<int>> q;	// 큰 숫자가 top
priority_queue<int, vector<int>, greater<int>> q;	// 작은 숫자가 top

 

 pq를 vector로 구현한다고 했을 때, 에서 자주 빼는 top은 제일 뒤에 있을 것이다. 즉, less로 정렬하면 vector는 오름차순 정렬이므로 top에는 제일 큰 수가 있을 것이고, greater로 정렬하면 vector는 내림차순 정렬이므로 top에는 제일 작은 수가 있을 것이다.

 

정렬 기준 변경

정렬 기준 변경은 operator overloading struct를 정의해 해결할 수 있다. 선언은 만든 구조체를 넣어주면 된다. 비교함수 작성 시 const 붙여야 함.

struct cmp {
	bool operator() (const string &a, const string &b) const{
		if (a.size() == b.size())
			return a < b;
		else
			return a.size() < b.size();
	}
};

priority_queue<string, vector<string>, cmp> pq;

 

Map

(key, value)의 자료구조이며, key를 기준으로 정렬된, red-black tree로 구현된 container이다.
map[i] = j를 하면, 값이 있는 경우 수정, 없는 경우 삽입한다.
map.find(i) == map.end()인 경우에는 i에 해당하는 key를 가진 element가 없는 경우이다.
map.erase(i)를 하면 key 또는 iter가 i인 element를 지워준다.

#include <map>

map<int, string> m; // key : int type, value : string type
m[1] = "abc"; // m에 key 1이 없는 경우 abc 삽입, 있는 경우 갱신

m.find(1) == m.end(); // true이면 m에 key 1에 해당하는 element가 없는 것.

m.erase(1); // key가 1인 element 지워줌.

 

정렬 기준 변경 - key값으로 정렬

 정렬 기준 변경은 operator overloading struct를 정의해 해결할 수 있다. 다만 map의 경우 key로 정렬된 자료구조이기 때문에 STL을 사용해 정렬하는 것은 key값만 이용해 정렬가능하다. default는 key 오름차순 정렬이다.

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

map<int, string, cmp> m;

 

정렬 기준 변경 - value값으로 정렬

 value값으로 정렬은 불가능하다. map은 key값으로 정렬되어 있기 때문이다. 만약 value값으로 정렬하려면 vector에 넣어서 vector를 정렬하는 방식이 좋다.

map<int, string, cmp> m;
vector<pair<int, string>> v(m.begin(), m.end());
sort(v.begin(), v.end());

 

Unordered Map

 (key, value)의 자료구조. map과 동일하지만 정렬되어 있지 않다는 점만 다르다. hash table이므로, 정렬이 필요없는 경우 이 자료구조를 사용하자.
 u_map[i] = j를 하면, 값이 있는 경우 수정, 없는 경우 삽입한다.
 u_map.find(i) == u_map.end()인 경우에는 i에 해당하는 key를 가진 element가 없는 경우이다.
 u_map.erase(i)를 하면 key 또는 iter가 i인 element를 지워준다.

#include <unordered_map>

unordered_map<int, string> um; // key : int, value : string
um[1] = "abc"; // um에 key 1이 없는 경우 abc 삽입, 있는 경우 갱신

um.find(1) == um.end(); // true이면 m에 key 1에 해당하는 element가 없는 것.

um.erase(1); // key가 1인 element 지워줌.

 

Set

 중복을 허용하지 않는, binary tree를 이용해 정렬된 자료구조이다.

 set.insert(value);를 하면 삽입되고, 중복된 경우 알아서 제거해 준다.
 set.erase(value)를 하면 value에 해당하는 값을 찾아서 제거해 준다.

#include <set>

set<int> s;
s.insert(1);
s.find(10);

 

 set 초기화를 할 때 다른 container에 있는 값을 넣고 싶을 때는 초기화 함수를 잘 이용해 보자. 

vector<int> nums; // 값들이 들어있는 배열. nums의 값을 set에 넣고 싶을때는
set<int> s(nums.begin(), nums.end()); // 이렇게 초기화 할 수도 있다.

 

정렬 기준 변경

 정렬 기준 변경은 operator overloading struct를 정의해 해결할 수 있다. 선언은 만든 구조체를 넣어주면 된다.

struct cmp {
	bool operator() (const string &a, const string &b) const{
		if (a.size() == b.size())
			return a < b;
		else
			return a.size() < b.size();
	}
};

set<string, cmp> sets;

 

String

#include <string>

 

front / back

front(), back() 함수로 첫/마지막 인수에 접근할 수 있다.

string s = "abcde";
s.front(); // "a"
s.back(); // "e"

 

erase

string s;
s.erase(index, length); // index부터 length 길이를 삭제.

 

substr

 s.substr(idx, length) : string s를 index부터 length만큼 잘라서 반환. length가 공백인 경우에는 string 끝까지 return한다.

string s = "abced";
s.substr(0, 2); // "ab"
s.substr(1, 0); // ""
s.substr(2); // "ced"

 

replace

 s.replace(idx, length, rs) : string s를 index부터 length만큼을 rs로 변경

string s = "abced";
s.replace(2, 3, "ccc"); // "abccc"
s.replace(2, 2, "ccc"); // "abcccd"

 

find

 s.find(target) : target에 해당하는 string을 s에서 찾아 시작하는 위치를 리턴한다.
 s.find(target, position) : target에 해당하는 string을 position부터 검색해서 s에서 찾아 시작하는 위치를 리턴한다.
 string::npos : 결과를 찾지 못한 경우에 리턴하는 값

string s = "abcedced";
s.find("ced"); // 2
s.find("ced", 3); // 5
s.find("afx"); // string::npos

string page = "~~~~~~~~~~~~~~....~~~~~~~~~~~~~";
string target = "target";
int nth_idx = 0;
while(1){
    nth_idx = page.find(target, idx);
    if(nth_idx == string::npos) break;
    // nth_idx 필요한 값에 저장
    nth_idx++;
}

 

문자열 split

외우자.
 - delimiter가 필요한 버전

#include <sstream>

vector<string> split(string input, char delimiter) {
    vector<string> result;
    istringstream iss(input);
    iss.str(input);  // 위 줄과 이 줄은 같은 방법입.
    string buffer;
 
    while (getline(ss, buffer, delimiter)) result.push_back(buffer);
 
    return result;
}

위와 같이 delimeter로 parsing하는 방법이 있고, string의 형태가 정해져 있다면 아래와 같이 stringstream에서 값을 따와도 된다. 다만 이 방법은 아마 공백만 파싱이 될 거다.

 

 - 공백을 기준으로 파싱하는 버전

istringstream iss;
string action, uid, nickname;

for(int elem : strList){
    iss.clear(); // 초기화 전 clear를 해 주어야 한다.
    iss.str(elem);
    iss >> action >> uid >> nickname;
}

// 이 때 strList는 "action uid nickname"의 형태로 이루어져 있음.

다만 ss.clear() 함수에 유의하자!

 

string parsing하는 함수를 직접 작성할 때 index가 정확하게 되는지 잘 보자.

 

Algorithm

Sort / Stable Sort

default는 오름차순. 

vector<int> a;
sort(a.begin(), a.end());

vector<pair<int, int>> a;
sort(a.begin(), a.end(), cmp); // 오름차순
stable_sort(a.begin(), a.end(), cmp); // stable sort

 

비교 연산자를 customize할 수도 있다. 정확한 사용법 기억해 두자.

// first 기준 오름차순 
bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
    return a.first < b.first;
}

< : 오름차순
> : 내림차순

vector<pair<int, int>> a;
sort(a.begin(), a.end(), cmp);

 

next_permutation - 순열/조합

배열에 대해 순열을 만들어 주는 STL. 주의점으로는 배열은 오름차순 정렬되어 있어야 한다.

// nPr, nCr 시
// arr : 순열/조합할 원소, size n
void permutation(vector<int>& arr){
    sort(arr.begin(), arr.end());
    
    do{
        for(int i : arr){
            cout<<i<<" ";
        }cout<<endl;
    }while(next_permutation(arr.begin(), arr.end()));
}

void combination(int n, int r, vector<int>& arr){
    vector<int> temp(n, 0);
    for(int i = n-r; i<n; i++){
        temp[i] = true;
    }
    
    do{
        for(int i = 0; i<n; i++){
            if(temp[i]) cout<<arr[i]<<" ";
        } cout<<endl;
    }while(next_permutation(temp.begin(), temp.end()));
}

 

정규 표현식

https://modoocode.com/303

씹어먹는 C++ - <17 - 2. C++ 정규 표현식(<regex>) 라이브러리 소개>

 이 블로그와 '숫자 문자열과 영단어' 문제 참고해서 정규표현식 정리를 한 번 해 보자.