STL

vector

头文件

#include <vector>

初始化

vector<int> v(n, value) // 初始化为大小为n的全是value的vector
int a[5] = {1,2,3,4,5}; vector<int> b(a, a+5);
vector b(a); // a -> another vector

// v1 {1, 2, 3, 4, 5, 6}
vector<int> v2(v1.begin()+2, v1.begin()+2+3); // {3, 4, 5}

操作

v.size()
v.push_back() // 后面插入元素
v.pop_back() //弹出最后一位元素，类型为void
v.back() // 直接访问最后一个元素

resize

把vector大小变为size，如果vector原本大小超过size，截取前size个元素，如果不足则补足

resize(int size)
resize(int size, value_type val)

排序

调用std::sort即可，不过需要#include <algorithm>

前两个参数是起止迭代器，第三个参数可以传入一个比较函数，函数以两个值为输入，输出一个bool值，bool值为true时前者在后者前面

vector<int> v = {5, 2, 1, 3, 4};
sort(v.begin(), v.end());
for (auto x : v) cout << x << ' '; cout << '\n';
// output: 1 2 3 4 5 
sort(v.begin(), v.end(), greater<int>());
for (auto x : v) cout << x << ' '; cout << '\n';
// output: 5 4 3 2 1
auto comp = [](int a, int b) -> bool { return a > b; };
sort(v.begin(), v.end(), comp);
for (auto x : v) cout << x << ' '; cout << '\n';
// output: 5 4 3 2 1

二分查找

调用std::lower_bound和std::upper_bound进行查找，参数和std::sort相同

前者返回包含target在内的结果，后者返回不包括target的结果

这里的vector应该已经是有序的，且两个函数的比较方式和排序方式相同

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    vector<int> v = { 1, 3, 8, 2, 4, 0, 4, 3 };
    auto cmp1 = [](int a, int b) -> bool { return a < b; };
    auto cmp2 = [](int a, int b) -> bool { return a > b; };
    // less
    sort(v.begin(), v.end(), cmp1);
    auto itr = lower_bound(v.begin(), v.end(), 3, cmp1);
    cout << (itr == v.end()) << ' ' << *itr << '\n'; // 0 3
    itr = upper_bound(v.begin(), v.end(), 3, cmp1);
    cout << (itr == v.end()) << ' ' << *itr << '\n'; // 0 4
    itr = upper_bound(v.begin(), v.end(), 8, cmp1);
    cout << (itr == v.end()) << ' ' << *itr << '\n'; // 1 0
    // greater
    sort(v.begin(), v.end(), cmp2);
    itr = lower_bound(v.begin(), v.end(), 3, cmp2);
    cout << (itr == v.end()) << ' ' << *itr << '\n'; // 0 3
    itr = upper_bound(v.begin(), v.end(), 3, cmp2);
    cout << (itr == v.end()) << ' ' << *itr << '\n'; // 0 2
    itr = upper_bound(v.begin(), v.end(), 0, cmp2);
    cout << (itr == v.end()) << ' ' << *itr << '\n'; // 1 0
}

---

Stack

后进先出，只允许push/pop末端元素，只能通过top来查看末端元素，不提供走访功能，也不提供迭代器

STL缺省用deque作为stack底部结构，因此stack被归类为container adapter

也可以指定别的底层容器，如list

s.empty();
s.size();
s.top();
void push(const value_type& x);
void pop();

stack<int> s;
s.push(1);
s.push(2);
s.push(3);
s.top(); // 3
s.pop();
s.top(); // 2

题目

32. Longest Valid Parentheses

---

双向队列: deque

声明

#include <deque>

操作

deque<int> q;
q.push_front(ele);
q.push_back(ele);
void q.pop_front();
void q.pop_back();
q.size();
int q.front();
int q.back();

---

unordered_map

题目

1. Two Sum

30. Substring with Concatenation of All Words

头文件

#include <unordered_map>

声明

std::unordered_map<int, int> map;

插入

如果second类型是int，初始值是0，如map[key] ++，则自动插入并变为1

map.insert(make_pair(i, j));
map[i] = j;

查找

map.find(num);
// unfound
map.find(num) == map.end();
// found
map.find(num)->first/second

map.count(key); // 1->found 0->unfound

删除

map.erase(num)

大小

map.size()

遍历

// unordered_map<int, int>::iterator iter = map.begin();
auto iter = map.begin();
while (iter != map.end()) {
    cout << iter->first << ' ' << iter->second << '\n';
    iter ++;
}

---

std::priority_queue

优先级队列

• 默认使用vector作为存储数据的结构
• 默认是大顶堆，即在compare函数表示弱序时大元素在前，要改为小顶堆应该用compare返回大于顺序

内部实现是用heap的

头文件

#include <queue>

声明

关于排序可以这样理解，每次增加元素，会将heap_size加一，并且将新加元素放在最后，执行上浮，比较father和node，如果返回结果为true，则进行交换，因此小于关系定义的是大顶堆，大于关系定义的是小顶堆

默认是大顶堆，用的比较函数是std::less

// 小顶堆
std::priority_queue<int, std::vector<int>, std::less<int>> pq;

如下是小顶堆

// 小顶堆
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

priority_queue不提供迭代器遍历，只能逐个pop来输出所有元素

while (!q.empty()) {
    cout << q.top() << '\n';
    q.pop();
}

自定义排序

可以自定义元素比较方式，并传入，cmp(a, b)为true时，a会在前面，false则b在前面

这里cmp会通过operator ()来调用，所以需要定义一下operator ()的作用

struct cmp {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        return a < b;
        return a.first + a.second < b.first + b.second;
    }
};
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;

也可以用lambda来定义比较函数，用decltype来推断类型，同时传入cmp作为参数来初始化decltype(cmp)类型

大顶堆

auto cmp = [](int a, int b) { return a < b; };
std::priority_queue<int, std::vector<int>, decltype(cmp)> q(cmp);

小顶堆

auto cmp = [](int a, int b) { return a > b; };
priority_queue<int, vector<int>, decltype(cmp)> q(cmp);

用法

q.push(ele)
q.pop()
q.top()
q.empty()
q.size()

题目

215. Kth Largest Element in an Array (Medium)

---

set

header file

#include <set>
set<T> s;

insert

s.insert(element);

delete

s.delete(set.find(element)); // by value
s.erase(std::prev(s.end())); // by iterator

---

multiset

头文件

#include <set>
multiset <T> s; // least element on the head
multiset <T, greater<T>> gs; // greatest element on the head

s.insert(element);

删除单个元素

s.erase(s.find(element));

删除所有元素

s.erase(element);

lower_bound

• 小顶树：返回大于等于该值的最小元素
• 大顶树：返回小于等于该值的最大元素

upper_bound

• 小顶树：返回大于该值的最小元素
• 大顶树：返回小于该值的最大元素

example

注意不同比较函数的multiset属于不同数据类型

#include <iostream>
#include <set>
using namespace std;

void display(multiset<int> s) {
    for (auto n : s) cout << n << ' ';
    cout << '\n';
}
void display(multiset<int, greater<int>> s) {
    for (auto n : s) cout << n << ' ';
    cout << '\n';
}
int main() {
    multiset<int> s;
    for (auto i : {1, 2, 3, 3, 3, 4, 5, 6}) s.insert(i);
    display(s); // 1 2 3 3 3 4 5 6
    s.erase(s.find(3));
    display(s); // 1 2 3 3 4 5 6
    s.erase(3);
    display(s); // 1 2 4 5 6
    cout << *s.lower_bound(4) << '\n'; // 4
    cout << *s.upper_bound(4) << '\n'; // 5

    multiset<int, greater<int>> gs;
    for (auto i : {1, 2, 3, 3, 3, 4, 5, 6}) gs.insert(i);
    display(gs); // 6 5 4 3 3 3 2 1 
    gs.erase(3);
    display(gs); // 6 5 4 2 1
    cout << *gs.lower_bound(4) << '\n'; // 4
    cout << *gs.upper_bound(4) << '\n'; // 2
}