什么数据结构适合使用？

Question

3

我正在寻找适合这种情况的数据结构。我可以使用boost。

原来的代码是用C#写的，我在那里使用了一个队列，但我认为那不是一个合适的选择，而且据我所知，在C++中没有与C#的队列相当的东西。以下是我考虑的属性：

- 需要快速迭代 - 需要能够快速推进结构（即当我从顶部取出一个元素时，下一个元素应该是结构头） - 偶尔会被清空然后完全重新填充 - 偶尔会被复制 - 不需要排序，因为元素将按正确的顺序添加

元素数量将在创建时确定，并且将是50到200个元素。该结构永远不会容纳超过这个数量，但偶尔可能容纳更少。

我考虑使用std::list，但由于需要偶尔清除并重新填充，这似乎不是一个好选择。当我创建一个固定大小的列表，然后清除它时，它会失去预设大小，对吗？有什么办法可以始终保持列表大小，以便它不必分配/释放内存？

我知道boost有一个队列数据结构，但它不能迭代，我不确定它是否会和std::list一样有问题。

如何将std::list适应我的问题或更合适的数据结构的一些建议将是有帮助的。

- Megatron

2

快速迭代是什么意思？你有基准吗？ - Sam Miller

3个回答

2

听起来循环缓冲区应该可以工作？在boost库中有一个：boost::circular_buffer。

- eevar

Boost中有一个循环列表，但STL中没有。 - greyfade

-3

根据eevar的建议，环形缓冲区（实现为静态数组Foo buffer [200]和两个计数器）是最好的选择。不需要STL/Boost。

- John

3

“不需要STL/Boost”为什么你会像这是一件好事或者值得注意的事情一样说呢？ - ildjarn

因为增加没有实际价值的复杂性是不好的。 - John

5

重写已经被很好地记录、维护和支持的东西，会增加复杂性。您可以将精力集中在使用现有实现上，以便更有效地解决问题。 - ildjarn

对于这样一个简单的数据结构，我可能会在比OP写问题所需的时间更短的时间内实现它。而最接近STL等效（就性能而言）的是使用自定义分配器的std::deque，这比简单数组要复杂得多。 - John

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- johnsyweb · Accepted Answer

std::deque 看起来符合您的所有要求。

如果性能对您来说真的很重要，您应该阅读 GMan's answer 来了解预分配 C++ STL 队列的空间。