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

posted on 2026-01-02 13:24 GlenTt 阅读(690) 评论(0) 收藏举报

刷新页面返回顶部

GlenTt

导航

公告