C++「multiset <int>」是否有Python等價物？

我將一些C++代碼移植到Python中，其中一個數據結構是一個multiset，但我不確定如何在Python中對其進行建模。C++「multiset <int>」是否有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()

來源

2013-06-27 MrP

您可以在python中查看'Counter'類：http://docs.python.org/2/library/collections.html#collections.Counter – taocp

是否有與我列出的函數/方法等價的東西？ – MrP

'計數器'不等同於'std :: multiset'。 – juanchopanza

沒有。請參閱Python's standard library - is there a module for balanced binary tree?，以獲取Python中C++樹形容器（map，set，multimap,multiset）的等效項的一般討論。

我能想到的最接近的是使用字典映射整數計數（也是整數）。但是，這並不能讓您按順序鍵入，因此您無法使用lower_bound進行搜索。另一種方法是使用有序列表，正如其他人所建議的那樣，可能是（整數，計數）元組列表？如果您在完成所有插入操作後只需要搜索，則可以使用字典作爲構建的臨時結構，在完成所有插入操作後構建列表，然後使用列表進行搜索。

來源

2013-06-27 15:39:51 TooTone

是的，代碼先進行大量插入，然後搜索/刪除各種項目。這兩個進程都使用很多lower_bound調用。 – MrP

@MrP你知道爲什麼在插入過程中有'lower_bound'調用嗎？在移除過程中重新調用'lower_bound'，如果你有一個'（integer，count）'元組列表，你可以通過遞減計數來移除項目，如果計數達到零，你可以離開項目並清理一段時間之後。（插入全新的整數將是更大的問題！） – TooTone

你可以保持使用列表中的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-27 15:30:37 doctorlove

或者使用heapq，也許。 – Marcin

有幾種排序列表數據類型的實現可以滿足您的條件。兩種流行的選擇是SortedContainers和blist模塊。這些模塊中的每一個都提供了一個SortedList數據類型，該數據類型按排序順序自動維護元素，並允許快速插入和下限/上限查找。有一個performance comparison這也有幫助。

使用來自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-28 18:53:49 GrantJ

有幾個數據結構接近。

蟒蛇類別：
- 有序字典：字典的子類，記得添加的條目順序。 link
- 計數器：用於計算可哈希對象的dict子類。link
由Django框架提供：
- 用相同值的多個鍵的字典：link
- 排序字典包括有序字典現在：link

來源

2015-01-10 20:50:45

C++「multiset <int>」是否有Python等價物？

回答

相關問題