我应该使用哪个 STL 容器?C++

Which STL container should I use? C++(我应该使用哪个 STL 容器?C++)

本文介绍了我应该使用哪个 STL 容器?C++的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我有一个对象列表",我想从中随机取出对象并将其推到此列表的前面.只会执行这种操作.所以我不需要快速访问列表末尾,只需要它的前面和对任何其他地方的平均访问.

I have a 'list' of objects, from which I want to take object at random position and push it on front of this list. Only this kind of operation will be performed. So I don't need a fast access to end of the list, only to it's front and average access to any other place.

哪个容器最适合这个?我在考虑std::vector,但我读到insert 操作效率不高.然后我想出了 std::deque 因为它可以快速访问前面,但是 erase 在特定位置方法的效率如何?

Which container would be the best for this? I was thinking about std::vector, but I've read that insert operation is not efficient. Then I came up with std::deque because of it's fast access to front, but what about efficiency of it's erase at specific position method?

提前感谢您的帮助.

推荐答案

我们可以为您提供指导,但没有明确的答案——您需要自己进行基准测试,因为它关键取决于您的集合和对象大小:

We can give you guidelines, but no definitive answer – you need to benchmark that yourself because it crucially depends on your collection and object size:

  • 对于小对象和/或相对较小的集合,std::vector 会更快,因为即使您需要复制更多数据,更好的随机访问时间(O(1) vs O(n) 对于 std::list) 并且缓存位置将占主导地位.
  • 对于大型对象和/或大型集合,std::list 会更快,因为虽然您需要 O(n) 来选择随机对象,但插入会更快,因为复制许多大对象非常慢.
  • For small objects and/or a relatively small collection, std::vector will be faster because even though you need to copy more data, the better random access time (O(1) vs O(n) for std::list) and the cache locality will dominate.
  • For large objects and/or a large collection, std::list will be faster because although you need O(n) to pick a random object, insertion will be much faster since the copying of many large objects is very slow.

但我不能说这两种情况之间的确切界限在哪里.

But where exactly the cut-off between these two scenarios lies I cannot say.

此外,如果您可以交换元素而不是插入,那么这很容易:始终使用 std::vector.

Furthermore, if you can get away with swapping the elements instead of insertion, this is a no-brainer: always use a std::vector.

这篇关于我应该使用哪个 STL 容器?C++的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!

本文标题为:我应该使用哪个 STL 容器?C++

基础教程推荐