向量具有良好的缓存效率(具有接近索引的元素在内存中放置在一起)，但在任意位置插入时效率低下。列表在任意位置插入O(1)(只要您知道该位置的地址)，但它们的缓存效率很差(元素随机分布在堆中)。
在任何索引中是否有任何具有 O(1) 插入的数据结构，以将具有邻近索引的元素保存在内存中邻近的位置？
最佳答案
在附近放置列表元素通常不是结构(向量、列表)作业，而是分配器作业
elements are spread randomly across the heap
对于不在堆中随机分布的元素，您必须使用池或固定大小的 block 分配
关于performance - 是否有任何类似列表的结构允许在任意索引处插入，同时保持缓存效率？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32976776/