考虑到插入顺序与搜索速度同样重要，20 个条目的 STL 列表或 STL Map 哪个更好
我有以下场景。实时应用程序需要实现。
1）我需要在容器中存储最多 20 个条目（STL Map、STL List 等）。 2）如果有新条目出现并且已经存在 20 个条目，我必须用新条目覆盖最旧的条目。
考虑到第 2 点，我觉得如果容器已满（最多 20 个条目），“列表”是最好的选择，因为我始终可以删除列表中的第一个条目并最后添加新条目（push_back）。但是，搜索不会那么有效。
只有20条条目，如果我用列表代替地图，搜索效率真的有很大区别吗？
还考虑到在地图中插入的成本，我觉得我应该选择一个列表？
您能告诉我什么是更好的选择吗？
I have the following scenario.The implementation is required for a real time application.
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.
Considering point 2, i feel if the container is full (Max 20 entries) 'list' is the best bet as i can always remove the first entry in the list and add the new one at last (push_back). However, search won't be as efficient.
For only 20 entries, does it really make a big difference in terms of searching efficiency if i use a list in place of a map?
Also considering the cost of insertion in map i feel i should go for a list?
Could you please tell what is a better bet for me ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
在我看来，这似乎是 boost::circular_buffer< 的工作/a>.
对于快速搜索，我认为只有 20 个元素（如果它们的比较不是太复杂）就可以使用像这样的“低成本”容器和普通的线性搜索，在我看来，这将很难实现与其他 STL 容器相比具有更好的性能。
This seems to me the job for boost::circular_buffer.
For the fast search, I think that with just 20 elements (if their comparison isn't too complicated) you're ok with a "low-cost" container like this and normal linear search, in my opinion it would be difficult to achieve better performance with other STL containers.
保持插入顺序，或允许快速搜索：选择其中之一。
std::map在这里不是一个选项，因为它不维护插入顺序。此外，它是一个关联容器。您应该在list、deque和vector之间进行选择。就性能而言，您最好的选择是列表，因为您可以从后面弹出一个元素并在前面插入一个新元素（反之亦然），而不会造成任何移位或性能损失。顺便说一句，在
map中插入的成本并不昂贵：大约为 O(log n)。对于 20 个元素来说几乎不相关。这同样适用于std::set。Maintain order of insertion, or allow fast searching: choose one.
std::mapis not an option here because it doesn't maintain the order of insertion. Besides, it's an associative container. You should choose between alist, adequeand avector. In terms of performance your best bet is alist, since you can pop off an element from the back and insert a new one at the front (or vice-versa) without any shifting or performance penalty.The cost of insertion in a
map, just as a sidenote, isn't expensive it all: it's in the order of O(log n). Practically irrelevant in the case of 20 elements. The same holds for astd::set.由于只有 20 个元素，我不会太担心您使用哪个容器。如果您确定所选的容器实际上会损害应用程序的性能，那么稍后更换所选的容器并用更高效的容器替换它应该相对容易。
话虽如此，对于大量元素， std::deque 可能会为您想要完成的任务提供最佳的全面效率。与 std::vector 不同，std::deque 允许从前面删除，而无需移动所有其他元素。与 std::list 不同，std::deque 允许随机访问其元素。
With only 20 elements, I would not worry much about which container you use. If you determine that the container chosen is in fact a detriment to the performance of your application, it should be relatively easy to swap out the container chosen and replace it with a more-efficient container later.
With that being said, for a large number of elements, the std::deque would probably give you the best all-around efficiency for what you are trying to accomplish. Unlike std::vector, std::deque allows for removal from the front without needing to move all of the other elements. Unlike std::list, std::deque allows for random access of its elements.
您只需要实现一个优先级队列。 STL 地图不起作用。
You just need to implement a priority queue. STL Map doesn't work.
这取决于元素的大小。
根据我自己的经验，我知道对于五个整数，使用线性搜索搜索的无序整数数组更快比有序集合、列表或插入排序和二分搜索更快。大批。
无序数组的 O() 表示法可能比任何其他选项都要差得多，但 O(N+C) + C 中通常看不见的 C 却要小得多。
列表、集合或映射（任何使用动态内存并通过指针链接的东西）将主要受到缓存未命中、内存分配和间接引用惩罚的影响。
It depends on the size of the elements.
I know from my own experience that for five integers an unordered array of integers searched with linear search is faster than a set, a list or insertion sort and binary search on an ordered array.
The O() notation of an unordered array may be much worse than any of the other options but the normally unseen C in O(N+C) + C is so much smaller.
A list, set or map (anything that uses dynamic memory and is linked by pointers) will be dominated by cache misses, memory allocations and indirect reference penalties.
您需要在阵列上实现优先级队列。
有关实现，请参阅二进制堆。
You need a Priority Queue implemented on an array.
See the Binary Heap for an implementation.
您已经知道这是一个瓶颈吗？
我的建议是首先使用在编程时更容易阅读的内容，并且仅在发现性能不是您需要的时候才优化它。
Do you already know that this is a bottleneck?
My advice would be to first use what is more natural to read while programming and only optimize it when you see that the performance is not what you need.
我的建议是制作一个循环缓冲区。但只有当“旧”是由插入时间决定的，而不是某个字段时，这才有效。
如果您需要一个合适的 LRU，那么您可能应该去看看类似 http://www.codeproject.com/KB/recipes/LRUCache.aspx?fid=1000025&df =90&mpp=25&noise=3&sort=Position&view=Quick&fr=15
但是，如果您的最大值为 20 个条目，您将很难找到实际上更快的复杂算法而不是对每个元素进行简单的线性检查。
My suggestion would be to make a circular buffer. But that only works if "old" is determined by when it was inserted, and not some field.
If you need to have a proper LRU, then you should probably go and look at something like http://www.codeproject.com/KB/recipes/LRUCache.aspx?fid=1000025&df=90&mpp=25&noise=3&sort=Position&view=Quick&fr=15
But with 20 entries as your max, it will be very hard to you to find a complex algorithm that is actually faster than the trivial lineary check of every element.