abh*_*ity 3 c++ algorithm stl data-structures
我有以下场景.实时是应用程序的实现.
1)我需要在容器中存储最多20个条目(STL Map,STL List等).2)如果有新条目并且已经存在20个条目,则必须使用新条目覆盖最旧的条目.
考虑到第2点,我觉得如果容器已满(最多20个条目)'list'是最好的选择,因为我总是可以删除列表中的第一个条目并最后添加新条目(push_back).但是,搜索效率不高.
对于只有20个条目,如果我使用列表代替地图,它在搜索效率方面是否真的有很大差异？
另外考虑在地图中插入的费用我觉得我应该去列表？
你能告诉我什么是更好的选择吗？
1)我需要在容器中存储最多20个条目(STL Map,STL List等).2)如果有新条目并且已经存在20个条目,则必须使用新条目覆盖最旧的条目.
这对我来说似乎是boost :: circular_buffer的工作.
通常,术语循环缓冲区是指存储器中用于存储输入数据的区域.当缓冲区被填满时,从缓冲区的开头开始写入新数据并覆盖旧数据.
circular_buffer是符合STL的容器.它是一种类似于std :: list或std :: deque的序列.它支持随机访问迭代器,缓冲区开头或结尾的恒定时间插入和擦除操作以及与std算法的互操作性.circular_buffer专门用于提供固定容量存储.当其容量耗尽时,新插入的元素将导致在缓冲区的开头或结尾处的元素(取决于使用的插入操作)被覆盖.
circular_buffer 仅在创建时,显式调整容量时或在必要时分配内存以适应调整大小或分配操作.另一方面,还有一个circular_buffer_space_optimized可用.它是circular_buffer的一个适配器,它在创建时不会立即分配内存,而是根据需要分配内存.
对于快速搜索,我认为只有20个元素(如果它们的比较不是太复杂)你可以使用像这样的"低成本"容器和正常的线性搜索,在我看来很难实现其他STL容器的性能更佳.