数据结构示例

理解并熟练使用 C++ 标准库提供的各种数据结构对于编写高效、简洁的代码至关重要。下面通过一系列示例，展示如何使用 C++ 中常见的数据结构及其基本函数。这些示例将帮助你熟悉各个数据结构的基本操作和常用函数名称。

# 1. `std::vector`

描述：动态数组，支持快速随机访问和末尾插入删除。

# 示例

#include <iostream>
#include <vector>

int main() {
    // 创建一个空的 vector，存储整数
    std::vector<int> vec;

    // 使用 push_back() 添加元素
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);

    // 访问元素
    std::cout << "第一个元素: " << vec[0] << std::endl; // 输出 10
    std::cout << "最后一个元素: " << vec.back() << std::endl; // 输出 30

    // 遍历 vector
    std::cout << "所有元素: ";
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 删除最后一个元素
    vec.pop_back();

    std::cout << "删除最后一个元素后: ";
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

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
33
34

# 关键函数

push_back(value)：在末尾添加元素。
pop_back()：删除末尾元素。
size()：返回元素个数。
empty()：检查是否为空。
operator[] 和 at(index)：访问指定位置的元素。
front() 和 back()：访问第一个和最后一个元素。

# 2. `std::list`

描述：双向链表，适合频繁的插入和删除操作。

# 示例

#include <iostream>
#include <list>

int main() {
    // 创建一个空的 list，存储整数
    std::list<int> lst;

    // 使用 push_back() 和 push_front() 添加元素
    lst.push_back(10);
    lst.push_front(5);
    lst.push_back(15);

    // 遍历 list
    std::cout << "List 元素: ";
    for (const auto& elem : lst) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 删除一个元素
    lst.remove(10);

    std::cout << "删除 10 后: ";
    for (const auto& elem : lst) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

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

# 关键函数

push_back(value) 和 push_front(value)：在末尾或开头添加元素。
pop_back() 和 pop_front()：删除末尾或开头元素。
insert(iterator, value)：在指定位置插入元素。
erase(iterator)：删除指定位置的元素。
remove(value)：删除所有值为 value 的元素。
size() 和 empty()：获取大小和检查是否为空。
遍历可以使用范围 for 循环或迭代器。

# 3. `std::deque`

描述：双端队列，支持在两端高效插入和删除元素。

# 示例

#include <iostream>
#include <deque>

int main() {
    // 创建一个空的 deque，存储整数
    std::deque<int> dq;

    // 在两端添加元素
    dq.push_back(10);
    dq.push_front(5);
    dq.push_back(15);

    // 访问元素
    std::cout << "第一个元素: " << dq.front() << std::endl; // 输出 5
    std::cout << "最后一个元素: " << dq.back() << std::endl; // 输出 15

    // 遍历 deque
    std::cout << "Deque 元素: ";
    for (const auto& elem : dq) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 删除元素
    dq.pop_front();
    dq.pop_back();

    std::cout << "删除后: ";
    for (const auto& elem : dq) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

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
33
34
35

# 关键函数

push_back(value) 和 push_front(value)：在末尾或开头添加元素。
pop_back() 和 pop_front()：删除末尾或开头元素。
operator[] 和 at(index)：访问指定位置的元素。
size() 和 empty()：获取大小和检查是否为空。

# 4. `std::set`

描述：有序集合，元素唯一，基于平衡二叉树（通常是红黑树）实现。

# 示例

#include <iostream>
#include <set>

int main() {
    // 创建一个空的 set，存储整数
    std::set<int> s;

    // 添加元素
    s.insert(10);
    s.insert(5);
    s.insert(15);
    s.insert(10); // 重复元素不会被插入

    // 遍历 set
    std::cout << "Set 元素: ";
    for (const auto& elem : s) {
        std::cout << elem << " "; // 输出 5 10 15
    }
    std::cout << std::endl;

    // 查找元素
    auto it = s.find(10);
    if (it != s.end()) {
        std::cout << "找到元素: " << *it << std::endl;
    }

    // 删除元素
    s.erase(5);

    std::cout << "删除 5 后: ";
    for (const auto& elem : s) {
        std::cout << elem << " "; // 输出 10 15
    }
    std::cout << std::endl;

    return 0;
}

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
33
34
35
36
37

# 关键函数

insert(value)：插入元素，重复元素不会插入。
erase(value) 和 erase(iterator)：删除元素。
find(value)：查找元素，返回迭代器。
size() 和 empty()：获取大小和检查是否为空。
自动按升序排序（可以自定义排序方式）。

# 5. `std::map`

描述：有序字典，键值对集合，键唯一，基于平衡二叉树实现。

# 示例

#include <iostream>
#include <map>

int main() {
    // 创建一个空的 map，键为字符串，值为整数
    std::map<std::string, int> m;

    // 添加键值对
    m["apple"] = 5;
    m["banana"] = 3;
    m["orange"] = 7;

    // 遍历 map
    std::cout << "Map 内容:" << std::endl;
    for (const auto& pair : m) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 查找键
    auto it = m.find("banana");
    if (it != m.end()) {
        std::cout << "找到 banana，对应值为 " << it->second << std::endl;
    }

    // 删除键值对
    m.erase("apple");

    std::cout << "删除 apple 后:" << std::endl;
    for (const auto& pair : m) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

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
33
34

# 关键函数

operator[]：访问或插入键值对。
insert({key, value})：插入键值对。
erase(key) 和 erase(iterator)：删除键值对。
find(key)：查找键，返回迭代器。
size() 和 empty()：获取大小和检查是否为空。
自动按键升序排序（可以自定义排序方式）。

# 6. `std::unordered_set`

描述：无序集合，元素唯一，基于哈希表实现，提供常数时间复杂度的查找。

# 示例

#include <iostream>
#include <unordered_set>

int main() {
    // 创建一个空的 unordered_set，存储整数
    std::unordered_set<int> us;

    // 添加元素
    us.insert(10);
    us.insert(5);
    us.insert(15);
    us.insert(10); // 重复元素不会被插入

    // 遍历 unordered_set
    std::cout << "Unordered Set 元素: ";
    for (const auto& elem : us) {
        std::cout << elem << " "; // 输出顺序不确定
    }
    std::cout << std::endl;

    // 查找元素
    if (us.find(5) != us.end()) {
        std::cout << "找到元素 5" << std::endl;
    }

    // 删除元素
    us.erase(10);

    std::cout << "删除 10 后: ";
    for (const auto& elem : us) {
        std::cout << elem << " "; // 10 被删除
    }
    std::cout << std::endl;

    return 0;
}

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
33
34
35
36

# 关键函数

insert(value)：插入元素，重复元素不会插入。
erase(value) 和 erase(iterator)：删除元素。
find(value)：查找元素，返回迭代器。
size() 和 empty()：获取大小和检查是否为空。
无序存储，元素顺序不确定。

# 7. `std::unordered_map`

描述：无序字典，键值对集合，键唯一，基于哈希表实现，提供常数时间复杂度的查找。

# 示例

#include <iostream>
#include <unordered_map>

int main() {
    // 创建一个空的 unordered_map，键为字符串，值为整数
    std::unordered_map<std::string, int> um;

    // 添加键值对
    um["apple"] = 5;
    um["banana"] = 3;
    um["orange"] = 7;

    // 遍历 unordered_map
    std::cout << "Unordered Map 内容:" << std::endl;
    for (const auto& pair : um) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 查找键
    auto it = um.find("banana");
    if (it != um.end()) {
        std::cout << "找到 banana，对应值为 " << it->second << std::endl;
    }

    // 删除键值对
    um.erase("apple");

    std::cout << "删除 apple 后:" << std::endl;
    for (const auto& pair : um) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

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
33
34

# 关键函数

operator[]：访问或插入键值对。
insert({key, value})：插入键值对。
erase(key) 和 erase(iterator)：删除键值对。
find(key)：查找键，返回迭代器。
size() 和 empty()：获取大小和检查是否为空。
无序存储，键的顺序不确定。

# 8. `std::stack`

描述：后进先出（LIFO）栈，基于 deque 或其他容器实现。

# 示例

#include <iostream>
#include <stack>

int main() {
    // 创建一个空的 stack，存储整数
    std::stack<int> stk;

    // 添加元素
    stk.push(10);
    stk.push(20);
    stk.push(30);

    // 访问栈顶元素
    std::cout << "栈顶元素: " << stk.top() << std::endl; // 输出 30

    // 弹出元素
    stk.pop();

    std::cout << "弹出后，栈顶元素: " << stk.top() << std::endl; // 输出 20

    // 检查栈是否为空
    if (!stk.empty()) {
        std::cout << "栈不为空，大小为: " << stk.size() << std::endl; // 输出 2
    }

    return 0;
}

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

# 关键函数

push(value)：在栈顶添加元素。
pop()：删除栈顶元素。
top()：访问栈顶元素。
empty() 和 size()：检查是否为空和获取大小。

# 9. `std::queue`

描述：先进先出（FIFO）队列，基于 deque 或其他容器实现。

# 示例

#include <iostream>
#include <queue>

int main() {
    // 创建一个空的 queue，存储整数
    std::queue<int> q;

    // 添加元素
    q.push(10);
    q.push(20);
    q.push(30);

    // 访问队首元素
    std::cout << "队首元素: " << q.front() << std::endl; // 输出 10
    std::cout << "队尾元素: " << q.back() << std::endl; // 输出 30

    // 弹出元素
    q.pop();

    std::cout << "弹出后，队首元素: " << q.front() << std::endl; // 输出 20

    // 检查队列是否为空
    if (!q.empty()) {
        std::cout << "队列不为空，大小为: " << q.size() << std::endl; // 输出 2
    }

    return 0;
}

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

# 关键函数

push(value)：在队尾添加元素。
pop()：删除队首元素。
front()：访问队首元素。
back()：访问队尾元素。
empty() 和 size()：检查是否为空和获取大小。

# 10. `std::bitset`

描述：定长的二进制位数组，适用于位操作。

# 示例

#include <iostream>
#include <bitset>

int main() {
    // 创建一个 8 位的 bitset
    std::bitset<8> bits(std::string("10110011"));

    // 输出 bitset
    std::cout << "Bitset: " << bits << std::endl; // 输出 10110011

    // 访问特定位
    std::cout << "第0位: " << bits[0] << std::endl; // 输出 1

    // 设置某位
    bits.set(1); // 设置第1位为1
    std::cout << "设置第1位后: " << bits << std::endl; // 输出 10110011 -> 10110011（已经是1）

    // 重置某位
    bits.reset(0); // 重置第0位为0
    std::cout << "重置第0位后: " << bits << std::endl; // 输出 10110010

    // 翻转所有位
    bits.flip();
    std::cout << "翻转后: " << bits << std::endl; // 输出 01001101

    // 计数1的个数
    std::cout << "1的个数: " << bits.count() << std::endl; // 输出 4

    return 0;
}

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

# 关键函数

set(pos)：将指定位置的位设置为1。
reset(pos)：将指定位置的位设置为0。
flip(pos)：翻转指定位置的位。
count()：返回设置为1的位的个数。
size()：返回 bitset 的总位数。
test(pos)：检查指定位置的位是否为1。
支持位运算（&, |, ^, ~ 等）。

# 11. `std::array`

描述：定长数组，大小在编译时固定，提供类似于 vector 的接口。

# 示例

#include <iostream>
#include <array>

int main() {
    // 创建一个包含 5 个整数的 array
    std::array<int, 5> arr = {1, 2, 3, 4, 5};

    // 访问元素
    std::cout << "第一个元素: " << arr[0] << std::endl; // 输出 1
    std::cout << "最后一个元素: " << arr.back() << std::endl; // 输出 5

    // 遍历 array
    std::cout << "Array 元素: ";
    for (const auto& elem : arr) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 修改元素
    arr[2] = 10;
    std::cout << "修改后的第三个元素: " << arr[2] << std::endl; // 输出 10

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 关键函数

at(index)：访问指定位置的元素，带边界检查。
operator[]：访问指定位置的元素，不带边界检查。
front() 和 back()：访问第一个和最后一个元素。
fill(value)：将所有元素设置为指定值。
size() 和 empty()：获取大小和检查是否为空。
支持范围 for 循环和迭代器。

# 12. `std::forward_list`

描述：单向链表，比 std::list 更轻量级，适合只需要单向遍历的场景。

# 示例

#include <iostream>
#include <forward_list>

int main() {
    // 创建一个空的 forward_list，存储整数
    std::forward_list<int> flist;

    // 使用 push_front() 添加元素
    flist.push_front(10);
    flist.push_front(20);
    flist.push_front(30);

    // 遍历 forward_list
    std::cout << "Forward List 元素: ";
    for (const auto& elem : flist) {
        std::cout << elem << " "; // 输出 30 20 10
    }
    std::cout << std::endl;

    // 插入元素
    auto it = flist.begin();
    ++it; // 指向第二个元素
    flist.insert_after(it, 25);

    std::cout << "插入 25 后: ";
    for (const auto& elem : flist) {
        std::cout << elem << " "; // 输出 30 20 25 10
    }
    std::cout << std::endl;

    // 删除元素
    flist.remove(20);

    std::cout << "删除 20 后: ";
    for (const auto& elem : flist) {
        std::cout << elem << " "; // 输出 30 25 10
    }
    std::cout << std::endl;

    return 0;
}

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
33
34
35
36
37
38
39
40
41

# 关键函数

push_front(value)：在开头添加元素。
insert_after(iterator, value)：在指定位置后插入元素。
erase_after(iterator)：删除指定位置后的元素。
remove(value)：删除所有值为 value 的元素。
begin() 和 end()：获取迭代器以遍历列表。
empty() 和 size()：注意，std::forward_list 不直接支持 size()，需要手动计算。

# 13. `std::multiset`

描述：允许重复元素的有序集合，基于平衡二叉树实现。

# 示例

#include <iostream>
#include <set>

int main() {
    // 创建一个 multiset，存储整数
    std::multiset<int> ms;

    // 添加元素，包括重复元素
    ms.insert(10);
    ms.insert(5);
    ms.insert(10);
    ms.insert(15);

    // 遍历 multiset
    std::cout << "Multiset 元素: ";
    for (const auto& elem : ms) {
        std::cout << elem << " "; // 输出 5 10 10 15
    }
    std::cout << std::endl;

    // 查找元素
    auto range = ms.equal_range(10);
    std::cout << "元素 10 的出现次数: " << std::distance(range.first, range.second) << std::endl;

    // 删除一个特定的元素（只删除一个）
    ms.erase(ms.find(10));

    std::cout << "删除一个 10 后: ";
    for (const auto& elem : ms) {
        std::cout << elem << " "; // 输出 5 10 15
    }
    std::cout << std::endl;

    return 0;
}

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
33
34
35

# 关键函数

insert(value)：插入元素，可以重复。
erase(value)：删除所有值为 value 的元素，或使用迭代器删除特定元素。
find(value)：查找第一个值为 value 的元素，返回迭代器。
equal_range(value)：返回值为 value 的元素范围。
count(value)：返回值为 value 的元素个数。
自动按升序排序。

# 14. `std::multimap`

描述：允许重复键的有序字典，基于平衡二叉树实现。

# 示例

#include <iostream>
#include <map>

int main() {
    // 创建一个 multimap，键为字符串，值为整数
    std::multimap<std::string, int> mm;

    // 添加键值对，包括重复键
    mm.insert({"apple", 5});
    mm.insert({"banana", 3});
    mm.insert({"apple", 10});
    mm.insert({"orange", 7});

    // 遍历 multimap
    std::cout << "Multimap 内容:" << std::endl;
    for (const auto& pair : mm) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 查找键
    auto range = mm.equal_range("apple");
    std::cout << "键 'apple' 对应的值: ";
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << " "; // 输出 5 10
    }
    std::cout << std::endl;

    // 删除一个特定的键值对
    auto it = mm.find("banana");
    if (it != mm.end()) {
        mm.erase(it);
    }

    std::cout << "删除 banana 后:" << std::endl;
    for (const auto& pair : mm) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

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
33
34
35
36
37
38
39
40

# 关键函数

insert({key, value})：插入键值对，可以重复键。
erase(key) 和 erase(iterator)：删除键值对。
find(key)：查找第一个匹配键的元素，返回迭代器。
equal_range(key)：返回匹配键的元素范围。
count(key)：返回匹配键的元素个数。
自动按键升序排序。

# 15. `std::unordered_multiset`

描述：允许重复元素的无序集合，基于哈希表实现。

# 示例

#include <iostream>
#include <unordered_set>

int main() {
    // 创建一个 unordered_multiset，存储整数
    std::unordered_multiset<int> ums;

    // 添加元素，包括重复元素
    ums.insert(10);
    ums.insert(5);
    ums.insert(10);
    ums.insert(15);

    // 遍历 unordered_multiset
    std::cout << "Unordered Multiset 元素: ";
    for (const auto& elem : ums) {
        std::cout << elem << " "; // 输出顺序不确定，可能是 10 5 10 15
    }
    std::cout << std::endl;

    // 查找元素
    auto range = ums.equal_range(10);
    std::cout << "元素 10 的出现次数: " << std::distance(range.first, range.second) << std::endl;

    // 删除一个特定的元素（只删除一个）
    ums.erase(ums.find(10));

    std::cout << "删除一个 10 后: ";
    for (const auto& elem : ums) {
        std::cout << elem << " "; // 可能是 5 10 15
    }
    std::cout << std::endl;

    return 0;
}

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
33
34
35

# 关键函数

insert(value)：插入元素，可以重复。
erase(value) 和 erase(iterator)：删除元素。
find(value)：查找第一个匹配的元素，返回迭代器。
equal_range(value)：返回匹配元素的范围。
count(value)：返回匹配元素的个数。
无序存储，元素顺序不确定。

# 16. `std::unordered_multimap`

描述：允许重复键的无序字典，基于哈希表实现。

# 示例

#include <iostream>
#include <unordered_map>

int main() {
    // 创建一个 unordered_multimap，键为字符串，值为整数
    std::unordered_multimap<std::string, int> umm;

    // 添加键值对，包括重复键
    umm.insert({"apple", 5});
    umm.insert({"banana", 3});
    umm.insert({"apple", 10});
    umm.insert({"orange", 7});

    // 遍历 unordered_multimap
    std::cout << "Unordered Multimap 内容:" << std::endl;
    for (const auto& pair : umm) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 查找键
    auto range = umm.equal_range("apple");
    std::cout << "键 'apple' 对应的值: ";
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << " "; // 输出 5 10
    }
    std::cout << std::endl;

    // 删除一个特定的键值对
    auto it = umm.find("banana");
    if (it != umm.end()) {
        umm.erase(it);
    }

    std::cout << "删除 banana 后:" << std::endl;
    for (const auto& pair : umm) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

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
33
34
35
36
37
38
39
40

# 关键函数

insert({key, value})：插入键值对，可以重复键。
erase(key) 和 erase(iterator)：删除键值对。
find(key)：查找第一个匹配键的元素，返回迭代器。
equal_range(key)：返回匹配键的元素范围。
count(key)：返回匹配键的元素个数。
无序存储，键的顺序不确定。

下面是 C++ 标准库中一些常见数据结构的关键函数的时间复杂度总结：

# 1. `std::vector`

访问元素（operator[] 或 at）: O(1)
插入元素到末尾（push_back）: 平摊 O(1)
插入或删除元素（中间位置）: O(n)
删除末尾元素（pop_back）: O(1)
大小（size）: O(1)

# 2. `std::deque`

访问元素（operator[] 或 at）: O(1)
插入或删除元素（两端）: O(1)
插入或删除元素（中间位置）: O(n)
大小（size）: O(1)

# 3. `std::list`（双向链表）

访问元素（双向遍历）: O(n)
插入或删除元素（任意位置，已知迭代器）: O(1)
大小（size）: O(1)

# 4. `std::forward_list`（单向链表）

访问元素（单向遍历）: O(n)
插入或删除元素（任意位置，已知迭代器）: O(1)
大小（size）: O(n)（没有内置的 size 计数）

# 5. `std::set`/`std::multiset`（有序平衡二叉树）

插入元素（insert）: O(log n)
删除元素（erase）: O(log n)
查找元素（find、count、lower_bound、upper_bound）: O(log n)
大小（size）: O(1)

# 6. `std::map`/`std::multimap`（有序平衡二叉树）

访问元素（operator[] 或 at）: O(log n)
插入元素（insert）: O(log n)
删除元素（erase）: O(log n)
查找元素（find、count、lower_bound、upper_bound）: O(log n)
大小（size）: O(1)

# 7. `std::unordered_set`/`std::unordered_multiset`（哈希表）

插入元素（insert）: 平均 O(1)，最坏 O(n)
删除元素（erase）: 平均 O(1)，最坏 O(n)
查找元素（find、count）: 平均 O(1)，最坏 O(n)
大小（size）: O(1)

# 8. `std::unordered_map`/`std::unordered_multimap`（哈希表）

访问元素（operator[] 或 at）: 平均 O(1)，最坏 O(n)
插入元素（insert）: 平均 O(1)，最坏 O(n)
删除元素（erase）: 平均 O(1)，最坏 O(n)
查找元素（find、count）: 平均 O(1)，最坏 O(n)
大小（size）: O(1)

# 9. `std::priority_queue`（基于堆的优先级队列）

插入元素（push）: O(log n)
删除最大元素（pop）: O(log n)
获取最大元素（top）: O(1)
大小（size）: O(1)

# 10. `std::stack`（基于 `deque` 或 `vector`）

插入元素（push）: O(1)
删除顶元素（pop）: O(1)
获取顶元素（top）: O(1)
大小（size）: O(1)

# 11. `std::queue`（基于 `deque` 或 `list`）

插入元素（push 或 emplace）: O(1)
删除头元素（pop）: O(1)
获取头元素（front）: O(1)
获取尾元素（back）: O(1)
大小（size）: O(1)

这些是 C++ 标准库中常用数据结构的关键函数及其时间复杂度和空间复杂度。这些复杂度有助于在不同情况下选择合适的数据结构。

编辑

上次更新: 2024/09/13, 11:59:12

← 内置数据结构 go和c++对比→

数据结构示例

# 1. std::vector

# 示例

# 关键函数

# 2. std::list

# 示例

# 关键函数

# 3. std::deque

# 示例

# 关键函数

# 4. std::set

# 示例

# 关键函数

# 5. std::map

# 示例

# 关键函数

# 6. std::unordered_set

# 示例

# 关键函数

# 7. std::unordered_map

# 示例

# 关键函数

# 8. std::stack

# 示例

# 关键函数

# 9. std::queue

# 示例

# 关键函数

# 10. std::bitset

# 示例

# 关键函数

# 11. std::array

# 示例

# 关键函数

# 12. std::forward_list

# 示例

# 关键函数

# 13. std::multiset

# 示例

# 关键函数

# 14. std::multimap

# 示例

# 关键函数

# 15. std::unordered_multiset

# 示例

# 关键函数

# 16. std::unordered_multimap

# 示例

# 关键函数

# 1. std::vector

# 2. std::deque

# 3. std::list（双向链表）

# 4. std::forward_list（单向链表）

# 5. std::set/std::multiset（有序平衡二叉树）

# 6. std::map/std::multimap（有序平衡二叉树）

# 7. std::unordered_set/std::unordered_multiset（哈希表）

# 8. std::unordered_map/std::unordered_multimap（哈希表）

# 9. std::priority_queue（基于堆的优先级队列）

# 10. std::stack（基于 deque 或 vector）

# 11. std::queue（基于 deque 或 list）

# 1. `std::vector`

# 2. `std::list`

# 3. `std::deque`

# 4. `std::set`

# 5. `std::map`

# 6. `std::unordered_set`

# 7. `std::unordered_map`

# 8. `std::stack`

# 9. `std::queue`

# 10. `std::bitset`

# 11. `std::array`

# 12. `std::forward_list`

# 13. `std::multiset`

# 14. `std::multimap`

# 15. `std::unordered_multiset`

# 16. `std::unordered_multimap`

# 1. `std::vector`

# 2. `std::deque`

# 3. `std::list`（双向链表）

# 4. `std::forward_list`（单向链表）

# 5. `std::set`/`std::multiset`（有序平衡二叉树）

# 6. `std::map`/`std::multimap`（有序平衡二叉树）

# 7. `std::unordered_set`/`std::unordered_multiset`（哈希表）

# 8. `std::unordered_map`/`std::unordered_multimap`（哈希表）

# 9. `std::priority_queue`（基于堆的优先级队列）

# 10. `std::stack`（基于 `deque` 或 `vector`）

# 11. `std::queue`（基于 `deque` 或 `list`）