вектор списка. Должен ли я использовать указатели или значения?

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

Так как базовые данные Структура Мне нужно vector of lists.
выбор я из 2-х вариантах:

std::vector<std::list<entry> >
std::vector<std::list<entry>* >

где запись структура, которая содержит значения данных и хэш;

Вопрос: Будет ли это огромным снижением эффективности, если я использую первый вариант (вопрос рассматривается на больших входных данных)?

Заранее благодарю вас!

источник

2013-04-20 spin_eight

Вам нужно реализовать хеш-таблицу? В C++ 11 есть std :: unordered_set и std :: unordered_map (а также их «несколько» аналогов). –

Да, это для образовательной цели. –

Не используйте 'std :: list ', если вы не вставляете/удаляете элементы из середины списка порядка чаще, чем вы перебираете по нему, или если 'entry' не движется и дорого копируется, или дорогой для перемещения. 'std :: list' - это' std :: '" двунаправленный связанный список ", а не' std :: '" идеальный контейнер для использования, когда вам нужен список вещей ". – Yakk

Нет смысла использовать указатель, и это добавляет сложность необходимости удаления при уничтожении вектора. Идем дальше и используем vector<list<entry> >. list будет распределять память для элементов в любом случае, но он будет невидим для вас.

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

источник

2013-04-20 03:11:38

Я нашел очень полезную информацию в вашем ответе, что вектор контейнера STL выделяет память в куче для ее элементов. Эта информация заставила меня понять, что в случае эффективности будет небольшая разница в 2-х вариантах, а 2-я нагрузка потребует больше работы (выделение/освобождение памяти). Я буду выбирать 1-й. Большое спасибо! –

-1

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

источник

2013-04-20 02:53:40 legacybass

Этот ответ неверен. В обоих случаях все, кроме внутренних 'std :: vector', всегда будет выделено из свободного хранилища. – Mankarse

Когда я прочитал ответ Марка Рэнсом, я понял, что в обоих вариантах цепочки (списки) будут храниться в стеке из-за векторной реализации. –

@spin_eight: Нет. Std :: vector всегда выделяет его содержимое в свободном хранилище, и ничто в ответе Марка не предполагает иного. –

вектор списка. Должен ли я использовать указатели или значения?

ответ

Смежные вопросы