我一直在阅读有关 C++ 标准库中不同容器的信息，而且我一直听说在实践中，简单 vector 在遍历元素时通常如何优于大多数其他容器。据说这是由于缓存一致性(所有存储在连续内存中)，而不是在二叉树或链表中从一个地方跳到另一个地方。但我在想，如果我们谈论的是指针 vector 或对对象的引用而不是对象本身，那么迭代 vector 将涉及在每次迭代时取消引用，其中对象位于单独的内存区域。在这种情况下，我看不出它比在列表或树中从一个链接跳到另一个链接更好。我看到它的方式如下所示，据我所知，每个人都做同样的事情。
如果这是真的，那么我是否可以假设每当人们声称 vector 对缓存更友好时，只有在存储对象时才是这种情况，而不是对象的指针或引用？另外，我不认为指向多态类型的指针是否会在两者之间产生差异？
最佳答案
|ptr1|ptr2|ptr3|ptr4| //vector
和
|ptr1|--->|ptr2|--->|ptr3|--->|ptr4| //list
现在考虑通过 ptr3 访问第三个对象。
vector 花费的时间。
O(1) time to reach ptr3 + time to dereference ptr3
列表花费的时间
O(2) time to reach ptr3 + time to dereference ptr3.
所以区别在于到达要取消引用的指针。
通常访问 vector 中的元素是 O(1) 而在 list 中是 O(n)
关于c++ - 当元素是指针或引用时，连续内存 vector 没有优势吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45800070/