代码收藏家技术教程 2025-01-29

常用数据结构Python与C++对比

Python和C++作为两门常用的编程语言，有着各自实现数据结构的方式，尽管它们的实现和使用方法不同，但可以在功能上相互映射。

文章目录

1. 数组（Array）

2. 链表（Linked List）

3. 栈（Stack）

4. 队列（Queue）

5. 哈希表（Hash Table）

6. 字符串（String）

7. 集合（Set）

8. 列表结构（List）

9. 树（Tree）

10. 堆（Heap）

总结

补充：Python中的双向队列-deque详细介绍

1）导入`deque` 类

2）基本操作

3）示例代码

4）性能对比

5）应用场景

1. 数组（Array）

C++：在C++ 中，数组是一种内置的数据类型，声明方式为type arrayName[arraySize];，例如int numbers[5];，它在内存中是连续存储的同类型元素序列，大小固定，访问元素通过索引，速度很快，不过缺乏一些便捷的高级操作。

使用 std::array 或 std::vector。

std::array 是固定大小的数组，性能接近原生数组。

std::vector 是动态数组，可以动态扩展。

#include <iostream>
#include <vector>
#include <array>
int main() {
    std::array<int, 3> arr = {1, 2, 3}; // 固定大小数组
    std::vector<int> vec = {1, 2, 3};   // 动态数组
    // 访问元素
    std::cout << "Array element: " << arr[0] << std::endl;
    std::cout << "Vector element: " << vec[0] << std::endl;
    // 添加元素
    vec.push_back(4);
    std::cout << "Vector size after push: " << vec.size() << std::endl;
    return 0;
}

Python：Python中的列表（List）可以充当数组的角色，用[]表示，例如my_list = [1, 2, 3]。列表更加灵活，存储的数据类型无需一致，可以动态扩容，支持如append()追加元素、pop()移除元素等丰富的操作方法。

# 创建数组
arr = [1, 2, 3]
# 访问元素
print(f"Array element: {arr[0]}")
# 添加元素
arr.append(4)
print(f"Array size after append: {len(arr)}")

对比

C++ std::vector 和 Python list 的行为类似，支持动态扩展。

C++ std::array 更类似 Python 的 tuple，大小固定。

2. 链表（Linked List）

C++：使用 std::list 实现双向链表。通常需要自定义结构体来实现链表节点，像struct Node { int data; Node* next; };，手动管理内存分配与释放，操作较为复杂，要注意避免悬空指针、内存泄漏等问题。

#include <iostream>

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

Python：没有内置链表，可以通过自定义类来模拟链表，不过Python内置的collections.deque 也能部分实现链表功能，deque支持在两端快速添加、删除元素，例如from collections import deque; my_deque = deque([1, 2, 3])。

from collections import deque
linked_list = deque([1, 2, 3])
# 添加元素
linked_list.append(4)  # 尾部添加
linked_list.appendleft(0)  # 头部添加
# 遍历链表
for val in linked_list:
    print(val, end=" ")
# 类实现链表
class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

对比

Python 的 deque 提供高效的头尾操作，类似 C++ 的 std::list。

C++ 有直接支持的单向链表和双向链表，而 Python 通常需要手动实现单链表。

数组与链表对比：数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。链表的长度可以是不固定的，并且可以动态增删，适合数据量不固定，频繁增删，较少查询的场景。（图源：代码随想录）

3. 栈（Stack）

C++：栈使用 std::stack，标准库提供了stack容器，位于<stack>头文件中，使用时先#include <stack>，然后声明stack<int> myStack;，它遵循后进先出原则，提供push、pop、top 等操作。

#include <iostream>
#include <stack>
int main() {
    std::stack<int> stack;
    stack.push(1);
    stack.push(2);
    std::cout << "Top of stack: " << stack.top() << std::endl;
    stack.pop();
    return 0;
}

Python：可以用列表简单模拟栈，append()方法充当push操作，pop()方法就是出栈操作，此外，collections模块中的deque也能高效实现栈，调用append入栈，pop出栈。

# 栈的简单示例
stack = []
stack.append(1)
stack.append(2)
print(f"Top of stack: {stack[-1]}")
stack.pop()

对比

Python 使用 list 模拟栈，但性能不如 deque。

力扣题目225. 用队列实现栈，解题思路参考代码随想录

// C++
class MyStack {
public:
    queue<int> que;
    MyStack() {
        
    }
    void push(int x) {
        que.push(x);
    }
    int pop() {
        int size = que.size();
        size--;
        while (size--){
            que.push(que.front());
            que.pop();
        }
        int res = que.front();
        que.pop();
        return res;
    }
    int top() {
        int size = que.size();
        size--;
        while (size--){
            que.push(que.front());
            que.pop();
        }
        int res = que.front();
        que.push(que.front());
        que.pop();
        return res;   
    }
    bool empty() {
        return que.empty();
    }
};

# Python
class MyStack:
    def __init__(self):
        self.que=[]
    def push(self, x: int) -> None:
        self.que.append(x)
    def pop(self) -> int:
        if not self.empty():
            n=len(self.que)-1
            for i in range(n):
                self.que.append(self.que[0])
                self.que.remove(self.que[0])
            res = self.que[0]
            self.que.remove(self.que[0])
            return res
    def top(self) -> int:
        if not self.empty():
            n=len(self.que)-1
            for i in range(n):
                self.que.append(self.que[0])
                self.que.remove(self.que[0])
            res = self.que[0]
            self.que.append(self.que[0])
            self.que.remove(self.que[0])
            return res
    def empty(self) -> bool:
        return not self.que

4. 队列（Queue）

C++：队列使用 std::queue 或 std::deque，<queue>头文件里的queue类可用于创建队列，声明如queue<int> myQueue;，按照先进先出的顺序处理元素，提供push、pop、front等方法。此外还有priority_queue用于优先队列。

#include <iostream>
#include <queue>
int main() {
    std::queue<int> queue;
    queue.push(1);
    queue.push(2);
    std::cout << "Front of queue: " << queue.front() << std::endl;
    queue.pop();
    return 0;
}

Python：collections模块中的deque能当作队列使用，它的append用于入队，popleft用于出队；queue模块也有Queue类用于线程安全的队列场景，PriorityQueue实现优先队列。

from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
print(f"Front of queue: {queue[0]}")
queue.popleft()

对比

Python 的 deque 和 C++ 的 std::deque 都支持高效的双端操作。

力扣题目232. 用栈实现队列，解题思路参考代码随想录

// 参考代码随想录解题思路 C++
class MyQueue {
public:
    stack<int> stout;
    stack<int> stin;
    MyQueue() {
   
    }
    void push(int x) {
        stin.push(x);
    }
    int pop() {
        if (stout.empty()){
            while (!stin.empty()){
                stout.push(stin.top());
                stin.pop();
            }
        }
        int res=stout.top();
        stout.pop();
        return res;
    }
    int peek() {
        int res = this->pop(); // 直接使用已有的pop函数
        stout.push(res); // 因为pop函数弹出了元素res，所以再添加回去
        return res;
    }
    bool empty() {
        return stin.empty() && stout.empty();
    }
};

# 参考代码随想录解题思路Python
class MyQueue:
    def __init__(self):
        self.stackin=[]
        self.stackout=[]
    def push(self, x: int) -> None:
        self.stackin.append(x)
    def pop(self) -> int:
        if self.empty():
            return None
        if not self.stackout:
            if self.stackin:
                for i in range(len(self.stackin)):
                    self.stackout.append(self.stackin.pop())
            return self.stackout.pop()
        else:  
            res=self.stackout.pop()
            return res
    def peek(self) -> int:
        res = self.pop()
        self.stackout.append(res)
        return res
    def empty(self) -> bool:
        return not (self.stackin or self.stackout)

5. 哈希表（Hash Table）

C++：使用 std::unordered_map 实现哈希表，<unordered_map>中的unordered_map（无序哈希表）以及<map>中的map（有序映射），前者以键值对形式存储，查找插入删除平均时间复杂度接近常数，如unordered_map<int, string> myMap; 。

在C++中，set 提供以下三种数据结构，其底层实现以及优劣如下表所示（图源：代码随想录），std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的。

#include <iostream>
#include <unordered_map>
int main() {
    std::unordered_map<std::string, int> hashTable;
    // 插入元素
    hashTable["apple"] = 1;
    hashTable["banana"] = 2;
    // 访问元素
    std::cout << "Value for apple: " << hashTable["apple"] << std::endl;
    return 0;
}

Python：字典（Dictionary）就是哈希表的实现，用{}表示，例如my_dict = {'a': 1, 'b': 2}，查找、插入、删除操作都非常高效。

hash_table = {}
# 插入元素
hash_table["apple"] = 1
hash_table["banana"] = 2
# 访问元素
print(f"Value for apple: {hash_table['apple']}")

对比

C++ 的 std::unordered_map 和 Python 的 dict 都是无序哈希表。

Python 的 dict 在 3.7+ 版本中保持插入顺序。

6. 字符串（String）

C++:使用 std::string 表示字符串。支持丰富的操作，包括拼接、查找、切片等。

示例：字符串操作

#include <iostream>
#include <string>
int main() {
    std::string str = "Hello";
    // 拼接
    str += " World";
    // 查找
    size_t pos = str.find("World");
    // 子串
    std::string substr = str.substr(0, 5);
    std::cout << "String: " << str << std::endl;
    std::cout << "Position of 'World': " << pos << std::endl;
    std::cout << "Substring: " << substr << std::endl;
    return 0;
}

Python:使用 str 表示字符串。原生支持操作符和方法进行操作。

示例：字符串操作

str = "Hello"
# 拼接
str += " World"
# 查找
pos = str.find("World")
# 子串
substr = str[:5]
print(f"String: {str}")
print(f"Position of 'World': {pos}")
print(f"Substring: {substr}")

对比

Python 的字符串操作更加直观、简洁。

C++ 的 std::string 提供更底层的控制，例如内存管理。

7. 集合（Set）

C++：使用 std::set 或 std::unordered_set，<set>头文件提供set容器，它存储唯一元素，会自动排序；<unordered_set>中的unordered_set则是无序集合，能快速查找元素，例如unordered_set<int> mySet;。

在C++中，set 提供以下三种数据结构，其底层实现以及优劣如下表所示（图源：代码随想录），std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

#include <iostream>
#include <unordered_set>
int main() {
    std::unordered_set<int> hashSet = {1, 2, 3};
    // 插入元素
    hashSet.insert(4);
    // 遍历集合
    for (int val : hashSet) {
        std::cout << val << " ";
    }
    return 0;
}

Python：使用set()函数或者{}（空集必须用set()）创建集合，像my_set = {1, 2, 3}，集合支持交集、并集、差集等数学集合运算。

hash_set = {1, 2, 3}
# 插入元素
hash_set.add(4)
# 遍历集合
for val in hash_set:
    print(val, end=" ")

对比

C++ 的 std::unordered_set 和 Python 的 set 都是基于哈希的集合。

C++ 的 std::set 是基于红黑树的有序集合，Python 没有直接对应的实现。

8. 列表结构（List）

C++：C++ 中有两种主要的列表结构：std::list（双向列表），std::vector（动态数组，用于线性表，更多用法请参考“数组”部分）

std::list 特点： 双向链表，支持快速插入和删除操作（O(1)）。访问特定位置的元素效率较低（O(n)）。适合需要频繁插入或删除中间元素的场景。

示例：std::list

#include <iostream>
#include <list>
int main() {
    std::list<int> linkedList = {1, 2, 3};
    // 添加元素
    linkedList.push_back(4);   // 尾部插入
    linkedList.push_front(0);  // 头部插入
    // 删除元素
    linkedList.pop_back();     // 删除尾部
    linkedList.pop_front();    // 删除头部
    // 遍历列表
    for (int val : linkedList) {
        std::cout << val << " ";
    }
    return 0;
}

Python ：Python 中的列表使用内置的 list 类，是一种动态数组。

Python list 特点： 动态数组，底层实现基于连续内存。支持快速随机访问（O(1)）。插入和删除操作效率取决于位置（插入/删除中间元素为 O(n)）。

示例：Python 列表

# 创建列表
my_list = [1, 2, 3]
# 添加元素
my_list.append(4)  # 添加到尾部
my_list.insert(0, 0)  # 指定位置插入
# 删除元素
my_list.pop()  # 删除尾部
my_list.pop(0)  # 删除指定位置的元素
# 遍历列表
for val in my_list:
    print(val, end=" ")

对比：Python list vs C++ std::list

特性	C++ `std::list`	Python `list`
底层实现	双向链表	动态数组
插入/删除头尾元素	O(1)	插入尾部 O(1)，头部 O(n)
插入/删除中间元素	O(1)（给定迭代器）	O(n)
随机访问	O(n)	O(1)
内存消耗	高（需存储指针）	低（连续内存）
适用场景	频繁插入/删除的场景	快速随机访问的场景

适用场景总结

使用 C++ std::list：插入或删除元素非常频繁，尤其在头部或中间位置。不需要频繁访问特定位置的元素。

使用 Python list：需要快速随机访问元素。操作主要集中在尾部追加或删除，插入操作不多。

9. 树（Tree）

C++：一般要手动定义树节点结构体，比如struct TreeNode { int val; TreeNode* left; TreeNode* right; };，递归或者迭代地去实现树的遍历、插入、删除等算法，代码复杂度较高。C++ 标准库中没有直接提供通用的树结构，但可以使用以下几种方式构建：

自定义节点类。

使用 std::map 或 std::set（实现平衡二叉搜索树）。

使用第三方库（如 Boost 提供的树结构）。

#include <iostream>
#include <memory>
// 二叉树节点
struct TreeNode {
    int val;
    std::shared_ptr<TreeNode> left;
    std::shared_ptr<TreeNode> right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 遍历函数
void inOrderTraversal(std::shared_ptr<TreeNode> root) {
    if (root) {
        inOrderTraversal(root->left);
        std::cout << root->val << " ";
        inOrderTraversal(root->right);
    }
}
int main() {
    // 创建二叉树
    auto root = std::make_shared<TreeNode>(1);
    root->left = std::make_shared<TreeNode>(2);
    root->right = std::make_shared<TreeNode>(3);
    // 中序遍历
    inOrderTraversal(root);
    return 0;
}

Python：Python 没有内置树结构，同样依赖自定义类来定义树节点，不过Python简洁的语法能让树相关算法代码量有所减少，例如在二叉树的遍历算法实现上，代码行数往往比C++版本少。

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
# 遍历函数
def in_order_traversal(root):
    if root:
        in_order_traversal(root.left)
        print(root.value, end=" ")
        in_order_traversal(root.right)
# 创建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
# 中序遍历
in_order_traversal(root)

对比

C++ 需要管理内存（推荐使用智能指针如 std::shared_ptr 或 std::unique_ptr），Python 自动管理内存。

Python 实现树结构更加简洁，但运行效率不如 C++。

10. 堆（Heap）

C++： C++ 提供 std::priority_queue 实现堆结构（默认是最大堆）。也可以使用 std::make_heap 构建堆。借助<algorithm>中的函数，配合数组或者vector容器，可以构建堆。例如，用make_heap把vector变成堆结构，用push_heap、pop_heap维持堆特性。

//示例（最大堆）
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
int main() {
    std::priority_queue<int> maxHeap;
    // 插入元素
    maxHeap.push(10);
    maxHeap.push(20);
    maxHeap.push(5);
    // 获取最大值
    std::cout << "Max element: " << maxHeap.top() << std::endl;
    // 删除最大值
    maxHeap.pop();
    std::cout << "Max element after pop: " << maxHeap.top() << std::endl;
    return 0;
}
// 示例（最小堆）
int main2() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    // 插入元素
    minHeap.push(10);
    minHeap.push(20);
    minHeap.push(5);
    // 获取最小值
    std::cout << "Min element: " << minHeap.top() << std::endl;
    // 删除最小值
    minHeap.pop();
    std::cout << "Min element after pop: " << minHeap.top() << std::endl;
    return 0;
}

Python：heapq模块提供了堆相关操作，默认是最小堆，例如heapq.heappush向堆中添加元素，heapq.heappop从堆顶移除元素，常用于实现优先队列。详细介绍参考博客

import heapq
# 创建最小堆
min_heap = []
heapq.heappush(min_heap, 10)
heapq.heappush(min_heap, 20)
heapq.heappush(min_heap, 5)
# 获取最小值
print(f"Min element: {min_heap[0]}")
# 删除最小值
heapq.heappop(min_heap)
print(f"Min element after pop: {min_heap[0]}")

# 创建最大堆
max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -20)
heapq.heappush(max_heap, -5)
# 获取最大值
print(f"Max element: {-max_heap[0]}")
# 删除最大值
heapq.heappop(max_heap)
print(f"Max element after pop: {-max_heap[0]}")

对比

C++ 的 std::priority_queue 默认是最大堆，Python 的 heapq 默认是最小堆。

Python 的堆需要通过额外逻辑（如取负）实现最大堆。

总结

数据结构	C++ 库/类	Python 类	备注
数组	`std::array`/`std::vector`	`list`	Python 的 `list` 更类似 C++ 的 `std::vector`
链表	`std::list`	`collections.deque`	双向链表
哈希表	`std::unordered_map`	`dict`	Python 的 `dict` 保留插入顺序
字符串	`std::string`	`str`	Python 的 `str` 使用简单功能强大
集合	`std::set`/`std::unordered_set`	`set`	Python 无对应的有序集合实现
栈与队列	`std::stack`/`std::queue`	`list`/`deque`	Python 推荐使用 `deque` 替代 `list`
树	自定义类或第三方库（如 Boost）	自定义类	C++ 更灵活但复杂，Python 更简单
堆	`std::priority_queue` 或 `std::make_heap`	`heapq` 模块	C++ 默认最大堆，Python 默认最小堆

补充：Python中的双向队列-deque详细介绍

deque（全称：double-ended queue）是 Python 标准库模块 collections 提供的一个类，用于实现高效的双端队列操作。它适用于需要频繁在两端插入或删除元素的场景，性能优于 list，因为 list 的两端操作涉及 O(n) 的移动成本，而 deque 的两端操作复杂度为 O(1)。deque 是一个非常高效和灵活的数据结构，适用于需要频繁在两端进行插入、删除或旋转操作的场景。与 list 相比，它在两端操作的性能更优。通过灵活的操作方法，deque 可以满足多种实际需求，是 Python 数据结构库中的一大亮点。

1）导入`deque` 类

from collections import deque

2）基本操作

操作	方法	描述
创建双向队列	`deque(iterable)`	从可迭代对象初始化 `deque`
从右端添加元素	`append(x)`	在队列右端添加元素，复杂度 O(1)
从左端添加元素	`appendleft(x)`	在队列左端添加元素，复杂度 O(1)
从右端移除元素	`pop()`	移除并返回右端的元素，复杂度 O(1)
从左端移除元素	`popleft()`	移除并返回左端的元素，复杂度 O(1)
查看队列中的元素	支持索引和迭代	直接通过索引访问元素或使用 `for` 循环遍历
扩展队列（右端）	`extend(iterable)`	将可迭代对象的元素添加到队列右端
扩展队列（左端）	`extendleft(iterable)`	将可迭代对象的元素逆序添加到队列左端
旋转队列	`rotate(n)`	将队列中的元素旋转 n 步（正数表示右旋，负数表示左旋）
清空队列	`clear()`	清空整个队列
最大长度限制	`maxlen` 参数	限制队列最大长度，超出时会自动丢弃多余的元素（从另一端）

3）示例代码

创建双向队列

from collections import deque
# 初始化队列
dq = deque([1, 2, 3])
print("Initial deque:", dq)

输出:

Initial deque: deque([1, 2, 3])

基本插入和删除操作

dq.append(4)  # 在右端添加
dq.appendleft(0)  # 在左端添加
print("After append operations:", dq)
dq.pop()  # 移除右端元素
dq.popleft()  # 移除左端元素
print("After pop operations:", dq)

输出:

After append operations: deque([0, 1, 2, 3, 4])
After pop operations: deque([1, 2, 3])

扩展队列

dq.extend([5, 6])  # 在右端扩展
print("After extend:", dq)

dq.extendleft([-1, -2])  # 在左端扩展（逆序添加）
print("After extendleft:", dq)

输出:

After extend: deque([1, 2, 3, 5, 6])
After extendleft: deque([-2, -1, 1, 2, 3, 5, 6])

限制最大长度

dq = deque(maxlen=5)  # 创建一个最大长度为 5 的队列
dq.extend([1, 2, 3, 4, 5])
print("Deque with maxlen=5:", dq)

dq.append(6)  # 添加新元素时，左端的元素被丢弃
print("After exceeding maxlen:", dq)

输出:

Deque with maxlen=5: deque([1, 2, 3, 4, 5], maxlen=5)
After exceeding maxlen: deque([2, 3, 4, 5, 6], maxlen=5)

旋转队列

dq = deque([1, 2, 3, 4, 5])
dq.rotate(2)  # 右旋 2 步
print("After rotating right by 2:", dq)

dq.rotate(-3)  # 左旋 3 步
print("After rotating left by 3:", dq)

输出:

After rotating right by 2: deque([4, 5, 1, 2, 3])
After rotating left by 3: deque([2, 3, 4, 5, 1])

清空队列

dq.clear()
print("After clearing:", dq)

输出:

After clearing: deque([])

4）性能对比

操作	`deque` 复杂度	`list` 复杂度	说明
头部插入	O(1)	O(n)	`list` 插入时需移动所有元素，`deque` 不需要
尾部插入	O(1)	O(1)	两者效率相当
头部删除	O(1)	O(n)	`list` 删除时需移动所有元素，`deque` 不需要
尾部删除	O(1)	O(1)	两者效率相当
随机访问	O(n)	O(1)	`list` 支持高效随机访问，而 `deque` 不支持直接索引操作