Объедините 2 вектора STL за постоянное время O (1)

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

Эта проблема решалась много раз раньше, например, с классами String Rope.

Базовый подход - создать новый тип контейнера, в котором будут храниться указатели на облака точек. Это похоже на std :: deque, за исключением того, что у вас будут куски переменного размера. Разве ваши облака разбиваются на стандартные размеры?

С этим новым контейнером ваши итераторы начинают с первого фрагмента, переходят до конца, а затем переходят к следующему фрагменту. Выполнение произвольного доступа в таком контейнере с кусками переменного размера требует двоичного поиска. Фактически, такую ​​структуру данных можно было бы записать как искаженную форму дерева B +.

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

Также нет способа конкатенации векторов с постоянным временем.

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

Есть другой способ сделать что-то, что похоже на конкатенированный вектор, и это с помощью контейнера-оболочки, который работает как двухсторонняя очередь и предоставляет унифицированный итератор и operator[] над ними. Однако я не знаю, достаточно ли гибкая библиотека облаков точек для работы с этим. (Предложение Джамина состоит в том, чтобы использовать что-то вроде этого вместо вектора, а Zan примерно то, что я имел в виду).

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

Тем не мение! Если вы реализуете семантику перемещения в своем типе элемента, вы, вероятно, получите значительный прирост скорости в зависимости от того, что содержит ваш элемент. Это не поможет, если ваши элементы не содержат нетривиальных типов. Кроме того, если у вас есть резервный вектор заранее необходимой памяти, это также поможет ускорить процесс, не требуя изменения размера (что приведет к нежелательному огромному новому распределению, возможно, к необходимости дефрагментации при этом размере памяти, а затем огромный memcpy).

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

std::list<std::vector<element>> forIllustrationOnly; //Just roll your own custom type.

index = 52403;

listIndex = index % 1000
vectorIndex = index / 1000

forIllustrationOnly[listIndex][vectorIndex] = still fairly fast lookups
forIllustrationOnly[listIndex].push_back(vector-of-points) = much faster appending and removing of blocks of points.

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

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

Взгляните на соединение диапазона Boost по адресу http://www.boost.org/doc/libs/1_54_0/libs/range/doc/html/range/reference/utilities/join.html

Это займет 2 диапазона и присоединится к ним. Скажем, у вас есть vector1 и vector 2.

Вы должны уметь писать

auto combined = join(vector1,vector2).

Затем вы можете использовать в сочетании с алгоритмами и т. Д. По мере необходимости.

Никакой копии O (1) для вектора никогда, но вы должны проверить:

• Тип элемента легко копируется? (он же memcpy)
• Мф, моя реализация vector использует этот факт, или она тупо перебирает все 300 тыс. Элементов, выполняя тривиальное присваивание (или, что еще хуже, вызов copy-ctor) для каждого элемента?

Я заметил, что, хотя и memcpy, и назначение цикла имеют сложность O (n), решение, использующее memcpy, может быть намного, намного быстрее.

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