Pages

mercredi 18 septembre 2013

Tableau dans un std::vector

Prenons le type suivant `std::vector<int[4]>` qui peut se justifier. À priori cela ne cause aucun problème ; et c'est vrai !

Ajoutons maintenant un élément à notre vector avec push_back et patatra rien ne va plus, il y a 2 erreurs.
La première concerne la construction du tableau et la seconde sa destruction car un tableau n'a ni constructeur ni destructeur.

La manière la plus facile pour éliminer ces erreurs de compilation est de mettre un wrapper sur le tableau. Écrire ce wrapper n'est pas très compliqué et Oh joie, Oh bonheur, il existe std::array.

Mais si l'on tient vraiment à notre tableau (pour d'obscures raisons satanique :D) il est toujours possible de modifier le comportement du vector pour qu'il comprenne les tableaux. Ceci à travers l'allocator, le second paramètre template d'un vector ; celui jamais utilisé, toujours oublié `std::vector<T, là_ici>`.

La technique consiste à remplacer l'allocator par un spécialisé pour les tableaux. Le plus simple est d'hériter d'un std::allocator et de redéfinir les 2 méthodes problématiques: construct. et destroy.
Et ne surtout pas oublier rebind qui permet de recréer l'allocateur avec un type interne différent (c'est utilisé par les containers :)).

(Un précédent article permet de comprendre les mécanismes utilisés par un allocateur.)

L'implémentation de construct et destroy est vraiment bateau, il suffit d'appeler le constructeur ou le destructeur pour chaque élément du tableau.
Mais pour faire au minimum bien les choses et supporter l'allocation de tableau de tableau (int[3][2]) on utilise array_allocator::construct/destroy si les cellules sont des tableaux (ce qui fait 2 fonctions récursives) ou std::allocator::construct/destroy dans le cas contraire.
À noter que la récursivité peut être éliminée en utilisant les propriétés d'alignement des tableaux (int[3][2] -> int[3*2]).

template<typename T>
class array_allocator;

//c'est juste pour les tableaux
template<typename T, std::size_t N>
class array_allocator<T[N]>
: public  std::allocator<T[N]>
{
public:
  using value_allocator = typename std::conditional<
    std::is_array<T>::value,
    array_allocator<T>,
    std::allocator<T>
  >::type;

public:
  template<typename U>
  struct rebind
  { typedef array_allocator<U> other; };

  template<typename U>
  void construct(U* p, const T(&val)[N])
  {
    value_allocator alloc;
    for (std::size_t n = 0; n < N; ++n) {
      alloc.construct(&(*p)[n], val[n]);
    }
  }

  template<typename U>
  void destroy(U* p)
  {
    value_allocator alloc;
    for (std::size_t n = 0; n < N; ++n) {
      alloc.destroy(&(*p)[n]);
    }
  }
};

Dans l'idéal il faudrait un `construct` avec un nombre variable d'arguments ce qui permet d'utiliser emplace_back.
Toutefois, cette version est fonctionnelle avec push_back :).

std::vector<int[3], array_allocator<int[3]> > v;
int a[3]{1,2,3};
v.push_back(a);
v.push_back({4,5,6});
(La lib falcon (dont je suis le seul développeur actuellement ^^) dispose d'un allocateur de ce style: generic_allocator. Comme son nom l'indique, l'allocateur couvre un spectre un peu plus large et gère en plus les types POD.)