resueltos - ¿Cómo puedo usar las plantillas variadic de C++ 11 para definir un vector de tuplas respaldado por una tupla de vectores?

vectores en c++ ejercicios resueltos

Question

Supongamos que tengo un montón de vectores:

vector<int> v1;
vector<double> v2;
vector<int> v3;

todos de la misma longitud Ahora, para cada índice i, me gustaría poder tratar (v1 [i], v2 [i], v3 [i]) como una tupla, y quizás pasarlo por alto. De hecho, quiero tener un vector de tuplas en lugar de una tupla de vectores, con lo cual puedo hacer lo anterior. (En términos de C, podría decir una matriz de estructuras en lugar de una estructura de matrices). No deseo efectuar ningún cambio de datos (piense en vectores realmente largos), es decir, el nuevo vector está respaldado por los vectores individuales que paso. Let''s.

Ahora, quiero que la clase que escribo ( ToVBackedVoT por falta de un mejor nombre) admita cualquier elección arbitraria de vectores para respaldarla (no solo 3, no int, double e int, no todos los escalares). Quiero que el vector de tuplas sea mutable, y que no se hagan copias en la construcción / asignaciones.

Si entiendo correctamente, las plantillas variadic y el nuevo tipo std::tuple en C ++ 11 son los medios para hacer esto (suponiendo que no quiero matrices void* tipo void* y así). Sin embargo, apenas los conozco y nunca he trabajado con ellos. ¿Me pueden ayudar a esbozar cómo será esa clase? O cómo, dado

template <typename ... Ts>

Puedo expresar algo así como "la lista de argumentos de la plantilla es la sustitución de cada nombre de tipo en los argumentos de la plantilla original con un vector de elementos de este tipo"?

Nota: Creo que también me gustaría poder unir vectores adicionales a los vectores de respaldo, creando una instancia de ToVBackedVoT<int, double, int> en, por ejemplo, una instancia de ToVBackedVoT<int, double, int, unsigned int> . Por lo tanto, tenlo en cuenta cuando respondas. Sin embargo, esto no es críticamente importante.

Answer 1

Como alternativa similar a boost::zip_iterator escribí una función zip con una interfaz muy simple:

vector<int> v1;
vector<double> v2;
vector<int> v3;

auto vec_of_tuples = zip(v1, v2, v3);

Por ejemplo, itere sobre estas tuplas:

for (auto tuple : zip(v1, v2, v3)) {
    int x1; double x2; int x3;
    std::tie(x1, x2, x3) = tuple;
    //...
}

Aquí, zip() toma cualquier cantidad de rangos de cualquier tipo. Devuelve un adaptador que se puede ver como un rango evaluado de forma diferida en una tupla de elementos que se originan en los rangos envueltos.

El adaptador es parte de mi biblioteca funcional de estilo Haskell "fn" y se implementó usando plantillas variadic.

Actualmente no es compatible con la modificación de los valores de los rangos originales a través del adaptador debido al diseño de la biblioteca (está destinado a ser utilizado con rangos no mutables, como en la programación funcional).

Una breve explicación sobre cómo se hace esto es: zip(...) devuelve un objeto adaptador que implementa begin() y end() , devolviendo un objeto iterador. El iterador contiene una tupla de iteradores para los rangos envueltos. Incrementar el iterador incrementa todos los iteradores envueltos (que se implementa usando una lista de índice y desempaquetando una expresión incrementada en una serie de expresiones: ++std::get<I>(iterators)... ). La desreferenciación del iterador reducirá todos los iteradores envueltos y lo pasará a std::make_tuple (que también se implementa como desempaquetar la expresión *std::get<I>(iterators)... ).

PD: su implementación se basa en muchas ideas provenientes de las respuestas a esta pregunta.

Answer 2

Conversión a una std :: tupla de vectores (vector :: iteradores):

#include <iostream>
#include <vector>

// identity
// ========

struct identity
{
    template <typename T>
    struct apply {
        typedef T type;
    };
};

// concat_operation
// ================

template <typename Operator, typename ...> struct concat_operation;

template <
    typename Operator,
    typename ...Types,
    typename T>
struct concat_operation<Operator, std::tuple<Types...>, T>
{
    private:
    typedef typename Operator::template apply<T>::type concat_type;
    public:
    typedef std::tuple<Types..., concat_type> type;
};

template <
    typename Operator,
    typename ...Types,
    typename T,
    typename ...U>
struct concat_operation<Operator, std::tuple<Types...>, T, U...>
{
    private:
    typedef typename Operator::template apply<T>::type concat_type;
    public:
    typedef typename concat_operation<
        Operator,
        std::tuple<Types..., concat_type>,
        U...>
    ::type type;
};

template <
    typename Operator,
    typename T,
    typename ...U>
struct concat_operation<Operator, T, U...>
{
    private:
    typedef typename Operator::template apply<T>::type concat_type;
    public:
    typedef typename concat_operation<
        Operator,
        std::tuple<concat_type>,
        U...>
    ::type type;
};


// ToVectors (ToVBackedVoT)
// =========

template <typename ...T>
struct ToVectors
{
    private:
    struct to_vector {
        template <typename V>
        struct apply {
            typedef typename std::vector<V> type;
        };
    };

    public:
    typedef typename concat_operation<to_vector, T...>::type type;
};

// ToIterators
// ===========

template <typename ...T>
struct ToIterators;

template <typename ...T>
struct ToIterators<std::tuple<T...>>
{
    private:
    struct to_iterator {
        template <typename V>
        struct apply {
            typedef typename V::iterator type;
        };
    };

    public:
    typedef typename concat_operation<to_iterator, T...>::type type;
};


int main() {
    typedef ToVectors<int, double, float>::type Vectors;
    typedef ToVectors<Vectors, int, char, bool>::type MoreVectors;
    typedef ToIterators<Vectors>::type Iterators;

    // LOG_TYPE(Vectors);
    // std::tuple<
    //     std::vector<int, std::allocator<int> >,
    //     std::vector<double, std::allocator<double> >,
    //     std::vector<float, std::allocator<float> > >

    // LOG_TYPE(Iterators);
    // std::tuple<
    //     __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >,
    //     __gnu_cxx::__normal_iterator<double*, std::vector<double, std::allocator<double> > >,
    //     __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > > >
}

Answer 3

De la aclaración de Asker sobre cómo se usaría esto (código que toma una tupla), voy a proponer esto en su lugar.

//give the i''th element of each vector
template<typename... Ts>
inline tuple<Ts&...> ith(size_t i, vector<Ts>&... vs){
    return std::tie(vs[i]...);
}

Hay una propuesta para permitir que los paquetes de parámetros se guarden como miembros de clases ( N3728 ). Usando eso, aquí hay un código no probado y no comprobable.

template<typename... Types>
class View{
private:
    vector<Types>&... inner;

public:

    typedef tuple<Types&...> reference;

    View(vector<Types>&... t): inner(t...) {}

    //return smallest size
    size_t size() const{
        //not sure if ... works with initializer lists
        return min({inner.size()...});
    }

    reference operator[](size_t i){
        return std::tie(inner[i]...);
    }
};

E iteración:

public:
    iterator begin(){
        return iterator(inner.begin()...);
    }
    iterator end(){
        return iterator(inner.end()...);
    }

    //for .begin() and .end(), so that ranged-based for can be used
    class iterator{
        vector<Types>::iterator... ps;
        iterator(vector<Types>::iterator... its):ps(its){}
        friend View;

    public:

        //pre:
        iterator operator++(){
            //not sure if this is allowed.
            ++ps...;
            //use this if not:
            //  template<typename...Types> void dummy(Types... args){} //global
            //  dummy(++ps...);
            return *this;
        }
        iterator& operator--();
        //post:
        iterator operator++(int);
        iterator operator--(int);
        //dereference:
        reference operator*()const{
            return std::tie(*ps...);
        }
        //random access:
        iterator operator+(size_t i) const;
        iterator operator-(size_t i) const;
        //need to be able to check end
        bool operator==(iterator other) const{
            return std::make_tuple(ps...) == std::make_tuple(other.ps...);
        }
        bool operator!=(iterator other) const{
            return std::make_tuple(ps...) != std::make_tuple(other.ps...);
        }

    };

Answer 4

Puede usar algo como:

#if 1 // Not available in C++11, so write our own

// class used to be able to use std::get<Is>(tuple)...
template<int... Is>
struct index_sequence { };

// generator of index_sequence<Is>
template<int N, int... Is>
struct make_index_sequence : make_index_sequence<N - 1, N - 1, Is...> { };

template<int... Is>
struct make_index_sequence<0, Is...> : index_sequence<Is...> { };

#endif

// The ''converting'' class
// Note that it doesn''t check that vector size are equal...
template<typename ...Ts>
class ToVBackedVoT
{
public:
    explicit ToVBackedVoT(std::vector<Ts>&... vectors) : data(vectors...) {}

    std::tuple<const Ts&...> operator [] (unsigned int index) const
    {
        return at(index, make_index_sequence<sizeof...(Ts)>());
    }
    std::tuple<Ts&...> operator [] (unsigned int index)
    {
        return at(index, make_index_sequence<sizeof...(Ts)>());
    }

private:
    template <int... Is>
    std::tuple<const Ts&...> at(unsigned int index, index_sequence<Is...>) const
    {
        return std::tie(std::get<Is>(data)[index]...);
    }

    template <int... Is>
    std::tuple<Ts&...> at(unsigned int index, index_sequence<Is...>)
    {
        return std::tie(std::get<Is>(data)[index]...);
    }

private:
    std::tuple<std::vector<Ts>&...> data;
};

Y para iterar, cree un ''IndexIterator'' como el que se encuentra en https://.com/a/20272955/2684539

Para unir vectores adicionales, debe crear otro ToVBackedVoT como std::tuple_cat para std::tuple

Answer 5

Una alternativa para todos los maleajes de plantillas variadic es usar el boost::zip_iterator para este propósito. Por ejemplo (no probado):

std::vector<int> ia;
std::vector<double> d;
std::vector<int> ib;

std::for_each(
  boost::make_zip_iterator(
    boost::make_tuple(ia.begin(), d.begin(), ib.begin())
    ),
  boost::make_zip_iterator(
    boost::make_tuple(ia.end(), d.end(), ib.end())
    ),
  handle_each()
  );

Donde su manejador, se ve así:

struct handle_each :
  public std::unary_function<const boost::tuple<const int&, const double&, const int&>&, void>
{
  void operator()(const boost::tuple<const int&, const double&, const int&>& t) const
  {
    // Now you have a tuple of the three values across the vector...
  }
};

Como puede ver, es bastante trivial expandir esto para admitir un conjunto arbitrario de vectores.

Answer 6

Una idea es mantener el almacenamiento en el estilo de "estructura de matriz" en forma de vectores para un buen rendimiento si solo se utiliza un subconjunto de los campos para una tarea en particular. Luego, para cada tipo de tarea que requiera un conjunto diferente de campos, puede escribir un envoltorio liviano alrededor de algunos de esos vectores, proporcionándole una agradable interfaz iterativa de acceso aleatorio similar a la que admite std::vector .

En cuanto a la sintaxis de las plantillas variadic, así es como una clase contenedora (sin ningún iterador aún) podría verse así:

template<class ...Ts> // Element types
class WrapMultiVector
{
    // references to vectors in a TUPLE
    std::tuple<std::vector<Ts>&...> m_vectors;

public:
    // references to vectors in multiple arguments
    WrapMultiVector(std::vector<Ts> & ...vectors)
        : m_vectors(vectors...)    // construct tuple from multiple args.
    {}
};

Para construir una clase con plantillas, a menudo se prefiere tener disponible una función auxiliar de deducir tipo de plantilla (similar a las make_{pair|tuple|...} en std ):

template<class ...Ts> // Element types
WrapMultiVector<Ts...> makeWrapper(std::vector<Ts> & ...vectors) {
    return WrapMultiVector<Ts...>(vectors...);
}

Ya ves diferentes tipos de "desempaquetar" la lista de tipos.

Agregar iteradores adecuados para su aplicación (lo solicitó en determinados iteradores de acceso aleatorio) no es tan fácil. Un inicio podría ser solo iteradores hacia adelante, que puede extender a iteradores de acceso aleatorio.

La siguiente clase de iterador se puede construir utilizando una tupla de iteradores de elementos, incrementándose y desreferenciando para obtener una tupla de referencias de elementos (importante para el acceso de lectura-escritura).

class iterator {
    std::tuple<typename std::vector<Ts>::iterator...> m_elemIterators;

public:
    iterator(std::tuple<typename std::vector<Ts>::iterator...> elemIterators) 
        : m_elemIterators(elemIterators)
    {}

    bool operator==(const iterator &o) const {
        return std::get<0>(m_elemIterators) == std::get<0>(o.m_elemIterators);
    }
    bool operator!=(const iterator &o) const {
        return std::get<0>(m_elemIterators) != std::get<0>(o.m_elemIterators);
    }

    iterator& operator ++() {
        tupleIncrement(m_elemIterators);
        return *this;
    }
    iterator operator ++(int) {
        iterator old = *this;
        tupleIncrement(m_elemIterators);
        return old;
    }

    std::tuple<Ts&...> operator*() {
        return getElements(IndexList());
    }

private:
    template<size_t ...Is>
    std::tuple<Ts&...> getElements(index_list<Is...>) {
        return std::tie(*std::get<Is>(m_elemIterators)...);
    }
};

Para propósitos de demostración, hay dos patrones diferentes en este código que "iteran" sobre una tupla para aplicar alguna operación o construir una nueva tupla con alguna epxresión que se llamará por elemento . Usé ambos para demostrar alternativas; también puedes usar el segundo método solamente.

1. tupleIncrement : puede usar una función auxiliar que usa meta programación para indexar una sola entrada y avanzar el índice en una, luego llamar a una función recursiva, hasta que el índice esté al final de la tupla (luego hay una implementación de caso especial que es desencadenado usando SFINAE). La función se define fuera de la clase y no arriba; aquí está su código:

   template<std::size_t I = 0, typename ...Ts>
   inline typename std::enable_if<I == sizeof...(Ts), void>::type
   tupleIncrement(std::tuple<Ts...> &tup)
   { }
   template<std::size_t I = 0, typename ...Ts>
   inline typename std::enable_if<I < sizeof...(Ts), void>::type
   tupleIncrement(std::tuple<Ts...> &tup)
   {
       ++std::get<I>(tup); 
       tupleIncrement<I + 1, Ts...>(tup);
   }

   Este método no puede utilizarse para asignar una tupla de referencias en el caso del operator* porque tal tupla debe inicializarse con referencias inmediatamente, lo que no es posible con este método. Entonces, necesitamos algo más para el operator* :

2. getElements : esta versión usa una lista de índices ( https://.com/a/15036110/592323 ) que se expande también y luego puede usar std::get con la lista de índices para expandir expresiones completas. El IndexList al llamar a la función instancia una lista de índice apropiada que solo es necesaria para la deducción del tipo de plantilla para obtener esos Is... El tipo se puede definir en la clase contenedora:

   // list of indices
   typedef decltype(index_range<0, sizeof...(Ts)>()) IndexList;

El código más completo con un pequeño ejemplo se puede encontrar aquí: http://ideone.com/O3CPTq

Los problemas abiertos son :

• Si los vectores tienen diferentes tamaños, el código falla. Mejor sería verificar todos los iteradores "finales" para la igualdad; si un iterador está "al final", también estamos "al final"; pero esto requeriría algo de lógica más que operator== y operator!= menos que esté bien "falsificarlo"; lo que significa que el operator!= podría devolver falso tan pronto como un operador sea desigual.

• La solución no es correcta, por ejemplo, no hay const_iterator .

• Agregar, insertar, etc. no es posible. La clase contenedora podría agregar alguna función insert y / o push_back para que funcione de manera similar a std::vector . Si su objetivo es que sea sintácticamente compatible con un vector de tuplas, vuelva a implementar todas las funciones relevantes de std::vector .

• No hay suficientes pruebas;)