fork download
copy 
  1. #include <iostream>
  2. #include <iterator>
  3. #include <algorithm>
  4. #include <functional>
  5. #include <utility>
  6. #include <vector>
  7. #include <cstdlib>
  8. #include <ctime>
  9.  
  10.  
  11. template<
  12.       typename InputIterator
  13.     , typename OutputIterator
  14.     , typename Compare = std::less<typename std::iterator_traits<InputIterator>::value_type>
  15. >
  16. OutputIterator
  17. merge(std::vector<std::pair<InputIterator, InputIterator>> input, OutputIterator output, Compare const compare = Compare()) {
  18.    using input_range = std::pair<InputIterator, InputIterator>;	
  19.  
  20.    auto const range_less = [=] (input_range lhs, input_range rhs) {
  21.    	  return compare(*lhs.first, *rhs.first);
  22.    };
  23.    auto const range_empty = [] (input_range range) {
  24.    	  return range.first == range.second;
  25.    };
  26.  
  27.    input.erase(std::remove_if(std::begin(input), std::end(input), range_empty), std::end(input));	
  28.  
  29.    while (!input.empty()) {
  30.       auto const min = std::min_element(std::begin(input), std::end(input), range_less);
  31.  
  32.       *output++ = *min->first++;
  33.  
  34.       if (range_empty(*min)) {
  35.          input.erase(min);
  36.       }
  37.    }
  38.  
  39.    return output;
  40. }
  41.  
  42.  
  43. int main() {
  44.    std::size_t const height = 10;
  45.    std::size_t const width  = 10;
  46.    int matrix[height][width];
  47.    int array[height * width];
  48.  
  49.    std::srand(std::time(nullptr));
  50.    for (auto & row : matrix) {
  51.       std::generate(std::begin(row), std::end(row), [] () { return std::rand() % 1000; });
  52.       std::sort(std::begin(row), std::end(row));
  53.    }
  54.  
  55.    std::cout << "before merge" << std::endl;
  56.    for (auto const& row : matrix) {
  57.       std::copy(std::begin(row), std::end(row), std::ostream_iterator<int>{std::cout, "\t"});
  58.       std::cout << std::endl;
  59.    }
  60.  
  61.    std::vector<std::pair<int *, int *>> rows(height);
  62.    for (std::size_t i = 0; i != height; ++i) {
  63.       rows[i] = {std::begin(matrix[i]), std::end(matrix[i])};
  64.    }
  65.    merge(rows, array);
  66.  
  67.    std::cout << "after merge" << std::endl;
  68.    std::copy(std::begin(array), std::end(array), std::ostream_iterator<int>{std::cout, "\t"});
  69.    std::cout << std::endl;
  70. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
before merge
87	337	597	599	617	657	735	917	920	978	
142	308	456	537	714	848	892	961	983	985	
7	10	115	302	469	594	633	773	839	995	
17	280	329	343	457	604	726	877	915	934	
58	231	258	404	539	764	866	871	886	895	
28	153	373	515	561	569	595	740	943	958	
96	161	196	205	477	523	706	706	938	980	
50	82	114	222	460	593	678	816	932	991	
30	191	296	336	450	767	854	916	931	988	
11	203	221	229	305	400	426	587	935	973	
after merge
7	10	11	17	28	30	50	58	82	87	96	114	115	142	153	161	191	196	203	205	221	222	229	231	258	280	296	302	305	308	329	336	337	343	373	400	404	426	450	456	457	460	469	477	515	523	537	539	561	569	587	593	594	595	597	599	604	617	633	657	678	706	706	714	726	735	740	764	767	773	816	839	848	854	866	871	877	886	892	895	915	916	917	920	931	932	934	935	938	943	958	961	973	978	980	983	985	988	991	995
https://ideone.com/C9VkKK
language:
C++14 (gcc 8.3)
created:
10 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!