Ad
arkevs.Arkadaq

Merge two sorted lists

Different algorithm: Rather than searching every time, it now iterates both lists at the same time, picking whichever is closest. Also, it now takes its parameters by ref to avoid unnecessary copies.

This could be generalized to arbitrary containers and arbitrary template parameters.

Code
Diff
  • #include <algorithm>
#include <list>

using std::list;

list<int> merge_list(const list<int>& a, const list<int>& b) {
  list<int> result;
  auto ia = a.begin();
  auto ib = b.begin();
  while (ia != a.end() && ib != b.end()) {
    if (*ia < *ib)
      result.push_back(*ia++);
    else
      result.push_back(*ib++);
  }
  result.insert(result.end(), ia, a.end());
  result.insert(result.end(), ib, b.end());
  return result;
}
    • #include <algorithm>
    • #include <list>
    • using std::list;
    • // just pretend that std::list::merge doesn't exist when you're reading this code
    • // this isn't that great a solution even if you do that, but I wanted to mirror the forked kumite a little
    • list<int> merge_list(list<int> a, list<int> b) {
    • auto i = a.begin();
    • for (auto x: b) {
    • i = a.insert(find_if(i, a.end(), [x](int &y) {return y > x;}), x);
    • list<int> merge_list(const list<int>& a, const list<int>& b) {
    • list<int> result;
    • auto ia = a.begin();
    • auto ib = b.begin();
    • while (ia != a.end() && ib != b.end()) {
    • if (*ia < *ib)
    • result.push_back(*ia++);
    • else
    • result.push_back(*ib++);
    • }
    • return a;
    • result.insert(result.end(), ia, a.end());
    • result.insert(result.end(), ib, b.end());
    • return result;
    • }