2

我最近从头开始编写了我的第一个程序，但不是该领域的专业人士，我担心我可能没有使用最合适的解决方案。

在我的程序中，我必须使用对象列表（和列表列表），在其中不断添加和删除元素，不一定在列表的开头或结尾。
给出要求，使用指针列表不是一种选择。

当我开始时，我只知道这个std::vector类，因此我使用了它，尽管我知道它需要连续的内存，因此这种选择会导致重复的重新分配。
在尝试解决另一个问题时，我发现存在其他可能更适合此任务的类，例如std::list和std::deque。

我主要通过使用索引来访问对象

myvector[index].function();

我使用最多的标准功能是

myvector.size();
myvector.begin();
myvector.pop_back();
myvector.push_back();
myvector.insert(myvector.begin()+offset, number, new_element);

而且我没有重载任何函数/运算符。

您能否为我的范围推荐最佳容器/双向链表？是否可以与任何其他标准容器
无缝替代？ 有什么特别需要注意的问题吗？std::vector

4

2 回答 2

4

您能否为我的范围推荐最佳容器/双向链表？

如果通过索引访问元素，链表不是一个好的解决方案：你必须从头开始遍历列表，所以它是一个 O(N) 操作。出于这个原因，在他们的界面std::list中std::forward_list没有这样的访问权限。

是否可以用任何其他标准容器无缝替换 std::vector ？

不是std::list, 因为它不能通过索引访问。std::deque 可能是合适的，但前提是您不依赖于一个连续块中的基础数据（我假设您不依赖，因为您询问的是链表）

有什么特别需要注意的问题吗？

与性能一样，您首先应该确定您是否有问题。如果您对 有性能问题，请std::vector尝试其他方法，并在实际运行场景中测量性能差异。不同容器的性能特征可能非常反直觉，因此测量在这里特别重要。

相关链接：std::vector vs. std::list vs. std::deque 比较。Bjarne Stroustrup 的Going Native 2012 主题演讲。

于 2013-06-05T07:29:17.460 回答
2

Boost 提供了一种替代方案：boost::stable_vector。

Big O 复杂度对于所有操作都是完全相同的，但是在内部它不会对元素进行混洗，而是对指针进行混洗（以失去连续性为代价）。

对于每次访问的额外间接成本，stable_vector在两种情况下是一个不错的选择：

  • 你想为元素有一个稳定的地址，所以你可以保留一个引用/指针
  • 该元素的复制成本非常高，因此您希望保证无论您在做什么操作都不会发生复制

显然，后者应该通过指出问题的分析器来证实。

于 2013-06-05T08:04:34.143 回答