Re: [Boost-users] [boost-users] anyways to flatten a stl container.

From: David Walthall (walthall_at_[hidden])
Date: 2007-10-24 19:14:44

Digvijoy Chatterjee wrote:
> ...and how do u intend to create a container that stores any container(
> set, multiset ,list, vector..... ) in C++ , if u really want stuff
> like Ruby ....take a look at boost::variant ( already known types of
> containers to store in a container ) , or boost::any ( unknown
> container types to be stored in a container )
> 
> HTH
> Digz
> 
> On 10/23/07, chun ping wang <cablepuff_at_[hidden]> wrote:
>> hmm it could be container of any type (set, multiset, list, vector, array,
>> deque).
>>
>> It should act like ruby on rails, flatten.
>>
>> http://www.ruby-doc.org/core/classes/Array.html#M002241

If you are looking for a function to flatten any STL container [of STL 
containers [etc]], the code below will work.  (It works under VS 2003.) 
    It may need cleaning up, and incorrect usage may generate horrid 
error messages.  There are some test functions at the end.

David

#include <vector>
#include <deque>
#include <list>
#include <cassert>

#include <boost/utility.hpp>
#include <boost/type_traits.hpp>
#include <boost/assign/std/vector.hpp>
#include <boost/assign/std/deque.hpp>
#include <boost/assign/std/list.hpp>

using namespace boost;
using namespace boost::assign;
using namespace std;

template <class ContainerObject, class OutIt, class Enable = void>
struct is_leaf_of_iterator
{
     static const bool value = false;
};

// Normal iterator
template <class ContainerObject, class OutIt>
struct is_leaf_of_iterator<ContainerObject, OutIt,
     typename disable_if<is_same<typename 
iterator_traits<OutIt>::value_type, void> >::type>
{
     static const bool value =
         is_same<
             ContainerObject,
             iterator_traits<OutIt>::value_type
         >::value;
};

// back iterator, front iterator, insert iterator(?)
template <class ContainerObject, class OutIt>
struct is_leaf_of_iterator<ContainerObject, OutIt,
     typename enable_if<is_same<typename 
iterator_traits<OutIt>::value_type, void> >::type>
{
     static const bool value =
         is_same<
             ContainerObject,
             OutIt::container_type::value_type
         >::value;
};

template <class ContainerObject, class OutIt, bool is_leaf>
struct do_flatten;

// Call self again with sub-container until reach a leaf.
// A leaf is defined as the type expected by the output iterator.
template <class ContainerObject, class OutIt>
struct do_flatten<ContainerObject, OutIt, false>
{
     static void apply(const ContainerObject &c, OutIt &out)
     {
         for(ContainerObject::const_iterator it = c.begin() ; it != 
c.end() ; ++it)
         {
             do_flatten<ContainerObject::value_type, OutIt,
                 is_leaf_of_iterator<typename 
ContainerObject::value_type, OutIt>::value
             >::apply(*it, out);
         }
     }
};

// partial specialization for non-containers
template <class ContainerObject, class OutIt>
struct do_flatten<ContainerObject, OutIt, true>
{
     static void apply(const ContainerObject &c, OutIt &out)
     {
         *out = c;
         ++out;
     }
};

template <class ContainerObject, class OutIt>
void flatten(const ContainerObject &c, OutIt &out)
{
     static const bool isleaf = is_same<ContainerObject, 
std::iterator_traits<OutIt>::value_type>::value;
     do_flatten<ContainerObject,OutIt, isleaf>::apply(c, out);
}

static std::vector<int> MakeV1_6()
{
     std::vector<int> v; v += 1,2,3,4,5,6; // this uses boost::assign
     return v;
}

static void Test1()
{
     typedef std::deque<int> deque_int;
     typedef std::vector< deque_int > vector_deque_ints;

     deque_int d1; d1 += 1,2,3;
     deque_int d2; d2 += 4,5,6;
     vector_deque_ints v; v += d1,d2; // [[1,2,3],[4,5,6]]

     std::vector<int> out;
     flatten(v, std::back_inserter(out));

     assert(out == MakeV1_6());
}

static void Test2()
{
     typedef std::deque<int> d_i;
     typedef std::list<d_i> l_d_i;
     typedef std::vector< l_d_i > v_l_d_i;

     d_i d1; d1 += 1,2;
     d_i d2; d2 += 3,4;
     d_i d3;d3 += 5,6;

     l_d_i l1; l1 += d1,d2;
     l_d_i l2; l2 += d3;

     v_l_d_i v; v += l1, l2; //[[[1,2],[3,4]],[[5,6]]]

     std::vector<int> out;
     flatten(v, std::back_inserter(out));

     assert(out == MakeV1_6());
}

int main()
{
     std::vector<int> v;
     v.push_back(0);

     flatten(static_cast<int>(0), v.begin());
     flatten(v, v.begin());

     std::vector<double> d;
     //flatten(d, v.begin()); // fails: v.begin() wrong type for double

     Test1();
     Test2();
}