Fastest type for std::map key?

Question

I would like to use the partitions of a graph as the key to a std::map

I could represent this as a std vector of nodes. Or I could convert it into a more compact 'custom' binary format (bitset?), or a string representation.

For simplicitiy's sake, we can say there is no inherent order to partitions of a graph.

Which will be fastest in terms of insertions and lookups (note the size of this map will be in the order of a billion nodes)

Answer 1

Keep your key type, but use boost's unordered_map and write your own hash() function for your graph partition.

For example, if order doesn't matter, you can hash each node in a way that is invariant to order. If you post how you are encoding it now, we can help more with this.