How to count non-empty vector in a vector recursive type

Question

I have a type that can be define as a vector of vector of vector ... of vector of an integral type. Example:

std::vector<std::vector<std::vector<std::vector< std::vector<signed char> > > > > _data;

I'm searching for an elegant way to determine the number of non-empty vector at the deeper level. I could do that for that example using a 4 encapsulate loop like

for (it0 = data.cbegin() ; it0 != _data.cend() ; ++it0)
 for (it1 = *it0.cbegin() ; it1 != *it0.cend() ; ++it1)
   for (it2 = *it1.cbegin() ; it2 != *it1.cend() ; ++it2)
      for (it3 = *it2.cbegin() ; it3 != *it2.cend() ; ++it3)
          nonEmpty += (unsigned int) (*it3.empty());

But how can I create a template (to support vector, list or any kind of container sharing the same API) function to do that for any deep (more than 4 level) ? I think a recursion is the correct way, but don't know how to do that with Template ...

All help & advice will be welcome because I quite sure that there is more than one solution to that.

Answer 1

Here's a C++98 solution using nothing more than basic template specialization:

template<typename T> struct VectorCounter {
    /* no count method: this is an error */
};

template<typename U> struct VectorCounter<vector<U> > {
    static int count(const vector<U> &v) {
        return (int)v.empty();
    }
};

template<typename V> struct VectorCounter<vector<vector<V> > > {
    static int count(const vector<vector<V> > &v) {
        int ret = 0;
        for(typename vector<vector<V> >::const_iterator it=v.cbegin(); it!=v.cend(); ++it) {
            ret += VectorCounter<vector<V> >::count(*it);
        }
        return ret;
    }
};

template<typename T> int count_nonempty_vectors(const T &v) {
    return VectorCounter<T>::count(v);
}

Tested with the following (this test code uses auto as an extension because I'm lazy):

#include <iostream>
#include <vector>
using std::vector;

typedef vector<vector<vector<vector<vector<signed char> > > > > data_t;

int count_fixed(const data_t &data) {
    int nonEmpty = 0;
    for (auto it0 = data.cbegin() ; it0 != data.cend() ; ++it0)
        for (auto it1 = it0->cbegin() ; it1 != it0->cend() ; ++it1)
            for (auto it2 = it1->cbegin() ; it2 != it1->cend() ; ++it2)
                for (auto it3 = it2->cbegin() ; it3 != it2->cend() ; ++it3)
                    nonEmpty += (unsigned int)(it3->empty());
    return nonEmpty;
}

data_t build_data() {
    data_t data(5);
    int sz = 0;
    for (auto it0 = data.begin() ; it0 != data.end() ; ++it0) {
        it0->resize(4);
        for (auto it1 = it0->begin() ; it1 != it0->end() ; ++it1) {
            it1->resize(3);
            for (auto it2 = it1->begin() ; it2 != it1->end() ; ++it2) {
                it2->resize(2);
                it2->at(0).resize(1);
                it2->at(1).resize(0);
            }
        }
    }
    return data;
};

int main() {
    std::cout << count_fixed(build_data()) << std::endl;
    std::cout << count_nonempty_vectors(build_data()) << std::endl;
    return 0;
}

Both print out "60".

Answer 2

Maybe Something like that ? (it uses std::enable_if so it's a C++11 answer, but maybe you can use the boost one instead).

template <typename T, typename U>
typename std::enable_if<std::is_same<typename U::value_type,T>::value,std::size_t>::type
non_empties(const U& r)
{
    return !r.empty();
}

template <typename T, typename U>
typename std::enable_if<!std::is_same<typename U::value_type,T>::value,std::size_t>::type
non_empties(const U& r)
{
    std::size_t res = 0;
    for(auto& it : r)
    {
        res += non_empties<T>(it);
    }
    return res;
}

usage :

auto non_empty_terminal = non_empties<signed char>(_data);

You have to put the 'stop' type as a template parameter, so maybe it's not ideal.

Live exemple here