Простой и эффективный контейнер на C ++ с характеристиками карт и списков контейнеров

Question

Я ищу контейнер C ++, который будет пользоваться преимуществами как контейнера карт, так и списка контейнеров.

карта преимущества контейнера, которые я бы хотел сохранить:

• O (log (n)) доступ
• оператор [] простота использования
• редкая природа

список преимущества контейнера, которые я хотел бы сохранить:

• при заказе между предметами
• возможность легко просматривать список ОБНОВЛЕНИЕ: по порядку сортировки по ключу или значению

Простым примером приложения было бы хранение списка определенных действительных дат (рабочих дат, праздников, некоторого другого набора важных дат ...), если задана определенная дата, вы можете сразу найти ее «стиль карты» и затем найдите следующую действительную дату "список стилей".

Answer 1

std::map уже отсортированный контейнер, в котором вы можете перебирать содержащиеся элементы по порядку.Это только обеспечивает доступ O (log (n)), хотя.

std::tr1::unordered_map (или std::unordered_map в C ++ 0x) имеет доступ O (1), но не отсортирован.

Вам действительно нужен O (1) доступ?Вы должны использовать большие наборы данных и делать много поисков для O (log (n)) не достаточно быстро.

Если O (log (n)) достаточно, std::map обеспечиваетвсе, что вы просите.

Answer 2

Если вы не учитываете редкость, вы можете взглянуть на Boost Multi-Index библиотеку . Для редкости вы можете взглянуть на библиотеку Boost Flyweight , но я думаю, вам придется объединить оба подхода самостоятельно. Обратите внимание, что ваши требования часто противоречивы и их трудно достичь. Например, O (1) и порядок между элементами трудно эффективно поддерживать.

Answer 3

Согласно Страуструпу, оператор [] для карт - это O (log (n)). Это намного лучше, чем O (n), которое вы получили бы, если бы попробовали сделать такую ​​вещь со списком, но это определенно не O (1) . Единственный контейнер, который дает вам это для оператора [] - это вектор.

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

Answer 4

Карты обычно реализованы в виде деревьев и, таким образом, имеют время поиска логарифмически, а не O (1), но звучит так, как будто вы хотите отсортированный ассоциативный контейнер. Хэш-карты имеют O (1) лучший случай, O (N) худший случай, так что, возможно, это то, что вы имеете в виду, но они не отсортированы, и я не думаю, что они являются частью стандартной библиотеки.

В стандартной библиотеке C ++ map, set, multimap и multiset являются отсортированными ассоциативными контейнерами, но вы должны отказаться от требования поиска O (1).

Answer 5

Вы можете хранить данные в списке и иметь карту для итераторов вашего списка, позволяющую вам найти сам фактический элемент списка.Подобные вещи я часто использую для контейнеров LRU, где мне нужен список, потому что мне нужно переместить элемент, к которому осуществляется доступ, в конец, чтобы сделать его доступным последним.Вы можете использовать функцию splice для этого, и, начиная со стандарта 2003, она не делает итератор недействительным, если вы храните его в том же списке.

Answer 6

• при заказе между элементами
• возможность легко просматривать список

Карты уже делают оба. Они отсортированы, поэтому вы начинаете с begin () и перемещаетесь до конца (). Конечно, вы можете начать с любого итератора карты; Вы можете найти полезными методы find, lower_bound и связанные с ними методы.

Answer 7

Как насчет этого: все даты хранятся в std::list<Date>, но вы просматриваете его с помощью вспомогательной структуры stdext::hash_map<Date, std::list<Date>::iterator>Если у вас есть итератор для списка, доступ к следующему элементу становится простым.В вашей реализации STL это может быть std::tr1::unordered_map вместо stdext::hash_map, а также boost::unordered_map.

Answer 8

Вы никогда не найдете контейнер, который удовлетворяет как O(log n) доступ, так и упорядоченный характер. Причина в том, что если контейнер заказан, то по своей сути он должен поддерживать произвольный порядок. Вот что означает упорядоченная природа: вы сами решаете, где именно расположен какой-либо элемент. Таким образом, чтобы найти любой элемент, вы должны угадать, где он находится. Это может быть где угодно, потому что вы можете разместить его где угодно!

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