1

X：我想做的事：

我有类型：BaseType和DerivedType<int k>（见下面的代码），我需要处理K派生类型的向量集合std::vector<DerivedType<k>>，k = 1...K. 我想访问这些向量中的对象，并对它们执行依赖于k. K是编译时间常数。问题在实现中说明：

类型定义为：

#include <iostream>
#include <algorithm>

struct BaseType { // Interface of the DerivedTypes
  virtual void print(){std::cout << "BaseType!" << std::endl; }
};

template< int k >
struct DerivedType : public BaseType {
  static const int k_ = k;
  // ... function calls templated on k ...
  void print(){std::cout << "DerivedType: " << k_ << std::endl;}
};

template< int k >
void doSomething ( DerivedType<k>& object ) { object.print(); }

我想做的是：

int main() {

  // My collection of vectors of the derived types:
  std::vector<DerivedType<0>> derType0(2);
  std::vector<DerivedType<1>> derType1(1);
  std::vector<DerivedType<2>> derType2(3);
  // ... should go to K: std::vector<DerivedType<K>> derTypeK;

  // Iterate over the derived objects applying a k-dependent templated function:
  std::for_each(begin(derType0),end(derType0),[](DerivedType<0>& object){
    doSomething<0>(object);
  });
  std::for_each(begin(derType1),end(derType1),[](DerivedType<1>& object){
    doSomething<1>(object);
  });
  std::for_each(begin(derType2),end(derType2),[](DerivedType<2>& object){
    doSomething<2>(object);
  });

  return 0;
}

我想避免重复代码，这样我只需要更改K，这是 的编译时间常数O(10)。理想情况下，我会有“更像”这样的东西：

// Pseudocode: do not try to compile this

create_derived_objects(DerivedType,K)
  = std::vector< std::vector<DerivedType<k>>* > my_K_derived_types;                                                  

for each vector<DerivedType<k>>* derivedTypes in my my_K_derived_types
  for each object in (*derivedTypes)
    doSomething<k> on object of type derivedType<k>
    // I could also restrict doSomething<k> to the base interface

O(10^6)派生类型的每个向量都包含O(10^9)对象。最内层的循环是我的应用程序中最耗时的部分，因此使 dynamic_cast 只是最外层循环的一个选项。

Y：我尝试过的都没有成功。

我目前正在研究 Abrahams C++ Template Metaprogramming 这本书，看看我是否可以使用boost::mpl. 我也在做教程boost::fusion，看看我是否也可以使用它。然而，这些库的学习曲线相当大，所以我想在我投入一周的时间之前先问一下，什么时候有更好、更简单的解决方案可用。

我的第一次尝试是包装我的向量std::vector<DerivedType<k>>，以便我可以创建一个, 并在一个循环中vector<WrappedDerivedTypes*>分别访问每个单个向量。for_each但是，在循环中，我有一系列if(dynamic_cast<std::vector<DerivedType<0>>>(WrappedVector) != 0 ){ do for_each loop for the derived objects } else if( dynamic_cast...) { do...} ...我无法消除的。

4

2 回答 2

3

那么基于向量的通用链表、策略模式和通过链表递归应用策略的递归解决方案呢？（注：见最后的改进版）：

#include <iostream>
#include <vector>

template <int j>
class holder {
public:
    const static int k = j;
};

template <int j>
class strategy {
public:
    void operator()(holder<j> t)
    {
        std::cout << "Strategy " << t.k << std::endl;
    }
};

template <int k>
class lin_vector {
private:
    std::vector<holder<k>> vec;
    lin_vector<k-1> pred;
public:
    lin_vector(const lin_vector<k-1> &pred, std::vector<holder<k>> vec)
        : vec(vec), pred(pred) { }
    std::vector<holder<k>> get_vec() { return vec; }
    lin_vector<k-1> &get_pred() { return pred; }
};

template <>
class lin_vector<0> {
public:
    lin_vector() { }
};

template <int k, template <int> class strategy>
class apply_strategy {
public:
    void operator()(lin_vector<k> lin);
};

template <int k, template <int> class strategy>
void apply_strategy<k, strategy>::operator()(lin_vector<k> lin)
{
    apply_strategy<k-1, strategy>()(lin.get_pred());
    for (auto i : lin.get_vec())
    strategy<k>()(i);
}

template <template <int> class strategy>
class apply_strategy<0, strategy>
{
public:
    void operator()(lin_vector<0> lin) { /* does nothing */ } 
};


template <int k>
lin_vector<k> build_lin()
{
    return lin_vector<k>(build_lin<k-1>(), {holder<k>()});
}

template <>
lin_vector<0> build_lin()
{
    return lin_vector<0>();
}

int main(void)
{
    apply_strategy<5, strategy>()(build_lin<5>());
}

使用 C++11 编译器对其进行编译。很可能您会发现构建 alin_vector需要大量复制这一事实并不令人满意，但是您可以根据您的需要专门化结构（也许pred用指针替换 a 或将创建策略直接嵌入到链表中）。

编辑：这里有一个改进的版本，它避免了大量的复制并以更连贯和统一的方式处理列表构建和处理：

#include <iostream>
#include <vector>

template <int j>
class holder {
public:
    const static int k = j;
};

template <int k>
class lin_vector {
private:
    std::vector<holder<k>> vec;
    lin_vector<k-1> pred;
public:
    std::vector<holder<k>> &get_vec() { return vec; }
    lin_vector<k-1> &get_pred() { return pred; }
};

template <>
class lin_vector<0> {
public:
    lin_vector() { }
};

template <int k, template <int> class strategy>
class apply_strategy {
public:
    void operator()(lin_vector<k> &lin);
};

template <int k, template <int> class strategy>
void apply_strategy<k, strategy>::operator()(lin_vector<k> &lin)
{
    apply_strategy<k-1, strategy>()(lin.get_pred());
    strategy<k>()(lin.get_vec());
}

template <template <int> class strategy>
class apply_strategy<0, strategy>
{
public:
    void operator()(lin_vector<0> &lin) { /* does nothing */ } 
};

template <int j>
class strategy {
public:
    void operator()(std::vector<holder<j>> &t)
    {
        std::cout << "Strategy " << j << ", elements: ";
        for (auto v : t)
            std::cout << v.k << " ";
        std::cout << std::endl;
    }
};

template <int j>
class build_strategy {
public:
    void operator()(std::vector<holder<j>> &t)
    {
        for (unsigned int i = 0; i < j; i++)
            t.push_back(holder<j>());
    }
};

int main(void)
{
    const int K = 5;
    lin_vector<K> list;
    apply_strategy<K, build_strategy>()(list);
    apply_strategy<K, strategy>()(list);
}
于 2012-07-27T13:44:09.113 回答
1

一个没有虚拟调度的解决方案是可能的，尽管它可能是矫枉过正的。

您需要的第一件事是doSomething<K>()专门针对每种派生类型的函数模板：

template <int K>
void doSomething(vector<DerivedType<K> >& x);

template <>
void doSomething<1>(vector<DerivedType<1> >& x) { ... }

template <>
void doSomething<2>(vector<DerivedType<2> >& x) { ... }   // etc.

struct然后，您可以使用递归定义的模板构建强类型的向量集合：

template <int K>
struct vov {
    vov<K - 1> prev;
    vector<DerivedType<K> > v;
};

template <>
struct vov<1> {
    vector<DerivedType<1> > v;
};

最后，你可以编写一个递归函数模板来处理这个结构：

template <int K>
void process(vov<K>& x) {
    doSomething(x.v);     // Type inference will find the right doSomething()
    process(x.prev);      // Here too
}

template <>
void process<1>(vov<1>& x) {
    doSomething(x.v);
}

现在主要代码将如下所示：

vov<42> foo;
process(foo);

因为process()函数调用通过使用递归来执行迭代，它可能会不必要地使用K个堆栈帧；但是它是尾递归，现代优化 C++ 编译器通常可以将其转换为纯迭代，而不会浪费堆栈。使用尾递归迫使我们以“反向”顺序处理向量，以便DerivedType<1>最后处理向量，但如有必要，这可以通过使用 2 个int模板参数的稍微更精细的模板来修复（一个将“向上计数”到另一个，而不是int向 1“倒计时”的单个参数）。

DerivedType<k>请注意，从该解决方案中派生出每个都不会带来任何好处BaseType——您最好完全忘记BaseType，除非您出于不同的原因需要它。

很可能有 MPL 原语可以简化其中的一些过程——如果有人知道它们，请随时编辑。

于 2012-07-27T13:43:45.750 回答