C++ How to traverse through different set elements of a vector in specific pattern

Question

I have a vector of sets which contain integers as given below:

std::vector<std::set<int> > vec = {{2,4},{1,3,8},{7,5}};

Diagram illustration of the above vector of set

| 2 | 4 |       
| 1 | 3 | 8 |
| 7 | 5 |

I need to traverse through each set elements of vector such that each set element in vector row visits every set element in the next row and so on.

For example, the first element of the set in first row of vector (i.e 2) will visit the first element of second row (i.e 1) and then visit the first element of third row (i.e 7). Similarly, these traversals will be in the order as below:

First vector row and first set element -> Second vector row and first set element -> Third vector row and first set element
First vector row and first set element -> Second vector row and first set element -> Third vector row and second set element
First vector row and first set element -> Second vector row and second set element -> Third vector row and first set element
First vector row and first set element -> Second vector row and second set element -> Third vector row and second set element 
First vector row and first set element -> Second vector row and third set element -> Third vector row and first set element
First vector row and first set element -> Second vector row and third set element -> Third vector row and second set element

First vector row and second set element -> Second vector row and first set element -> Third vector row and first set element
First vector row and second set element -> Second vector row and first set element -> Third vector row and second set element
First vector row and second set element -> Second vector row and second set element -> Third vector row and first set element
First vector row and second set element -> Second vector row and second set element -> Third vector row and second set element 
First vector row and second set element -> Second vector row and third set element -> Third vector row and first set element
First vector row and second set element -> Second vector row and third set element -> Third vector row and second set element

The resultant vector should be a vector of list with each of its elements as below:

std::vector<std::list<int> > list = {{2,1,7},{2,1,5},{2,3,7},{2,3,5},{2,8,7},{2,8,5},{4,1,7},{4,1,5},{4,3,7},{4,3,5},{4,8,7},{4,8,5}};

Diagram illustration of the resultant vector of list

| 2 | 1 | 7 |
| 2 | 1 | 5 | 
| 2 | 3 | 7 |
| 2 | 3 | 5 |
| 2 | 8 | 7 |
| 2 | 8 | 5 |
| 4 | 1 | 7 |
| 4 | 1 | 5 | 
| 4 | 3 | 7 |
| 4 | 3 | 5 |
| 4 | 8 | 7 |
| 4 | 8 | 5 |

What would be the most efficient way to achieve this in C++?

Answer 1

Let's break down this into a couple of steps:

// Add the int to a copy of the list
std::list<int> append_copy(std::list<int> l, int i)
{
    l.push_back(i);
    return l;
}

// append_copy the list for each element in the set
template<typename OutputIterator>
OutputIterator cross_append(const std::set<int>& s, const std::list<int>& l, OutputIterator d_first)
{
    return std::transform(s.begin(), s.end(), d_first, [&](int i){ return append_copy(l, i); });
}

std::vector<std::list<int> > cross_apply(const std::vector<std::set<int> > & vec)
{
    // start with a single empty list
    std::vector<std::list<int> > result{ {} };

    // loop over the input to get the sets
    for (auto& s : vec)
    {
        std::vector<std::list<int> > inner;
        auto it = std::back_inserter(inner);

        // loop over the last run's intermediate, duplicating it
        for (auto& l : result)
        {
             it = cross_append(s, l, it);
        }
        result = inner;
    }
    return result;
}

See it live