AtomKrieg: спасибо, очень похоже на то, что надо. Причём я уже находил эту страницу, но почему то прошёл мимо. С учётом того, что начиная с 11 стандарта можно пользоваться tuple без boost, выглядит многообещающе. Осталось аккуратно проверить корректность и производительность.
Ринат Велиахмедов: с точки зрения производительности это решение на высоте, но вот с точки зрения оправданность сотен строк скопированного кода ради нескольких исправлений - это кошмар.
maaGames: Я и написал, это в решении 1. Это действительно не сложно cmd+c, cmd+v из std::sort, добавить передачу дополнительных массивов и переписать все вхождения std::swap на свою. Но это решение похоже на изобретение велосипеда, так как переписывать std::sort по сути из за 5 раз, когда встречается std::swap, не звучит элегантным решением. Но повторюсь, что это единственное решение, удовлетворяющие ограничениям, которое я нашёл на данный момент.
Тип T - это float/double/int, тоесть объекты сравнимые по размеру с int. И n ~ 10^9.
Но это решение использует O(n) дополнительной памяти и требует массу ненужных действий с памятью.
Реализуемый мною алгоритм подразумевает использования независимых векторов и не представляется возможным использовать другую структуру данных.
Помимо этого второй массив сортируется не только по первому массиву. И тогда прийдётся дублировать его неоднократно.
Не уверен, что std::sort вызывает std::swap, каждый раз когда компаратор даёт TRUE. То есть у меня нет уверенности, что некоторые алгоритмы сортировки не будут сравнивать в других целях помимо сортировки (допустим для выявление частичной упорядоченности массива и вызова подходящего алгоритма сортировки). Стандарт этого не запрещает. Помимо этого, компаратор не будет знать какие номера в первом массиве имеют сравниваемые элементы и мы не сможем поменять местами соответствующие элементы во втором массиве.
Это то, что я использую в данный момент(у меня 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>>
@AxisPod@vik523 Всё же стоит учитывать особенности реализации std::deque, так как прямой доступ(через чистые указатели) не указывает на непрерывные куски памяти. И в случая обхода std::deque скорость будет меньше, чем у std::vector (как я понимаю, при хорошой реализации не значительно).
Если знакомы с O-нотацией, то посмотрите вот тут сравнение контейнеров std: john-ahlgren.blogspot.ru/2013/10/stl-container-per...
Да, я про это написал в пункте 1, но большая загвоздка в том, что на самом деле, они будут не прижаты, а в окрестности этого плюс минус несколько пикселей.
@jcmvbkbc, спасибо. Только знакомлюсь с c++ и ещё не вошло в привычку сразу смотреть стандарт. То что вы предложили действительно лучше подходит для моих нужд (во всяком случае на данном этапе). Кстати, при беглом просмотре стандарта(ISO+IEC+14882-2011, то есть c++11) не нашёл, вычисляется ли value_type на этапе компиляции.
Ещё возник вопрос к @zvorygin, как понять "отталкиваться не от значений, а от типа"? Разве не будет рвенства между sizeof(v[0]) и sizseof(std::vector::value_type) (подразумевая что v - std::vector)?