C ++ Variadi c Функция для сортировки аргументов на месте

Question

При реализации варианта задачи бинарного поиска мне нужно было переупорядочить точки среза (т. Е. Начало, середина, конец), чтобы они сохранялись в соответствующей переменной (например, (1,5,2) -> (1,2,5)). Это довольно просто сделать с несколькими if statements и swaps. Однако, как мысленный эксперимент, я теперь заинтересован в обобщении этого для работы с n многими T переменными типа. Я начал экспериментировать с некоторыми интуитивными решениями и в качестве отправной точки я придумал эту функцию шаблона:

template<typename T>
void 
sortInPlace(
    std::function<bool (const T&, const T&)> compareFunc,
    T& start, 
    T& mid, 
    T& end)
    {
        std::vector<T> packed {start, mid, end};
        std::sort(packed.begin(), packed.end(), compareFunc);
        auto packedAsTuple = make_tuple(packed[0], packed[1], packed[2]);
        std::tie(start, mid, end) = packedAsTuple;
    }

И когда я запустил следующее, используя typedef std::pair<int,int> Pivot:

//Comparison function to sort by pair.first, ascending:
std::function<bool(const Pivot&, const Pivot&)>
  comp =[](const Pivot & a, const Pivot & b) {
     return std::get < 0 > (a) < std::get < 0 > (b);
  };

int main(){
    Pivot a(8,1);
    Pivot b(2,3);
    Pivot c(4,6);

    sortInPlace(comp,a,b,c);
}

Получается, что работает как задумано:

a after sort: 2, 3
b after sort: 4, 6
c after sort: 8, 1

В идеале, следующий шаг - преобразовать этот шаблон в шаблон variadi c, но у меня возникают проблемы с достижением этого. У меня также есть несколько вещей, которые беспокоят меня относительно текущей версии:

1. Использование std::vector было произвольным решением. Я сделал это, потому что мне неясно, какую структуру / контейнер лучше всего использовать для упаковки этих значений. Мне кажется, что выбор структуры должен быть легко сконструирован, отсортирован и распакован / преобразован в кортежи, и я не уверен, существует ли такая магическая структура.
2. Просто чтобы что-то пошло, я пришлось довольствоваться ручной упаковкой / распаковкой аргументов. Мне также неясно, как использовать std::tie или любую другую операцию распаковки / перемещения с переменным номером (т.е. неизвестным во время компиляции) элементов.
3. Хотя нет особой причины использовать исключительно функции / структуры stl, я был бы удивлен, узнав, что нет интуитивного способа добиться этого с помощью абстракций, представленных в stl. В результате я больше заинтересован в достижении своей цели, используя минимальную помощь за пределами stl.

Я начал этот мысленный эксперимент, ожидая, что в итоге получу синтаксически правильную версию std::move(std::sort({x,y,z}, comp), {x,y,z}) и учитывая, к чему меня привели мои исследования, я начинаю думать, что я слишком усложняю эту проблему. Любая помощь, понимание или предложение будет высоко ценится!

Answer 1

Одно возможное решение C ++ 17 с std::sort, которое обобщает ваш пример:

template<class Comp, class... Ts>
void my_sort(Comp comp, Ts&... values) {
    using T = std::common_type_t<Ts...>;
    T vals[]{std::move(values)...};

    std::sort(std::begin(vals), std::end(vals), comp);

    auto it = std::begin(vals);
    ((values = std::move(*it++)), ...);
}

using Pivot = std::pair<int, int>;

const auto comp = [](Pivot a, Pivot b) {
    return std::get<0>(a) < std::get<0>(b);
};

Pivot a(8, 1);
Pivot b(2, 3);
Pivot c(4, 6);

my_sort(comp, a, b, c);

Если число N параметров в пакете мало, вам не нужно std::sort совсем. Просто серия (жестко закодированных) сравнений (а для небольших N минимальное количество сравнений точно известно) сделает эту работу - см. Se c. 5.3 Оптимальная сортировка из Кнута TAOCP vol. 3.