Переупорядочение алгоритма с помощью повторного поворота

Рассмотрим набор данных с N образцы, где каждый образец состоит из head элементы, сопровождаемые tail элементы. Я хотел бы выполнить стабильное переупорядочение таким образом, чтобы N tails сгруппированы вверху, и N heads сгруппированы внизу.

Например, набор данных:

 -1  -2  -3   1   2   3   4   5
-4  -5  -6   6   7   8   9  10
-7  -8  -9  11  12  13  14  15
-10 -11 -12  16  17  18  19  20

имеет имеет N = 4 образцы, с head = 3 (отрицательные целые числа) и tail = 5 (положительные целые числа). Желаемое преобразование даст:

  1   2   3   4   5   6   7   8
9  10  11  12  13  14  15  16
17  18  19  20  -1  -2  -3  -4
-5  -6  -7  -8  -9 -10 -11 -12

Я реализовал решение, основанное на повторном применении поворотов. Вращения осуществляются алгоритмом C ++ std::rotate:

std::rotate(first, n_first, last) меняет элементы в диапазоне
[first, last) таким образом, что элемент n_first становится
первый элемент нового ассортимента и n_first - 1 становится последним
элемент.

Моя реализация (показанная ниже) обеспечивает правильное решение и хорошо подходит для моих проблем. Однако для этого необходимо выполнить N повороты, где сложность каждого поворота увеличивается от O(head + tail) в O(N * tail + head),

Вам знаком алгоритм с лучшей сложностью?.

Мой код выглядит следующим образом:

#include <algorithm>
#include <vector>
#include <iostream>
#include <iomanip>

template <typename I> // I models Forward Iterator
I reorder(I f, I l, std::size_t head_size, std::size_t tail_size)
{
std::size_t k = 1;
auto m = std::next(f, head_size);
auto t = std::next(m, tail_size);
while (t != l) {
f = std::rotate(f, m, std::next(m, tail_size));
m = std::next(f, ++k * head_size);
t = std::next(m, tail_size);
};
return std::rotate(f, m, t);
}

template <typename C>
void show(const char* message, const C& c)
{
std::size_t shown { 0 };
std::cout << message << "\n";
for (auto && ci : c)
std::cout << std::setw(3) << ci
<< (++shown % 8 == 0 ? "\n" : " ");
}

int main()
{
std::vector<int> v {
-1,  -2,  -3,  1,  2,  3,  4,  5,
-4,  -5,  -6,  6,  7,  8,  9, 10,
-7,  -8,  -9, 11, 12, 13, 14, 15,
-10, -11, -12, 16, 17, 18, 19, 20 };

std::size_t head_size { 3 };
std::size_t tail_size { 5 };

show("before reorder", v);

reorder(v.begin(), v.end(), head_size, tail_size);

show("after reorder", v);

return 0;
}

Скомпилируйте и запустите:

$ clang++ example.cpp -std=c++14
before reorder
-1  -2  -3   1   2   3   4   5
-4  -5  -6   6   7   8   9  10
-7  -8  -9  11  12  13  14  15
-10 -11 -12  16  17  18  19  20
after reorder
1   2   3   4   5   6   7   8
9  10  11  12  13  14  15  16
17  18  19  20  -1  -2  -3  -4
-5  -6  -7  -8  -9 -10 -11 -12

Подробности о проблемной области

Я читаю изображения, где каждый линия предшествует метаданным пикселя, а затем необработанным пикселям, например:

[metadata] [pixels...]
[metadata] [pixels...]
[ many more of these]
[metadata] [pixels...]

Мне нужно собрать все пиксели вместе и передать их в OpenGL, но мне также нужно поддерживать метаданные, доступные для программы. Итак, я делаю это:

 [all the pixels] [all the metadata]

и передать [all the pixels] к моей видеокарте, сохраняя при этом ручку [all the metadata] в процессоре.

редактировать

Спасибо за ваши ответы — в итоге я внедрил альтернативное решение, которое не зависит от переупорядочения. Однако остаётся вопрос: можете ли вы улучшить алгоритм переупорядочения набора данных «на месте»? Это похоже на вместо матрицы транспонировать.