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)
The only way to reliably answer this question is the only way to answer ANY optimization question: Try it and see.
That said, I doubt there'd be much difference between the two, so long as there is an efficient comparison operator you can use.
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.
If you're going to have that many entries and performance is critical, I would suggest to definitely use unordered_map.
If you are using C++1x it's in the standard library; otherwise you can get it from boost.
If performance is really critical you can go even further and use boost::intrusive. It contains "intrusive" versions of the standard library containers: they copy the pointers of the values you insert instead of the values themselves. If the values are large you'll get a big performance benefit.