c++ - 如何计算 vector 递归类型中的非空 vector

Question

我有一个类型可以定义为一个 vector 的 vector vector ...的一个整数类型的 vector 。示例:

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

我正在寻找一种优雅的方法来确定更深层次的非空 vector 的数量。对于那个例子，我可以使用 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());

但是我如何创建一个模板(以支持 vector 、列表或任何类型的共享相同 API 的容器)函数来为任何深度(超过 4 层)执行此操作？我认为递归是正确的方法，但不知道如何使用模板...

我们欢迎所有的帮助和建议，因为我很确定解决这个问题的方法不止一种。

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”。