c++容器 和数据结构

stl容器实现使用的数据结构

C++ STL 的容器实现背后使用了不同的底层数据结构，根据容器的类型和需求，选择了最适合的实现。 STL 常用容器及其底层数据结构的说明：

1. std::vector

• 底层数据结构：动态数组
• 特点：std::vector 使用一块连续的内存来存储元素，类似于动态数组。当容量不足时，它会分配一个更大的内存块并将现有元素拷贝到新内存块中。
• 时间复杂度：随机访问为 O(1)，末尾插入和删除为均摊 O(1)，但插入时扩容可能会导致 O(n) 的代价。

2. std::deque

• 底层数据结构：双端队列
• 特点：std::deque 使用一系列连续的内存块，而不是一块完整的连续内存。这使得它可以在头尾两端高效地插入和删除元素。
• 时间复杂度：头尾插入和删除操作为 O(1)，随机访问为 O(1)。

3. std::list

• 底层数据结构：双向链表
• 特点：std::list 是一个双向链表，每个节点都包含指向前一个和后一个节点的指针。它适合频繁的插入和删除操作。
• 时间复杂度：插入和删除为 O(1)，但不支持随机访问，遍历的时间复杂度为 O(n)。

4. std::forward_list

• 底层数据结构：单向链表
• 特点：std::forward_list 是一个单向链表，与 std::list 类似，但每个节点只包含一个指向下一个节点的指针，节省了内存。
• 时间复杂度：插入和删除为 O(1)，遍历为 O(n)，不支持随机访问。

5. std::set 和 std::map

• 底层数据结构：红黑树（自平衡二叉搜索树）
• 特点：std::set 是一个有序集合，不允许重复元素；std::map 是一个有序键值对容器。两者都基于红黑树实现，确保插入、删除、查找等操作的时间复杂度为 O(log n)。
• 时间复杂度：插入、删除、查找为 O(log n)。

6. std::multiset 和 std::multimap

• 底层数据结构：红黑树
• 特点：std::multiset 允许重复元素，而 std::multimap 允许多个相同键的键值对。两者同样基于红黑树实现，时间复杂度与 set 和 map 相同。
• 时间复杂度：插入、删除、查找为 O(log n)。

7. std::unordered_set 和 std::unordered_map

• 底层数据结构：哈希表
• 特点：std::unordered_set 是无序集合，std::unordered_map 是无序键值对容器。它们基于哈希表实现，查找、插入和删除操作的平均时间复杂度为 O(1)，但最坏情况为 O(n)。
• 时间复杂度：插入、删除、查找为平均 O(1)，最坏情况 O(n)。

8. std::unordered_multiset 和 std::unordered_multimap

• 底层数据结构：哈希表
• 特点：std::unordered_multiset 允许重复元素，std::unordered_multimap 允许多个相同键的键值对，且二者基于哈希表实现。
• 时间复杂度：插入、删除、查找为平均 O(1)，最坏情况 O(n)。

9. std::stack

• 底层数据结构：适配器（通常基于 std::deque 或 std::vector）
• 特点：std::stack 是容器适配器，默认基于 std::deque 实现。它封装了基本的栈操作，后进先出（LIFO）。
• 时间复杂度：插入和删除为 O(1)。

10. std::queue

• 底层数据结构：适配器（通常基于 std::deque 或 std::list）
• 特点：std::queue 是容器适配器，默认基于 std::deque 实现，支持先进先出（FIFO）。
• 时间复杂度：插入和删除为 O(1)。

11. std::priority_queue

• 底层数据结构：最大堆（通常基于 std::vector）
• 特点：std::priority_queue 基于最大堆实现，支持高效地获取优先级最高的元素。
• 时间复杂度：插入和删除为 O(log n)，访问最大值为 O(1)。

12. std::array

• 底层数据结构：静态数组
• 特点：std::array 是一个固定大小的数组，大小在编译时确定。它的行为类似于 C 风格的数组，但带有更多的 STL 特性。
• 时间复杂度：随机访问为 O(1)。

13. std::bitset

• 底层数据结构：位数组
• 特点：std::bitset 是用于处理位的集合的结构。它用位数组表示固定大小的二进制数，适合位操作。
• 时间复杂度：按位操作为 O(1)。

14. std::string

• 底层数据结构：动态数组
• 特点：std::string 作为字符序列，底层通常实现为动态数组，支持字符的随机访问和字符串的拼接等操作。
• 时间复杂度：随机访问为 O(1)，拼接的时间复杂度取决于具体实现。

这些容器的底层实现选择了不同的数据结构以满足不同的使用需求：有些注重高效的随机访问（如 vector），有些适合快速的插入和删除操作（如 list），而有些则专注于快速查找和有序性（如 map 和 set）。通过这些实现，STL 提供了强大且灵活的容器工具，可以适应各种不同的编程场景。

数据结构

数据结构是指在计算机中存储和组织数据的方式，不同的数据结构适用于不同的应用场景。根据数据的存储方式、访问方式和操作方式，数据结构可以分为以下几大类：

1. 线性数据结构

在这种结构中，数据以线性顺序排列，每个元素仅与前一个和后一个元素有关系。常见的线性数据结构包括：

• 数组（Array）：固定大小的连续内存块，每个元素都可以通过索引直接访问，时间复杂度为 O(1)。
• 链表（Linked List）：由节点组成的线性结构，每个节点包含数据以及指向下一个节点的指针。常见类型有：
  • 单向链表（Singly Linked List）
  • 双向链表（Doubly Linked List）
  • 循环链表（Circular Linked List）
• 栈（Stack）：一种后进先出（LIFO，Last In First Out）的数据结构，只允许在一端插入和删除数据。常见操作是 push（入栈）和 pop（出栈）。
• 队列（Queue）：一种先进先出（FIFO，First In First Out）的数据结构，数据从一端入队，从另一端出队。变种包括：
  • 双端队列（Deque）：两端都可以进行插入和删除操作。
  • 优先队列（Priority Queue）：每个元素都有优先级，优先级高的元素会先出队。
• 字符串（String）：可以看作是字符数组，常用于处理字符序列。标准库如 C++ 的 std::string。

2. 树形数据结构

树是一种非线性数据结构，由节点和边组成，呈现层次关系。常见的树结构包括：

• 二叉树（Binary Tree）：每个节点最多有两个子节点，分别称为左子节点和右子节点。
  • 满二叉树（Full Binary Tree）：每个节点要么有两个子节点，要么没有子节点。
  • 完全二叉树（Complete Binary Tree）：除了最后一层，其他层都被完全填满，最后一层从左到右顺序填充。
  • 平衡二叉树（Balanced Binary Tree）：确保左右子树的高度差不超过 1。
  • 二叉搜索树（Binary Search Tree, BST）：左子节点小于父节点，右子节点大于父节点。
• 红黑树（Red-Black Tree）：一种自平衡的二叉搜索树，保证插入和删除的时间复杂度为 O(log n)。
• AVL 树（AVL Tree）：另一种自平衡的二叉搜索树，通过调整树的高度来保证平衡。
• B 树（B-Tree）：一种多路搜索树，广泛用于数据库和文件系统中，节点可以拥有多个子节点。
• 堆（Heap）：一种特殊的二叉树，分为最大堆和最小堆，常用于优先队列和堆排序。
• Trie（字典树）：主要用于字符串处理，特别是用于快速查找前缀匹配的操作。

3. 图（Graph）

图是一种非线性数据结构，由顶点（节点）和边组成，边可以是有向或无向的。图可以表示为：

• 邻接矩阵（Adjacency Matrix）：使用二维数组表示图，适用于密集图。
• 邻接表（Adjacency List）：使用链表或数组的数组表示，适用于稀疏图。
• 图的类型：
  • 有向图（Directed Graph, Digraph）：边有方向。
  • 无向图（Undirected Graph）：边没有方向。
  • 加权图（Weighted Graph）：边具有权重。
  • 无环图（Acyclic Graph）：图中没有环。
  • 连通图（Connected Graph）：图中每两个节点间都有路径。

4. 哈希表（Hash Table）

哈希表是一种通过哈希函数将键映射到数组位置的结构，具有快速的插入和查找操作，平均时间复杂度为 O(1)。哈希表包括：

• 哈希映射（Hash Map）：存储键值对（key-value pairs），键通过哈希函数映射到桶中。
• 解决哈希冲突的方法：
  • 开放地址法（Open Addressing）：冲突时寻找其他可用位置。
  • 链地址法（Chaining）：将冲突的键存储在链表或其他容器中。

5. 集合（Set）

集合是一个无序的元素集合，元素不能重复。常见的集合结构包括：

• 集合（Set）：保证元素唯一性，通常通过哈希表或树实现。
• 位图（Bitmap）或布隆过滤器（Bloom Filter）：一种基于位数组的集合结构，用于空间高效的集合表示。

6. 其他数据结构

• 矩阵（Matrix）：二维数组，常用于处理图像、图论、线性代数等问题。
• 栈与队列的扩展：
  • 环形缓冲区（Circular Buffer）：一种固定大小的队列，当缓冲区满时新数据覆盖旧数据。
• 跳表（Skip List）：通过在链表的基础上增加多级索引实现的结构，提供 O(log n) 的查找、插入、删除性能。

7. 高级数据结构

• 并查集（Disjoint Set / Union-Find）：一种用于处理不相交集合合并及查询操作的数据结构，常用于图的连通性问题。
• 拓扑排序（Topological Sort）：用于对有向无环图（DAG）进行排序。
• 线段树（Segment Tree）：用于处理数组区间查询的问题，如求区间最小值、最大值或和。
• 树状数组（Binary Indexed Tree, BIT）：用于高效处理前缀和、区间更新等问题。

总结

不同的数据结构适用于不同类型的问题。线性数据结构（如数组、链表）适合顺序处理数据，树形和图结构适合处理具有层次关系或网络状数据，哈希表和集合适合快速查找，堆则适合处理优先级问题。根据具体问题选择合适的数据结构，可以显著提高算法的性能。

原文地址：https://blog.csdn.net/weixin_43881088/article/details/142861004

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！