C++ 核心基础：STL 容器、位运算与常用算法库

STL 容器基础

vector

vector 是序列容器，支持运行时动态插入和删除元素。使用前需包含 <vector> 头文件。

• size() 返回实际长度，empty() 判断是否为空，两者时间复杂度均为 O(1)。所有 STL 容器均支持。
• 迭代器类似指针，可用 * 解除引用。vector 的迭代器属于'随机访问迭代器'，支持与整数加减及两个迭代器相减，行为同指针。
• begin() 指向首元素，end() 指向尾元素的下一个位置。
• front() 获取首元素，back() 获取尾元素。
• push_back(x) 尾部插入，pop_back() 删除尾部元素。

示例：

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

int main() {
    vector<int> a;
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);
    a.push_back(4);
    a.push_back(5);

    int len = a.size();
    bool is_empty = a.empty();
    cout << len << " " << is_empty << endl;

    int first = a.front();
    int last = a.back();
    cout << first << " " << last << endl;

    a.pop_back();
    a.erase(a.begin() + 2); // 删除第三个元素

    first = a.front();
    last = a.back();
    cout << first << " " << last << endl;

    for (vector<int>::iterator it = a.begin(); it != a.end(); ++it) {
        cout << *it << endl;
    }

    cout << a[2] << endl;
    a.clear();

    len = a.size();
    is_empty = a.empty();
    cout << len << " " << is_empty << endl;
    return 0;
}

queue

包含 <queue> 头文件。主要有循环队列 queue 和优先队列 priority_queue。遵循先进先出规则。

优先队列 priority_queue：

默认是大根堆（升序排列）。

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

int main() {
    priority_queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);

    priority_queue<int> m = q;
    while (!m.empty()) {
        cout << m.top() << endl;
        m.pop();
    }

    q.pop();
    q.pop();
    while (!q.empty()) {
        cout << q.top() << endl;
        q.pop();
    }
    return 0;
}

常用方法：

• top()：返回顶部元素（不删除）。
• pop()：移除顶部元素。
• push()：添加元素。

循环队列 queue：

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

int main() {
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);

    queue<int> m = q;
    while (!m.empty()) {
        cout << m.front() << endl;
        m.pop();
    }

    cout << q.front() << endl;
    cout << q.back() << endl;
    cout << q.size() << endl;
    return 0;
}

常用方法：

• front()：队首元素。
• back()：队尾元素。
• pop()：移除队首。
• push()：队尾添加。

声明示例：

queue<int> q;
priority_queue<int> a; // 大根堆
priority_queue<int, vector<int>, greater<int>> b; // 小根堆
priority_queue<pair<int,int>> c;

stack

包含 <stack> 头文件。后进先出结构。

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

int main() {
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);

    stack<int> t = s;
    while (!t.empty()) {
        cout << t.top() << endl;
        t.pop();
    }

    s.pop();
    s.pop();
    while (!s.empty()) {
        cout << s.top() << endl;
        s.pop();
    }
    return 0;
}

常用方法：

• top()：返回栈顶元素。
• pop()：移除栈顶。
• push()：栈顶添加。

deque

双端队列，两端均可操作。

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

int main() {
    deque<int> q;
    q.push_front(1);
    q.push_back(2);
    q.push_front(3);
    q.push_back(4);

    int len = q.size();
    bool is_empty = q.empty();
    cout << len << " " << is_empty << endl;

    for (deque<int>::iterator it = q.begin(); it != q.end(); ++it) {
        cout << *it << endl;
    }

    q.pop_back();
    q.pop_front();
    len = q.size();
    is_empty = q.empty();
    cout << len << " " << is_empty << endl;

    for (deque<int>::iterator it = q.begin(); it != q.end(); ++it) {
        cout << *it << endl;
    }

    q.clear();
    len = q.size();
    is_empty = q.empty();
    cout << len << " " << is_empty << endl;
    return 0;
}

常用方法：

• clear()：清空。
• pop_front/pop_back()：两端出队。
• push_front/push_back()：两端入队。
• front/back()：两端元素。
• begin/end()：迭代器。

set

包含 <set> 头文件。自动排序且去重。

• size(), empty(), clear() 用法同上。
• 迭代器为'双向访问迭代器'，不支持随机访问，仅支持 ++ 和 --。
• insert(x)：插入元素，若存在则不重复插入，复杂度 O(log n)。
• find(x)：查找元素，返回迭代器，不存在返回 end()，复杂度 O(log n)。
• lower_bound(x)：返回大于等于 x 的最小元素迭代器。
• upper_bound(x)：返回大于 x 的最小元素迭代器。
• erase(it)：删除迭代器指向元素，O(log n)。
• erase(x)：删除所有等于 x 的元素，O(k + log n)。

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

int main() {
    set<int> s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(4);
    s.insert(5);

    int len = s.size();
    bool is_empty = s.empty();
    cout << len << " " << is_empty << endl;

    for (set<int>::iterator it = s.begin(); it != s.end(); ++it) {
        cout << *it << endl;
    }

    s.erase(3);
    len = s.size();
    is_empty = s.empty();
    cout << len << " " << is_empty << endl;

    for (set<int>::iterator it = s.begin(); it != s.end(); ++it) {
        cout << *it << endl;
    }

    if (s.find(2) != s.end()) {
        cout << "2 is yes" << endl;
    } else {
        cout << "2 is no" << endl;
    }

    int count = s.count(0);
    cout << count << endl;
    return 0;
}

map

包含 <map> 头文件。键值对映射，内部为红黑树。key 必须定义小于号运算符。

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> employees;
    employees.insert(make_pair("Alice", 30));
    employees.insert(make_pair("Bob", 25));
    employees.insert(make_pair("Charlie", 35));

    for (map<string, int>::iterator it = employees.begin(); it != employees.end(); ++it) {
        cout << it->first << ":" << it->second << endl;
    }

    int len = employees.size();
    bool is_empty = employees.empty();
    cout << len << " " << is_empty << endl;

    map<string, int>::iterator it = employees.find("Bob");
    if (it != employees.end()) {
        if (it->second == 25) {
            cout << "Bob: 25 is yes" << endl;
        } else {
            cout << "Bob: 25 is no" << endl;
        }
    } else {
        cout << "Bob: 25 is no" << endl;
    }

    employees.clear();
    len = employees.size();
    is_empty = employees.empty();
    cout << len << " " << is_empty << endl;
    return 0;
}

常用方法：

• find(x)：查找 key 为 x 的二元组。
• insert/erase：参数为 pair<key_type, value_type>。
• size/empty/clear/begin/end：同 set。

位运算

符号	含义
&	与
|	或
~	非
^	异或
>>	右移
<<	左移

常见操作

lowbit(x)：返回 x 最后一位 1。公式：x & -x。

#include <iostream>
using namespace std;

int main() {
    int num;
    cin >> num;
    int lowbit = num & -num;
    cout << lowbit << endl;
    return 0;
}

求 x 的第 k 位数字：(x >> k) & 1。

#include <iostream>
using namespace std;

int main() {
    int num, k;
    cin >> num >> k;
    cout << ((num >> k) & 1) << endl;
    return 0;
}

常用库函数

reverse

翻转元素。适用于数组和 vector。

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

int main() {
    int a[10] = {1, 2, 3, 4, 5, 6, 5, 4, 3, 2};
    for (int i = 0; i < 10; i++) {
        cout << a[i] << endl;
    }
    cout << endl;

    reverse(a, a + 10);
    for (int i = 0; i < 10; i++) {
        cout << a[i] << endl;
    }
    cout << endl;

    vector<int> q;
    q.push_back(1);
    q.push_back(2);
    q.push_back(3);
    q.push_back(4);

    for (vector<int>::iterator it = q.begin(); it != q.end(); ++it) {
        cout << *it << endl;
    }
    cout << endl;

    reverse(q.begin(), q.end());
    for (vector<int>::iterator it = q.begin(); it != q.end(); ++it) {
        cout << *it << endl;
    }
    return 0;
}

unique

去重（仅去除相邻相同元素），返回去重后的尾迭代器。常用于离散化。

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

int main() {
    vector<int> q;
    q.push_back(1);
    q.push_back(2);
    q.push_back(2);
    q.push_back(2);
    q.push_back(3);
    q.push_back(3);
    q.push_back(4);

    for (vector<int>::iterator it = q.begin(); it != q.end(); ++it) {
        cout << *it << endl;
    }
    cout << endl;

    vector<int>::iterator new_end = unique(q.begin(), q.end());
    q.erase(new_end, q.end());

    int m = q.size();
    cout << "Number of unique elements: " << m << endl;
    cout << "After removing duplicates: ";
    for (vector<int>::iterator it = q.begin(); it != q.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    return 0;
}

random_shuffle

随机打乱序列。

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

int main() {
    vector<int> a;
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);
    a.push_back(4);
    a.push_back(5);

    for (vector<int>::iterator it = a.begin(); it != a.end(); ++it) {
        cout << *it << endl;
    }
    cout << endl;

    random_shuffle(a.begin(), a.end());
    for (vector<int>::iterator it = a.begin(); it != a.end(); ++it) {
        cout << *it << endl;
    }
    return 0;
}

sort

快速排序，默认升序。

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

int main() {
    int a[10] = {1, 2, 3, 2, 1, 4, 3, 2, 1, 10};
    sort(a, a + 10);
    for (int i = 0; i < 10; i++) {
        cout << a[i] << endl;
    }
    cout << endl;

    sort(a, a + 10, greater<int>());
    for (int i = 0; i < 10; i++) {
        cout << a[i] << endl;
    }
    return 0;
}

lower_bound / upper_bound

二分查找。需在已排序区间执行。

• lower_bound：返回第一个大于等于 x 的位置。
• upper_bound：返回第一个大于 x 的位置。

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

int main() {
    int a[10] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
    sort(a, a + 10);

    int i = lower_bound(a, a + 10, 5) - a;
    cout << i << endl;

    int j = upper_bound(a, a + 10, 5) - a;
    cout << j << endl;
    return 0;
}