empty vector in a vector recursive type
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.
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".
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
您可以执行模式匹配来计算深度
template <typename Base>
struct NestedVectors //non vector match
{
static const size_t depth=0;
static size_t count_empty(const Base& b)
{
throw std::string("cant be here");
}
};
template <class Rv>
struct NestedVectors<std::vector<Rv> >
{
static const size_t depth=1 + NestedVectors<Rv>::depth ;
static size_t count_empty(const std::vector<Rv>& vec)
{
size_t r=0;
if(NestedVectors<Rv>::depth == 0)
{
if(vec.empty())
return 1;
}
else
{
for(size_t i =0; i < vec.size() ; ++i)
{
r+=NestedVectors<Rv>::count_empty(vec[i]);
}
}
return r;
}
};
int main()
{
typedef std::vector<
std::vector<
std::vector<
std::vector<
std::vector<
signed char
> > > > > data_t;
data_t t;
std::cout << NestedVectors<data_t>::depth << " " << NestedVectors<data_t>::count_empty(t);
}
下一篇: 向量中的空矢量递归类型