31

我正在将一些 C++ 代码移植到 Python 中，其中一个数据结构是一个多重集，但我不确定如何在 Python 中对此进行建模。

让我们ms成为 C++multiset<int>

如何ms使用（发布一些示例）

multiset<int>::iterator it = ms.find(x)
ms.erase(it)

ms.insert(x)
ms.end()
ms.lower_bound(x)
ms.clear()
4

5 回答 5

8

有几种符合您标准的排序列表数据类型的实现。两个流行的选择是SortedContainers和blist模块。这些模块中的每一个都提供了一个SortedList数据类型，该数据类型自动以排序顺序维护元素，并允许快速插入和下限/上限查找。有一个性能比较也很有帮助。

使用 SortedContainers 模块中的 SortedList 类型的等效代码是：

from sortedcontainers import SortedList
sl = SortedList()

# Start index of `x` values
start = sl.bisect_left(x)

# End index of `x` values
end = sl.bisect_right(x)

# Iterator for those values
iter(sl[start:end])

# Erase an element
del sl[start:end]

# Insert an element
sl.add(x)

# Iterate from lower bound
start = sl.bisect_left(x)
iter(sl[x] for x in range(start, len(sl)))

# Clear elements
sl.clear()

所有这些操作都应该在排序列表数据类型上有效地工作。

于 2014-04-28T18:53:49.697 回答
8

没有。请参阅Python 的标准库 - 是否有平衡二叉树的模块？有关Python中 C++ 树容器 ( map, set, multimap, )等价物的一般性讨论。multiset

我能想到的最接近的是使用字典将整数映射到计数（也是整数）。但是，这不会让您按顺序获得密钥，因此您无法使用lower_bound. 另一种方法是使用有序列表，正如其他人已经建议的那样，也许是（整数，计数）元组的列表？如果您只需要在完成所有插入后进行搜索，您可以将字典用作构建的临时结构，在完成所有插入后构建列表，然后使用列表进行搜索。

于 2013-06-27T15:39:51.917 回答
4

有几个数据结构很接近。

  • 蟒蛇集合：

    • Ordered dict：记住添加的订单条目的 dict 子类。关联
    • Counter：用于计算可散列对象的 dict 子类。关联

  • 由 django 框架提供：

    • 具有多个具有相同值的键的字典：链接
    • 已被弃用为 python 集合的排序字典现在包括一个有序字典：链接
于 2015-01-10T20:50:45.367 回答
3

您可以使用bisect函数保持列表有序。例如find会变成

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

您将在文档中找到其他等价物。而不是检查end你现在将得到一个ValueError

于 2013-06-27T15:30:37.837 回答
-1

如果不需要排序，可以将其用作multiset<int>（或unordered_multiset<int>）：

from collections import Counter

def multiset(array):
    return set(Counter(array).items())
于 2021-08-11T13:23:35.120 回答