c++ - 更好的是，STL 列表或 20 个条目的 STL 映射，考虑到插入顺序与搜索速度一样重要

Question

我有以下场景。实时应用程序需要实现。

1)我需要在容器中存储最多 20 个条目(STL map 、STL 列表等)。2) 如果出现新条目并且已经存在 20 个条目，我必须用新条目覆盖最旧的条目。

考虑到第 2 点，我觉得如果容器已满(最多 20 个条目)“列表”是最好的选择，因为我总是可以删除列表中的第一个条目并最后添加新的条目 (push_back)。但是，搜索效率不高。

对于只有 20 个条目，如果我用列表代替 map ，在搜索效率方面真的会有很大的不同吗？

同时考虑到在 map 中插入的成本，我觉得我应该使用列表？

你能告诉我什么是更好的选择吗？

Answer 1

1)I need to store at max 20 entries in a container(STL Map, STL List etc). 2)If a new entry comes and 20 entries are already present i have to overwrite the oldest entry with the new entry.

这对我来说似乎是 boost::circular_buffer 的工作.

In general the term circular buffer refers to an area in memory which is used to store incoming data. When the buffer is filled, new data is written starting at the beginning of the buffer and overwriting the old.

The circular_buffer is a STL compliant container. It is a kind of sequence similar to std::list or std::deque. It supports random access iterators, constant time insert and erase operations at the beginning or the end of the buffer and interoperability with std algorithms. The circular_buffer is especially designed to provide fixed capacity storage. When its capacity is exhausted, newly inserted elements will cause elements either at the beginning or end of the buffer (depending on what insert operation is used) to be overwritten.

The circular_buffer only allocates memory when created, when the capacity is adjusted explicitly, or as necessary to accommodate resizing or assign operations. On the other hand, there is also a circular_buffer_space_optimized available. It is an adaptor of the circular_buffer which does not allocate memory at once when created, rather it allocates memory as needed.

对于快速搜索，我认为只有 20 个元素(如果它们的比较不是太复杂的话)你可以使用像这样的“低成本”容器和正常的线性搜索，在我看来它会是使用其他 STL 容器很难获得更好的性能。