Python的标准库提供了丰富的内置数据结构和函数，使用这些工具能为我们提供一套强有力的工具。
需要注意的是，相比C++与Java，Python的一些特点：
- Python不需要显式声明变量类型
- Python没有模板(Template)的概念，因为Python是动态类型语言
- Python的标准库导入更简单，只需要
import相关模块即可
我们主要介绍以下几种数据结构：
list：列表set：集合dict：字典queue和deque：队列heapq：堆
如果在比赛的过程中，忘记了某些函数的使用或者拼写，可能查看比赛机器桌面上的手册，会有这些函数的具体使用方法。
1. 迭代器说明
在Python中，迭代器的概念比C++更简单。所有的Python集合都是可迭代的，不需要显式声明迭代器。我们可以直接使用for循环进行遍历：
numbers = [1, 2, 3, 4, 5]
for num in numbers:print(num) # 输出: 1 2 3 4 5# 如果需要索引，可以使用enumerate
for index, num in enumerate(numbers):print(f"索引 {index}: {num}")
2. 数据结构详解
2.1 list（列表）
list是Python中最基础的序列数据结构，本身则就具有可变数组的能力。
基本操作：
# 创建列表
lst = [] # 创建空列表
lst = [1, 2, 3] # 创建包含元素的列表
lst = [0] * 5 # 创建长度为5的列表，所有元素为0# 常用操作
lst.append(x) # 在末尾添加元素x
lst.pop() # 删除并返回末尾元素
lst.pop(i) # 删除并返回索引i处的元素
lst.insert(i, x) # 在索引i处插入元素x
len(lst) # 返回列表长度
lst[i] # 访问第i个元素
例子：
numbers = []
numbers.append(1) # numbers = [1]
numbers.append(2) # numbers = [1, 2]
numbers.append(3) # numbers = [1, 2, 3]
print(len(numbers)) # 输出: 3
numbers.pop() # numbers = [1, 2]
2.2 set（集合）
set是Python中的无序不重复元素集合，实现方式是哈希表，而不是C++中的红黑树。这意味着Python的set操作复杂度是O(1)，而不是O(log n)。
基本操作：
s = set() # 创建空集合
s.add(x) # 添加元素x
s.remove(x) # 删除元素x（元素不存在会报错）
s.discard(x) # 删除元素x（元素不存在不会报错）
len(s) # 返回元素个数
x in s # 检查元素是否在集合中
例子：
s = set()
s.add(3) # s = {3}
s.add(1) # s = {1, 3}
s.add(2) # s = {1, 2, 3}
s.add(2) # s仍然是{1, 2, 3}
print(2 in s) # 输出: True
2.3 dict（字典）
dict是Python中的键值对容器，同样基于哈希表实现，操作复杂度是O(1)。
基本操作：
d = {} # 创建空字典
d[key] = value # 添加或更新键值对
d.pop(key) # 删除并返回键对应的值
len(d) # 返回键值对数量
key in d # 检查键是否存在
例子：
scores = {}
scores["Alice"] = 95 # 记录Alice的分数
scores["Bob"] = 89 # 记录Bob的分数
print(scores["Alice"]) # 输出: 95
2.4 queue和deque（队列）
Python提供了collections.deque作为双端队列实现，功能比C++的queue更强大。
from collections import deque# 基本操作
q = deque() # 创建空队列
q.append(x) # 在右侧添加元素
q.appendleft(x) # 在左侧添加元素
q.pop() # 删除并返回右侧元素
q.popleft() # 删除并返回左侧元素
len(q) # 返回元素个数
例子：
from collections import deque
q = deque()
q.append(1) # q = deque([1])
q.append(2) # q = deque([1, 2])
q.append(3) # q = deque([1, 2, 3])
print(q[0]) # 输出: 1
q.popleft() # q = deque([2, 3])
2.5 heapq（堆）
Python通过heapq模块提供堆的功能，默认是小根堆（最小元素在顶部），注意，该模块使用需要一个容器来进行操作。
基本操作：
import heapqheap = [] # 创建空列表作为堆
heapq.heappush(heap, x) # 将元素x压入堆
heapq.heappop(heap) # 弹出并返回最小元素
heap[0] # 查看最小元素
len(heap) # 返回元素个数
例子：
import heapqheap = []
heapq.heappush(heap, 3) # heap = [3]
heapq.heappush(heap, 1) # heap = [1, 3]
heapq.heappush(heap, 4) # heap = [1, 3, 4]
print(heap[0]) # 输出: 1（最小元素）
3. 补充说明-关于有序集合
Python的set和dict不支持像C++那样的二分查找API（lower_bound、upper_bound），因为它们是基于哈希表实现的。在python组的题目中，也基本不会出现相关的题。
5. 实践与例题
5.1 真题-连连看
很明显，需要求的是每条对角线上的相同数值的对数，如下图：
我们可以枚举每一条45度角对角线，然后进行从上到下、或是从下到上进行遍历，一边遍历一边记录当前数值的数量即可，使用map 进行维护：
def get_l(x, y):global ansmp = {}while x <= n and y <= m:if a[x][y] not in mp:mp[a[x][y]] = 0ans += mp[a[x][y]] mp[a[x][y]] += 1x += 1y += 1def get_r(x, y):global ansmp = {}while x > 0 and y <= m:if a[x][y] not in mp:mp[a[x][y]] = 0ans += mp[a[x][y]] # 当 key 不存在 mp 中时，默认值为 0mp[a[x][y]] += 1x -= 1y += 1n, m = map(int, input().split())
a = [[0] * (m + 1) for _ in range(n + 1)] # 创建二维数组 a，索引从 1 开始
ans = 0# 读取输入
for i in range(1, n + 1):a[i] = [0] + list(map(int, input().split())) # 读取每一行，并加上前导零，保持从索引 1 开始# 遍历处理主对角线和另外一条对角线
for i in range(1, n + 1):get_l(i, 1) # 处理主对角线get_r(i, 1) # 处理另外一条对角线for i in range(2, m + 1):get_l(1, i)get_r(n, i)print(ans * 2)
5.2 哈希表的实现-set
我们直接使用 set 即可
n = int(input()) # 读取输入的整数 n
st = set() # 创建一个空的集合for _ in range(n):opt, m = input().split() # 读取操作符和整数 mm = int(m) # 将 m 转换为整数if opt == 'I': # 如果操作符是 'I'，则插入元素 mst.add(m)elif m not in st: # 如果操作符不是 'I' 且 m 不在集合中print("No")else:print("Yes")
5.3 堆与优先队列
我们使用优先队列解决：
import heapqn = int(input()) # 读取操作次数 n
pq = [] # 使用列表来模拟小根堆for _ in range(n):op = input().split() # 读取操作符if op[0] == "push":x = int(op[1])heapq.heappush(pq, x) # elif op[0] == "remove":if not pq:print("empty")else:heapq.heappop(pq) # 弹出堆顶元素elif op[0] == "min":if not pq:print("empty")else:print(pq[0]) # 输出堆顶元素elif op[0] == "print":k = int(op[1])if 0 < k <= len(pq):temp = []for _ in range(k):temp.append(pq[0]) # 获取堆顶元素heapq.heappop(pq) # 弹出堆顶元素print(*temp) # 打印出来
5.4 小蓝的图书馆
题，要求我们，每一个作者对应一个书的列表，我们可能使用map，同时套上vector。
mp = {}n = int(input()) # 读取操作次数 nfor _ in range(n):arg = input().split() # 读取操作指令if arg[0] == "add":book, au = arg[1], arg[2] # 读取书名和作者if au not in mp:mp[au] = []mp[au].append(book) # 将书名添加到对应作者的列表中else:au = arg[1] # 读取作者名if au not in mp:mp[au] = []print(len(mp[au])) # 输出该作者的书籍数量
