Есть ли Python-эквивалент для C ++ «multiset & lt; int & gt;»?

Question

Есть ли Python-эквивалент для C ++ «multiset & lt; int & gt;»?

Я портирую некоторый код 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()

9

c++multiset python set

Решение

Другие решения

Существует пара реализаций типов отсортированных списков, которые соответствуют вашим критериям. Два популярных варианта SortedContainers а также Blist модули. Каждый из этих модулей обеспечивает SortedList тип данных, который автоматически поддерживает элементы в отсортированном порядке и позволяет быстро вставлять и искать нижнюю / верхнюю границу. Есть сравнение производительности это тоже полезно.

Эквивалентный код, использующий тип SortedList из модуля SortedContainers:

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

Все эти операции должны эффективно работать с типом данных отсортированного списка.

4

Есть пара структур данных, которые приближаются.

коллекции питона:
- Упорядоченный dict: подкласс dict, который помнит записи заказа, был добавлен. ссылка на сайт
- Counter: подкласс dict для подсчета хеш-объектов. ссылка на сайт
обеспеченный структурой django:
- Дикт с несколькими ключами с одинаковым значением: ссылка на сайт
- Сортированный dict, который устарел как коллекция python, теперь включает в себя упорядоченный dict: ссылка на сайт

2

Вы можете сохранить заказанный список, используя разрез`ать функции. Например 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

2

Источник

Accepted Answer

Нет Увидеть Стандартная библиотека Python — есть ли модуль для сбалансированного бинарного дерева? для общего обсуждения эквивалентов контейнеров дерева C ++ (map, set, multimap, multiset) в Python.

Самое близкое, что я могу придумать, это использовать словарь, отображающий целые числа в числа (также целые числа). Однако это не приводит вас в порядок ключей, поэтому вы не можете искать с помощью lower_bound, Альтернативой является использование упорядоченного списка, как уже предлагали другие, может быть, список (целое число, число) кортежей? Если вам нужно искать только после того, как вы сделали все свои вставки, вы можете использовать словарь как временную структуру для построения, построить список после того, как вы сделали все вставки, а затем использовать список для поиска.

1