# STL 筆記

### `heap` 自訂排序

struct node{
    int x, y, num;
};

bool operator < (node l, node r){
    return l.num < r.num;
}
priority_queue<node> pq;   // 從大到小
priority_queue<int> pq;                            // 從大到小
priority_queue<int, vector<int>, greater<int>> pq; // 從小到大

### `UpperBound() / LowerBound()`
- lower_bound: 找出 `>=num` 的最小值位置
- upper_bound: 找出 `>num` 的最小值位置

// Map 的用法
map<int,int> mp = {{0,0}, {1,2}, {2,3}};
auto u = mp.upper_bound(1);
cout<<u->first<<" "<<u->second<<endl;	// 2 3

// Set 的用法
set<int> data = {3,7,5,4,2,6};
auto u = data.upper_bound(4);
cout<<*u<<endl;		// 5

// Vector 的用法
vector<int> data = {3,7,5,4,2,6};
sort(data.begin(),data.end()); // 必須對 sorted vector 操作
auto u = upper_bound(data.begin(),data.end(),4);
cout<<*u<<endl;		// 5

### 字串整數轉換

string s = to_string(123);
int num = stoi(s);

### 幾何

double getAngle(int xDiff, int yDiff) {
    return atan2(yDiff, xDiff) * 180 / PI;
}

// positive if clockwise
// negative if counter clockwise
int getOrientation(vector<int> &p, vector<int> &q, vector<int> &r) {
    int pqx = q[0]-p[0], pqy = q[1]-p[1];
    int qrx = r[0]-q[0], qry = r[1]-q[1];
    return pqy*qrx - pqx*qry;
}

int getDistance(vector<int> &p, vector<int> &q) {
    return (p[0]-q[0])*(p[0]-q[0]) + (p[1]-q[1])*(p[1]-q[1]);
}

### Heap / Set / List / Deque 用法

// heap
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
while(!maxHeap.empty()){
    int data = maxHeap.top(); maxHeap.pop();
}

// set
set<int> s;
multiset<int> s;
s.erase(2);
s.erase(s.begin());
s.erase(s.find(2));
s.erase(prev(s.end()));

// list
list<int> l;
l.push_back(3);
l.push_front(4);
l.pop_back();
l.pop_front();
l.insert(l.begin(), 5);
l.erase(l.begin());

// deque
deque<int> dq;
l.push_back(3);
l.push_front(4);
l.pop_back();
l.pop_front();

### 集合中元素是否存在`Count()`

set<int> s;
map<int,int> mp;
unordered_set<int> s2;
unordered_map<int,int> mp2;
if(mp.count(1)) // ...
if(mp2.count(1)) // ...
if(s.count(1)) // ...
if(s2.count(1)) // ...

### 去除重複

sort(ans.begin(),ans.end());
auto it = unique(ans.begin(),ans.end());
ans.erase(it, ans.end());