C++“multiset<int>”有等效的 Python 吗？

Question

我正在将一些 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()

Answer 1

没有。请参阅 Python 的标准库 - 是否有平衡二叉树模块？，了解 Python 中 C++ 树容器（

map

、

set

、

multimap

、

multiset

）的等效项的一般讨论。

我能想到的最接近的是使用字典将整数映射到计数（也是整数）。然而，这并不能按顺序为您提供键，因此您无法使用

lower_bound

进行搜索。另一种方法是使用有序列表，正如其他人已经建议的那样，也许是（整数，计数）元组的列表？如果你只需要在完成所有插入后进行搜索，你可以使用字典作为构建的临时结构，在完成所有插入后构建列表，然后使用列表进行搜索。

Answer 2

有几种排序列表数据类型的实现可以满足您的标准。两个流行的选择是 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()

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

Answer 3

有几个数据结构很接近。

• python 集合：

  • Ordered dict：记住添加顺序条目的 dict 子类。 链接
  • Counter：用于计数可哈希对象的 dict 子类。 链接

    ---

• django框架提供：

  • 具有多个具有相同值的键的字典：link
  • 已弃用的排序字典，因为 python 集合现在包含有序字典：link

    ---

Answer 4

您可以使用 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

Answer 5

如果不需要排序，可以将其用作

multiset<int>

（或

unordered_multiset<int>

）：

from collections import Counter

def multiset(array):
    return set(Counter(array).items())

Answer 6

是的，有一个像 cpp 这样的模型你可以：-> 您可以使用

https://pypi.org/project/orderdmultiset/0.1.1/ 与 cpp 等多重集相同 用户指南
https://github.com/rishiko/sortedmultiset/blob/main/User%20Guide

$ pip install orderdmultiset
import sortedmultiset
mset=sortedmultiset.orderdmultiset()--->To create an object of sorted multiset
mset.append(5)#-----> add an element to the multiset
mset.append(4)
print(mset.multiset)#-------->To print the multiset #output [4,5]
mset.erase(4) #---------> True element present and erased #output True
print(mset.multiset)#-------->To print the multiset #output [5]
mset.erase(56)-----------------> False as element not present in multiset #output False.
mset.append(6)
mset.append(3)
print(mset.multiset)#-------->To print the multiset #output [3,5,6]
chq=mset.search(5)#----------> will give a memory address as element present #output 
                              <sortedmultiset.sortedmultiset.TreeNode object at 0x000002C6C69E44F0>
chq=mset.search(678) #-----------> output will be None as element is not present

这只是我正在处理字符串的整数