内置数据结构

C++ 标准库提供了多种数据结构，每种数据结构在不同场景下具有不同的应用和性能特性。以下是 C++ 中一些常用的数据结构：

# 0. `std::priority_queue`

最大堆（最大优先级在顶部），元素按照优先级顺序被访问。
特性：元素插入后自动排序。
复杂度：O(1) 随机访问，O(1) 末尾添加，O(n) 插入或删除。

# 1. `std::vector`

动态数组，可以在末尾添加和删除元素，支持随机访问。
特性：自动扩展大小，元素存储在连续的内存块中。
复杂度：O(1) 随机访问，O(1) 末尾添加，O(n) 插入或删除。
底层结构：一段连续的内存空间。这意味着vector中所有的元素在内存中是顺序存储的，类似于一个动态数组。

# 2. `std::list`

双向链表，允许快速的插入和删除操作。
特性：不支持随机访问，适合频繁插入或删除操作的场景。
复杂度：O(1) 插入或删除，O(n) 访问。
底层结构：一个双向链表，这意味着它的内存是非连续的。

# 3. `std::deque`

双端队列，支持在两端快速插入和删除元素。
特性：类似 vector，但允许在两端高效操作。
复杂度：O(1) 随机访问，O(1) 两端插入或删除。
底层结构：介于vector和list之间的折中方案，每一小块连续，但整体不一定连续。这提供了一种兼具内存效率和操作灵活性的设计。

# 4. `std::set`

有序集合，元素按照键值自动排序，所有元素唯一。
特性：基于红黑树实现，适合需要有序、不重复元素的场景。
复杂度：O(log n) 插入、删除、查找。
std::set 中的元素是有序的，通常按照升序排列。以下是一个示例，展示了如何遍历 std::set 并输出其元素，确保输出的顺序是从小到大的。

#include <set>  
int main() {
    // 创建一个 set   
    std::set<int> mySet = {1, 4, 8, 20};  
    // 插入元素
    mySet.insert(6);
    // 删除元素
    mySet.erase(6);
    //查找元素 
    auto it = mySet.find(4);
    if (it != mySet.end()) {
        cout <<"*it:" << *it <<endl; //4
    }
    // 统计元素
    auto c = mySet.count(4);
    cout << "count " << c <<endl;    //1

    // lower_bound 返回指向第一个不小于指定值的元素的迭代器。
    auto lowIt = mySet.lower_bound(8);
    cout << "lower_bound:" << *lowIt <<endl;//8

    // upper_bound, 返回指向第一个大于指定值的元素的迭代器。
    auto it2 = mySet.upper_bound(8);
    cout << "upper_bound:" << *it2 <<endl;//20
    
    // 遍历 set  
    for (const auto& elem : mySet) {  
            std::cout << elem << " ";  //1 4 8 20
    } 
}

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

// 自定义比较函数  
struct CustomComparator {  
    bool operator()(const std::string& a, const std::string& b) const {  
        // 按长度排序，如果长度相同则按字典顺序排序  
        if (a.size() != b.size()) {  
            return a.size() < b.size();  
        }  
        return a < b;  
    }  
};  

int main() {  
    // 使用自定义比较函数构造 set  
    std::set<std::string, CustomComparator> mySet;  
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 5. `std::map`

有序字典，键值对的集合，键按顺序排列。
特性：基于红黑树实现，键值对唯一。
复杂度：O(log n) 插入、删除、查找。
自定义排序规则map，按照key

// 自定义比较函数  
struct CustomComparator {  
    bool operator()(const std::string& a, const std::string& b) const {  
        // 按长度排序，如果长度相同则按字典顺序排序  
        if (a.size() != b.size()) {  
            return a.size() < b.size();  
        }  
        return a < b;  
    }  
};  

int main() {  
    // 使用自定义比较函数构造 map  
    std::map<std::string, int, CustomComparator> myMap;  

    // 插入元素  
    myMap["apple"] = 1;  
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

自定义排序规则map，按照value

#include <map>  
#include <vector>  
// 函数用于根据值排序  
bool compareByValue(const std::pair<std::string, int>& a, const std::pair<std::string, int>& b) {  
    return a.second < b.second; // 按值升序排序  
}  

int main() {  
    // 创建一个 map  
    std::map<std::string, int> myMap;  
    myMap["apple"] = 3;  
    myMap["banana"] = 1;   

    // 将 map 转换为 vector 以便排序  
    std::vector<std::pair<std::string, int>> vec(myMap.begin(), myMap.end());  
    // 根据值排序  
    std::sort(vec.begin(), vec.end(), compareByValue);  
    for (const auto& pair : vec) {  
        std::cout << pair.first << ": " << pair.second << std::endl;  
    }  
}

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

# 6. `std::unordered_set`

无序集合，元素不按顺序存储，所有元素唯一。
特性：基于哈希表实现，适合需要快速查找、不重复元素的场景。
复杂度：O(1) 插入、删除、查找（平均）。
遍历 std::unordered_set 的结果是无序的，因为它是基于哈希表实现的。以下是一个示例，展示了如何遍历 std::unordered_set 并输出其元素。由于元素的存储顺序是随机的，每次运行程序时输出的顺序可能会不同。

// 创建一个 unordered_set 并插入元素  
std::unordered_set<int> mySet = {5, 1, 3, 2, 4};  
// 遍历 unordered_set  
std::cout << "Elements in unordered_set: ";  
for (const auto& elem : mySet) {  
        std::cout << elem << " ";  
}

1
2
3
4
5
6
7

# 7. `std::unordered_map`

无序字典，键值对的集合，键不按顺序存储。
特性：基于哈希表实现，适合需要快速查找的键值对集合。
复杂度：O(1) 插入、删除、查找（平均）。

# 8. `std::stack`

后进先出（LIFO）栈，基于 deque 实现。
特性：只允许在一端（栈顶）插入和删除元素。
复杂度：O(1) 插入和删除。

# 9. `std::queue`

先进先出（FIFO）队列，基于 deque 实现。
特性：只允许在一端（队尾）插入，在另一端（队首）删除。
复杂度：O(1) 插入和删除。

# 10. `std::deque`

双端队列，既可以在队首也可以在队尾高效插入和删除。
特性：允许在两端进行高效的插入和删除操作。
复杂度：O(1) 插入和删除。
分段结构：deque 将元素存储在多个小的连续内存块中，每个内存块包含若干个元素，这些内存块之间是不连续的。
指针数组管理：deque 使用一个指针数组来管理这些内存块，指针数组本身是连续的，但每个指针指向一个内存块，这些内存块彼此之间可能不连续。

# 11. `std::bitset`

定长的二进制位数组，适用于位操作。
特性：高效存储和操作二进制位。
复杂度：O(1) 位操作。

# 12. `std::array`

定长数组，大小在编译时固定。
特性：提供类似于 vector 的接口，但大小固定且不能动态调整。
复杂度：O(1) 随机访问。

# 13. `std::forward_list`

单向链表，比 std::list 更轻量级。
特性：适合只需要单向遍历和操作的场景。
复杂度：O(1) 插入或删除，O(n) 访问。

# 14. `std::multiset`

允许重复元素的有序集合，元素按顺序存储。
特性：基于红黑树实现，适合需要有序、允许重复元素的场景。
复杂度：O(log n) 插入、删除、查找。

# 15. `std::multimap`

允许重复键的有序字典，键按顺序排列。
特性：基于红黑树实现，适合需要有序、允许重复键的键值对集合。
复杂度：O(log n) 插入、删除、查找。

# 16. `std::unordered_multiset`

允许重复元素的无序集合，元素不按顺序存储。
特性：基于哈希表实现，适合需要快速查找、允许重复元素的场景。
复杂度：O(1) 插入、删除、查找（平均）。

# 17. `std::unordered_multimap`

允许重复键的无序字典，键不按顺序存储。
特性：基于哈希表实现，适合需要快速查找、允许重复键的键值对集合。
复杂度：O(1) 插入、删除、查找（平均）。

# 总结

C++ 提供了丰富的数据结构，每种数据结构都有其特定的用途和性能特点。根据不同的应用场景选择合适的数据结构，可以有效提升程序的性能和代码的简洁性。

编辑

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

← vector、deque、list 数据结构示例→

内置数据结构

# 0. std::priority_queue

# 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::deque

# 11. std::bitset

# 12. std::array

# 13. std::forward_list

# 14. std::multiset

# 15. std::multimap

# 16. std::unordered_multiset

# 17. std::unordered_multimap