1

我会给出一些关于我为什么要这样做的背景，但最终可以忽略背景，因为它主要是一个经典的计算机科学和 C++ 问题（之前肯定已经问过这个问题，但是有几个粗略的搜索什么都没出现……）

我正在使用（大型）实时流式点云，并且有一个案例我需要从多个传感器获取 2/3/4 点云并将它们粘在一起以创建一个大点云。我的情况是，我确实需要一个结构中的所有数据，而通常当人们只是将点云可视化时，他们可以将它们分别输入查看器中。

我使用的是 Point Cloud Library 1.6，仔细观察它的PointCloud 类（<pcl/point_cloud.h>如果你感兴趣的话）将所有数据点存储在一个 STL 向量中。

现在我们回到了香草 CS 领域......

PointCloud 有一个 += 运算符，用于将一个点云的内容添加到另一个点云。到目前为止，一切都很好。但是这种方法效率很低 - 如果我理解正确，它 1) 调整目标向量的大小，然后 2) 遍历另一个向量中的所有点，并将它们复制过来。

在我看来，这就像 O(n) 时间复杂度的情况，这通常可能不会太糟糕，但在实时处理每个云至少 300K 点时是个坏消息。

向量不需要排序或分析，它们只需要在内存级别“粘在一起”，所以程序知道一旦它到达第一个向量的末尾，它只需要跳转到起始位置第二个。换句话说，我正在寻找一种 O(1) 向量合并方法。在 STL 中有没有办法做到这一点？还是它更像是 std::list#splice 之类的领域？

注意：本课程是 PCL 的基础部分，因此“非侵入性手术”更为可取。如果需要对类本身进行更改（例如从向量更改为列表，或保留内存），则必须根据对 PCL 其余部分的连锁效应来考虑它们，这可能会影响深远。

更新：我已经在 PCL 的 GitHub 存储库中提交了一个问题，以便与库作者就以下建议进行讨论。一旦就采用哪种方法达成某种解决方案，我将接受相关建议作为答案。

4

7 回答 7

8

向量不是列表，它代表一个序列，但附加要求元素必须存储在连续的内存中。您不能在不移动对象的情况下将两个向量（其缓冲区不连续）捆绑到一个向量中。

于 2013-07-25T16:08:21.247 回答
6

这个问题之前已经解决过很多次了，比如使用 String Rope 类。

基本方法是创建一个新的容器类型来存储指向点云的指针。这就像一个 std::deque ，除了你的会有可变大小的块。除非你的云块成标准尺寸？

使用这个新容器，您的迭代器从第一个块开始，继续到最后，然后进入下一个块。在这种具有可变大小块的容器中进行随机访问需要二进制搜索。事实上，这样的数据结构可以写成 B+ 树的变形形式。

于 2013-07-25T16:08:05.297 回答
5

没有向量等效于 splice - 不可能，特别是因为内存布局要求，这可能是首先选择它的原因。

也没有固定时间的方法来连接向量。

我可以想到一种（脆弱的）方法来在恒定时间内连接原始数组，但这取决于它们在开始和结束时在页面边界上对齐，然后将它们重新映射为相邻。这将很难一概而论。

还有另一种方法可以制作看起来像级联向量的东西，那就是使用像双端队列一样工作的包装容器，并提供统一的迭代器和operator[]它们之上。不过，我不知道点云库是否足够灵活。（Jamin 的建议本质上是使用类似这样的东西而不是矢量，而 Zan 的建议大致是我的想法）。

于 2013-07-25T16:09:31.293 回答
3

不，您不能通过简单的链接连接两个向量，您实际上必须复制它们。

然而！如果您在元素类型中实现移动语义，您可能会获得显着的速度提升，具体取决于您的元素包含的内容。如果您的元素不包含任何重要的类型，这将无济于事。此外，如果您提前保留了所需的内存，那么这也有助于加快速度，因为不需要调整大小（这会导致不希望的巨大新分配，可能必须以该内存大小进行碎片整理，然后一个巨大的内存）。

除此之外，您可能希望在链表和向量之间创建某种混合，列表的每个“元素”都是具有 10k 个元素的向量，因此您只需要每 10k 个元素跳转一次列表链接，但它允许您可以更轻松地动态增长，并使您的连接变得轻而易举。

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.
于 2013-07-25T16:07:59.833 回答
2

您不会使用矢量获得这种缩放行为，因为使用矢量，您不会绕过复制。而且您不能在固定时间内复制任意数量的数据。

我不知道 PointCloud，但是如果您可以使用其他列表类型，例如链表，那么这种行为是很有可能的。您可能会发现一个在您的环境中工作的链表实现，并且可以简单地将第二个列表粘贴到第一个列表的末尾，就像您想象的那样。

于 2013-07-25T16:07:52.363 回答
1

在http://www.boost.org/doc/libs/1_54_0/libs/range/doc/html/range/reference/utilities/join.html上查看 Boost range 联合

这将需要 2 个范围并加入它们。假设你有vector1和vector 2。

你应该可以写

auto combined = join(vector1,vector2).

然后您可以根据需要与算法等结合使用。

于 2013-07-25T18:59:16.227 回答
0

永远没有向量的 O(1) 副本，但是，您应该检查：

  • 元素类型可以简单地复制吗？（又名memcpy）
  • IFF，我的vector实现是利用了这个事实，还是愚蠢地循环遍历所有 300k 元素，为每个元素执行一个简单的赋值（或更糟糕的是，copy-ctor-call）？

我所看到的是，虽然memcpy分配循环和分配循环都具有 O(n) 复杂性，但利用的解决方案memcpy可以快得多。

因此，问题可能在于向量实现对于普通类型来说不是最优的。

于 2013-07-26T09:00:02.990 回答