структура данных ключ-значение для поиска ключа в O (1) и получения максимального значения в O (1)

Question

структура данных ключ-значение для поиска ключа в O (1) и получения максимального значения в O (1)

Мне нужно реализовать структуру данных ключ-значение, которая ищет уникальный ключ в O (LGN) или O (1) И получить максимум значение в O (1). Я думаю о

boost::bimap< unordered_set_of<key> ,multiset_of<value> >

Обратите внимание, что в моих наборах данных значения ключа нет дублированного ключа. Однако два ключа могут иметь одинаковое значение. Поэтому я использовал мультимножество для хранения значений.

Мне нужно часто вставлять / удалять / обновлять пару ключ-значение

Как это звучит?

3

bimap boost c++data-structures stl

Решение

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

Вы можете построить это с помощью std::map и std::set,

Одна карта для хранения фактических значений, т.е. std::map<key, value> m;, Здесь хранятся ваши ценности. Вставка элементов в карту — это O (log n).
Набор итераторов, указывающих на карту; этот набор сортируется по значению соответствующей записи карты, т.е. std::set<std::map<key, value>::iterator, CompareBySecondField> s; с чем-то вроде (не проверено):
```
template <class It>
struct CompareBySecondField : std::binary_function<It, It, bool> {
bool operator() ( const T &lhs, const T &rhs ) const {
return lhs->second > rhs->second;
}
};
```
Затем вы можете получить итератор для записи карты с наибольшим значением, используя *s.begin();,

Это довольно просто построить, но вы должны обязательно обновлять оба контейнера всякий раз, когда добавляете / удаляете элементы.

1

Источник

Accepted Answer

Это зависит от того, что вы хотите сделать. Таким образом, ясно, что вы хотите использовать его для некоторой конструкции «получить максимальные значения в итерации».

Вопрос 1: Вы получаете доступ к элементам по их ключи также?

Если да, Я могу придумать для вас два решения:
1. использование boost::bimap — простое, проверенное решение с логарифмическим временем выполнения.
2. создать пользовательский контейнер, который содержит std::map (или еще быстрее с помощью ключа доступа std::unordered_map) и реализация кучи (например, std::priority_queue<std::map<key, value>::iterator> + пользовательский компаратор), а также синхронизирует их и т. д. Это сложный путь, но, возможно, быстрее. Большинство операций на обоих будет O (logn) (вставить, получить&поп макс, получить ключом, удалить) но константа иногда имеет значение. Хотя вы используете std::unordered_map доступ по нажатию клавиши будет O (1).
  
  Вы также можете написать тесты для нового контейнера и оптимизировать его для работы, которую вы используете чаще всего.
Если нет, вы действительно просто используете элементы, используя максимальное значение

Вопрос 2: Вы вставляете / удаляете / обновляете элементы случайным образом или сначала вставляете все элементы в один раунд, а затем удаляете их один за другим?
- для случайного использования / удаления / обновления std::priority_queue<std::pair<value, key>>
- если вы сначала вставите элементы, а затем удалите их один за другим, используйте и std::vector<std::pair<value, key>> а также std::sort() это перед первой операцией удаления. На самом деле не удаляйте элементы, просто итерируйте их.

2