Python与C数据结构，如何优化为？
摘要：Python和C++数据结构整理 引言 数据结构是软件开发的基石，但许多开发者对数据结构的分类和选型仍存在认知盲区。本文将系统梳理数据结构的逻辑分类，深入剖析C++和P
Python和C++数据结构整理
引言
数据结构是软件开发的基石，但许多开发者对数据结构的分类和选型仍存在认知盲区。本文将系统梳理数据结构的逻辑分类，深入剖析C++和Python中常用数据结构的底层实现与应用场景，通过实际代码示例帮助开发者建立完整的知识体系。
第一部分：数据结构的逻辑分类
逻辑结构的本质
数据结构的分类应当从逻辑结构角度理解，而非物理存储方式。逻辑结构描述数据元素之间的关系，这种关系独立于具体编程语言和底层实现。从逻辑层面看，数据结构分为线性结构和非线性结构两大类。
线性结构
线性结构指数据元素之间存在一对一的顺序关系。除首尾元素外，每个元素都有唯一的前驱和后继。典型的线性结构包括数组、链表、栈、队列和哈希表。哈希表虽然在物理存储上通过散列函数分散存储元素，但从逻辑关系看，每个键值对是独立的一一对应关系，因此属于线性结构。
非线性结构
非线性结构表现为数据元素之间存在一对多或多对多的关系。树结构是典型的一对多关系，每个父节点可以拥有多个子节点，形成层次化结构。图结构代表多对多关系，图中节点可以与任意数量的其他节点建立连接，这种灵活性使得图成为表达复杂关系网络的理想选择。
第二部分：核心数据结构详解
Python的四大内置结构
1. list：动态数组
底层实现：Python的list是动态数组实现，基于动态数组（Dynamic Array）实现，使用连续内存空间存储元素引用。在底层，Python维护一个数组指针和当前大小，当容量不足时自动分配更大内存空间并复制现有元素，采用过度分配（Over-Allocation）机制减少频繁的内存重新分配。
特性：
有序、可变、允许重复元素
O(1)时间复杂度的索引访问
O(1)均摊时间复杂度的末尾追加操作
O(n)时间复杂度的中间插入/删除操作
基本操作：
lst = [1, 2, 3]
# 末尾添加
lst.append(4) # [1, 2, 3, 4] | O(1)均摊
# 指定位置插入
lst.insert(0, 0) # [0, 1, 2, 3, 4] | O(n)
# 索引访问
element = lst[2] # 3 | O(1)
# 末尾删除
lst.pop() # 4 | O(1)
# 指定位置删除
lst.pop(0) # 0 | O(n)
# 切片操作
sub_list = lst[1:3] # [1, 2] | 创建新列表
lst[1:3] = [10, 20] # [0, 10, 20, 4] | 替换子序列
# 列表推导式
squares = [x**2 for x in range(10)] # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
# 遍历
for item in lst:
print(item)
高级操作：
# 合并列表
combined = lst + [5, 6] # [0, 10, 20, 4, 5, 6]
# 复制列表
copy = lst[:] # [0, 10, 20, 4]
# 排序
lst.sort() # [0, 4, 10, 20] | 原地排序
sorted_lst = sorted(lst) # [0, 4, 10, 20] | 返回新列表
# 去重
unique = list(set(lst)) # [0, 4, 10, 20]
最佳实践：
频繁在末尾添加元素时优先使用append
频繁在头部插入/删除时考虑使用collections.deque
避免在循环中频繁修改列表（如insert(0, x)）
2. dict：哈希表
底层实现：Python的dict基于哈希表实现，采用开放地址法（Open Addressing）解决哈希冲突。自Python 3.7起，dict保证维护插入顺序，这使得字典在大多数情况下是有序的。
特性：
键值对集合，键唯一
O(1)平均时间复杂度的查找、插入和删除
键必须是可哈希的不可变对象（字符串、数字、元组等）
值可以是任意类型
基本操作：
d = {'name': 'Alice', 'age': 30}
# 插入/更新
d['city'] = 'Beijing' # O(1)
# 安全访问
value = d.get('name') # 'Alice' | O(1)
value = d.get('gender', 'N/A') # 'N/A' | 提供默认值
# 删除
del d['age'] # O(1)
value = d.pop('city') # 'Beijing' | 返回值
# 检查键存在
if 'name' in d:
print(d['name']) # 'Alice'
# 遍历
for key, value in d.items():
print(f"{key}: {value}")
# 字典推导式
squared = {x: x**2 for x in range(5)} # {0: 0, 1: 1, 2: 4, 3: 9, 4: 16}
# 合并字典 (Python 3.9+)
d1 = {'a': 1, 'b': 2}
d2 = {'b': 3, 'c': 4}
merged = d1 | d2 # {'a': 1, 'b': 3, 'c': 4}
高级操作：
# 获取所有键/值
keys = list(d.keys()) # ['name', 'age']
values = list(d.values()) # ['Alice', 30]
# 从键值对创建字典
d = dict([('name', 'Alice'), ('age', 30)])
# 初始化默认值
from collections import defaultdict
d = defaultdict(int)
d['a'] += 1 # 1
最佳实践：
避免在循环中频繁修改字典
使用get()代替直接访问避免KeyError
使用字典推导式简化数据转换
对于大量数据，考虑使用collections.Counter统计频率
3. set：集合
底层实现：Python的set基于哈希表实现，用于存储唯一元素，提供O(1)的成员检查、添加和删除操作。
特性：
无序、不重复元素集合
O(1)平均时间复杂度的成员检查、添加和删除
适用于快速判断元素是否存在、去重和集合运算
基本操作：
s = {1, 2, 3}
# 添加元素
s.add(4) # {1, 2, 3, 4} | O(1)
# 删除元素
s.remove(2) # {1, 3, 4} | 不存在会报错
s.discard(2) # {1, 3, 4} | 不存在不报错
# 成员检查
exists = 3 in s # True | O(1)
# 集合运算
s1 = {1, 2, 3, 4}
s2 = {3, 4, 5, 6}
union = s1 | s2 # {1, 2, 3, 4, 5, 6} | 并集
intersection = s1 & s2 # {3, 4} | 交集
difference = s1 - s2 # {1, 2} | 差集
sym_diff = s1 ^ s2 # {1, 2, 5, 6} | 对称差
# 去重
lst = [1, 2, 2, 3, 3, 3]
unique = list(set(lst)) # [1, 2, 3]
# frozenset (不可变集合)
fs = frozenset([1, 2, 3])
# fs可以作为dict的键或另一个set的元素
最佳实践：
使用set进行快速成员检查
用set进行数据去重
用集合运算进行数据处理
当需要不可变集合时使用frozenset
4. tuple：不可变序列
底层实现：tuple是Python的不可变序列类型，创建后无法修改。底层内存布局比list更紧凑，创建速度更快。
特性：
不可变序列
可以作为dict的键
多线程环境中天然线程安全
适合表示固定的数据组合
基本操作：
# 创建tuple
t = (1, 2, 3)
t = 1, 2, 3 # 括号可省略
single = (1,) # 单元素tuple需要逗号
empty = ()
# 访问元素
first = t[0] # 1 | O(1) 索引访问
sub = t[1:3] # (2, 3) | 切片返回新tuple
# 解包
a, b, c = t
x, *rest = (1, 2, 3, 4) # x=1, rest=[2,3,4]
# 作为字典的键
point_data = {(0, 0): 'origin', (1, 1): 'diagonal'}
# 函数返回多值
def get_coordinates():
return 10, 20
x, y = get_coordinates()
# 命名元组 (更好的可读性)
from collections import namedtuple
Point = namedtuple('Point', ['x', 'y'])
p = Point(10, 20)
print(p.x, p.y) # 10 20
最佳实践：
用tuple表示固定数据组合（如坐标、日期）
用tuple作为dict的键
用tuple返回多值函数结果
用命名元组提高代码可读性
C++的核心容器体系
1. vector：动态数组
底层实现：vector在连续内存空间中存储元素，提供O(1)的随机访问和O(1)均摊的末尾插入。采用容量翻倍的扩容策略以减少重新分配的频率。
特性：
连续内存，随机访问O(1)
末尾插入/删除O(1)均摊
中间插入/删除O(n)
有容量管理方法
基本操作：
#include <vector>
#include <iostream>
// 基本操作
std::vector<int> vec = {1, 2, 3};
vec.push_back(4); // O(1) 末尾添加
vec.pop_back(); // O(1) 末尾删除
int elem = vec[0]; // O(1) 访问，无边界检查
int safe = vec.at(0); // O(1) 访问，有边界检查
// 插入删除
vec.insert(vec.begin(), 0); // O(n) 头部插入
vec.erase(vec.begin()); // O(n) 头部删除
// 容量管理
vec.reserve(1000); // 预分配容量
vec.shrink_to_fit(); // 释放多余容量
size_t sz = vec.size(); // 当前元素数量
size_t cap = vec.capacity(); // 当前容量
// 遍历
for (int x : vec) {
std::cout << x << " ";
}
// 使用迭代器
for (auto it = vec.begin(); it != vec.end(); ++it) {
std::cout << *it << " ";
}
// 算法配合
#include <algorithm>
std::sort(vec.begin(), vec.end()); //先对vector进行排序`
auto it = std::find(vec.begin(), vec.end(), 3); //在排序后的vector中查找元素3`
高级操作：
// emplace_back (与push_back相同，末尾添加，但避免了拷贝，添加更加高效)
vec.emplace_back(5); // 直接在末尾构造元素
// 范围初始化
std::vector<int> vec2(vec.begin() + 1, vec.end() - 1); // 范围即为索引，begin()为索引0——第一个元素，vec.end()表示遍历结束的信号，为索引size+1，vec.end()-1表示不输出最后一个，这里会输出[2,3]
// 与数组互转
int arr[] = {1, 2, 3};
// 方式1: 使用数组指针
std::vector<int> vec1(arr, arr + 3); // {1, 2, 3}
// 方式2: 使用std::begin/std::end
std::vector<int> vec2(std::begin(arr), std::end(arr));
最佳实践：
优先使用vector而非原生数组
使用emplace_back替代push_back避免拷贝
预先reserve()避免频繁扩容
用范围for循环遍历
2. unordered_map：哈希表
底层实现：unordered_map基于哈希表实现，使用哈希函数将键映射到桶中，采用链地址法解决冲突。提供O(1)的平均查找时间。
特性：
键值对集合，键唯一
O(1)平均时间复杂度的查找、插入、删除
无序（不保证元素顺序）
需要提供哈希函数
基本操作：
#include <unordered_map>
#include <string>
// 基本操作
std::unordered_map<int, std::string> map;
map[1] = "one"; // O(1) 插入/更新
map.insert({2, "two"}); // O(1) 插入
std::string val = map[1]; // O(1) 访问
// 安全访问
if (map.find(3) != map.end()) {
std::cout << map[3];
}
// 检查键存在
if (map.count(1) > 0) {
// 键存在
}
// 删除
map.erase(1); // O(1) 删除
// 遍历
for (const auto& [key, value] : map) {
std::cout << key << ": " << value << "\n";
}
// 预分配
map.reserve(1000);
// 自定义类型需要提供哈希函数
struct Point {
int x, y;
};
struct PointHash {
size_t operator()(const Point& p) const {
return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
}
};
struct PointEqual {
bool operator()(const Point& a, const Point& b) const {
return a.x == b.x && a.y == b.y;
}
};
std::unordered_map<Point, std::string, PointHash, PointEqual> point_map;
最佳实践：
优先使用emplace()代替insert()
使用find()代替operator[]进行查找
预先reserve()避免频繁rehash
为自定义类型提供合适的哈希函数
3. map：有序映射
底层实现：map基于红黑树实现，提供O(log n)的查找时间但保证元素按键有序。
特性：
键值对集合，键唯一
O(log n)时间复杂度的查找、插入、删除
元素按键有序（升序）
支持范围查询
基本操作：
#include <map>
// 基本操作
std::map<int, std::string> map;
map[1] = "one";
map[2] = "two";
map[3] = "three";
// 有序遍历
for (const auto& [key, value] : map) {
std::cout << key << ": " << value << "\n";
// 输出顺序: 1, 2, 3
}
// 范围查询
auto lower = map.lower_bound(2); // 第一个 >= 2 的元素
auto upper = map.upper_bound(2); // 第一个 > 2 的元素
// 区间遍历
for (auto it = lower; it != upper; ++it) {
std::cout << it->first << ": " << it->second << "\n";
}
// 查找
auto it = map.find(2);
if (it != map.end()) {
std::cout << "Found: " << it->second;
}
最佳实践：
当需要有序遍历或范围查询时使用map
使用lower_bound/upper_bound进行范围查询
用insert()代替operator[]避免意外插入
4. unordered_set与set
底层实现：
unordered_set：基于哈希表实现，提供O(1)的平均成员检查
set：基于红黑树实现，提供O(log n)的成员检查但保证元素有序
基本操作：
#include <unordered_set>
#include <set>
// unordered_set 基本操作
std::unordered_set<int> uset = {1, 2, 3};
uset.insert(4); // O(1) 插入
uset.erase(2); // O(1) 删除
bool exists = uset.count(3); // O(1) 检查存在
// set 基本操作
std::set<int> oset = {3, 1, 4, 2};
oset.insert(5);
// 有序遍历
for (int x : oset) {
std::cout << x << " "; // 输出: 1 2 3 4 5
}
// 范围查询
auto lower = oset.lower_bound(2);
auto upper = oset.upper_bound(4);
// 集合运算
std::set<int> s1 = {1, 2, 3, 4};
std::set<int> s2 = {3, 4, 5, 6};
std::set<int> result;
std::set_intersection(s1.begin(), s1.end(),
s2.begin(), s2.end(),
std::inserter(result, result.begin()));
// result = {3, 4}
最佳实践：
无需维护顺序时使用unordered_set
需要有序遍历或范围查询时使用set
使用set_intersection等算法进行集合运算
5. array：固定大小数组
底层实现：array是C++11引入的固定大小数组容器，在栈上分配内存，提供编译时大小检查。
特性：
固定大小，编译时确定
栈上分配，性能高
提供STL容器的接口
与原生数组兼容
基本操作：
#include <array>
#include <iostream>
// 创建固定大小数组
std::array<int, 5> arr = {1, 2, 3, 4, 5};
// 访问元素
int first = arr[0];
int safe = arr.at(0);
// 大小
size_t sz = arr.size(); // 编译时常量
// 遍历
for (int x : arr) {
std::cout << x << " ";
}
// 与STL算法配合
std::sort(arr.begin(), arr.end());
// 多维数组
std::array<std::array<int, 3>, 3> matrix = {{
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
}};
最佳实践：
表示固定维度的数学向量
小型查找表
配置常量数组
需要栈上分配且大小固定的场景
总结对比
特性
Python list
Python dict
Python set
Python tuple
C++ vector
C++ unordered_map
C++ map
C++ array
底层
动态数组
哈希表
哈希表
不可变序列
连续数组
哈希表
红黑树
固定大小数组
访问
O(1)索引
O(1)平均
O(1)平均
O(1)索引
O(1)随机
O(1)平均
O(log n)
O(1)随机
插入
O(1)均摊
O(1)平均
O(1)平均
无
O(1)均摊
O(1)平均
O(log n)
无
删除
O(n)
O(1)平均
O(1)平均
无
O(n)
O(1)平均
O(log n)
无
排序
有序
有序(3.7+)
无序
有序
有序
无序
有序
有序
键/索引
索引
键
无
索引
索引
键
键
索引
可变性
可变
可变
可变
不可变
可变
可变
可变
不可变
典型用途
序列数据
数据索引
唯一元素
固定组合
动态数组
快速查找
有序查找
固定大小数组
选择建议：
Python：需要动态序列？用list；需要键值对？用dict；需要唯一元素？用set；需要固定组合？用tuple
C++：需要动态数组？用vector；需要快速查找？用unordered_map；需要有序查找？用map；需要固定大小数组？用array
第三部分：次要结构速览
栈与队列
栈遵循后进先出（LIFO）原则，队列遵循先进先出（FIFO）原则。这两种结构在算法实现中广泛应用，但通常不需要专门的栈或队列类型。
# Python - 栈操作
stack = []
stack.append(10) # 入栈
stack.append(20)
top = stack[-1] # 查看栈顶
stack.pop() # 出栈
# Python - 队列操作
from collections import deque
queue = deque()
queue.append(10) # 入队
queue.append(20)
front = queue[0] # 查看队首
queue.popleft() # 出队
// C++ - 栈
#include <stack>
std::stack<int> s;
s.push(10); // 入栈
s.push(20);
int top = s.top(); // 查看栈顶
s.pop(); // 出栈
// C++ - 队列
#include <queue>
std::queue<int> q;
q.push(10); // 入队
q.push(20);
int front = q.front();// 查看队首
q.pop(); // 出队
栈的典型应用包括函数调用栈模拟、括号匹配、表达式求值、深度优先搜索的迭代实现。队列的主要应用在广度优先搜索、任务调度、消息传递、缓冲区管理等场景。
deque：双端队列
deque支持在两端高效插入和删除。Python的collections.deque和C++的std::deque都提供O(1)的两端操作。
# Python deque
from collections import deque
dq = deque([1, 2, 3])
dq.append(4) # 右端添加
dq.appendleft(0) # 左端添加
dq.pop() # 右端删除
dq.popleft() # 左端删除
dq.rotate(1) # 循环右移
// C++ deque
#include <deque>
std::deque<int> dq = {1, 2, 3};
dq.push_back(4); // 右端添加
dq.push_front(0); // 左端添加
dq.pop_back(); // 右端删除
dq.pop_front(); // 左端删除
int elem = dq[1]; // O(1) 随机访问
deque的典型应用包括实现固定大小的滑动窗口、维护最近访问记录、实现双端队列算法等。deque作为std::stack和std::queue的默认底层容器，因为它比vector在头部操作更高效，比list的随机访问更快。
堆：优先级队列
堆是特殊的完全二叉树结构，满足堆性质。堆能够在O(log n)时间内插入元素和取出最大或最小元素，这使得它成为实现优先级队列的标准数据结构。
# Python heapq (最小堆)
import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
min_elem = heapq.heappop(heap) # 1
# 将列表转换为堆
lst = [3, 1, 4, 1, 5]
heapq.heapify(lst)
# Top K问题
numbers = [5, 2, 8, 1, 9, 3]
top3 = heapq.nlargest(3, numbers) # [9, 8, 5]
// C++ priority_queue (最大堆)
#include <queue>
std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(2);
int max_elem = pq.top(); // 3
pq.pop();
// 最小堆
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(3);
min_pq.push(1);
int min_elem = min_pq.top(); // 1
堆的应用场景包括Top-K问题、任务调度、Dijkstra最短路径算法、合并K个有序数组等。
树与图
树和图是表达层次关系和网络关系的非线性数据结构，在Python和C++中都没有内置的标准实现，需要根据具体问题自行设计。
# Python - 树节点定义
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 二叉树遍历
def inorder(root):
if root:
inorder(root.left)
print(root.val)
inorder(root.right)
# Python - 图的邻接表表示
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# BFS遍历
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
// C++ - 树节点定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// C++ - 图的邻接表表示
#include <unordered_map>
#include <vector>
std::unordered_map<int, std::vector<int>> graph;
graph[1] = {2, 3};
graph[2] = {1, 4};
graph[3] = {1, 4};
graph[4] = {2, 3};
// DFS遍历
void dfs(int node, std::unordered_set<int>& visited) {
visited.insert(node);
std::cout << node << " ";
for (int neighbor : graph[node]) {
if (visited.find(neighbor) == visited.end()) {
dfs(neighbor, visited);
}
}
}
树结构应用于文件系统、语法分析树、决策树、B树索引等。C++的std::map和std::set底层就是红黑树实现。图结构用于表达任意的多对多关系，应用于网络路由、社交网络分析、依赖关系解析等领域。
第四部分：选型实战指南
核心三件套的应用场景
在实际开发中，大约90%的数据结构需求可以由数组、字典和集合满足。这三种结构分别对应三种最基本的数据组织需求：有序集合、键值映射、无重复集合。
# Python实战示例：推荐系统中的数据结构选择
# 1. 用户历史行为 - 使用list
user_history = [101, 205, 303, 410] # 按时间顺序的物品ID
# 2. 物品特征映射 - 使用dict
item_features = {
101: {'category': 'electronics', 'price': 999},
205: {'category': 'books', 'price': 29}
}
# 3. 已推荐物品 - 使用set
recommended = {101, 205, 303}
# 过滤已推荐物品
candidates = [101, 205, 401, 502]
new_candidates = [item for item in candidates if item not in recommended]
# 计算用户共同兴趣
user1_items = {101, 205, 303}
user2_items = {205, 303, 401}
common_interests = user1_items & user2_items # {205, 303}
// C++实战示例：高性能计算中的数据结构选择
#include <vector>
#include <unordered_map>
#include <unordered_set>
// 1. 大规模数值计算 - 使用vector
std::vector<double> data(1000000);
for (size_t i = 0; i < data.size(); ++i) {
data[i] = compute(i);
}
// 2. 特征索引 - 使用unordered_map
std::unordered_map<std::string, int> feature_index;
feature_index["age"] = 0;
feature_index["income"] = 1;
// 3. 去重与快速查找 - 使用unordered_set
std::unordered_set<int> seen;
for (int value : data) {
if (seen.count(value) == 0) {
process(value);
seen.insert(value);
}
}
特定场景的选型决策
// 场景1：需要维护有序数据并进行范围查询 - 使用map
std::map<int, std::string> timestamp_events;
timestamp_events[1000] = "event1";
timestamp_events[2000] = "event2";
timestamp_events[3000] = "event3";
// 查询时间区间[1500, 2500]内的所有事件
auto start = timestamp_events.lower_bound(1500);
auto end = timestamp_events.upper_bound(2500);
for (auto it = start; it != end; ++it) {
std::cout << it->second << "\n";
}
# 场景2：频繁在序列两端操作 - 使用deque
from collections import deque
# 实现固定大小的滑动窗口
window = deque(maxlen=5)
for value in data_stream:
window.append(value)
if len(window) == 5:
avg = sum(window) / 5
print(f"Moving average: {avg}")
# 场景3：优先级调度 - 使用堆
import heapq
# 任务调度系统
tasks = []
heapq.heappush(tasks, (1, "high priority task"))
heapq.heappush(tasks, (5, "low priority task"))
heapq.heappush(tasks, (3, "medium priority task"))
# 按优先级处理任务
while tasks:
priority, task = heapq.heappop(tasks)
process(task)
性能优化要点
// 优化1：预分配空间避免频繁扩容
std::vector<int> vec;
vec.reserve(1000000); // 预分配容量
for (int i = 0; i < 1000000; ++i) {
vec.push_back(i); // 不会触发扩容
}
// 优化2：使用emplace避免不必要的拷贝
std::vector<std::string> strings;
strings.emplace_back("hello"); // 就地构造，无拷贝
// 优化3：使用const引用传递容器
void process(const std::vector<int>& data) {
// 避免拷贝整个容器
}
# 优化1：使用生成器减少内存占用
def process_large_file(filename):
with open(filename) as f:
for line in f: # 逐行处理，不加载整个文件
yield process(line)
# 优化2：使用集合判断成员资格而非列表
# 错误方式 - O(n)
if item in large_list:
pass
# 正确方式 - O(1)
large_set = set(large_list)
if item in large_set:
pass