c++ - 交换集合的后缀和前缀

Question

我有一个数字列表L（在一般意义上，不是std::list），我也有i它是 中最小元素的索引L。我想交换由 index 分隔的两个分区i。我应该执行什么标准数据结构和什么操作才能尽可能高效地执行此操作（最好是在恒定时间内）？

L一个例子：让9 6 -4 6 12。最小值是L[2] = -4，所以i = 2。交换两个分区后，我想L成为-4 6 12 9 6.

该列表将非常大（最多 10 ^{3 个}元素），我还必须多次遍历它（在最坏的情况下最多 10 3 次遍历），因此由于缓存问题，使用^不是std::list一个好主意。另一方面，std::vector会使两个分区的交换变得困难。这是std::deque一个不错的选择吗？

Answer 1

你的问题有两个方面：

1-恒定时间交换：从概念上讲，就交换而言，最好的方法是双向链表（std::list）。

由于您的数据很大，因此节点将始终保留在内存中的初始位置，并且您只会更改一些恒定数量的指针来执行您提到的交换类型。

2-局部性：我们都知道内存中连续分配的空间对于缓存性能更好。这偏向std::vector。

中间是什么？ 可通过自定义分配器分配的可调整大小的连续内存块。有很多方法可以设计这些。一个例子。