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

Question

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

1. Может кто-нибудь объяснить мыслительный процесс для выбора между 3 структурами данных, которые я упомянул?
2. Кроме того, векторы даже больше используются?Я слышал, что они устарели, но все еще вижу много недавних примеров.

Чтобы быть понятным, я имею в виду ALL подмножеств, поэтому они имеют разные размеры.

Answer 1

Решение о том, какую структуру данных использовать, зависит от:

• Тип данных для хранения
• Операции, которые вы собираетесь выполнять с данными

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

С std::vector вы получаете произвольный доступ к данным, причем смежный, как и массивы, но вектор - это динамический массив, он увеличивается по мере добавления новых элементов и амортизируется постоянной сложностью, однако вставка / удаление элементов происходит быстрее на концах, так как все элементы должны быть перемещены.

С std::list вы не получаете произвольный доступ, но вставка и удаление элементов происходит быстрее, поскольку для этого требуется просто перемещаться по ссылкам указателя.

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

Answer 2

Однажды я использовал битовые поля для определения подмножеств.Где, если i th бит равен 1, тогда i элемент в наборе выбирается в подмножестве, а 0 в противном случаеВ этом случае вам необходимо сохранить порядок элементов.То же самое можно сделать с bool векторами, я думаю.