boost — C ++ Bimap Слева unordered_map Сортировка справа изменяемой мультикарты
Мне нужно реализовать следующую структуру данных для моего проекта. У меня есть отношение
const MyClass*
в
uint64_t
Для каждого указателя я хочу сохранить счетчик, связанный с ним, который может быть изменен во времени (фактически только увеличен). Это не будет проблемой, я могу просто сохранить его в std :: map. Проблема в том, что мне нужен быстрый доступ к указателям, которые имеют самые высокие значения.
Вот почему я пришел к выводу использовать boost :: bimap. Для моего проекта определено следующее:
typedef boost::bimaps::bimap<
boost::bimaps::unordered_set_of< const MyClass* >,
boost::bimaps::multiset_of< uint64_t, std::greater<uint64_t> >
> MyBimap;
MyBimap bimap;
Это будет работать нормально, но я прав, что я не могу изменить uint64_t для пары, которые были вставлены один раз? Документация говорит, что multiset_of является константой, и поэтому я не могу изменить значение пары в bimap.
Что я могу сделать? Каков будет правильный способ изменить значение одного ключа в этом бимапе? Или для этой проблемы возможна более простая структура данных?
Решение
Вот простое решение, сделанное вручную.
Внутренне он хранит карту для хранения счетчиков, проиндексированных указателем объекта, и последующего множества наборов итераторов, упорядоченных по убыванию количества их пуантеев.
Всякий раз, когда вы изменяете счет, вы должны переиндексировать. Я сделал это по частям, но вы можете сделать это как пакетное обновление, в зависимости от требований.
Обратите внимание, что в C ++ 17 есть предложенный splice операция для наборов и карт, которая сделает переиндексацию чрезвычайно быстрой.
#include <map>
#include <set>
#include <vector>
struct MyClass { };struct store
{
std::uint64_t add_value(MyClass* p, std::uint64_t count = 0)
{
add_index(_map.emplace(p, count).first);
return count;
}
std::uint64_t increment(MyClass* p)
{
auto it = _map.find(p);
if (it == std::end(_map)) {
// in this case, we'll create one - we could throw instead
return add_value(p, 1);
}
else {
remove_index(it);
++it->second;
add_index(it);
return it->second;
}
}
std::uint64_t query(MyClass* p) const {
auto it = _map.find(p);
if (it == std::end(_map)) {
// in this case, we'll create one - we could throw instead
return 0;
}
else {
return it->second;
}
}
std::vector<std::pair<MyClass*, std::uint64_t>> top_n(std::size_t n)
{
std::vector<std::pair<MyClass*, std::uint64_t>> result;
result.reserve(n);
for (auto idx = _value_index.begin(), idx_end = _value_index.end() ;
n && idx != idx_end ;
++idx, --n) {
result.emplace_back((*idx)->first, (*idx)->second);
}
return result;
}
private:
using map_type = std::map<MyClass*, std::uint64_t>;
struct by_count
{
bool operator()(map_type::const_iterator l, map_type::const_iterator r) const {
// note: greater than orders by descending count
return l->second > r->second;
}
};
using value_index_type = std::multiset<map_type::iterator, by_count>;
void add_index(map_type::iterator iter)
{
_value_index.emplace(iter->second, iter);
}
void remove_index(map_type::iterator iter)
{
for(auto range = _value_index.equal_range(iter);
range.first != range.second;
++range.first)
{
if (*range.first == iter) {
_value_index.erase(range.first);
return;
}
}
}
map_type _map;
value_index_type _value_index;
};
Другие решения
Других решений пока нет …