C++ std::list Operations

To sort the doubly linked list std::list, we can simply call the sort() member function. For example,

#include <iostream>
#include <list>

int main() {
  std::list<int> xs{5, 4, 3, 2, 1};

  xs.sort();  // Sort the std::list!

  for (auto &x : xs) {
    std::cout << x << std::endl;
  }
}

We can't replace xs.sort() with std::sort(xs), because the std::sort() function from <algorithm> header requires random access iterator as the input argument. Unfortunately, std::list only provides bidirectional iterator. That's why the C++ standard library provides an std::list-specific sort function.

To move the nodes in std::list, we can call the member function splice(). For example, we can move the second element to the beginning of the list with:

#include <iostream>
#include <list>

int main() {
  std::list<int> xs{5, 4, 3, 2, 1};

  // Find the iterator to the second element
  std::list<int>::iterator second(xs.begin());
  ++second;

  // Move the second node to the beginning of xs
  xs.splice(xs.begin(), xs, second);

  for (auto &x : xs) {
    std::cout << x << std::endl;
  }
}

The splice() function can move the a sequence of nodes from one list to the other as well. For example,

#include <algorithm>
#include <iostream>
#include <list>

void move_nelements(std::list<int> &dst, std::list<int> &src, size_t n) {
  // Find the iterator to the n-th element
  std::list<int>::iterator it(src.begin());
  std::advance(it, n);

  // Move the elements
  dst.splice(dst.begin(), src, src.begin(), it);
}

int main() {
  std::list<int> xs{5, 4, 3, 2, 1};
  std::list<int> ys;

  move_nelements(ys, xs, 4);

  for (auto &y : ys) {
    std::cout << y << std::endl;
  }
}

To test our understanding, let's write our merge_sort() for std::list. Here's the code:

#include <algorithm>
#include <iostream>
#include <list>

template <typename T, typename Alloc, typename Compare>
void merge_sort_helper(std::list<T, Alloc>& xs,
                       size_t num_elem,
                       Compare is_less_than) {
  typedef std::list<T, Alloc> list;
  typedef typename list::iterator iterator;

  // Induction basis: List with small number of elements.
  switch (num_elem) {
  case 0:
  case 1:
    return;
  case 2:
    {
      iterator first(xs.begin());
      iterator second(xs.begin());
      ++second;
      if (is_less_than(*second, *first)) {
        // Swap the node if they are not ordered
        xs.splice(first, xs, second);
      }
      return;
    }
  }

  // Partition
  size_t mid = num_elem / 2;
  iterator mid_iter(xs.begin());
  std::advance(mid_iter, mid);

  // Split the list
  list ys;
  ys.splice(ys.begin(), xs, mid_iter, xs.end());

  // Sort the xs and ys
  merge_sort_helper(xs, mid, is_less_than);
  merge_sort_helper(ys, num_elem - mid, is_less_than);

  // Merge the ys back to xs
  iterator xs_it = xs.begin();
  iterator xs_end = xs.end();
  iterator ys_it = ys.begin();
  iterator ys_end = ys.end();

  while (xs_it != xs_end && ys_it != ys_end) {
    if (is_less_than(*ys_it, *xs_it)) {
      // *ys_it is less than *xs_it, thus insert ys_it before xs_it.
      xs.splice(xs_it, ys, ys_it++);
    } else {
      ++xs_it;
    }
  }

  xs.splice(xs_end, ys, ys_it, ys_end);
}

template <typename T, typename Alloc, typename Compare = std::less<T> >
void merge_sort(std::list<T, Alloc>& xs,
                Compare is_less_than = Compare()) {
  merge_sort_helper(xs, xs.size(), is_less_than);
}

int main() {
   std::list<int> xs{4, 5, 3, 2, 1};
   merge_sort(xs);
   for (auto &x : xs) {
     std::cout << x << std::endl;
   }
}

Let's call it a day. In this article, we have introduced the usage of std::list<T>::sort() and std::list::splice(). Hope you enjoy this article.

C++ std::list Operations

Logan's Note