Ведение упорядоченной коллекции объектов

Question

я следующие требования к коллекции объектов:

• Динамического размера (теоретически неограничен, но на практике несколько тысяч должна быть более чем достаточно)
• нумерованной , но разрешая переупорядочивание и вставку в произвольных местах.
• Позволяет для удаления
• индексированного Access - случайного доступ
• Граф

Объекты Я хранящие не большие, несколько свойств и небольшой массив или два (256 булевых)

Есть ли какие-либо встроенные классы, о которых я должен знать, прежде чем я напишу связанный список?

Answer 1

Оригинальный ответ: Это звучит как std::list (двойной список) из стандартной библиотеки.

Новый ответ: После вашего изменения в спецификации, std::vector может работать до тех пор, пока не более чем несколько тысяч элементов, а не огромное количество вставок и делеций в середине вектора. Линейная сложность вставки и удаления в середине может быть перевешена небольшими константами векторных операций. Если вы делаете много вложений и удалений только в начале и конце, может работать std::deque.

Answer 2

Вы не указали достаточно своих требований, чтобы выбрать лучший контейнер.

Динамический размер (теоретически неограниченной, но на практике несколько тысяч должно быть более чем достаточно)

STL контейнеры предназначены для расти по мере необходимости.

Упорядочено, но разрешает переупорядочивание и установку в произвольных местах.

Разрешение на изменение порядка? Невозможно переупорядочить std :: map: вы можете удалить с одной std :: map и вставить в другую с помощью другого порядка, но в качестве разных экземпляров шаблона две переменные будут иметь разные типы. У std :: list есть функция sort() [спасибо Blastfurnace за указание этого], особенно эффективный для больших объектов. Std :: vector можно легко использовать с помощью функции non-member std::sort(), особенно эффективной для крошечных объектов.

Эффективная вставка в произвольных местах может быть выполнена на карте или в списке, но как вы найдете эти местоположения? В списке поиск является линейным (вы должны начинать с того, что уже знаете, и отсканировать вперед или назад элемент по элементу). std :: map обеспечивает эффективный поиск, как и уже отсортированный вектор, но вставка в вектор включает в себя перемещение (копирование) всех последующих элементов для создания пространства: это дорогостоящая операция в схеме вещей.

Позволяет для удаления

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

индексированные доступа - Random Access

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

Граф

std::list обеспечивает O (N) size() функцию (так что она может обеспечить O (1) сплайсинга), но вы можете легко отслеживать размер самостоятельно (если вы не склеить). Другие контейнеры STL уже имеют O (1) раз для size().

Выводы

Рассмотрят ли с помощью зОго :: список приводит к большому количеству неэффективных линейных поисков элемента вам необходимо. Если нет, то список дает вам эффективную вставку и удаление. Курорт - это хорошо.

карты или хэш-карта позволит быстрому поиску и простую вставке/удаление, не может быть прибег, но вы можете легко перенести данные к другой карте с другими критериями сортировки (с умеренной эффективностью.

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

Answer 3

-Исследование и удаление: это возможно для любого контейнера STL, но вопрос сколько времени требуется для этого. Любой контейнер с указанным списком (список, карта, набор) будет делать это в постоянное время, в то время как контейнеры (вектор), подобные массиву, будут делать это в линейном времени (с распределением с постоянной амортизацией).

-Сортинг: учитывая, что вы можете хранить отсортированную коллекцию в любое время, это не проблема, любой контейнер STL позволит это. Для карт и множеств вам не нужно ничего делать, они уже заботятся о том, чтобы сортировка всегда сортировалась. Для вектора или списка вам нужно выполнить эту работу, т. Е. Вам нужно выполнить двоичный поиск для места, где идут новые элементы, и вставить их туда (но для алгоритмов STL есть все необходимые для этого элементы).

-Resorting: Если вам нужно взять текущую коллекцию, которую вы отсортировали в соответствии с правилом A, и прибегнуть к коллекции в отношении правила B, это может быть проблемой. Контейнеры, такие как map и set, параметризуются (как тип) по правилу сортировки, это означает, что для его использования вам нужно будет извлечь каждый элемент из исходной коллекции и вставить их в новую коллекцию с новым правилом сортировки. Однако, если вы используете векторный контейнер, вы можете просто использовать функцию сортировки STL в любое время, чтобы прибегнуть к любому правилу, которое вам нравится.

-Random Access: Вы сказали, что вам нужен произвольный доступ. Лично мое определение случайного доступа означает, что любой элемент в коллекции может быть доступен (по индексу) в постоянное время.С этим определением (которое я считаю вполне стандартным) любая реализация связанных списков не квалифицируется, и она оставляет вам единственную возможность использования контейнера типа типа (например, std :: vector).

Заключение, чтобы иметь все эти свойства, вероятно, было бы лучше всего использовать вектор std :: и реализовать собственную сортированную вставку и сортировку удаления (выполнение двоичного поиска в векторе, чтобы найти элемент для удаления, или место для вставьте новый элемент). Если ваши объекты, которые вам нужно хранить, имеют значительный размер, а данные, в соответствии с которыми они отсортированы (имя, идентификатор и т. Д.), Невелики, вы можете рассмотреть вопрос о разделении проблемы, удерживая несортированный связанный список объектов (с полная информация) и сохранение сортированного вектора ключей вместе с указателем на соответствующий узел в связанном списке (в этом случае, конечно, используйте std :: list для первого и std :: vector для последнего).

Кстати, я не великий эксперт с контейнерами STL, поэтому, возможно, я ошибся в вышеупомянутом, просто подумайте о себе. Исследуйте STL для себя, я уверен, вы найдете то, что вам нужно, или, по крайней мере, все части, которые вам нужны. Возможно, посмотрите также на библиотеки Boost.