OI学习笔记-C++中的STL容器

发表于 更新于 阅读次数： 本文字数： 5.1k 阅读时长 ≈ 9 分钟

auto 你是我的神

1. vector

  • 特点：动态数组，支持随机访问，插入和删除效率较低。
  • 适用场景：需要频繁随机访问的场景。
  • 典型操作：
    • push_back(): 添加元素到末尾。
    • pop_back(): 删除末尾元素。
    • size(): 获取当前大小。
    • capacity(): 获取当前容量。
    • resize(): 调整大小。
    • erase(): 删除指定位置的元素。
    • clear(): 清空容器。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
using namespace std;

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

    cout << "Vector size: " << vec.size() << endl;
    cout << "Elements: ";
    for (auto x : vec) {
        cout << x << " ";
    }
    cout << endl;

    vec.erase(vec.begin() + 1); // 删除索引为1的元素
    cout << "After erase: ";
    for (auto x : vec) {
        cout << x << " ";
    }
    cout << endl;

    vec.clear();
    cout << "After clear: " << vec.size() << endl;

    return 0;
}

2. list

  • 特点：双向链表，插入和删除效率高，不支持随机访问。
  • 适用场景：需要频繁插入和删除的场景。
  • 典型操作：
    • push_front(): 添加元素到头部。
    • push_back(): 添加元素到尾部。
    • pop_front(): 删除头部元素。
    • pop_back(): 删除尾部元素。
    • insert(): 在指定位置插入元素。
    • erase(): 删除指定位置的元素。
    • reverse(): 反转链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst;
    lst.push_back(1);
    lst.push_back(2);
    lst.push_front(0);

    cout << "List elements: ";
    for (auto x : lst) {
        cout << x << " ";
    }
    cout << endl;

    lst.erase(lst.begin()); // 删除第一个元素
    cout << "After erase: ";
    for (auto x : lst) {
        cout << x << " ";
    }
    cout << endl;

    lst.reverse();
    cout << "After reverse: ";
    for (auto x : lst) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

3. deque

  • 特点：双端队列，支持从两端插入和删除，支持随机访问。
  • 适用场景：需要从两端插入和删除的场景。
  • 典型操作：
    • push_front(): 添加元素到头部。
    • push_back(): 添加元素到尾部。
    • pop_front(): 删除头部元素。
    • pop_back(): 删除尾部元素。
    • front(): 获取头部元素。
    • back(): 获取尾部元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> dq;
    dq.push_back(1);
    dq.push_back(2);
    dq.push_front(0);

    cout << "Deque elements: ";
    for (auto x : dq) {
        cout << x << " ";
    }
    cout << endl;

    dq.pop_front(); // 删除头部元素
    cout << "After pop_front: ";
    for (auto x : dq) {
        cout << x << " ";
    }
    cout << endl;

    dq.pop_back(); // 删除尾部元素
    cout << "After pop_back: ";
    for (auto x : dq) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

4. set

  • 特点：有序集合，元素唯一，支持快速查找。
  • 适用场景：需要存储唯一元素并快速查找的场景。
  • 典型操作：
    • insert(): 插入元素。
    • erase(): 删除元素。
    • find(): 查找元素。
    • count(): 检查元素是否存在。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <set>
using namespace std;

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

    cout << "Set elements: ";
    for (auto x : s) {
        cout << x << " ";
    }
    cout << endl;

    s.erase(2); // 删除元素2
    cout << "After erase: ";
    for (auto x : s) {
        cout << x << " ";
    }
    cout << endl;

    if (s.find(3) != s.end()) {
        cout << "Element 3 exists" << endl;
    }

    return 0;
}

5. map

  • 特点：键值对集合，键唯一，支持快速查找。
  • 适用场景：需要存储键值对并快速查找的场景。
  • 典型操作：
    • insert(): 插入键值对。
    • erase(): 删除键值对。
    • find(): 查找键对应的值。
    • count(): 检查键是否存在。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <map>
using namespace std;

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

    cout << "Map elements:" << endl;
    for (auto &pair : m) {
        cout << pair.first << ": " << pair.second << endl;
    }

    m.erase("Bob"); // 删除键"Bob"
    cout << "After erase:" << endl;
    for (auto &pair : m) {
        cout << pair.first << ": " << pair.second << endl;
    }

    if (m.find("Alice") != m.end()) {
        cout << "Alice's age: " << m["Alice"] << endl;
    }

    return 0;
}

6. stack

  • 特点：后进先出（LIFO）的容器适配器。
  • 适用场景：需要模拟栈操作的场景。
  • 典型操作：
    • push(): 添加元素到栈顶。
    • pop(): 删除栈顶元素。
    • top(): 获取栈顶元素。
    • empty(): 检查栈是否为空。
    • size(): 获取栈的大小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <stack>
using namespace std;

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

    cout << "Stack size: " << stk.size() << endl;
    cout << "Top element: " << stk.top() << endl;

    stk.pop(); // 删除栈顶元素
    cout << "After pop: " << stk.top() << endl;

    return 0;
}

7. queue

  • 特点：先进先出（FIFO）的容器适配器。
  • 适用场景：需要模拟队列操作的场景。
  • 典型操作：
    • push(): 添加元素到队尾。
    • pop(): 删除队首元素。
    • front(): 获取队首元素。
    • back(): 获取队尾元素。
    • empty(): 检查队列是否为空。
    • size(): 获取队列的大小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <queue>
using namespace std;

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

    cout << "Queue size: " << q.size() << endl;
    cout << "Front element: " << q.front() << endl;
    cout << "Back element: " << q.back() << endl;

    q.pop(); // 删除队首元素
    cout << "After pop: " << q.front() << endl;

    return 0;
}

总结

  • vector: 动态数组，适合随机访问。
  • list: 双向链表，适合频繁插入和删除。
  • deque: 双端队列，支持两端操作。
  • set: 有序集合，支持快速查找。
  • map: 键值对集合，支持快速查找。
  • stack: 后进先出，适合栈操作。
  • queue: 先进先出，适合队列操作。

通过这些容器，可以根据具体需求选择合适的容器来优化代码性能和可读性。