C++ 数据结构

在 C++ 中，常见的数据结构既包括标准库（STL）提供的容器，也包括你可以自己基于指针／模板等手写的经典结构。下面从 STL 容器到手写结构依次介绍。

---

1. 原生数组 (C‑style Array)

int a[5];         // 静态分配，长度固定
int b[] = {1,2,3};// 编译期推断长度为 3

• 优点：内存连续，随机访问 O(1)，开销极小。
• 缺点：大小固定，不可越界检查，不支持动态扩容。

---

2. 动态数组：std::vector

见上节【C++ vector 容器】。

• 动态扩容、随机访问 O(1)、尾部插入/删除均摊 O(1)。
• 推荐使用：大部分需要数组语义且元素数量动态变化的场景。

---

3. 双端队列：std::deque

#include <deque>
std::deque<int> dq;
dq.push_back(1);
dq.push_front(0);
dq.pop_back();
dq.pop_front();

• 支持两端插入/删除 O(1)，中间插入/删除 O(n)，随机访问 O(1)。
• 底层由一组固定大小的缓冲区组成，适合需要头尾都频繁操作的场景。

---

4. 链表系列

4.1 单向链表：std::forward_list (C++11)

#include <forward_list>
std::forward_list<int> fl = {1,2,3};
fl.push_front(0);      // O(1)
fl.insert_after(fl.begin(), 42);
fl.remove(2);          // O(n)

• 只支持单向遍历，插入／删除节点 O(1)（已知前驱时），随机访问 O(n)。
• 内存开销小于双向链表。

4.2 双向链表： std::list

#include <list>
std::list<int> lst = {1,2,3};
lst.push_back(4);
lst.insert(std::next(lst.begin()), 42);
lst.erase(lst.begin());

• 双向遍历，插入／删除节点 O(1)（已知位置时），随机访问 O(n)。
• 适合在容器中间频繁插入／删除的场景。

---

5. 适配器：栈、队列、优先队列

#include <stack>
#include <queue>

// 栈（LIFO）
std::stack<int> st;
st.push(1);
st.top();         // 1
st.pop();

// 队列（FIFO）
std::queue<int> qu;
qu.push(1);
qu.front();       // 1
qu.pop();

// 优先队列（默认大顶堆）
std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.top();         // 3

• 底层默认用 deque，也可指定 vector 或 list 作为底层容器。

---

6. 关联容器：有序集合和映射

6.1 有序集合 std::set / std::multiset

#include <set>
std::set<int> s = {3,1,4};
s.insert(2);         // 保持元素有序
auto it = s.find(3);

• 底层通常是红黑树（平衡 BST），插入/查找/删除均摊 O(log n)。
• multiset 允许重复元素。

6.2 有序映射 std::map / std::multimap

#include <map>
std::map<std::string,int> mp;
mp["apple"] = 3;
mp.insert({"banana",2});

• 键值对按键有序存储，操作均摊 O(log n)。
• multimap 允许相同键出现多次。

---

7. 无序关联容器（哈希表）

7.1 std::unordered_set / std::unordered_multiset

#include <unordered_set>
std::unordered_set<int> us = {1,2,3};
us.insert(4);

• 基于哈希表，平均插入/查找/删除 O(1)，最坏 O(n)。
• unordered_multiset 允许重复。

7.2 std::unordered_map / std::unordered_multimap

#include <unordered_map>
std::unordered_map<std::string,int> ump;
ump["key"] = 42;

• 哈希映射，平均 O(1)，最坏 O(n)。
• unordered_multimap 允许相同键多次。

---

8. 其他常用容器

• std::array<T,N>（C++11）：固定大小的数组封装，支持 STL 接口，随机访问 O(1)。
• std::bitset<N>：位数组，支持按位操作；空间高效，大小在编译期固定。
• std::string / std::wstring：字符序列容器，参见之前章节。
• std::tuple / std::pair：简易的异构数据打包结构。

---

9. 自定义经典数据结构示例

9.1 单链表 (手写)

template<typename T>
struct Node {
    T data;
    Node* next = nullptr;
    Node(const T& v): data(v) {}
};

template<typename T>
class LinkedList {
    Node<T>* head = nullptr;
  public:
    void push_front(const T& v) {
        Node<T>* p = new Node<T>(v);
        p->next = head;
        head = p;
    }
    // … 析构、遍历、删除等
};

9.2 二叉树节点

template<typename T>
struct TreeNode {
    T val;
    TreeNode* left  = nullptr;
    TreeNode* right = nullptr;
    TreeNode(const T& v): val(v) {}
};

9.3 图的邻接表

#include <vector>
#include <list>

int V; // 顶点数
std::vector<std::list<int>> adj(V);
void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u); // 若为无向图
}

---

10. 时间复杂度一览

容器/操作	随机访问	头部插入	尾部插入	中间插入	查找/删除
vector	O(1)	O(n)	O(1)*	O(n)	O(n)
deque	O(1)	O(1)	O(1)	O(n)	O(n)
list	O(n)	O(1)	O(1)	O(1)	O(n)
forward_list	O(n)	O(1)	—	O(n)	O(n)
set/map	—	—	—	—	O(log n)
unordered_set/map	—	—	—	—	O(1) avg.

* 尾部插入对于 vector 在容量足够时为 O(1)，否则需扩容 O(n)。

---

小结

• 优先使用 STL 容器：它们实现成熟、性能可预测，并与算法库无缝配合。
• 选择合适的容器：根据访问模式（随机访问 vs. 顺序遍历）、插入/删除位置、是否需要排序／哈希等，权衡时间与空间。
• 必要时自定义：当 STL 容器无法满足特殊需求（比如内存池、紧凑存储、复杂指针关系）时，可手写结构。

熟练掌握以上数据结构，能让你的 C++ 程序既高效又易维护。