Как сортировать два массива по одному из них в C++?

Question

[dansheb]

Предположим есть два (или несколько) векторов std::vector<T> (или std::array<T>) A и B одинаковой длины n.
Нужно отсортировать массивы по A, при этом переставить соответствующие элементы B. (Так делают табличные процессоры типа Excel и также обрабатываются таблицы в СУБД).

Пример для двух массивов A и B:
A B
5 R
4 Q
1 T
3 A
2 X

Сортируем по A:
A B
1 T
2 X
3 A
4 Q
5 R

Ограничения по дополнительной памяти O(1).

Из идей как это сделать средствами С++ без библиотек:
1. Скопировать std::sort и заменить в нем функцию std::swap, на свою, которая переставляет связанные элементы.
2. Перегрузить std::swap для какого-то типа, что бы использовать std::sort без изменений, но я не понимаю как это сделать, так как при обмене двух значений в std::vector<T> будет вызвана std::swap<T, T>.

Вопрос как реализовать такую сортировку просто и без переписывания лишнего кода.
Желательно без использования дополнительных библиотек. (Ответы с ними я бы тоже с удовольствием увидел).

Comments

[abcd0x00]

Пиши обычную сортировку с индексами, которая будет сравнивать в первом, а переставлять в обоих.

[dansheb]

abcd0x00: не совсем понимаю, что значит сортировка с индексами?

[abcd0x00]

dansheb: ну, обычные индексы элементов в векторе. То есть можно при сортировке использовать ссылки или указатели, а тут надо использовать индексы элементов. Потому что два массива и ты через ссылки или указатели на один ничего не сможешь сделать со вторым.

Answer 1

[AtomKrieg]

Есть такой подход web.stanford.edu/~dgleich/notebook/2006/03/sorting...

или

Положите значения в map - в нем значения сортируются по ключу

vector<int> intv{5, 4, 1, 3, 2};
vector<char> charv{'R', 'Q', 'T', 'A', 'X'};
map<int, char> res;

for (size_t idx {0} ; idx < intv.size() ; idx++)
	res[intv[idx]] = charv[idx];

for (auto kv : res)
	cout << kv.first << " " << kv.second << endl;

Comments

[dansheb]

Спасибо за ответ.

Но это решение использует O(n) дополнительной памяти и требует массу ненужных действий с памятью.
Реализуемый мною алгоритм подразумевает использования независимых векторов и не представляется возможным использовать другую структуру данных.
Помимо этого второй массив сортируется не только по первому массиву. И тогда прийдётся дублировать его неоднократно.

[AtomKrieg]

dansheb: зато тяп-ляп и в продакшн. Вы же не хайлоад пишите судя по вопросу :)

[dansheb]

AtomKrieg: при n~10^9, тип данных float, при 10^3 итераций сортировки - это будет весьма ощутимо по времени.

[AtomKrieg]

dansheb: Нисколько не спорю что 10^9 это много, я бы рекомендовал попробовать и потом утверждать что вам не подходит.

[AtomKrieg]

dansheb: web.stanford.edu/~dgleich/notebook/2006/03/sorting... такой подход находили?

[dansheb]

AtomKrieg: спасибо, очень похоже на то, что надо. Причём я уже находил эту страницу, но почему то прошёл мимо. С учётом того, что начиная с 11 стандарта можно пользоваться tuple без boost, выглядит многообещающе. Осталось аккуратно проверить корректность и производительность.

Answer 2

[Alexander Movchan]

Сделать вектор пар std::vector<std::pair<int, char>>, а в std::sort передавать собственный компаратор, который будет сравнивать только первые элементы:

vector<pair<int, char>> vec;
sort(vec.begin(), vec.end(), [](pair<int, char> a, pair<int, char> b){return a.first < b.first;});

Comments

[dansheb]

Спасибо за ответ.

Это то, что я использую в данный момент(у меня std::vector<std::vector<T>>).
Это решение использует O(n) дополнительной памяти и требует массу ненужных действий с памятью.
Реализуемый мною алгоритм подразумевает использования независимых векторов и не представляется возможным использовать другую структуру данных.
Предложенный вами способ вызывает следующую цепочку действий:
1. std::vector<T> A,B
2. создание std::vector<std::pair<T,T>> (+O(n) памяти)
3. удаление std::vector<T> A,B
4. сортировка std::sort<std::vector<std::pair<T,T>>>
5. создание отсортированных std::vector<T> A^,B^ из отсортированного std::vector<std::pair<T,T>>
6. удаление std::vector<std::pair<T,T>>

Answer 3

[maaGames]

Сделай свой объект компаратор, в котором сохрани указатель на второй массив. В операторе сравнения не только сравнивай значения аргументов, но и меняй местами значения во втором массиве.

Comments

[dansheb]

Не уверен, что std::sort вызывает std::swap, каждый раз когда компаратор даёт TRUE. То есть у меня нет уверенности, что некоторые алгоритмы сортировки не будут сравнивать в других целях помимо сортировки (допустим для выявление частичной упорядоченности массива и вызова подходящего алгоритма сортировки). Стандарт этого не запрещает. Помимо этого, компаратор не будет знать какие номера в первом массиве имеют сравниваемые элементы и мы не сможем поменять местами соответствующие элементы во втором массиве.

[maaGames]

dansheb: Компаратор, это class Compare{ bool operator<( int lhs, int rhs); };
std::sort( array.begin(), array.end(), Compare() );

Но я понял ошибку. Всё таки придётся создать массив с индексами первого массива и вызывать сортировку именно этого массива, но сравнения делать по первому массиву, через эти индексы и менять значения сразу в первом и втором массиве (индексы обменяются сами).

[dansheb]

maaGames: Опять же получается, что нужно O(n) дополнительной памяти.

[maaGames]

dansheb: Если sizeof(T ) сильно больше, чем sizeof(int), может не так страшно наличие памяти дополнительной.

[maaGames]

Я придумал самое эффективное решение. Напиши свою версию функции сортировки, принимающую два массива, вместо одного. Возможно, std::sort скопируй и дорисуй.

[dansheb]

maaGames: Я и написал, это в решении 1. Это действительно не сложно cmd+c, cmd+v из std::sort, добавить передачу дополнительных массивов и переписать все вхождения std::swap на свою. Но это решение похоже на изобретение велосипеда, так как переписывать std::sort по сути из за 5 раз, когда встречается std::swap, не звучит элегантным решением. Но повторюсь, что это единственное решение, удовлетворяющие ограничениям, которое я нашёл на данный момент.

Тип T - это float/double/int, тоесть объекты сравнимые по размеру с int. И n ~ 10^9.

[dansheb]

Ринат Велиахмедов: с точки зрения производительности это решение на высоте, но вот с точки зрения оправданность сотен строк скопированного кода ради нескольких исправлений - это кошмар.

[maaGames]

Ринат Велиахмедов: Учитывая, что нужно синхронно сортировать массивы по 4-8 гигабайт каждый, то отсутствие временных контейнеров тут весьма уместно. Я вижу только два решения: 1 - массив индексов, 2 - своя функция сортировки. Вы бы лучше решение предложили, а не отднострочный флуд... Давайте, забацайте самое эффективное решение, раз модификация std::sort "и близко не самое эффективное"(с).

[maaGames]

Ринат Велиахмедов: Использование map вместо vector для int увеличивает использование памяти на 500% при 64 битной адресации. И это при условии аллокатора, оптимально использующего память (int-ключ + int-значение + 2 указателя по 8 байт). Т.е вместо 4 гигабайт получается жалких 24 гигабайт для одной пары массивов. И выше уже было сказано, что массивов может быть не два.

[maaGames]

Ринат Велиахмедов: Не говоря уж о том, что формирование массива с последующей сортировкой с вероятностью 99% будет эффективнее, чем формирование словаря.