title: How to synchronize a vector and its subset
body: <p>I have a graph implementation that uses vectors to store its nodes and edges (objects).</p>
  
  <pre><code>class Node
  {
      int index;
      std::vector&lt;Edge*&gt; from;
      std::vector&lt;Edge*&gt; to;
  };
  
  class Edge
  {
      int index;
      Node *from;
      int indexFrom;
      Node *to;
      int indexTo;
  };
  
  class Graph
  {
      std::vector&lt;Node*&gt; nodes;
      std::vector&lt;Edge*&gt; edges;
  };
  </code></pre>
  
  <p>The indexes are updated whenever the graph structure changes via a swap-with-last trick. Basically on removal I swap the element-to-be-removed with the last one (including the indexes). This graph structure gives me O(1) on all operations at the cost of inconsistent order of elements in the vectors (but consistent indexes on the elements).</p>
  
  <p>Now I struggle implementing decently efficient <strong>subgraph</strong>. The first instinct is to use vectors like in the main graph to store only the relevant elements.</p>
  
  <pre><code>class Subgraph
  {
      std::vector&lt;Node*&gt; nodes; //subset of Graph::nodes
      std::vector&lt;Edge*&gt; edges; //subset of Graph::edges
  };
  </code></pre>
  
  <p>However suddenly such a sub-graph performs in linear time or worse because when traversing I need to check every edge for presence in the sub-graph, when removing I need to look it up first in the sub-vector.</p>
  
  <p>Now I am trying to figure out how to do this and get at least O(1) for traversal (or rather, checking the presence of an element in the subgraph) and at worst O(log n) for the rest (removals, insertions).</p>
  
  <p>So far I figured vector of bools shadowing the original vectors could do the trick. But maybe there is a better way?</p>