Is there a Python equivalent for C++ multiset?

Is there a Python equivalent for C++ multiset?

There isnt. See Pythons standard library – is there a module for balanced binary tree? for a general discussion of the equivalents of C++ tree containers (map, set, multimap, multiset) in Python.

The closest I can think of is to use a dictionary mapping integers to counts (also integers). However this doesnt get you the keys in order, so you cant search using lower_bound. An alternative is a to use an ordered list, as suggested by others already, maybe a list of (integer, count) tuples? If you only need to search after youve done all your insertions, you could use the dictionary as a temporary structure for construction, build the list after youve done all the insertions, then use the list for searching.

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. Theres a performance comparison thats 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

# Erase an element
del sl[start:end]

# Insert an element

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

# Clear elements

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

Is there a Python equivalent for C++ multiset?

There are a couple of data-structures which come close.

  • python collections:

    • Ordered dict: dict subclass that remembers the order entries were added. link
    • Counter: dict subclass for counting hashable objects. link

  • provided by django framework:

    • A dict with multiple keys with same value: link
    • Sorted dict which is deprecated as python collection includes an ordered dict now: link

Leave a Reply

Your email address will not be published. Required fields are marked *