如何使用C++标准库原地对并行数组进行排序？

首先明确：C标准库在C20及以后提供了原生支持原地同步排序的方法，无需额外分配内存；C++20之前则没有直接的标准库方案，需要手动实现或通过自定义逻辑处理。

C++20及以上：利用std::views::zip和std::ranges::sort #

通过std::views::zip将两个向量打包成一个视图（不复制元素，仅引用原向量的对应元素），然后对这个视图排序，就能实现两个向量的同步原地排序。代码示例：

#include <vector>
#include <algorithm>
#include <ranges>
#include <cassert>

void foo(std::vector<int>& a, std::vector<int>& b) {
    assert(a.size() == b.size());
    // 将a和b打包为视图，根据a的元素排序，同步调整b的元素
    std::ranges::sort(std::views::zip(a, b), 
        [](const auto& lhs, const auto& rhs) {
            return std::get<0>(lhs) < std::get<0>(rhs);
        });
}

这里std::views::zip(a, b)生成的视图会把a[i]和b[i]配对成元组，std::ranges::sort在排序时会同步交换两个向量中的对应元素，完全原地操作，不会分配额外内存空间，非常适合处理大型向量。

C++20之前：手动实现同步排序逻辑 #

由于旧标准库没有原生的zip视图支持，若要严格避免分配额外数组，只能手动实现排序算法（如快速排序），在交换a中元素的同时同步交换b中对应位置的元素。示例以快速排序为例：

#include <vector>
#include <cassert>
#include <algorithm>

template<typename T, typename U>
void syncQuickSort(std::vector<T>& a, std::vector<U>& b, int left, int right) {
    if (left >= right) return;
    T pivot = a[right];
    int i = left - 1;
    for (int j = left; j < right; ++j) {
        if (a[j] <= pivot) {
            ++i;
            std::swap(a[i], a[j]);
            std::swap(b[i], b[j]); // 同步交换b的对应元素
        }
    }
    std::swap(a[i+1], a[right]);
    std::swap(b[i+1], b[right]); // 同步交换b的对应元素
    syncQuickSort(a, b, left, i);
    syncQuickSort(a, b, i+2, right);
}

void foo(std::vector<int>& a, std::vector<int>& b) {
    assert(a.size() == b.size());
    if (a.empty()) return;
    syncQuickSort(a, b, 0, static_cast<int>(a.size()) - 1);
}

这种方法完全原地操作，不分配任何额外内存，但需要自行实现排序逻辑，不如C++20的方案简洁。

补充说明 #

如果可以接受临时分配少量栈内存（而非额外的元素数组），C++20之前也可借助第三方库的zip_iterator（如Boost库）配合std::sort实现，但这类实现不属于标准库范畴。

内容的提问来源于stack exchange，提问作者Lajos Nagy