C ++ структура данных для объединения поиска и упорядоченных данных

Question

У меня есть отсортированный график, когда я загружаю ребра, я использую хеш-таблицу для поиска вершин.Ребра отсортированы по источнику, поэтому мне нужно только искать «более глубокие» вершины.Если у данного ребра есть вершина источника на уровне n , то вершина приемника должна быть на уровне m , где m> n .Мне нужно использовать это поведение для повышения производительности.

«Идеальным» наивным решением будет хеш-таблица для каждого уровня, где я могу использовать уровень, чтобы найти правильную таблицу, а затем найти элемент в таблице.Это также позволило бы мне получить дополнительное преимущество от возможности восстановления памяти, когда n , уровень источника, больше, чем уровень.К сожалению, график слишком велик для этого подхода, 10 ^ 6 уровней и 10 ^ 9 вершин.

Кто-нибудь есть какие-либо предложения о том, на какую структуру данных я должен смотреть?Грэкиас

Answer 1

Учитывая ваши оценки размера для задачи, я бы предложил вектор векторов: внешний вектор содержит один внутренний вектор для каждого уровня, поэтому он содержит около 1 миллиона записей;внутренние векторы (которые содержат около 1000 записей каждый?) должны храниться в отсортированном порядке и использовать отсортированные вставки, используя lower_bound() и т. д.

Вы можете восстановить память с помощью трюка копирования / замены, чтобы заменить старые, неиспользованныевекторы по пустым.

typedef std::vector<Node> level_nodes;
typedef std::vector<level_nodes> graph_nodes;

graph_nodes g;
r.reserve(1000000); // OK, just a few MB

// ...

g[12].insert(std::lower_bound(g[12].begin(), g[12].end(), x), x);

level_nodes().swap(g[11]); // kill level 11 and reclaim memory