fork download
copy 
  1. #include <vector>
  2. #include <queue>
  3. #include <iostream>
  4.  
  5.  
  6. template<
  7.     class InIts, 
  8.     typename OutIt,
  9.     class Cmp=std::less<typename std::iterator_traits<typename InIts::value_type::first_type>::value_type>>
  10. OutIt merge(const InIts &in_its, OutIt out_it, Cmp cmp=Cmp())
  11. {
  12.     using it_t = typename InIts::value_type::first_type;
  13.     using pair_t = std::pair<it_t, std::size_t>;
  14.     auto pair_cmp = [cmp](const pair_t &lhs, const pair_t &rhs) { return !cmp(*lhs.first, *rhs.first); };
  15.     using q_t = std::priority_queue<pair_t, std::vector<pair_t>, decltype(pair_cmp)>;
  16.  
  17.     std::vector<std::pair<it_t, it_t>> origs{in_its};
  18.     std::cout << origs.size() << std::endl;
  19.     q_t q{pair_cmp};
  20.  
  21.     for(std::size_t i = 0; i < origs.size(); ++i)
  22.     {   
  23.         auto &p = origs[i];
  24.         if(p.first != p.second) 
  25.             q.push(std::make_pair(p.first, i));
  26.     }
  27.  
  28.     while(!q.empty()) 
  29.     {
  30.         auto t = q.top();
  31.         *(out_it++) = *t.first;
  32.         const auto i = t.second;
  33.         q.pop();
  34.  
  35.         auto &p = origs[i];
  36.         if(++p.first != p.second)
  37.             q.push(std::make_pair(p.first, i));
  38.     }
  39.  
  40.     return out_it;
  41. }
  42.  
  43.  
  44. int main()
  45. {
  46.     using vec_t = std::vector<int>;
  47.  
  48.     vec_t v0{1, 2, 3}; 
  49.     vec_t v1{2, 3, 4}; 
  50.     vec_t v2{4, 5, 6}; 
  51.  
  52.     using vec_it_t = vec_t::iterator;
  53.  
  54.     std::vector<std::pair<vec_it_t, vec_it_t>> its{
  55.         std::make_pair(std::begin(v0), std::end(v0)),
  56.         std::make_pair(std::begin(v1), std::end(v1)),
  57.         std::make_pair(std::begin(v2), std::end(v2))};
  58.  
  59.     vec_t res;
  60.     merge(its, std::back_inserter(res));
  61.     for(auto &e: res)
  62.         std::cout << e << std::endl;
  63. }
  64.  
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
1
2
2
3
3
4
4
5
6
https://ideone.com/h2LfZc
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!