我目前正在研究一种算法的实现，我想证明它可以在恒定时间内工作，即使元素数量非常多。
不幸的是，我需要一个数据结构来存储元素。当元素的数量非常多时，但对于我的算法而言并非不合理的高，std::vector 和 std::valarray 都不会在恒定时间内访问任意元素 as you can see in this graph .
是否有更好的数据结构来存储这些值？是否有任何我可以实现的技术来实现恒定时间访问？
最佳答案
对于较高的 n 值，很可能是:
您遇到了缓存问题。在某些时候，每次内存访问都会错过缓存，从而导致更长的内存负载。
您正在遇到内存分页的缓存问题。现代计算机内存以树状结构组织。每个内存访问都通过该树，使每个内存访问 O(log n) 其中 n 是可寻址内存空间。你通常不会注意到它，因为那棵树的高度和良好的缓存。但是，对于非常高的 n 和随机内存访问，这可能会成为一个问题。
例如，我的一个 friend 证明了由于随机内存访问，计数排序算法具有 O(n log n) 时间复杂度。快速排序算法 - 作为比较 - 对内存的顺序访问非常好，并且分页开销要低得多。
底线是，您很可能会遇到架构/操作系统内存访问开销 - 除非您使用一些非常极端的方法(例如实现您自己的操作系统)，否则您将无法克服这些开销。
关于c++ - 恒定时间访问列表中的任意元素 (C++)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42928989/