Мне нужно отсортировать 2 вектора на С ++. Первые должны быть в порядке возрастания, а вторые должны быть отсортированы в точно так же, как и первый, поскольку элементы каждого вектора с заданным индексом i соответствуют друг другу без пар.
У кого-нибудь есть способ сделать это без использование дополнительных структур для пар? Мне просто нужно отсортировать их одинаково. Я нашел способ получить индексный вектор, который запоминает, как мы должны переупорядочить второй вектор, но проблема в том, что временная сложность функции переупорядочения равна n ^ 2, и мне нужно, чтобы он был в nlog n в худшем случае.
Вот код, который я нашел для индексной функции:
template <typename T>
vector<size_t> sort_indexes(const vector<T> &v) {
// initialize original index locations
vector<size_t> idx(v.size());
iota(idx.begin(), idx.end(), 0);
//sort indexes based on comparing values in v
//using std::stable_sort instead of std::sort
//to avoid unnecessary index re-orderings
//when v contains elements of equal values
stable_sort(idx.begin(), idx.end(),
[&v](size_t i1, size_t i2) {return v[i1] < v[i2];});
return idx;
}
Если у кого-то есть другой способ их сортировки или есть способ изменить функцию переупорядочения без использования пар, это будет большим подспорьем, спасибо.