Unordered_Map of Maps или Priority_Queues?
У меня есть структура, которая состоит из имени и возраста. Я хотел бы иметь unordered_map, который принимает строки в качестве ключей, а затем либо карту, либо priority_queue, в которой затем сохраняется возраст с учетом этой строки:
struct Person{
string name;
int age;
bool operator() (const Person &other){}
};
unordered_map<string,priority_queue<Person,vector<Person>> map;
or
unordered_map<string,map<int,Persons>> map;
Я знаю, что синтаксис объявлений полностью верен, но, надеюсь, вы поняли …
Что я должен пойти для лучшей производительности? Идея состоит в том, чтобы иметь возможность искать, вставлять, удалять очень быстро.
Решение
priority_queue — это очень специфическая структура данных, которая поддерживает ограниченный набор операций: получить размер, получить или удалить максимальный элемент, добавить новый элемент. Так что, если вам нужен случайный доступ и удаление ваших элементов, карта является единственным допустимым выбором этих двух вариантов.
В общем, они оба работают в O (log N). priority_queue быстрее, но менее мощен. Это быстрее, потому что он использует кучу вместо сбалансированных деревьев, что приводит к лучшему использованию памяти (все элементы лежат вместе в одном блоке памяти) и меньшему выделению памяти (пере).
Другие решения
Других решений пока нет …