title: Linking graphs of structures by pointer vs. index in array
body: <p>This is question about <strong>good practice</strong></p>
  
  <p>Consider situation which is typical e.g. in 3D engines, physics engines, <a href="https://en.wikipedia.org/wiki/Finite_element_method" rel="nofollow noreferrer">Finite element method</a> or <a href="https://en.wikipedia.org/wiki/Force_field_%28chemistry%29" rel="nofollow noreferrer">classical molecular dynamics</a> solvers: You have objects of various types ( e.g. vertexes, edges, faces, bounded solid volumes ) which are cross-linked to each other (e.g. vertex know which edge are connected to it and vice versa). For performance and convenience of usage of such engine is crucial to be able quickly browse the network of such connections.</p>
  
  <p>The question is: <strong>Is it better to point to the linked object by index in array, or by pointer ?</strong> ... especially <strong>performance-wise</strong></p>
  
  <pre><code>typedef index_t uint16_t;
  
  class Vertex{
      Vec3 pos;
      #ifdef BY_POINTER
      Edge*   edges[nMaxEdgesPerVertex];
      Face*   faces[nMaxFacesPerVertex];
      #else
      index_t edges[nMaxEdgesPerVertex];
      index_t faces[nMaxFacesPerVertex];
      #endif
  }
  
  class Edge{
      Vec3   direction;
      double length;
      #ifdef BY_POINTER
      Vertex* verts[2];
      Faces*  faces[nMaxFacesPerEdge];  
      #else
      index_t verts[2];
      index_t faces[nMaxFacesPerEdge];
      #endif
  }
  
  class Face{
      Vec3   normal;
      double isoVal; // Plane equation: normal.dot(test_point)==isoVal
      #ifdef BY_POINTER
      Vertex* verts[nMaxVertsPerFace];
      Edge*   edges[nMaxEdgesPerFace];
      #else
      index_t verts[nMaxVertsPerFace];
      index_t edges[nMaxEdgesPerFace];
      #endif
  }
  
  #ifndef BY_POINTER
  // we can use other datastructure here, such as std:vector or even some HashMap 
  int nVerts,nEdges,nFaces;
  Vertex verts[nMaxVerts];
  Edge   edges[nMaxEdges];
  Vertex faces[nMaxFaces];
  #endif 
  </code></pre>
  
  <p><strong>Advantages of index:</strong></p>
  
  <ul>
  <li>using index can be more memory efficient when we use <code>uint8_t</code> or <code>uint16_t</code> for index instead of 32-bit or 64-bit pointer</li>
  <li>index can carry some additional information ( e.g. about orientation of edge ) encoded in some bits;</li>
  <li>the ordering of objects in array can carry some information about structure ( e.g. vertexes of cube could be ordered as <code>{0b000,0b001,0b010,0b011,0b100,0b101,0b110,0b111}</code> ). This information is not visible in pointers </li>
  </ul>
  
  <p><strong>Advantages of pointers:</strong></p>
  
  <ul>
  <li>We don't need to care about the arrays (or other data-structures) to store the objects. The objects can be simply allocated dynamically on the heap by <code>new Vertex()</code>.</li>
  <li><a href="https://stackoverflow.com/questions/4939834/in-c-accessing-my-array-index-is-faster-or-accessing-by-pointer-is-faster">May be faster (?)</a> because it does not need to add the base address of the array (?). But this is probably negligible with respect to memory latency (?) </li>
  </ul>