что лучше вообще, карта или вектор в с ++?

Question

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

Поэтому я хочу спросить, какой из них лучше вообще? Я рассматриваю возможность использования одного из этих двух элементов в моей программе, которая содержит около 1000 элементов. Я планирую использовать 3-мерный вектор, который будет принимать 1000x1000x1000 элементов.

Answer 1

Нет правильного ответа на этот вопрос. Правильный вопрос должен звучать так: «что лучше для конкретного приложения - вставьте свой проект здесь». Чтобы выбрать правильный контейнер, вам нужно объяснить, как он будет использоваться.

Answer 2

Карта является ассоциативным контейнером - она ​​выполняет функцию, совершенно отличную от вектора. Используйте карту, если вы хотите связать ключи со значениями. Если ваши ключи являются просто неотрицательными последовательными целыми числами, то вектор превосходит во всех отношениях.

Answer 3

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

Answer 4

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

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

Однако во многих случаях вам захочется получить доступ к вашим данным другим способом. Например, если вы хотите проиндексировать свои данные, используя строку (например, поиск по словарю), тогда карта будет работать лучше. Чтобы индексировать данные строкой, используя вектор, вам нужно будет выполнить линейный поиск (O (n)), чтобы найти элемент, если вы не сохраняете вектор отсортированным. Карта должна была бы только выполнить двоичный поиск (O (log n)), который был бы МНОЖЕ быстрее при увеличении n.

Answer 5

В общем, лучше не бывает. Все зависит от операций, которые вы собираетесь выполнять, и от частоты этих операций.

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

Answer 6

Если у вас есть разреженный трехмерный массив, вы можете сэкономить много памяти, используя карту с ключом в качестве комбинации индексов. Для вашего случая с индексами <1000 ключ может быть 32-разрядным целым числом без знака: </p>

#include <stdint.h>
...
int index1 = 12, index2 = 34, index3 = 56;

// construct key:
uint32_t key = 
  ((index1&0x3FF) << 20) | 
  ((index2&0x3FF) << 10) | 
  (index3&0x3FF)
  );

// restore indexes:
index1 = (key >> 20) & 0x3FF;
index2 = (key >> 10) & 0x3FF;
index3 = (key) & 0x3FF;

Answer 7

Откровенно смешно предположить, что вы создали 1 000 000 000 пустых объектов для хранения только 1000 полезных. Если вы думаете, что вектор будет быстрее, вы, вероятно, совершенно не правы, если учесть, что будет происходить переполнение файла подкачки, динамическое распределение памяти и создание ненужных объектов!

Описание вашего приложения, вероятно, слишком расплывчато; но если значение может быть проиндексировано с помощью x, y, z; затем используйте объект, содержащий x, y, z в качестве ключа карты. Это не займет много времени, чтобы найти только 1000 объектов - это очень маленькая карта.

Answer 8

Я считаю vector<> лучшим выбором контейнера по умолчанию (кроме vector<bool>). Если у меня есть причина предпочесть другой контейнер, я использую другой; если нет, я использую vector<> (или deque<bool>). Это как можно ближе к «лучше в целом».

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

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

Answer 9

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

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

Answer 10

Deque - более подходящая замена для вектора, чем карта.Но это зависит от ваших потребностей.Вектор требует линейной памяти для всех своих данных, но deque не делает.А деку в большинстве случаев можно использовать как замену вектора.