@jinxonik / UniLecs #211

flist_merge1.cpp

#include <iostream>
#include <forward_list>

using std::cout;
using std::forward_list;
using std::next;

template <typename T>
forward_list<T> forward_list_merge(forward_list<T> list1, const forward_list<T>& list2)
{
  if (!list2.empty()) {
    auto it2 = list2.begin();
    if (list1.empty() || *next(list1.begin()) > *it2) {
      list1.push_front(*it2++);
    }
    for (auto it1 = list1.begin(); it2 != list2.end(); it2++) {
      while (next(it1) != list1.end() && *next(it1) <= *it2) { ++it1; }
      list1.insert_after(it1, *it2);
    }
  }
  return list1;
}

int main()
{
  forward_list<int> list1 { 1, 2, 4, 6, 9, 12 };
  forward_list<int> list2 { -2, -1, 0, 2, 3, 5, 7, 9, 13, 15 };
  forward_list<int> list3 = forward_list_merge(std::move(list1), list2);

  cout << "{ ";
  for (auto n : list3) {
    cout << n << " ";
  }
  cout << "}\n";

  return 0;
}

flist_merge2.cpp

#include <iostream>
#include <forward_list>

using std::cout;
using std::forward_list;
using std::next;

template <typename T>
forward_list<T> forward_list_merge(forward_list<T> list1, const forward_list<T>& list2)
{
  if (!list2.empty()) {
    auto it2 = list2.begin();
    if (list1.empty() || *next(list1.begin()) > *it2) {
      list1.push_front(*it2++);
    }
    auto it1 = list1.begin();
    do {
      while ((it2 != list2.end()) && (next(it1) == list1.end() || *next(it1) > *it2)) {
        list1.insert_after(it1, *it2++);
      }
    } while (++it1 != list1.end());
  }
  return list1;
}

int main()
{
  forward_list<int> list1 { 1, 2, 4, 6, 9, 12 };
  forward_list<int> list2 { -2, -1, 0, 2, 3, 5, 7, 9, 13, 15 };
  forward_list<int> list3 = forward_list_merge(std::move(list1), list2);

  cout << "{ ";
  for (auto n : list3) {
    cout << n << " ";
  }
  cout << "}\n";

  return 0;
}

flist_merge3.cpp

#include <iostream>
#include <forward_list>

using std::cout;
using std::forward_list;

template <typename T>
forward_list<T> forward_list_merge(const forward_list<T>& list1, const forward_list<T>& list2)
{
  forward_list<T> list3;
  if (list1.empty() && list2.empty()) { return list3; }

  list3.push_front(0);
  auto it1 = list1.begin(), it2 = list2.begin(), it3 = list3.begin();

  while (it1 != list1.end() && it2 != list2.end()) {
    list3.insert_after(it3, (*it1 <= *it2 ? *it1++ : *it2++));
    ++it3;
  }
  while (it1 != list1.end()) {
    list3.insert_after(it3, *it1++);
    ++it3;
  }
  while (it2 != list2.end()) {
    list3.insert_after(it3, *it2++);
    ++it3;
  }

  list3.pop_front();
  return list3;
}

int main()
{
  forward_list<int> list1 { 1, 2, 4, 6, 9, 12 };
  forward_list<int> list2 { -2, -1, 0, 2, 3, 5, 7, 9, 13, 15 };
  forward_list<int> list3 = forward_list_merge(list1, list2);

  cout << "{ ";
  for (auto n : list3) {
    cout << n << " ";
  }
  cout << "}\n";

  return 0;
}

flist_merge4.cpp

#include <iostream>
#include <forward_list>

using std::cout;
using std::forward_list;

// it указывает на элемент, после которого должна быть вставка.
// Если list пуст, значение it не важно.
template <typename T>
void forward_list_add(forward_list<T>& list, typename forward_list<T>::iterator& it, const T& value)
{
  if (list.empty()) {
    list.push_front(value);
    it = list.begin();
  } else {
    list.insert_after(it, value);
    ++it;
  }
}

template <typename T>
forward_list<T> forward_list_merge(const forward_list<T>& list1, const forward_list<T>& list2)
{
  forward_list<T> list3;
  if (list1.empty() && list2.empty()) { return list3; }
  auto it1 = list1.begin(), it2 = list2.begin(), it3 = list3.begin();

  while (it1 != list1.end() && it2 != list2.end()) {
    forward_list_add(list3, it3, (*it1 <= *it2 ? *it1++ : *it2++));
  }
  while (it1 != list1.end()) {
    forward_list_add(list3, it3, *it1++);
  }
  while (it2 != list2.end()) {
    forward_list_add(list3, it3, *it2++);
  }
  return list3;
}

int main()
{
  forward_list<int> list1 { 1, 2, 4, 6, 9, 12 };
  forward_list<int> list2 { -2, -1, 0, 2, 3, 5, 7, 9, 13, 15 };
  forward_list<int> list3 = forward_list_merge(list1, list2);

  cout << "{ ";
  for (auto n : list3) {
    cout << n << " ";
  }
  cout << "}\n";

  return 0;
}