Управление набора векторов шаблонных производных типов

Question

Х: То, что я хочу сделать:

У меня есть типы: 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: то, что я пробовал без успеха.

Я нахожусь в данный момент, изучая шаблон метапрограммирования Абрахама C++, чтобы узнать, могу ли я использовать boost::mpl. Я также делаю учебники по boost::fusion, чтобы узнать, могу ли я использовать его. Тем не менее, кривая обучения этих библиотек довольно велика, поэтому я хотел сначала спросить, прежде чем инвестировать неделю во что-то, когда доступно более простое и простое решение.

Моя первая попытка была wrapp мои векторы 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...} ..., которую я не смог устранить.

Answer 1

А как насчет рекурсивного решения на основе общего связанного списка векторов, шаблона стратегии и того, что рекурсивно применяет стратегии через связанный список? (примечания: см улучшенной версии в конце):

#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 компилятора. Скорее всего, вы найдете неудовлетворительным тот факт, что для построения lin_vector требуется много копий, но вы можете специализировать структуру в соответствии с вашими потребностями (возможно, подставляя pred указателем или вставляя стратегию создания прямо в связанный список).

EDIT: здесь есть улучшенная версия, которая позволяет избежать много копирования и ручки построения списка и обработки в более последовательной и единообразно:

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

Answer 2

Возможно решение без виртуальной отправки, хотя это, вероятно, перебор.

Первое, что вам нужно, это шаблон функции 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, которые упрощают некоторые из этих процессов - если кто их знает, отредактируйте их.