vector具有良好的缓存效率(索引接近的元素在内存中放置得很近)，但是在任意位置插入时效率很低。列表可以在任意位置插入O(1)(只要您知道该位置的地址)，但是它们的缓存效率很差(元素随机分布在堆中)。
是否有任何数据结构与O(1)插入在任何索引保持元素与近索引在近的地方在内存上?
在附近放置列表元素通常不是结构(vector, list)作业，而是分配器作业
元素随机分布在堆中
对于不随机分布在堆中的元素，您必须使用池或固定大小的块分配
不能同时进行最坏情况下的O(1)随机访问插入和具有相似索引的元素的并置。如果具有相似指标的元素必须位于彼此的O(1)个单位内，那么您可以总是在相同的位置插入足够的元素，以便下一次插入迫使O(n)个其他元素移动。事实上，你需要插入的元素的数量来强制至少一些移动是0(1)(因为相邻元素之间的间距也是0)。
查看std::deque。它混合了向量和列表的属性。我相信它是像一个列表一样实现的，但它不是每次分配一个节点，而是分配固定数量的节点。