当列表/数组中的元素数量可变时，哪种结构最适合实现？

Question

我有一个稍微具体的问题。我正在使用 C/C++ 和 OpenCV。我的目标是将检测到的矩形存储在列表/数组样式结构中。但是，每个帧（迭代）的长度都是可变的。

我应该用什么来存储这些信息？我想到了链表，但是它们的遍历速度很慢，而且如果节点数量减少，我将不得不手动删除额外的节点，这会占用更多的处理器时间。我放弃了数组，因为它们的长度不太灵活。我可以使用 malloc 执行动态数组，但即使如此，我认为我仍需要指定最大元素数。

如果我有什么地方错了，请随时纠正我。另外，请分享您的观点，并让我知道您认为解决此问题的最佳方法是什么？

谢谢

编辑：我不限于C（我知道我提到了malloc）。我可以使用 C++ 功能，并且我的程序的其余部分不使用任何 C 特定功能。所以请随时向我建议任何更好的方法。

Answer 1

我建议您使用std::vector。 C++ 标准保证 std::vector 中的元素是连续的，就像 C 数组一样。这使得 std::vector 成为 C++ 数据结构和 C 函数之间的接口。您可以使用 std::vector::resize 确保在将空间传递给 OpenCV 函数之前已分配空间。

哦，要获取指向向量内部存储的指针，通常使用以下表示法：&rectangleCollection[0]。

祝你好运！

Answer 2

您可以使用动态数组并在需要增长时使用realloc()。如果可能：

• 由于您的初始数组（也许）是您期望的平均长度
• 使用指数增长，因此当您重新分配数组时，分配的大小会加倍

当然，您也可以做一些更复杂的事情，但我建议首先使用普通的重新分配数组进行测试。

Answer 3

通常，您将释放最大大小的现有数组，然后分配一个更大大小的新数组，并将原始指针分配给新数组。另外，如果您知道将来可能需要更多空间，则没有必要或理由仅仅因为没有填充数组而缩小数组大小。不断调整数据结构的大小以使其完全适合其中的数据是对性能的浪费。

编辑：哦，所以你实际上正在使用 C++。在这种情况下，只需获取一个向量即可。

Answer 4

如果您因为向量的灵活性而想要使用向量，但仅限于 C，则可以使用结构和支持函数轻松复制它们的行为。以下是 C 向量的示例定义：

struct cvector {
  rectangle** array_;
  int size_;
  int allocation_;
};

array_ 将保存指向矩形的指针的内部数组，size_ 将保存向量内有效矩形的总数，分配是当前为 array_ 分配的空间量。您可能会编写一些辅助函数的示例声明来处理此问题：

int cvector_push_back(rectangle* rec);
rectangle* cvector_access(int index);
cvector* cvector_create();
int cvector_free(cvector* cv);

如果您在访问接口时坚持使用接口，那么您应该能够获得与向量相同的功能，而无需做太多工作。

Answer 5

答案取决于：

通常我会推荐 DirectX SDK 中的 CGrowableArray。
（您不需要包含 DirectX，只需删除该类模板即可）
（如果你不想使用 C++ 类模板，你可以轻松地实现与一堆 C 函数相同的逻辑）

它比 std::vector 有什么好处？

a) 它使用启发式方法提前分配对象

b) 您可以 Reset() 它，这只会销毁所包含的对象，但不会释放内存。

每一帧你都会 Reset() 数组，然后愉快地添加你的对象。
您只需为 ctor/dtor 调用付费，但（大多数时候）无需为 alloc/free 调用付费。

---

另一方面，如果您不打算存储实际对象而是指针，那么侵入式链表是理想的选择。在这种情况下，“Append”（2 个分配）和“Clear”（1 个分配）都是微不足道的，并且不涉及任何分配。 “删除”是一个不同的故事，但鉴于您的问题陈述，您似乎不需要这样做。