Существует ли структура данных, которая не позволяет дубликаты и также поддерживает порядок записи?

A Boost.Bimap с порядком вставки в качестве индекса должен работать (например, boost :: bimap ). Если вы удаляете объекты из структуры данных, вам нужно будет отдельно отслеживать значение следующего порядка вставки.

Написание собственного класса, который переносит вектор и набор, может показаться очевидным решением - не существует стандартного контейнера библиотеки C ++, который бы делал то, что вы хотите.

Похоже на задание для OrderedDictionary .

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

Быстрая повторная проверка, по-видимому, является важной частью здесь. Я мог бы использовать какой-то тип карты / словаря и, возможно, сам отслеживать порядок вставки в качестве фактических данных. Таким образом, ключ - это «данные», в которые вы добавляете данные (которые затем хэшируются, и вы не разрешаете дублирование ключей), и в качестве «данных» укажите текущий размер карты. Конечно, это работает, только если у вас нет удалений. Если вам это нужно, просто добавьте внешнюю переменную, которую вы увеличиваете при каждой вставке, и относительный порядок сообщит вам, когда что-то было вставлено.

Не обязательно красиво, но не так сложно реализовать.

Предполагая, что вы говорите здесь ANSI C ++, я бы либо написал свой собственный, либо использовал состав и делегирование, чтобы обернуть карту для хранения данных и вектор ключей для порядка вставки. В зависимости от характеристик данных вы можете использовать индекс вставки в качестве ключа карты и избегать использования вектора.

Java имеет это в форме упорядоченного набора. Я не думаю, что C ++ имеет это, но это не так сложно реализовать самостоятельно. Ребята из Sun сделали с классом Java расширение хеш-таблицы таким образом, чтобы каждый элемент одновременно вставлялся в хеш-таблицу и хранился в двойном связанном списке. В этом есть очень мало накладных расходов, особенно если вы предварительно выделяете элементы, которые используются для создания связанного списка.

Если бы я был вами, я бы написал класс, который использовал бы частный вектор для хранения элементов или реализации Hashtable в классе самостоятельно. Когда какой-либо элемент должен быть вставлен в набор, проверьте, находится ли он в хеш-таблице, и при необходимости замените элемент там, если такой элемент есть в нем. Затем найдите старый элемент в хеш-таблице, обновите список, чтобы он указывал на новый элемент, и все готово.

Чтобы вставить новый элемент, вы делаете то же самое, за исключением того, что вы должны использовать новый элемент в списке - вы не можете повторно использовать старые.

Чтобы удалить элемент, вы переупорядочиваете список, чтобы указывать вокруг него. и освободите элемент списка.

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

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

Возможно, вы захотите взглянуть на алгоритм танцующих ссылок.

за исключением того, что вы должны использовать новый элемент в списке - вы не можете повторно использовать старые.

Чтобы удалить элемент, вы переупорядочиваете список, чтобы указать вокруг него, и освобождаете элемент списка.

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

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

Возможно, вы захотите взглянуть на алгоритм танцующих ссылок.

за исключением того, что вы должны использовать новый элемент в списке - вы не можете повторно использовать старые.

Чтобы удалить элемент, вы переупорядочиваете список, чтобы указать вокруг него, и освобождаете элемент списка.

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

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

Возможно, вы захотите взглянуть на алгоритм танцующих ссылок.

вы переупорядочиваете список так, чтобы он был вокруг него, и освобождаете элемент списка.

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

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

Возможно, вы захотите взглянуть на алгоритм танцующих ссылок.

вы переупорядочиваете список так, чтобы он был вокруг него, и освобождаете элемент списка.

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

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

Возможно, вы захотите взглянуть на алгоритм танцующих ссылок.

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

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

Возможно, вы захотите взглянуть на алгоритм танцующих ссылок.

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

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

Возможно, вы захотите взглянуть на алгоритм танцующих ссылок.