我有一个数字的L列表（一般而言，不是std::list），还有i，它是L中最小元素的索引。我想交换由索引i分隔的两个分区。我应该执行什么标准的数据结构和什么操作，以使我可以尽可能高效地执行此操作（最好在固定时间内执行）？
例如：让L为9 6 -4 6 12。最小值为L[2] = -4，因此为i = 2。交换两个分区后，我希望L是-4 6 12 9 6。
该列表将非常大（最多103个元素），并且我还将不得不遍历多次（在最坏的情况下最多103个遍历），因此由于缓存问题，使用std::list并不是一个好主意。另一方面，std::vector将使得很难交换两个分区。 std::deque是一个不错的选择吗？
最佳答案
您的问题有两个方面：
1-恒定时间交换：从概念上讲，最佳交换方式是doubly linked list（std::list）。
由于您的数据很大，因此节点将始终保留在内存中的初始位置，并且您将仅更改一些恒定数量的指针来执行您要提及的交换类型。
2-局部性：我们都知道，在内存中连续分配空间对于提高缓存性能更好。这倾向于std::vector。
中间是什么？
可调整大小的连续内存块，可以通过自定义分配器分配。有许多方法可以设计这些。 example。
关于c++ - 交换集合的后缀和前缀，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15466537/