Generic function to flatten a container of containers

Question

I am trying to get a better hold on iterators and generic functions. I thought it would be a useful exercise to write a function that converts container1 < container2 <type> > to container3 <type>. For example, it should be able to convert vector< deque<int> > to list<int>.

I figured all the container access should be through iterators, like the functions in <algorithm>.

Here is my code:

#include <iterator>
#include <algorithm>

// COCiter == Container of Containers Iterator
// Oiter == Output Iterator
template <class COCiter, class Oiter>
void flatten (COCiter start, COCiter end, Oiter dest)
{
    using namespace std;

    while (start != end) {
        dest = copy(start->begin(), start()->end(), dest);
        ++start;
    }
}

But when I try to call it in the following code:

int main ()
{
    using namespace std;

    vector< vector<string> > splitlines;
    vector<string> flat;

    /* some code to fill SPLITLINES with vectors of strings */

    flatten(splitlines.begin(), splitlines.end(), back_inserter(flat));
}

I get a huge C++ template error message, undefined reference to void flatten< ... pages of templates ...

I feel like my code was too easy to write, and I must need some more stuff to ensure that the data type in the inner containers matches the data type in the output container. But I don't know what to do.

Note that stack does not have iterators, and no begin/end functions. If you want it to work with stacks, you will most certainly have to special case it. — Benjamin Lindley, Jun 19 '11 at 20:23
That's true; I will change the question. I don't actually need stack compatibiliy; just iterable containers. — japreiss, Jun 19 '11 at 20:31

score 10 · Accepted Answer · answered Jun 19 '11 at 20:16

10

I found the issue. Thanks to SFINAE (Substitution failure is not an error) your compiler couldn't find the correct template because you are trying to call operator() on start by typing start() (probably a typo). Try this:

#include <iterator>
#include <algorithm>

// COCiter == Container of Containers Iterator
// Oiter == Output Iterator
template <class COCiter, class Oiter>
void flatten (COCiter start, COCiter end, Oiter dest) {
    while (start != end) {
        dest = std::copy(start->begin(), start->end(), dest);
        ++start;
    }
}

answered Jun 19 '11 at 20:16

orlp

112,504
36
218
315

SFINAE does not work for substitution failures that would occur in the body of the function. It only works in the function signature (return type and parameters). – Peter Alexander Jun 19 '11 at 20:22
That was indeed a typo, but it turned out that I was also making the error of including my generic function prototype in a header file. I just found out you can't do that; you have to include the whole cpp file (I think). – japreiss Jun 19 '11 at 20:40

score 4 · Answer 2 · answered Jun 02 '18 at 20:42

std::accumulate can do it for you. You need to gather up the contents of each of the inside vectors into the outside vector.

vector<vector<int>> v_of_v;
vector<int> v = std::accumulate(
    v_of_v.begin(), v_of_v.end(),
    vector<int>(),
    [](vector<int> a, vector<int> b) {
        a.insert(a.end(), b.begin(), b.end());
        return a;
    });

Generic function to flatten a container of containers

2 Answers2

Linked

Related