具有STL风格接口的Python列表

1 投票

6 回答

2557 浏览

数据工程师

提问于 2025-04-15 17:32

我需要把一个用C++ STL写的应用程序移植到Python。虽然我对Python还不太熟，但我已经编程超过十年了，对STL有很多经验，这让我一直想用C++。这几天我在Google上搜索了以下几个内容：

Python STL（希望能利用我多年的STL经验）
Python链表
Python高级列表用法
Python列表优化
Python有序集合

但是我找到的帖子要么是关于这些主题的，要么是一些根本不算高级的Python列表教程，或者是死胡同。我对自己没找到有用的信息感到很惊讶，可能是因为我工作太累了，搜索的关键词也不太对！

（我的问题）有没有办法得到一个Python的STL包装器，或者一个能像STL那样工作的Python列表接口？如果没有，能不能给我推荐一些真正高级的教程或论文，教我如何管理非常大的、排序的复杂对象集合？

附注：我可以轻松实现一两个使用场景的变通方法，但如果管理层想要移植更多代码，我希望能随时用等效的Python代码替换掉任何STL代码。而且是的，我已经测量过，确实需要完全优化的代码！我不能只是做冗余的排序和搜索！

（补充）感谢大家的回复，我查看了一些参考资料，感觉不错。针对这里的一些评论：

1 - 之所以要移植到Python，是因为管理层这么要求，我其实更想不动它——如果没坏，为什么要修？

2 - 关于复杂对象的高级列表用法，我的意思是：有很多不同的方式来排序和比较对象，而不是仅仅用一个cmp方法。我想要广泛地进行切片、排序、合并、搜索、插入、删除和组合列表。我想要列表的列表迭代器，尽量避免复制。

3 - 我现在知道内置的列表其实是数组，我应该寻找其他的Python类。我觉得这可能是我困惑的根源。

4 - 当然，我在学习用Python的方式来做事情，但我也有截止日期。我正在移植的STL代码是正常工作的，我希望尽量少改动，因为那样可能会引入bug。

感谢大家的意见，我真的很感激。

数据结构有序集合代码移植 STL 列表优化复杂对象高级编程列表迭代器

6 个回答

对于像链表那样的操作，人们通常会使用 collections.deque。

你需要快速进行哪些操作呢？是二分查找？还是插入数据？

回答于 2025-04-15 由 Python大师

分享举报

如果我是你，我会花时间学习如何正确使用Python中各种数据结构，而不是寻找和C++相似的东西。

其实你并不是在寻找什么复杂的东西，只是想处理一些数据结构。在这种情况下，我建议你看看Python的相关文档。

按照“Python”的方式来做，会对你有帮助，更重要的是，对将来维护你代码的人也会有帮助，他们会想知道你为什么要在Python中用C++的方式编程。

为了引起你的兴趣，其实没有理由偏爱 STL的风格而不是Python（顺便说一下，我也是一个熟悉STL的C++程序员），我们可以看看构建一个列表并遍历它的最简单例子：

Python的方式：

mylist = [1, 2, 3, 4]

for value in mylist:
    # playaround with value

STL的方式（我编的，模仿STL）在Python中：

mylist = [1, 2, 3, 4]
mylistiter = mylist.begin()

while mylistiter != mylist.end():
    value = mylistiter.item()
    mylistiter.next()

回答于 2025-04-15 由 Python大师

分享举报

Python中的“列表”并不是链表，它们更像是Java的ArrayList或者C++的std::vector，简单来说，就是一种可以调整大小的紧凑数组，里面存的是指针。

关于这些主题，一个不错的“进阶教程”是Hettinger的核心Python容器：内部原理的演讲（这个视频是在意大利的一次会议上录制的，但讲的是英语；还有一个更短的演讲，基本上是同样的内容，可以在这里找到）。

所以，Python列表的性能特点基本上和C++的std::vector一样：Python的.append方法就像C++的push_back，时间复杂度是O(1)，但是在“中间”插入或删除元素的时间复杂度是O(N)。因此，保持列表有序（可以借助Python标准库中的bisect模块轻松实现）是比较耗费时间的（如果元素是随机到达或离开的，每次插入和删除都是O(N)，这和在std::vector中保持顺序是一样的。对于某些用途，比如优先队列，你可以使用“堆队列”，这也可以通过Python标准库中的heapq模块轻松维护——但当然，这样的结构没有完全有序的列表（或向量）那么多用途。

所以，对于在C++中你会使用std::set（并依赖它是有序的，也就是说，哈希集合不行——Python的set是基于哈希的，不是有序的）这样的情况，你可能更好地选择一些其他的模块，比如这个模块（如果你需要保持纯Python），或者这个模块（它提供AVL树，而不是红黑树，但作为C实现的Python扩展，可能会提供更好的性能），如果可以使用C编写的扩展的话。

如果你最终使用自己的模块（无论是纯Python还是C编写的），你可以选择给它一个类似STL的接口（比如有.begin、.end，以及通过递增而不是调用next方法来推进的迭代器对象……），不过它的性能永远不会像“顺应语言特性”那样好（for语句是优化过的，使用的是正常的Python迭代器，也就是带有next方法的迭代器，它的速度会比用不太标准的STL风格迭代器包裹一个有些笨拙的while要快）。

如果你想给任何Python内置容器加上STL风格的外壳，会产生相当大的开销，因此性能损失可能会很大。如果你如你所说，“确实需要完全优化的代码”，那么仅仅为了“语法方便”而使用这样的外壳似乎是个很糟糕的选择。

Boost Python，这个Python扩展包可以封装强大的C++ Boost库，可能最适合你的需求。

回答于 2025-04-15 由 Python大师

分享举报

具有STL风格接口的Python列表

6 个回答

撰写回答