如何计算向量递归类型中的非空向量

Question

我有一种类型,可以定义为矢量向量的矢量...整数类型的向量.例:

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

我正在寻找一种优雅的方法来确定更深层次的非空向量的数量.我可以使用像4这样的封装循环来做那个例子

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());

但是,我如何创建一个模板(支持向量,列表或任何类型的容器共享相同的API)功能,以便为任何深度(超过4级)执行此操作？我认为递归是正确的方法,但不知道如何使用Template ...

欢迎提供所有帮助和建议,因为我非常确定有多种解决方案.

Answer 1

这是一个仅使用基本模板专门化的 C++98 解决方案：

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);
}

使用以下内容进行测试（此测试代码用作auto扩展，因为我很懒）：

#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;
}

两者都打印出“60”。