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;
}