c++里面自带的数据结构

<think>嗯，用户想了解C++标准库中的数据结构列表。这个问题很专业，说明用户有一定C++基础。从用户提到的"standard library data structures"来看，ta可能正在学习STL或者准备面试。 用户提供的引用资料已经涵盖了STL的核心概念。引用[1]和[2]解释了STL是什么，引用[3]给出了vector的代码示例，引用[4]则点明了数据结构的重要性。这些正好可以组成完整的回答框架。 需要特别注意几点： 第一，STL容器分为序列容器、关联容器等类别，每类都有典型代表。比如vector和array属于序列容器，map/set属于关联容器。这点必须清晰分类。 第二，用户要求的是"list"，但list在STL中特指双向链表。为避免混淆，回答时既要包含list容器，也要说明这是完整的数据结构列表。 第三，C++11之后新增的容器如unordered_set、array等需要特别标注，这对用户选择合适容器很重要。 第四，性能特征必须说明，比如vector的尾部O(1)插入、map的O(log n)查找。用户实际使用时最关心的就是这些。 第五，适配器如stack/queue虽然不算完整容器，但作为常用数据结构必须包含。 最后考虑设计相关问题。用户问的是数据结构列表，后续可能想了解具体容器的使用场景或性能对比。可以围绕容器选择、新标准特性、底层实现来设计问题，帮助用户深入理解。</think>以下是C++标准库（STL）中主要数据结构的分类列表及其核心特性： ### 📦 一、序列容器（按线性顺序存储） 1. **`vector`** - 动态数组，支持快速随机访问（$O(1)$） - 尾部插入/删除高效（$O(1)$ 均摊），中间操作 $O(n)$ - 示例：`std::vector<int> v = {1,2,3};` 2. **`deque`** - 双端队列，头尾插入/删除 $O(1)$ - 随机访问 $O(1)$，内存非连续 3. **`list`** - 双向链表，任意位置插入/删除 $O(1)$ - 不支持随机访问，遍历 $O(n)$ - 示例：`std::list<std::string> names;` 4. **`forward_list`** (C++11) - 单向链表，内存占用更小，仅前向遍历 5. **`array`** (C++11) - 固定大小数组，替代原生数组 - 栈上分配，支持STL算法 - 示例：`std::array<float, 3> points = {0.1, 1.5, -2.0};` ### 🔑 二、关联容器（基于键排序） 1. **`set`** - 唯一键集合，红黑树实现，查找 $O(\log n)$ - 自动排序（`std::set<int> s = {5,2,7};` → {2,5,7}） 2. **`map`** - 键值对映射（`std::map<std::string, int> ages;`） - 键唯一，按键排序 3. **`multiset`/`multimap`** - 允许重复键，其他特性同 `set/map` ### ⚡ 三、无序关联容器（哈希实现） 1. **`unordered_set`** (C++11) - 哈希集合，平均查找 $O(1)$，最差 $O(n)$ - 无序存储（`std::unordered_set<int> us;`） 2. **`unordered_map`** (C++11) - 键值对哈希表（`std::unordered_map<std::string, Phone> directory;`） 3. **`unordered_multiset`/`unordered_multimap`** - 允许重复键的哈希版本 ### 📚 四、容器适配器（接口受限） 1. **`stack`** - LIFO（后进先出），默认基于 `deque` - 操作：`push()`, `pop()`, `top()` 2. **`queue`** - FIFO（先进先出），默认基于 `deque` - 操作：`push()`, `pop()`, `front()` 3. **`priority_queue`** - 优先级队列（最大堆），默认 `vector` 容器 - 顶部始终为最大元素（可通过比较器自定义） ### 💡 关键特性总结 - **迭代器支持**：所有容器提供迭代器（随机/双向/前向）[^2][^3] - **内存管理**：容器自动处理内存分配/释放（RAII原则） - **算法兼容**：可与STL算法（如 `sort`, `find`）无缝协作 - **性能差异**：根据操作频率选择容器（如频繁随机访问用 `vector`，频繁插入用 `list`） > STL 的核心设计思想是将**数据结构**（容器）、**算法**和**迭代器**分离，通过泛型编程实现高度复用[^4]。例如排序算法 `std::sort` 可作用于 `vector`、`deque` 等随机访问容器，但不适用 `list`（需用 `list::sort()`）。 --- ### ❓ 相关问题 1. **如何选择`vector`和`list`？在元素频繁插入删除的场景下哪个更优？** 2. **C++11的`unordered_map`与`map`在底层实现上有何本质区别？** 3. **`priority_queue`如何通过自定义比较器实现最小堆？** 4. **STL容器的迭代器失效有哪些常见场景？如何避免？** 5. **C++17新增了哪些容器特性？（如`std::optional`、`std::variant`）** [^1]: STL 是一组提供通用数据结构和算法的 C++ 模板类，包含容器、算法和迭代器三大组件。 [^2]: STL 实现了常见数据结构（如动态数组、哈希表、红黑树），通过模板参数实现泛型。 [^3]: 容器需配合迭代器使用，例如 `std::vector` 可通过索引或迭代器访问元素。 [^4]: 特定数据结构的设计旨在优化特定操作（如搜索/排序），STL 容器封装了最广泛使用的实现。