C ++ STL чередование двух диапазонов

Question

Я сделал что-то для достижения чередования двух диапазонов.Вот проблема.

Скажем, у меня есть два диапазона [a1, b1), call R1 и [a2, b2) call R2.Пока предположим, что их std::distance результаты совпадают, скажем n.Я хочу написать алгоритм

std::interleave(a1, b1, a2, b2, bool swap)

Это позволит изменить порядок элементов таким образом, что один элемент R2 будет следовать элементу R1 через все элементы 2n.В зависимости от значения swap, оно также должно быть переупорядочено, так как за одним элементом R1 следует элемент R2.

Я сделал это, используя дополнительное хранилище и два для циклов.Это решение легко.Я также мог бы придумать решение на месте, если бы попытался немного дольше.Но что я хочу, так это то, что я хочу достичь этой цели, собирая алгоритмы из STL.Как вы можете решить эту проблему с помощью STL?Лучше, если решение будет на месте, но я также открыт для использования дополнительного хранилища, если мы используем алгоритмы из STL.

РЕДАКТИРОВАТЬ: перестановка элементов в указанных диапазонах не должнабыть изменен.Другими словами, это должно быть что-то вроде stable_interleave.Вот почему я не смог придумать что-то, что использует std::merge.

ПРИМЕНЕНИЕ. Одним из применений этого является преобразование форматов видео и изображений из плоских в непланарные или полуплоскостные.

Answer 1

Мой шаг использования std::merge может закончиться неудачей. Я не достаточно изобретателен, чтобы понять, почему кто-то может написать merge, чтобы это могло, но это нарушает требования для Сравните , как указано в комментариях ниже, чтобы кто-то мог.

Независимо от того, merge - это решение для перерасхода. Это меньше строк кода, скрывающих дополнительные усилия, потому что предполагаемое использование merge для более сложной работы, чем мы делаем здесь.

Пример:

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <list>
#include <deque>

template<typename IN1,
         typename IN2,
         typename OUT>
inline OUT interleave(IN1 it1,
                      IN1 end1,
                      IN2 it2,
                      IN2 end2,
                      OUT out)
{
    // interleave until at least one container is done
    while (it1 != end1 && it2 != end2) 
    {
        // insert from container 1
        *out = *it1;
        out++;
        it1++;
        // insert from container 2
        *out = *it2;
        out++;
        it2++;
    }
    if (it1 != end1) // check and finish container 1
    {
        return std::copy (it1, end1, out);
    }
    else if (it2 != end2)// check and finish container 2
    {
        return std::copy (it2, end2, out);
    }
    return out; // both done
}

int main()
{
    // fill the containers  with numbers
    std::vector<int> in1 = {1,3,5,7,9};
    std::list<int> in2 = {8,6,4,2};

    // construct output container of sufficient size.
    // Could also use empty container and *_inserter
    std::deque<int> out(in1.size() + in2.size());

    // Container-agnostic. reads from vector and list and stores in deque
    interleave(in1.begin(), in1.end(),
               in2.begin(), in2.end(),
               out.begin());
    for (int val: out)
    {
        std::cout << val << ' ';
    }
}

Примечание: вместо того, чтобы реализовывать с опцией, чтобы поменять местами порядок ввода и заставить всех пользователей interleave платить за это, вызывающий должен вызывать с обратным порядком ввода параметров.