STL

指针

void increment(int *p)
{
    (*p) ++;
}

void myswap(int *a, int *b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

int main()
{
    int n = 10;
    int *p;
    p = &n;
    (*p) ++;
    cout << "n = " << n << endl;

    increment(p);
    cout << "n = " << n << endl;

    int a, b;
    cin >> a >> b;
    myswap(&a, &b);
}

vector

访问第一个元素：front()；访问最后一个元素：back()
向队尾添加一个元素：push_back()；删除队尾元素：pop_back()
支持size()、empty()、clear()
assign()：清空原容器中的数冰重新赋值

vector<int> num = {1, 2, 3, 4, 5};
cin >> n;
while (n --)
{
    int x;
    cin >> x;
    num.push_back(x);
}
for (auto i = num.begin(); i != num.end(); ++ i) cout << *i << ' ';

反向迭代器：rbegin()、rend()

for (auto i = num.rbegin(); i != num.rend(); ++ i) cout << *i << ' ';

pair

第一关键字：first()；第二关键字：second()

pair<char, int> p[n];
for (int i = 0; i < n; i ++)
{
    char letter;
    int count;
    cin >> letter >> count;
    p[i] = make_pair(letter, count);
}
for (int i = 0; i < n; i ++) cout << p[i].first << ':' << p[i].second << endl;

stack

size( )：返回栈中元素个数
top( )：返回栈顶的元素
pop( )：从栈中取出并删除元素
push(e)：向栈中添加元素e
empty( )：栈为空时返回true

用stack实现逆序输出数组

int n;
cin >> n;
stack<int> stk;
for (int i = 0; i < n; i ++)
{
    int x;
    cin >> x;
    stk.push(x);
}
for (int i = 0; i < n; i ++)
{
    cout << stk.top() << ' ';
    stk.pop();
}

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））

class MinStack {
public:

    stack<int> stk, min_stk;

    MinStack() {

    }

    void push(int x) {
        stk.push(x);
        if (min_stk.empty() || min_stk.top() >= x) min_stk.push(x);
    }

    void pop() {
        if (stk.top() == min_stk.top()) min_stk.pop();
        stk.pop();
    }

    int top() {
        return stk.top();
    }

    int getMin() {
        return min_stk.top();
    }
};

queue

访问队头：q.front()
访问队尾：q.tail()
入队列：q.push()
出队头：q.pop()

priorty_queue优先队列

快速维护一个序列中动态最大值

int n;
cin >> n;
priority_queue<int> pq;
for (int i = 0; i < n; i ++)
{
    int x;
    cin >> x;
    pq.push(x);
}
while (pq.size())
{
    cout << pq.top() << ' ';
    pq.pop();
}

快速维护一个序列中动态最小值

int n;
cin >> n;
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 1; i <= n; i ++)
{
    int x;
    cin >> x;
    pq.push(x);
}
while (pq.size())
{
    cout << pq.top() << ' ';
    pq.pop();
}

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列

set、multiset

元素不重复且有序
不能直接对set元素进行修改，只能先删除再插入
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器

int n;
cin >> n;
set<int> s;
for (int i = 0; i < n; i ++)
{
    int x;
    cin >> x;
    s.insert(x);
}
for (auto i = s.begin(); i != s.end(); ++ i) cout << *i << ' ';

map、multimap

map<int, int> mp;
for (int i = 0; i < 5; i ++) mp.insert({i, -i});
for (auto i = mp.begin(); i != mp.end(); ++ i)
    printf("%d %d\n", i->first, i->second);
cout << mp.find(3)->first << endl; // 返回数据所在位置的迭代器
cout << mp.find(-2)->first << endl; // 返回end()函数所在的迭代器

string作为第一关键字时

map<string, int> mp;
mp.insert(make_pair("Tom", 1));
mp.insert(make_pair("Lily", 2));
for (auto i = mp.begin(); i != mp.end(); ++ i)
    printf("%s\n", i->first.c_str());
    // 或者 cout << i->first << endl;

例：书的分类

map<string, int> mp;
while (n --)
{
    string name;
    cin >> name;
    mp[name] ++;
}

unordered_map、unordered_set、unordered_multimap、unordered_multiset

数据结构基于哈希表，增删改查效率为O(1)

技巧

map 套 set
vector 套 pair[HTML_REMOVED]
make_heap(l, r) 根据这一段区间创建对应的 heap
stable_sort 是稳定的排序，有时候有用。
nth_element 将第 k kk 大的元素归位。