Каковы проблемы с вектором векторов?

Question

Я читал, что a vector -of- vector s является плохим с учетом фиксированного размера 2 ^и, но я не могу найти четкое объяснение проблем на http://www.stackoverflow.com.

Может кто-то дать объяснение, почему использование 2D индексации на одном vector предпочтительно используя vectorvector -of- с для фиксированного 2 ^я измерения?

Кроме того, я предполагая, что vectorvector -of- с предпочтительным является структура данных для 2D-массива с переменной 2-й измерение? Если есть какие-либо доказательства противного, я бы с удовольствием это увидел.

Answer 1

Я отвечу с простой аналогией.

Что такое «лучше» вообще из двух вещей?

1. телефонная книга, в которой каждая запись представляет собой код со ссылкой на другую книгу, которую вы должны найти и прочитать, чтобы обнаружить чей-то телефонный номер
2. телефонной книги, которая перечисляет человек номера телефонов

Keeping все ваши данные в одном большом блобе проще, понятнее и проще в кеше вашего компьютера. Вектор с N векторы внутри него гораздо более оперативно сложны (помните, что каждый из них требует динамических операций по распределению и управлению размером!); один вектор, ну, один вектор. Вы не умножили рабочую нагрузку на N.

Единственным недостатком является то, что для имитации доступа 2D-массива с 1D базовым хранилищем данных вам необходимо написать фасад. К счастью, это очень легко.

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

Answer 2

Используя вектор векторов:

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

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

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

Лучшее решение для всех - это, конечно, использовать нечто вроде библиотеки линейной алгебры (BLAS), доступной в Boost. Это прекрасно справляется с большими разреженными матрицами.

Answer 3

Для std::vector базовый массив динамически выделяется из кучи. Если у вас есть, например, std::vector<std::vector<double>>, то ваш внешний вектор будет выглядеть

{v1, v2, v3, v4, ... vn} 

Это выглядит как каждый из внутренних векторов будет в непрерывной памяти, и они будут, но их основные массивы не должны быть смежными. См. Схему расположения памяти в this post. Другими словами, вы не можете сказать, что

&(v1.back()) + 1 == &(v2.front()) // not necessarily true! 

Вместо если вы использовали один вектор с striding, то вы получили бы локальность данных, и было бы по своей сути более cache friendly, как все ваши данные смежный.

Для полноты картины, я хотел бы использовать ни из этих методов, если ваша матрица была редка, так как есть more elegant and efficient storage schemes, чем прямой 1D или 2D массивы. Хотя, поскольку вы упомянули, что у вас есть «фиксированное второе измерение», я предполагаю, что здесь не так.