当我们需要存储"最后n个项目"时,列表是否比矢量更好？
Kai*_*zay 43 c++ buffering fifo data-stream c++11
有很多问题表明应该总是使用向量,但在我看来,列表对于场景更好,我们需要存储"最后n个项目"
例如,假设我们需要存储最后看到的5个项目:迭代0:
3,24,51,62,37,
然后在每次迭代时,删除索引0处的项目,并在末尾添加新项目:
迭代1:
24,51,62,37,8
迭代2:
51,62,37,8,12
似乎对于这个用例,对于向量,复杂度将是O(n),因为我们必须复制n个项目,但是在列表中,它应该是O(1),因为我们总是只是砍掉了头部,并在每次迭代时添加到尾部.
我的理解是否正确？这是std :: list的实际行为吗？
Tae*_*myr 95
都不是.您的系列有固定的尺寸,std::array足够了.
您实现的数据结构称为环形缓冲区.要实现它,您需要创建一个数组并跟踪当前第一个元素的偏移量.
当您添加一个将项目推出缓冲区的元素时 - 即当您删除第一个元素时 - 您会增加偏移量.
要获取缓冲区中的元素,可以添加索引和偏移量,并获取此模数和缓冲区的长度.
- +1循环缓冲区是一个完全理想的实现,用于具有固定最大大小的队列(遗憾的是,没有标准的库容器). (20认同)
- @KaizerSozay:使用`boost :: circular_buffer`. (8认同)
- 虽然我自己可以实现一个,但我认为如果包含一个简单的实现,这个答案对其他人会更有用. (3认同)
Dav*_*ett 33
std :: deque是一个更好的选择.或者,如果您对std :: deque进行了基准测试并发现其性能不适合您的特定用途,则可以在固定大小的数组中实现循环缓冲区,并存储缓冲区起始的索引.替换缓冲区中的元素时,将覆盖起始索引处的元素,然后将起始索引设置为其先前的值加上缓冲区大小的模数.
列表遍历非常慢,因为列表元素可以分散在整个内存中,并且向量移位实际上非常快,因为即使存在大块,内存在单个内存块上移动也非常快.
讲座驯服野兽性能从会议C++ 2015年会议可能是你的兴趣.
- [参考地点](https://en.wikipedia.org/wiki/Locality_of_reference).数组(以及矢量)有它; 链表没有.当您访问数组中的元素时,相邻元素会随之被拉入CPU缓存,因此可以更快地访问它们.链接列表更有可能导致缓存未命中. (3认同)
- 是的,`std :: deque`使用数组 - 虽然不止一个.引用[cppreference](http://en.cppreference.com/w/cpp/container/deque):"与`std :: vector`相反,双端队列的元素不是连续存储的:典型的实现使用序列单独分配的固定大小数组".这比将每个单独的项目分别分配到不同的地方要好得多. (3认同)
- @KaizerSozay你最好用不同的结构进行一些性能测试.我个人认为*vector*会赢得这样的东西. (2认同)
man*_*lio 25
如果你可以使用Boost,试试boost :: circular_buffer:
这是一种类似于std::list或的序列std::deque.它支持随机访问迭代器,缓冲区开头或结尾的恒定时间插入和擦除操作以及与std算法的互操作性.
它提供固定容量存储:当缓冲区被填满时,从缓冲区的开头开始写入新数据并覆盖旧数据
// Create a circular buffer with a capacity for 5 integers.
boost::circular_buffer<int> cb(5);
// Insert elements into the buffer.
cb.push_back(3);
cb.push_back(24);
cb.push_back(51);
cb.push_back(62);
cb.push_back(37);
int a = cb[0]; // a == 3
int b = cb[1]; // b == 24
int c = cb[2]; // c == 51
// The buffer is full now, so pushing subsequent
// elements will overwrite the front-most elements.
cb.push_back(8); // overwrite 3 with 8
cb.push_back(12); // overwrite 24 with 12
// The buffer now contains 51, 62, 37, 8, 12.
// Elements can be popped from either the front or the back.
cb.pop_back(); // 12 is removed
cb.pop_front(); // 51 is removed
所述circular_buffer存储其在存储器的连续区域,其然后能快速元件常数时间插入,删除和元件的随机接入.
PS ......或者按照Taemyr的建议直接实现循环缓冲.
Overload Journal#50 - 2002年8月有一个很好的介绍(由Pete Goodliffe编写)来编写强大的STL类循环缓冲区.
- `然后它可以实现快速恒定时间插入,元素移除`只在任何一端,否则它是线性的. (2认同)
问题是O(n)只讨论渐近行为,因为n倾向于无穷大.如果n很小,则所涉及的常数因子变得显着.结果是,对于"最后5个整数项目",如果向量没有击败列表,我会被震惊.我甚std::vector至希望能够击败std::deque.
对于"最后500个整数项目",我仍然期望std::vector比std::list- 更快- 但std::deque现在可能会获胜.对于"最后500万个缓慢复制的项目",std:vector将是最慢的.
在环形缓冲区基于std::array或std::vector将可能更快还在虽然.
(几乎)始终存在性能问题:
- 用固定的接口封装
- 编写可以实现该接口的最简单的代码
- 如果分析显示您有问题,则优化(这将使代码更复杂).
在实践中,只要使用一个std::deque或预先构建的环形缓冲区(如果有的话),就足够了.(但是除非分析说你需要,否则不值得编写环形缓冲区.)