Vecteur de stockage en C++

Question

Je souhaite stocker un grand vecteur de d-dimensionnelle des points de (d immobilisations et les petits: <10).

Si je définis Point comme vector<int>, je pense qu'un vector<Point> serait de stocker dans chaque position d'un pointeur vers un Point.

Mais si définir une Point fixe de la taille de l'objet, comme: std::tuple<int,int,...,int> ou std::array<int, d>, le programme de stocker tous les points de la mémoire contiguë ou le niveau supplémentaire d'indirection rester?

Dans le cas où la réponse est que les tableaux d'éviter l'indirection supplémentaire, cela pourrait avoir un impact important sur les performances (cache exploiter la localité) lors de la numérisation de l' vector<Point>?

Answer 1

Si vous définissez votre Point comme ayant contiguë de stockage de données (par exemple, struct Point { int a; int b; int c; } ou à l'aide de std::array), alors std::vector<Point> va stocker l' Points dans la mémoire contiguë endroits, de sorte que la mémoire de votre mise en page sera:

p0.a, p0.b, p0.c, p1.a, p1.b, p1.c, ..., p(N-1).a, p(N-1).b, p(N-1).c

D'autre part, si vous définissez Point comme vector<int>, puis un vector<Point> a la disposition de l' vector<vector<int>>, ce qui n'est pas contigu, comme vector stocke des pointeurs de la mémoire allouée dynamiquement. Si vous avez la contiguïté des single Points, mais pas pour l'ensemble de la structure.

La première solution est beaucoup plus efficace que le second (comme les Processeurs modernes de l'amour l'accès contigus emplacements de mémoire).

Answer 2

vector va stocker quel que soit votre type contient en mémoire contiguë. Alors, oui, si c'est un array ou tuple, ou probablement même mieux, un type personnalisé, elle permet d'éviter d'indirection.

Performance sage, comme toujours, vous devez mesurer. Ne pas spéculer. Au moins autant que la numérisation est concerné.

Cependant, il y aura certainement un énorme gain de performance lorsque vous créez ces points, en premier lieu, parce que vous allez éviter les allocations de mémoire pour chaque vector qui stocke un point. Et les allocations de mémoire sont généralement très coûteux en C++.

Answer 3

Pour la valeur de d (<10), la définition d' Point comme vector<int> sera presque le double de la pleine utilisation de la mémoire en std::vector<Point> et apportera presque aucun avantage.

Answer 4

Que la dimension est fixe, je vous suggère d'aller avec un modèle qui utilise la dimension d'un modèle param. Quelque chose comme ceci:

template <typename R, std::size_t N> class ndpoint 
{
public:
  using elem_t=
    typename std::enable_if<std::is_arithmetic<R>::value, R>::type;

  static constexpr std::size_t DIM=N;

  ndpoint() = default;

  // e.g. for copying from a tuple
  template <typename... coordt> ndpoint(coordt... x) : elems_ {static_cast<R>(x)...} {
  }
  ndpoint(const ndpoint& other) : elems_() {
    *this=other;
  }

  template <typename PointType> ndpoint(const PointType& other) : elems_() {
    *this = other;
  }

  ndpoint& operator=(const ndpoint& other) {
    for(size_t i=0; i<N; i++) {
      this->elems_[i]=other.elems_[i];
    }
    return *this;
  }

  // this will allow you to assign from any source which defines the
  // [](size_t i) operator
  template <typename PointT> ndpoint& operator=(const PointT& other) {
    for(size_t i=0; i<N; i++) {
      this->elems_[i]=static_cast<R>(other[i]);
    }
  }

  const R& operator[](std::size_t i) const { return this->elems_[i]; }

  R& operator[](std::size_t i) { return this->elems_[i]; }

private:
  R elems_[N];
};

Ensuite, utilisez un std::vector<ndpoint<...>> , pour une collection de points pour de meilleures performances.

Answer 5

La seule façon d'être sûr à 100% de vos données est structurée est à mettre pleinement en œuvre la propre gestion de la mémoire..

Cependant, il existe de nombreuses bibliothèques qui mettent en œuvre des matrices et de la matrice des opérations que vous pouvez vérifier. Certains ont documenté l'information à propos de la mémoire contiguë, remodeler etc. (par exemple, OpenCV Mat).

Notez qu'en général, vous ne pouvez pas faire confiance un tableau de Points contigus. C'est en raison de l'alignement, de l'allocation de bloc d'en-tête, etc. Par exemple, considérons

struct Point {
   char x,y,z;
};

Point array_of_points[3];

Maintenant, si vous essayez de "remodeler", c'est-itérer entre les éléments de Point relais sur le fait que les points sont adjacents dans le conteneur qu'il est le plus susceptible d'échouer:

(char *)(&array_of_points[0].z) != (char *)(&array_of_points[1].x)