How to iterate through map of map of map of map of map of map of vector

Question

I am trying to gather all the data from a map of map of map of map of map of map of map of vector without having to have 7 loops in C++.

Here is how the data looks:

Map 1=>Map 1.1=>Map 1.1.1=>Map 1.1.2=>Map 1.1.3=>Map 1.1.4=>Vector 1.1.5=>Elem 1
                                                                        =>Elem 2
       Map 1.2=>Map 1.2.1=>Map 1.2.2=>Map 1.2.3=>Map 1.2.4=>Vector 1.2.5=> Elem 1
                                                                        =>Elem 2
Map 2 =>Map 1.1=>Map 1.1.1=>Map 1.1.2=>Map 1.1.3=>Map 1.1.4=>Vector 1.1.5=>Elem 1
                                                                         =>Elem 2
        Map 1.2=>Map 1.2.1=>Map 1.2.2=>Map 1.2.3=>Map 1.2.4=>Vector 1.2.5=>Elem 1
                                                                         =>Elem 2

So I am trying to collect all the Elem 1, Elem 2 from all the maps into a map.

Can someone help me do this instead of the obvious loop through each map and leading to 7 loops in C++?

Thanks for the help.

(Update: Wow looking back at this after 10 years, what a code nightmare it was trying to fix someone else's legacy code. Hopefully no needs this now :)

Why do you have such deeply nested maps and vectors? Rather than try to iterate over your map-of-a-map-...of-a-vector, there's probably a better way to structure your code to make it unnecessary. — Alex, Aug 19 '11 at 19:34
You clearly sense that this has gone a bit far because you're reluctant to write seven nested for loops, but if you have seven nested maps what else can you do? This is a bit ridiculous, there must be an alternative. If you explain what you are trying to achieve, someone will suggest a better way. — john, Aug 19 '11 at 19:41
Batman is riding seven nested maps, this renders your argument invalid. — Matteo Italia, Aug 19 '11 at 20:24

score 4 · Accepted Answer · edited May 23 '17 at 12:29

I like @inflagranti's idea - so, without claim to utility, here's a for-each template that iterates over everything. It uses the is_container trait from the pretty printer, which I don't replicate here.

Update: Now fully worked out to deal with both with naked value types and with pair value types.

Update 2: Simplified the implementation class, thanks to @Luc Danton.

#include <algorithm>

#include "prettyprint.hpp"    
using namespace pretty_print;  // for "is_container" trait

template <typename T> struct is_pair : public std::false_type { };
template <typename S, typename T> struct is_pair<std::pair<S,T>> : public std::true_type { };

template <typename T> struct final_value { typedef T type; };
template <typename S, typename T> struct final_value<std::pair<S,T>> { typedef T type; };

template <typename Iter, typename F> void for_each_recursive(Iter begin, Iter end, F f);

template <typename F, bool Recurse> struct for_each_rec_impl;

template <typename F>
struct for_each_rec_impl<F, false>
{
  template <typename Iter>
  static typename std::enable_if<is_pair<typename std::iterator_traits<Iter>::value_type>::value, void>::type
  go(Iter begin, Iter end, F f)
  {
    for (Iter it = begin; it != end; ++it) f(it->second);
  }

  template <typename Iter>
  static typename std::enable_if<!is_pair<typename std::iterator_traits<Iter>::value_type>::value, void>::type
  go(Iter begin, Iter end, F f)
  {
    for (Iter it = begin; it != end; ++it) f(*it);
  }
};

template <typename F>
struct for_each_rec_impl<F, true>
{
  template <typename Iter>
  static typename std::enable_if<is_pair<typename std::iterator_traits<Iter>::value_type>::value, void>::type
  go(Iter begin, Iter end, F f)
  {
    for (Iter it = begin; it != end; ++it)
      {
        for_each_recursive(it->second.begin(), it->second.end(), f);
      }
  }

  template <typename Iter>
  static typename std::enable_if<!is_pair<typename std::iterator_traits<Iter>::value_type>::value, void>::type
  go(Iter begin, Iter end, F f)
  {
    for (Iter it = begin; it != end; ++it)
      {
        for_each_recursive(it->begin(), it->end(), f);
      }
  }
};

template <typename Iter, typename F>
void for_each_recursive(Iter begin, Iter end, F f)
{
  typedef typename std::iterator_traits<Iter>::value_type value_type;
  typedef typename final_value<value_type>::type type;

  for_each_rec_impl<F, is_container<type>::value>::go(begin, end, f);
}

Usage: for_each_recursive(v.begin(), v.end(), my_predicate<final_value_type>);

score 3 · Answer 2 · answered Aug 19 '11 at 20:10

Barring a change of the data type, you're probably stuck with loops-within-loop.

However, I would start by re-writing the maps of maps of maps of .... vector into 1 map of vectors. I would recommend using either boost::tuple or std::tuple (C++0x) to create the class, but you can also define your own, and overload operator < so that it can be used as a map key (or write the comparator)

Using boost::tuple, if you have map<Key1, map< Key2, map<Key3, map<Key4, map<Key5, map<Key6, vector<T> > > > > > > you could rework it into map< boost::tuple< Key1, Key2, Key3, Key4, Key5, Key6 >, vector<T> >.

@Xirdus: It probably will be once the standard is published. I'm still not holding my breath. — Mike Seymour, Aug 19 '11 at 21:27

score 2 · Answer 3 · answered Aug 19 '11 at 19:46

If you really must, you could do some template meta programming (for instance using boost mpl), to abstract away the loops. However, as many people have suggested, there is very likely a better solution to your original problem than one that needs 7 nested maps and a vector.

How to iterate through map of map of map of map of map of map of vector

3 Answers3