如何高效排序数组并同步跟踪排列索引？

我有两个随机访问可迭代对象：一个存储数值，另一个存储排列索引。希望对数值排序的同时，跟踪排列索引的变化。

示例输入 #

std::array values{7, 45, 18, 33, 77, 96, 83, 80, 4, 51};
std::array<int, values.size()> index;

示例输出 #

values == {4, 7, 18, 33, 45, 51, 77, 80, 83, 96};
index == {8, 0, 2, 3, 1, 9, 4, 7, 6, 5};

已考虑的解决方案 #

简单解决方案：vector pair sort

构造存储数值与其索引的vector<pair>，按数值排序后提取结果。但大数组场景下需要避免两次转换的开销。

其他解决方案

基于数值对初始为0、1、2…的排列索引执行std::sort，仅得到排列索引但不排序数值数组，后续有两种选择：

• double sort方案：对数值单独执行std::sort()，但需要两次排序，若比较操作开销大则不划算。
• 利用排列索引排序数值：
  • boost index apply sort：用boost::algorithm::apply_permutation()实现，但需先复制排列索引；
  • permutate in place sort：原地置换排序，还可将索引转换为循环置换后应用，但暂未实现。

理想解决方案设想

希望在正常排序数值时，同步交换排列索引中对应元素，实现原地同时排序且无额外开销。计划复用std::sort()，通过自定义迭代器结合值与索引的迭代器，返回带自定义swap()的包装类引用，重载swap()实现同步交换。

基准测试情况 #

对含100万随机int（范围INT_MIN至INT_MAX）和double（范围0至1）的vector进行200次测试，结果显示vector pair sort表现优异，推测是编译器优化带来的效果。

待解答问题 #

1. 这种基于自定义迭代器的理想方案是否可行？如何实现？
2. 是否存在被忽略的解决方案？
3. 哪种方案最优？

注：基准测试曾存在重大缺陷已修复，添加了非索引排序的原始排序基准；带的方案并非实际索引排序。

1. 自定义迭代器方案的可行性与实现 #

这种方案完全可行，核心思路是通过自定义"配对迭代器"，让std::sort在交换数值元素时自动同步交换索引元素。

实现示例 #

我们可以定义一个绑定数值和索引引用的包装类，重载swap函数；再实现适配std::sort的随机访问迭代器：

#include <algorithm>
#include <array>
#include <iterator>
#include <numeric>

// 包装类，绑定数值和索引的引用
template <typename ValueT, typename IndexT>
struct SortPairRef {
    ValueT& value;
    IndexT& index;

    // 仅基于数值比较，保证排序逻辑与单独排序数值一致
    bool operator<(const SortPairRef& other) const {
        return value < other.value;
    }
};

// 自定义随机访问迭代器，同时遍历数值和索引容器
template <typename ValueIter, typename IndexIter>
struct PairIterator {
    using value_type = SortPairRef<typename ValueIter::value_type, typename IndexIter::value_type>;
    using reference = value_type;
    using pointer = void;
    using difference_type = typename ValueIter::difference_type;
    using iterator_category = std::random_access_iterator_tag;

    ValueIter value_it;
    IndexIter index_it;

    PairIterator(ValueIter v_it, IndexIter i_it) : value_it(v_it), index_it(i_it) {}

    reference operator*() { return {*value_it, *index_it}; }
    PairIterator& operator++() { ++value_it; ++index_it; return *this; }
    PairIterator operator++(int) { auto tmp = *this; ++*this; return tmp; }
    PairIterator& operator--() { --value_it; --index_it; return *this; }
    PairIterator operator--(int) { auto tmp = *this; --*this; return tmp; }
    PairIterator& operator+=(difference_type n) { value_it += n; index_it += n; return *this; }
    PairIterator operator+(difference_type n) const { auto tmp = *this; tmp += n; return tmp; }
    PairIterator& operator-=(difference_type n) { value_it -= n; index_it -= n; return *this; }
    PairIterator operator-(difference_type n) const { auto tmp = *this; tmp -= n; return tmp; }
    difference_type operator-(const PairIterator& other) const { return value_it - other.value_it; }
    bool operator==(const PairIterator& other) const { return value_it == other.value_it; }
    bool operator!=(const PairIterator& other) const { return !(*this == other); }
    bool operator<(const PairIterator& other) const { return value_it < other.value_it; }
};

// 全局swap重载，同步交换数值和索引
template <typename ValueT, typename IndexT>
void swap(SortPairRef<ValueT, IndexT> a, SortPairRef<ValueT, IndexT> b) {
    std::swap(a.value, b.value);
    std::swap(a.index, b.index);
}

// 辅助函数，快速生成配对迭代器
template <typename ValueIter, typename IndexIter>
auto make_pair_iterator(ValueIter v_begin, IndexIter i_begin) {
    return PairIterator<ValueIter, IndexIter>(v_begin, i_begin);
}

// 使用示例
int main() {
    std::array values{7, 45, 18, 33, 77, 96, 83, 80, 4, 51};
    std::array<int, values.size()> index;
    // 初始化索引为0,1,2...
    std::iota(index.begin(), index.end(), 0);

    // 用自定义迭代器执行同步排序
    std::sort(make_pair_iterator(values.begin(), index.begin()),
              make_pair_iterator(values.end(), index.end()));

    // 此时values和index已按要求完成排序
    return 0;
}

该实现完全复用std::sort的优化逻辑，实现原地同步排序，无额外内存开销（仅迭代器本身的极小开销）。

2. 被忽略的方案 #

还有一种更轻量的方案：先排序索引数组，再通过循环置换原地重排数值数组：

// 第一步：基于数值排序索引数组
std::sort(index.begin(), index.end(), [&values](int a, int b) {
    return values[a] < values[b];
});

// 第二步：通过循环置换原地重排values数组
std::vector<bool> visited(values.size(), false);
for (size_t i = 0; i < values.size(); ++i) {
    if (visited[i] || index[i] == static_cast<int>(i)) continue;
    size_t current = i;
    while (!visited[current]) {
        visited[current] = true;
        size_t next = index[current];
        if (current != next) {
            std::swap(values[current], values[next]);
        }
        current = next;
    }
}

这种方案无需自定义迭代器或包装类，逻辑直观，若仅需索引数组可直接跳过第二步，资源消耗极低。

3. 最优方案选择 #

最优方案取决于具体场景：

• 优先性能且内存充足：选vector pair sort，编译器对std::pair的排序有成熟优化，代码实现最简单：

  std::vector<std::pair<int, int>> pairs;
  pairs.reserve(values.size());
  for (size_t i = 0; i < values.size(); ++i) {
      pairs.emplace_back(values[i], i);
  }
  std::sort(pairs.begin(), pairs.end());
  // 提取排序结果
  for (size_t i = 0; i < values.size(); ++i) {
      values[i] = pairs[i].first;
      index[i] = pairs[i].second;
  }
  

• 内存受限（超大数组）：选自定义迭代器方案或循环置换方案，两者均为原地操作，无额外内存开销。自定义迭代器方案代码更整洁，循环置换方案更轻量。
• 仅需索引数组：直接排序索引数组即可，无需处理数值数组，是最省资源的选择。

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