For storing an adjacency list with edge weights, the (apparently) standard way is to store a vector of vector of pairs (vertex end, weight). I realized recently that it is possible to store the adjacency list as for an unweighted graph and store the edge weights separately (in a map or unordered map). noedne pointed out that storing the weight in the adjacency list is more organized. In theory by storing the edge weights separately we can reuse algorithms for unweighted graphs that take the unweighted adjacency list.
Which do you think is better?
The map/unordered_map makes it a lot slower, probably not worth it.
Ok, what about unordered_map? It should have constant insert and lookup time (though amortized, and not always like when adding (vertex, weight) pair)
Big constant though.
Maps are pretty slow and it's not just about asymptotic $$$O(1)$$$ performance, constant factors matter too. Try timing basic operations on arrays/vectors vs. unordered_maps.
One thing that's pretty common (for example, in flow implementations) is to number your edges. Then your adjacency lists store edge ids and you can keep separate arrays for destination, capacity, and so on.
You could also make edge structs with named members and templatize your algorithms.