Объединение нескольких отсортированных диапазонов

Question

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

#include <algorithm> 
#include <vector> 

template <typename OutputIterator> 
OutputIterator multi_merge (OutputIterator result) {return result;} 

template <typename InputIterator1, typename InputIterator2, typename OutputIterator, 
    typename... InputIterators1, typename... InputIterators2> 
OutputIterator multi_merge (InputIterator1 first1, InputIterators1... firsts1, 
InputIterator1 last1, InputIterators1... lasts1, 
InputIterator2 first2, InputIterators2... firsts2, InputIterator2 last2, 
InputIterators2... lasts2, OutputIterator result) { 
    // incorrect algorithm deleted 
    return multi_merge (firsts1..., lasts1..., firsts2..., lasts2..., result); 
} 

int main() { 
    std::vector<int> a = {3,4,6,1,2}, b = {6,8,9,2}, c = {6,7,4,5,2}, result; 
    std::sort (a.begin(), a.end()); 
    std::sort (b.begin(), b.end()); 
    std::sort (c.begin(), c.end()); 
    multi_merge (a.begin(), b.begin(), c.begin(), a.end(), b.end(), c.end(), 
     std::back_inserter(result)); 
} 

Кроме того, я хотел бы аргумент, чтобы быть в first1 порядке, last1, first2, last2, ..., а, но это незначительная вещь.

Редактировать: Я понимаю, что моя логика слияния неверна. Я думаю, что это так: сначала слить [a1, b1) с [a2, b2), а затем использовать полученный объединенный диапазон [merged1, merged2) и слить с [a3, b3) и т. Д. Таким образом, ошибка компиляции больше не является проблемой. Другая идея состоит в том, чтобы скопировать все элементы из каждого диапазона в контейнер и затем отсортировать (если это имеет смысл даже), но это не решение, которое я ищу, но я соглашусь, если это единственный способ.

Answer 1

Проблема заключается в том, что в каждом шаблоне не может быть более одного вариатора.

Как вы узнаете, с чего начать, а с другой стороны?

Answer 2

Хорошо, я изменил подпись функции с моего вступительного сообщения. И теперь он работает.

#include <iostream> 
#include <vector> 
#include <array> 
#include <algorithm> 

template <typename Container> 
std::vector<typename Container::value_type> multi_merge (const Container& container) { 
    return container; 
} 

template <typename Container1, typename Container2, typename... Containers> 
std::vector<typename Container1::value_type> multi_merge (const Container1& container1, 
const Container2& container2, const Containers&... containers) { 
    std::vector<typename Container1::value_type> v; 
    auto it = std::merge (container1.begin(), container1.end(), container2.begin(), 
     container2.end(), std::back_inserter(v)); 
    return multi_merge (v, containers...); 
} 

int main() { 
    std::vector<int> a = {3,4,6,1,2}, b = {6,8,9,2}, c = {6,7,4,5,2}, d = {3,2,4}; 
    std::array<int,6> e = {5,6,2,7,1,3}; 
    std::sort (a.begin(), a.end()); 
    std::sort (b.begin(), b.end()); 
    std::sort (c.begin(), c.end()); 
    std::sort (d.begin(), d.end()); 
    std::sort (e.begin(), e.end()); 
    const std::vector<int> result = multi_merge (a, b, c, d, e); 
    for (int x : result) std::cout << x << ' '; // 1 1 2 2 2 2 2 3 3 3 4 4 4 5 5 6 6 6 6 7 7 8 9 
} 

Я до сих пор удивляюсь, как это будет сделано с оригинальной подписью в своем вступительном посте, хотя, потому что подпись следует в духе станд :: слияния (с использованием только итераторов), и обобщает выходной контейнер с выходной итератор.