Recent Posts

Flattening lists of lists of lists of…

Recently i answered a question on StackOverflow, and i thought it was a good example of a code that is efficient and elegant, and decided to post it here. The problem was, having a std::list of other lists of T, we want to flatten the list and obtain a std::list of T containing all the element of the given structure. Basically, we want to find all lists of T and put it in our result, the depth being unknown.

So let’s start by the first problem. We need to know what type T is. So how to recover it automatically? We’ll use for that a structure:

template <typename T>
struct NestedListType {
  using type = T;
};

Given a type, it only gives the same type. To give the type inside the list, we need to specialize it:


template <typename T>
struct NestedListType<std::list<T> > {
  using type = typename NestedListType<T>::type;
};

Now if our type is a list, it will give the value_type of the std::list, and so recursively until the type is not a std::list. So it can work with several layers of std::list.

It is used that way:

// DataType will be int
using DataType = typename NestedListType<std::list<std::list<int>>>::type;

Next we need to define our function. We want a function that will put every list of the nested type inside one big list. To avoid unnecessary copies we will pass our resulting list in parameter of our function too, so we need a first function that will do that:

// if we do not want to modify the original list, this is here where you should remove the reference and make a copy
// T could be itself an std::list, no problem with that
template <typename T>
std::list<typename NestedListType<T>::type> flatten(std::list<T> & list) {
  // obtain a std::list with the appropriate type
  std::list<typename NestedListType<T>::type> result;
  flatten(list, result);
  return result;
}

And finally we need to do the actual work. What we need is two functions: one that receives a list of lists and dispatch each list, and one that receives a list and add it to our result. For that we will simply use overloading, as we cannot (and do not need to) partially specialize functions:

template <typename T, typename V>
void flatten(std::list<std::list<T> > & list, std::list<V> & result) {
  // if we want to change the order or the resulting list, change here
  // here simply add the first list first and continue until the last
  for (auto & sublist : list)
    flatten(sublist, result);
}

template <typename T, typename V>
void flatten(std::list<T> & list, std::list<V> & result) {
  // add the list to our result using references and splice to avoid unecessary copies or move
  result.splice(result.end(), list);
}

And that’s all! Now, we can simply use it with as much list and sublist we want:

std::list<int> l1{ 1, 2, 3 };
std::list<int> l2{ 4, 5, 6 };
std::list<int> l3{ 7, 8, 9 };
std::list<int> l4{ 10, 11, 12 };

std::list<std::list<int> > sl1{ l1, l2 };
std::list<std::list<int> > sl2{ l3, l4 };

std::list<std::list<std::list<int> > > ssl{ sl1, sl2 };

auto result1 = flatten(l1); // gives { 1, 2, 3 }
auto result2 = flatten(sl1); // gives { 1, 2, 3, 4, 5, 6 }
auto result3 = flatten(ssl); // gives { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }
...

Hope it helps! If anything is not clear, let me know and i’ll try to explain it better.

  1. Proposal: Optimizing out useless functions 1 Reply
  2. An update on “A simple signal system” 2 Replies
  3. A simple signal system 11 Replies
  4. A function to visit nodes of a graph with C++14 5 Replies