12/30 TIL C++ 알고리즘을 위한 STL 소소팁

연차 덕분에 조금 많이 공부할 수 있었다.

map, set

파이썬 보다 편한 counter

map을 선언했을 때,  m[key] 로 접근하면, 해당 key가 없는 경우 자동으로 기본값으로 key,value가 생성된다.
이를 이용해 counter를 만들 수 있다.

unordered_map<int,int> m;
m[3]++;

위 코드에서 3은 자동으로 1로 증가한다.
자동으로 생기는 게 불편하다면 m.at(index) 와 같이 접근해야 한다.

요소 확인

위 내용처럼 if(m[index]) 와 같이 접근하면 기본값으로 요소가 생겨버리기 때문에 불편하다. find나 count를 써야 하는데 count가 더 편하다.

if(m.count(3)) //0을 false로 취급한다.
//또는
if(m.find(3)!=m.end())
//find는 iterator를 반환한다. count보다 번거로운대신, count보다 빠르다.

vector화

map은 key, value pair를 갇는 vector로 바로 복사할 수 있다.  pair가 아닌 다른 vector( vector<vector<int,int>> 등) 로는 복사되지 않는다.

vector<pair<int,int>> vec1(m.begin(), m.end());

sort

map 선언시 key에 대해 sort되게 compare lambda를 만들 수 있다. 

function<bool(int,int)> compare = [](int a, int, b){return a > b;};
map<int, string, function<bool(int,int)>> m(compare);

//혹은

std::map<int, string, decltype(auto)> m(
    [](int a, int b) { return a > b; }
);

그러나 value에 대해 sort 되게는 생성시에는 못한다.

vector를 key로 가지기

map<vector<int>,int> m;   //이건 되고
unorderd_map<vector<int>, int> um; //이건 안된다.

vector<int> 에 대한 hash가 정의되어 있지 않기 때문에, 기본적으로 map에서 key로 사용할 수 없다.
그러나 map의 경우 ordering을 위해 key를 '비교' 하는데 이 때문에 비교가 구현된 type은 key로 사용할 수 있게 된다.

관련문제 > [leetcode] 2352.Equal Row and Column Pairs

pair

make_pair를 통해 생성자 대신 사용할 수도 있지만, 추론을 이용할 수도 있다.

stack<pair<int,TreeNode*>> stk;


stk.push(make_pair(root->val, root));
//자동 추론
stk.push({root->val ,root}};

튜플

튜플은 index로 접근을 못한다.

//이렇게 접근하거나
auto first = get<0>(tup);

//다 써야 한다면 차라리 이렇게 풀어버리자
auto [first, second, third] = tup;

힙

vector<int> vec ={1,3,5,2};
priority_queue<int> pq(vec.begin(), vec.end());

make_heap을 쓰는 방법도 있다.

make_heap은 최우선순위를 가장 앞으로 뺀다. con.front()로 접근 가능

pop_heap()은 제거해야 할 원소를 가장 뒷쪽으로 빼고, 나머지는 heap으로 유지한다. 따라서 맨 앞 요소는 두번째 최우선 요소다.
push_heap() 가장 뒷쪽의 원소를 heap을 유지하면서 다시 넣는다.
위 두 메서드 모두 실제로 제거, 추가하는 메서드는 아니므로, con.push_back(), con.pop_back()의 도움이 필요하다.

vector<int> vec = {1,3,5,6,2,5};
make_heap(vec.begin(), vec.end());
auto prime = vec.front(); //최우선순위는 맨 앞에 있음

pop_heap(vec.begin(), vec.end()); //가장 뒷쪽으로뺌
vec.pop_back();  //실제 제거

vec.push_back(30); //실제 추가
push_heap(vec.begin(), vec.end()); //heapify

일반

begin, end

begin(vec) 은 vec.begin() 과 같다.  end() 도 마찬가지.  대부분의 STL 컨테이너는 모두 가지고 있다.
 -> stack, queue는 없음, map,set은 오히려 있음

begin, end가 있어야  initializer_list로 초기화 할 수 있다.  그래서 stack, queue는 {} 로 초기화를 못한다.

구조화 바인딩

아래 셋다 유효한 문법이다.

auto [key,value] = p;
auto &[key, value] = p;
auto [key, &value] = p;

max, minmax_element, min_element

int mx = max(a,b);

auto [miniter, maxiter] = minmax_element(vec);
auto it = min_element(vec);

count, count_if

count(vec.begin(), vec.end(), 2);
count_if(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });