вектор указателей или структур?

Question

Скажем, я определяю структуру (или класс, неважно) с именем Node. В C ++ мы можем использовать вектор структур или вектор указателей для хранения множества Node s.

struct Node {...}
void main() {
    std::vector<Node> nodes;
    // or we can write:
    std::vector<Node*> nodes;
}

Насколько я узнал, если я использую вектор структур, то вектор нужен большой объем памяти для хранения каждой структуры внутри вектора. Так что я думаю, что вектор указателей лучше. Но теперь я думаю, есть ли какая-то грамматика, которую я не знаю, или какой-нибудь обходной метод для записи vector<Node>, не копируя каждую структуру внутри вектора? Или еще лучше, может быть, компилятор уже делает эту оптимизацию за меня?

Answer 1

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

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

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

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

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

В некоторых других ответах упоминаются перемещения. Однако это не так плохо, как может показаться на первый взгляд. Прежде всего, перемещения через push_back гарантированно имеют амортизированную постоянную сложность. И есть несколько простых способов еще больше смягчить их, например предварительное бронирование. Если перераспределение действительно является проблемой - определяемой с помощью профилирования - тогда лучшей альтернативой может быть std::list.

Есть несколько допустимых применений для вектора указателей, например, необходимость хранить объекты polymorphi c. А если вы используете указатели, используйте интеллектуальные указатели.