Is there a Python equivalent for C++ "multiset<int>"?

Question

I am porting some C++ code to Python and one of the data structures is a multiset, but I am not sure how to model this in Python.

Let ms be the C++ multiset<int>

How ms is used (posting some examples)

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

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

Answer 1

There are a couple implementations of sorted list data types which would fit your criteria. Two popular choices are SortedContainers and blist modules. Each of these modules provides a SortedList data type which automatically maintains the elements in sorted order and would allow for fast insertion and lower/upper bound lookups. There's a performance comparison that's helpful too.

The equivalent code using the SortedList type from the SortedContainers module would be:

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()

All of those operations should work efficiently on a sorted list data type.