#include <iostream>
#include <vector>
#include <thread>
#include <chrono>

void GetNext(int n)
{
  std::this_thread::sleep_for(std::chrono::milliseconds(n*500));
  std::cout << "GetNext << " << n << std::endl;
}


void Start(int* p, size_t sz)
{
    for(size_t i = 0; i < sz; i++)
      std::thread(GetNext, p[i]);
}


int main(int argc, char * argv[])
{
    int vec1[] = {1, 5, 12, 28, 31};
    int vec2[] = {6, 9, 13};
    int vec3[] = {3, 7, 10, 15};

    Start(vec1, sizeof(vec1)/sizeof(int));
    Start(vec2, sizeof(vec2)/sizeof(int));
    Start(vec3, sizeof(vec3)/sizeof(int));
  
    std::this_thread::sleep_for(std::chrono::seconds(30));
    return 0;
}

Тест

#define _HAS_ITERATOR_DEBUGGING 0
#define _SECURE_SCL 0

#include <boost/exception/detail/type_info.hpp>
#include <boost/range/algorithm_ext.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/timer/timer.hpp>
#include <exception>
#include <iostream>
#include <iterator>
#include <vector>
#include <list>

#if defined(__GNUC__)
    #define NOINLINE __attribute__ ((noinline))
#elif defined(_MSC_VER)
    #define NOINLINE __declspec(noinline)
#else
    #define NOINLINE
#endif

template<int> NOINLINE void ASM_MARKER() { volatile int x = 0; (void)x; }

/******************************************************************************/
using namespace std;

template<typename Range>
void test(Range &r)
{
    cout << boost::type_name<Range>() << ": ";

    boost::timer::auto_cpu_timer t;

    ASM_MARKER<111>();
    volatile int result = boost::accumulate(r, 0);
    ASM_MARKER<222>();

    (void)result;
}

int main() try
{
    vector<int> v(40000000);
    boost::iota(v, 0);
    boost::random_shuffle(v);

    list<int> l(begin(v), end(v));

    l.sort();
    boost::sort(v);

    for(unsigned i=0; i!=2; ++i)
    {
        test(v);
        test(l);
    }
}
catch(const exception &e)
{
    cout << e.what() << endl;
}

class std::vector<int,class std::allocator<int> >:  0.022010s wall, 0.015600s user + 0.000000s system = 0.015600s CPU (70.9%)
class std::list<int,class std::allocator<int> >:  4.811541s wall, 4.820431s user + 0.000000s system = 4.820431s CPU (100.2%)
class std::vector<int,class std::allocator<int> >:  0.023067s wall, 0.031200s user + 0.000000s system = 0.031200s CPU (135.3%)
class std::list<int,class std::allocator<int> >:  4.812521s wall, 4.820431s user + 0.000000s system = 4.820431s CPU (100.2%)

; vector
$LL61@test:
    add    ebx, DWORD PTR [rax]
    add    rax, 4
    cmp    rax, r11
    jne    SHORT $LL61@test
    
; list
$LL82@test@2:
    add    ebx, DWORD PTR [rax+16]
    mov    rax, QWORD PTR [rax]
    cmp    rax, r11
    jne    SHORT $LL82@test@2

while(!q.empty())
{
    auto range = heap.top();  
    q.pop();

    //assert(!empty(range));
    *out++ = *begin(range);
    range = make_iterator_range(next(begin(range)), end(range));
    if(!empty(range))
        q.push(range);
}

_> Вообще-то такое должно на автомате писаться. Ну я так думаю

_> Основоположники, ЕМНИП, учили использовать unsigned там и только там, где требуются операции с битами.

bool is_valid_index(int i, int size)
{
    return i >= 0 && i < size;
}

bool is_valid_index(unsigned i, unsigned size)
{
   return i < size;
}

void process_string(char const* str, int len);

// приходится их использовать так:
std::string str = "fgfg";
process_string(str.data(), static_cast<int>(str.size()));

EP>while(!q.empty())
EP>{
EP>    auto range = heap.top();  
EP>    q.pop();

EP>    //assert(!empty(range));
EP>    *out++ = *begin(range);
EP>    range = make_iterator_range(next(begin(range)), end(range));
EP>    if(!empty(range))
EP>        q.push(range);
EP>}
EP>

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

using namespace std;

typedef vector<int> list_type;

void print(const vector<list_type>& in) {
    using list_iter = pair < list_type::const_iterator, list_type::const_iterator >;
    using iter_state = vector < list_iter >;
    iter_state iters;
    iters.reserve(in.size());
    for(auto& l : in)
        if(!l.empty())
            iters.push_back({ l.begin(), l.end() });

    auto iter_compare = [](const list_iter& i1, const list_iter& i2) {
        return *i1.first > *i2.first;
    };
    make_heap(iters.begin(), iters.end(), iter_compare);
    while(!iters.empty()) {
        pop_heap(iters.begin(), iters.end(), iter_compare);
        list_iter& min = iters.back();
        cout << *min.first << endl;
        ++min.first;
        if(min.first == min.second)
            iters.pop_back();
        else
            push_heap(iters.begin(), iters.end(), iter_compare);
    }
}

int main(int argc, char* argv[])
{
    vector<list_type> lists = {
            { 1, 5, 12, 28, 31 },
            { 6, 9, 13 },
            { 3, 7, 10, 15 }
    };
    print(lists);
    return 0;
}

template<T> inc(T::iterator& i) { ++i; }

template <typename C> traverse_test(const C& c) {
    volatile auto x = accumulate(c.begin(), c.end(), 0);
}

.L5:
        addl    8(%rax), %edx  // сложили в аккумулятор
        movq    (%rax), %rax   // взяли адрес следующего элемента
        testq   %rax, %rax     // проверили, что список не закончился
        jne     .L5            // и начали обрабатывать следующий элемент

.L5:
        addl    (%rax), %edx   // сложили в аккумулятор
        addq    $4, %rax       // взяли адрес следующего элемента
        cmpq    %rax, %rcx     // проверили, что список не закончился
        jne     .L5            // и начали обрабатывать следующий элемент

.L15:
        addq    $1, %rdx       // обновили счётчик
        paddd   (%rsi), %xmm0  // сложили в аккумулятор 
        addq    $16, %rsi      // взяли адрес следующего элемента
        cmpq    %rdx, %r9      // проверили счётчик
        ja      .L15           // и начали обрабатывать следующий элементы

list    590 ms // c и без автовекторизации
vector  103 ms // без автовекторизации
vector  43  ms // c автовекторизацией

К>>int main()
К>>{
К>>    sources = vector< list<int> > {
К>>        list<int> { 1, 5, 12, 28, 31 },
К>>        list<int> { 6, 9, 13 },
К>>        list<int> { 3, 7, 10, 15 },
К>>    };
К>>}

....

vector<vector<int>*> vectors;//тут хранятся наши списки

vector<int> vec1;
vector<int> vec2;
vector<int> vec3;//сами списки

....

vectors.push_back(&vec1);
vectors.push_back(&vec2);
vectors.push_back(&vec3);

vector<int> indexes(vectors.size(),0);//тут храним индекс элемента, который последний раз брали для каждого из списков

GetNext(indexes);
....


bool isExist(vector<int> &vec, int index)
{
    return index < vec.size();
}

int GetNext( vector<int> &indexes)
{
    int min = 0;
    int index = -1;
    for(int i=0;i<vectors.size();++i)
    {
        if(isExist(*vectors.at(i),indexes.at(i)))
        {
            min = vectors.at(i)->at(indexes.at(i));
            index = i;
            break;
        }
    }
    
    if(index == -1)
        throw exception();
    
    for(int i=0;i<vectors.size();++i)
    {
        if(isExist(*vectors.at(i),indexes.at(i)))
        {
            if(vectors.at(i)->at(indexes.at(i))<min)
            {
                min = vectors.at(i)->at(indexes.at(i));
                index = i;
            }
        }
    }
    
    indexes.at(index)++;
    
    return vectors.at(index)->at(indexes.at(index)-1);
    
}

PM>int GetNext()
PM>{
PM>    int min_head = 0;
PM>    for (int i = 0; i < NUM_LISTS; ++i)
PM>    {
PM>        if (heads[i] == lists[i].end()) continue;
PM>        if (*heads[i] < *heads[min_head]) min_head = i; // свалится, когда heads[0] == lists[0].end()
PM>    }
        
PM>    if (heads[min_head] == lists[min_head].end())
PM>        throw exception(); // end of lists

PM>    int min = *heads[min_head];
PM>    ++heads[min_head];
PM>    return min; 
PM>}
O>>}
O>>

 
    int min = *heads[min_head];
    ++heads[min_head];
    return min;

    return *(heads[min_head]++);

Наташенька, ну вы же сами просили сказать, что я думаю

PM>>        if (heads[i] == lists[i].end()) continue;
PM>>        if (*heads[i] < *heads[min_head]) min_head = i; // свалится, когда heads[0] == lists[0].end()

_> 
_>    int min = *heads[min_head];
_>    ++heads[min_head];
_>    return min;
_>
_>    return *(heads[min_head]++);
_>

return *heads[min_head]++;

PM>С чего бы, если строкой выше есть проверка с комментарием "пропускаем пройденный список"

 
PM>int GetNext()
PM>{
PM>    int min_head = 0; // Пусть, первый список уже пуст. Тогда heads[min_head] == lists[min_head].end()
PM>    for (int i = 0; i < NUM_LISTS; ++i)
PM>    {
PM>        if (heads[i] == lists[i].end()) continue; // сработает при i == 0
           // здесь мы оказываемся при i == 1, и разыменовываем heads[min_head], т.е. heads[0], т.е. lists[0].end()
           // всё пропало!
PM>        if (*heads[i] < *heads[min_head]) min_head = i;
PM>    }
        
PM>    if (heads[min_head] == lists[min_head].end())
PM>        throw exception(); // end of lists

PM>    int min = *heads[min_head];
PM>    ++heads[min_head];
PM>    return min; 
PM>}
O>>}

_>Ну, это еще ничего не доказывает

 
int GetNext()
{
    int min_head = -1;
    for (int i = 0; i < NUM_LISTS; ++i)
    {
        if (heads[i] == lists[i].end()) continue;
        if (min_head == -1 || *heads[i] < *heads[min_head]) min_head = i;
    }

    if (min_head == -1)
        throw exception();

    int min = *heads[min_head];
    ++heads[min_head];
    return min;
}

vectors.at(i)

O>....

O>vector<vector<int>*> vectors;//тут хранятся наши списки

O>vector<int> vec1;
O>vector<int> vec2;
O>vector<int> vec3;//сами списки

O>....

O>vectors.push_back(&vec1);
O>vectors.push_back(&vec2);
O>vectors.push_back(&vec3);

O>vector<int> indexes(vectors.size(),0);//тут храним индекс элемента, который последний раз брали для каждого из списков

O>GetNext(indexes);
O>....


O>bool isExist(vector<int> &vec, int index)
O>{
O>    return index < vec.size();
O>}

O>int GetNext( vector<int> &indexes)
O>{
O>    int min = 0;
O>    int index = -1;
O>    for(int i=0;i<vectors.size();++i)
O>    {
O>        if(isExist(*vectors.at(i),indexes.at(i)))
O>        {
O>            min = vectors.at(i)->at(indexes.at(i));
O>            index = i;
O>            break;
O>        }
O>    }
    
O>    if(index == -1)
O>        throw exception();
    
O>    for(int i=0;i<vectors.size();++i)
O>    {
O>        if(isExist(*vectors.at(i),indexes.at(i)))
O>        {
O>            if(vectors.at(i)->at(indexes.at(i))<min)
O>            {
O>                min = vectors.at(i)->at(indexes.at(i));
O>                index = i;
O>            }
O>        }
O>    }
    
O>    indexes.at(index)++;
    
O>    return vectors.at(index)->at(indexes.at(index)-1);
    
O>}
O>

template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
                            ForwardIterator2 first2, ForwardIterator2 last2)

template<class ForwardRange1, class ForwardRange2>
typename range_iterator<ForwardRange1>::type
search(ForwardRange1& rng1, const ForwardRange2& rng2);

_>> Откуда порядки? Обход вектора — грубо говоря — выкомпилируется в инкремент адреса на константу. Обход связного списка — в чтение адреса следующего элемента.

  4006fc:       48 8b 45 f8             mov    -0x8(%rbp),%rax
  400700:       48 8b 00                mov    (%rax),%rax
  400703:       48 89 45 f8             mov    %rax,-0x8(%rbp)

  
  4006f9:       8b 45 fc                mov    -0x4(%rbp),%eax
  4006fc:       8d 50 01                lea    0x1(%rax),%edx
  4006ff:       89 55 fc                mov    %edx,-0x4(%rbp)
  400702:       48 98                   cltq   
  400704:       8b 84 85 60 fe ff ff    mov    -0x1a0(%rbp,%rax,4),%eax
  40070b:       89 45 f8                mov    %eax,-0x8(%rbp)

template <typename T, int N, template <typename...> class U, template <typename...> class P >
 struct iter {
  typedef U<T> value_array;
  typedef P<value_array*> pointer_array;
  iter(const pointer_array& u): mas(u), msz(mas.size()),
                sz(0), current(0)
  {  size_t n=msz, m=0, tmp;
    max_sz=0;
      while(m<n)
       {
        tmp=mas[m]->size();
        index[m]=0;
        max_sz+=tmp;
        sz1[m++]=tmp;
       
       };
     
     };

  bool allow(size_t n){ return sz1[n] > index[n]; };
  const pointer_array& mas;
  size_t sz;
  size_t msz;
  size_t sz1[N];
  size_t index[N];
  size_t max_sz;
  size_t current;
 };
 

template <typename T, int N, template <typename...> class U, template <typename...>  class P>
T* GetNext(iter<T, N, U, P>& m){
  typedef typename iter<T, N, U, P>::value_array value_array;
  T* p=NULL;
  size_t  lim=m.msz, cnt=0, tmp=m.sz;
  if(tmp == m.max_sz) return NULL;
  tmp=m.current;
  if(!m.allow(tmp))
   {
     while(cnt< lim)
       {
    if(m.allow(cnt))
         {  
       tmp=cnt; m.current=tmp; break;
         };
    ++cnt;
       };
       if(cnt==lim) return NULL;
     }; 
  
  value_array& ref=*m.mas[tmp];
   p=const_cast<T*>(std::addressof(ref[m.index[tmp]]));
   cnt=0;
   while(cnt < lim){
     if(!m.allow(cnt)){ ++cnt; continue; }
     tmp=m.index[cnt];
     value_array& ref=*m.mas[cnt];
     if(p)
       {
     if(ref[tmp] < *p)
            {
             p=const_cast<T*>(std::addressof(ref[tmp]));
             m.current=cnt;         
        }
       };
     ++cnt;
       };
  ++m.sz;
  ++m.index[m.current];
  return p;
 };

#include <vector>
#include <list>
#include <set>
#include <iostream>
#include <stdint.h>

std::set<int32_t> GetNext(const std::vector<std::list<int32_t>> &source)
{
    if (source.empty()) return std::set<int32_t>();

    std::set<int32_t> result;
    for (uint32_t sourceIndex = 0; sourceIndex < source.size(); ++sourceIndex) {
        result.insert(source[sourceIndex].begin(), source[sourceIndex].end());
    }
    return result;
}
int main()
{
    std::list<int32_t> source1 = { 1, 5, 12, 28, 31 };
    std::list<int32_t> source2 = { 6, 9, 13 };
    std::list<int32_t> source3 = { 3, 7, 10, 15 };

    std::vector<std::list<int32_t>> sources;
    sources.push_back(source1);
    sources.push_back(source2);
    sources.push_back(source3);

    auto result = GetNext(sources);
    for (auto value : result) {
        std::cout << value << std::endl;
    }

    return 0;
}

template<>
  class allocator<void>
  {
  public:
  typedef size_t size_type;

E>Одно из уродств STL в том, что в ней по умолчанию лучше брать list...

23.2.3 Sequence containers
The sequence containers offer the programmer different complexity trade-offs and should be used accordingly. vector or array is the type of sequence container that should be used by default. list or forward_list should be used when there are frequent insertions and deletions from the middle of the sequence. deque is the data structure of choice when most insertions and deletions take place at the beginning or at the end of
the sequence.

S>int main(int argc, char* argv[])
S>{
S>    vector<list_type> lists = {
S>            { 1, 5, 12, 28, 31 },
S>            { 6, 9, 13 },
S>            { 3, 7, 10, 15 }
S>    };
S>    print(lists);
S>    return 0;
S>}
S>

template<typename TIter, typename TElem = typename TIter::value_type>
class CSeqMerger {
public:
    template<typename TCont>
    CSeqMerger& operator << ( TCont& c ) 
    {
        add( c.begin(), c.end() );
        return *this;        
    } 

    bool IsEmpty() const
         { return data.empty(); }
    TElem GetNext() 
    {
        assert( !IsEmpty() );
        std::vector<rahge_t>::iterator m = min_element( data.begin(), data.end(), predicate );
        TElem res = *m->first++;
        if( m->first == m->second ) {
            data.erase( m );
        }
        return res;
    }
private:
    typedef std::pair<TIter, TIter> range_t;
    std::vector<range_t> data;
    static bool predicate( const range_t& a1, const range_t& a2 ) 
        { return *a1->first < *a2->first; }
    add( TIter beg, TIter end ) 
        { data.push_back( range_t( beg, end ) ); }
};

template<typename TCont> CSeqMerger<TCont::const_iterator> GetSeqMerger( const TCont c )
{
    CSeqMerger<TCont::const_iterator> res;
    res << c;
    return res;
}

template<typename TOut, typename TSeq> void print( TOut& o, TSeq seq )
{
    while( !seq.IsEmpty() )
        o << seq.GetNext() << " ";
}

int main(int argc, char* argv[])
{
    vector<int> 
        a = { 1, 5, 12, 28, 31 },
        b = { 6, 9, 13 },
        c = { 3, 7, 10, 15 }
    ;
    
    print( std::cout, GetSeqMerger( a ) << b << c );
    return 0;
}

return partition_point_n(first, distance(first, last), p);

while(!q.empty())
{
    auto range = heap.top();  
    q.pop();
    if(!q.empty())
    {
        auto ceiling = *begin(heap.top());
        auto last = upper_bound(range, ceiling); // can be linear or binary search
        copy(begin(range), last, out)

        range = make_iterator_range(last, end(range));
        if(!empty(range))
            q.push(range);
    }
    else
    {
        copy(range, out);
    }
}

25.4.6.1 push_heap
Complexity: At most log(last — first) comparisons.

25.4.6.2 pop_heap
Complexity: At most 2 * log(last — first) comparisons.

#include "stdafx.h"

#include <iostream>

int a1[] = { 1, 5, 12, 28, 31 };
int a2[] = { 6, 9, 13 };
int a3[] = { 3, 7, 10, 15 };

int s[] = { sizeof(a1) / sizeof (int),
            sizeof(a2) / sizeof (int),
            sizeof(a3) / sizeof (int) };

int i[] = { 0, 0, 0 };
int * a[] = { a1, a2, a3 };

bool GetMin(int *a, int &n, int s, int &val)
{
    if (n < s && (val == 0 || a[n] < val))
    {
        val = a[n];
        return true;
    }
    return false;
}

bool GetNext(int &val)
{
    int ndx = -1;

    val = 0;

    for (int k = 0; k < 3; ++k)
    {
        if (i[k] >= 0 && GetMin(a[k], i[k], s[k], val) != false)
            ndx = k;
    }

    if (ndx >= 0)
    {
        if (i[ndx] >= s[ndx])
            i[ndx] = -1;
        else
            i[ndx] += 1;
        return true;
    }

    return false;
}

int main(int argc, char* argv[])
{
    int val = 0;
    while (GetNext(val))
    {
        std::cout << val << std::endl;
    }

    return 0;
}