title: Efficient representation for adjacency list and weights in directed graph
body: <p>I would like to get some feedback on storing adjacency lists for graphs. </p>
  
  <p>I typically represent an adjacent list using a vector of vectors, e.g., <code>std::vector&lt;std::vector&lt;int&gt;&gt; adj_list</code></p>
  
  <p>For an edge E=(u,v), it is simply stored using <code>adj_list[u].push_back(v)</code>. If I want to remove this edge, I simply do    </p>
  
  <pre><code>it = std::find(adj_list[u_idx].begin(), adj_list[u_idx].end(), v);
  adj_list[u_idx].erase(it);
  </code></pre>
  
  <p>I also need a data structure for storing the weights corresponding to the edges. So originally, I was thinking of making another vector of vectors <code>std::vector&lt;std::vector&lt;double&gt;&gt; weights</code>, but it seems this is not the most efficient solution. Adding a new element in weights is simple, just like the above. All I have to do is <code>weights[u].push_back(weight_to_add)</code>. But removing a weight from the weights seems a bit more difficult than doing what I did above, i.e., finding the iterator, and then using that iterator to perform the deletion. I could find the index corresponding to the iterator in <code>adj_list</code>, and then delete the index from weights, but I don't know if that is the best way to go about this.</p>
  
  <p>So instead of having two variables to represent the adjacency list and weights, I was thinking of making a single 3-D vector that stores both the adjacency list and weights. A vector of vector of vectors. The last dimension is size 2, that stores the node ID, v, and the corresponding weight of the edge. So really, it could just be a vector of vector of arrays. So something like <code>vector&lt;vector&lt;array&lt;...&gt;&gt;&gt;</code>. But the problem here is v is an <code>int</code> and the weights are doubles, so obviously I can't use arrays here. I could encapsulate the two inside a struct and then do something like <code>vector&lt;vector&lt;my_struct&gt;&gt;</code>. Or perhaps something like <code>vector&lt;vector&lt;pair&lt;int,double&gt;&gt;&gt;</code> would be better? </p>
  
  <p>Any advice on how to approach this problem? </p>