How to sort and keeping track of indexes in C ++ ?

This is very useful in many application scenarios, such as data analysis and machine learning, where data is often sorted based on specific criteria while preserving the original positions for subsequent processing.

In C++, we can implement this functionality in various ways. Below, I will introduce two common methods:

Method 1: Using an Additional Index Array

The approach involves creating an index array initialized in ascending order, then sorting this index array based on the values of the data array.

cpp
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> data = {10, 20, 5, 23, 50};
    std::vector<int> indices(data.size());

    // Initialize the index array
    for (int i = 0; i < indices.size(); ++i) indices[i] = i;

    // Sort the indices using a lambda expression based on data values
    std::sort(indices.begin(), indices.end(),
        [&](int i, int j) { return data[i] < data[j]; });

    // Output the sorted indices
    for (int index : indices) {
        std::cout << "Value: " << data[index] << ", Original Index: " << index << std::endl;
    }

    return 0;
}

Method 2: Using a Pair Array

Another approach is to create a pair array where each pair stores a value and its original index, then sort the array based on the values.

cpp
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> data = {10, 20, 5, 23, 50};
    std::vector<std::pair<int, int>> value_index_pairs;

    // Create the pair array
    for (int i = 0; i < data.size(); ++i) {
        value_index_pairs.emplace_back(data[i], i);
    }

    // Sort the pair array
    std::sort(value_index_pairs.begin(), value_index_pairs.end());

    // Output the sorted results
    for (const auto& pair : value_index_pairs) {
        std::cout << "Value: " << pair.first << ", Original Index: " << pair.second << std::endl;
    }

    return 0;
}

Both methods have distinct advantages. The first method uses the original data alongside a separate index array, preserving the data structure, which is highly efficient for large datasets. The second method bundles the data and indices together, resulting in more concise and readable code, though it may incur a minor memory overhead (which is typically negligible).

These are several common methods for sorting and tracking indices in C++. With these techniques, we can effectively sort and manage data without altering the original data. These approaches are particularly valuable for complex data processing tasks.