Using pair<int, int> or string as map<> key, which is more efficient?

Question

I want to use a map to store key-value pairs.

The key of the map should contain information about the coordinates(int) of one point.

One possibility is to convert the ints to string. For example, coordinate(x,y) can be represented as "x#y" and store this string "x#y" as a key.

Another possibility is to use a pair to store the coordinates as pair<int, int> and using this pair as key.

Which way is a better approach and why ?

Answer 1

This depends on your definition of efficient, and we very quickly devolve into what might be considered premature optimization. There are a lot of things at play, and by the way you phrased your question I think we should take a very simplistic look:

Your primary considerations are probably:

• Storage: how much memory is used by each key
• Speed: how complex a key comparison is
• Initialization: how complex it is to create a key

And let's assume that on your system:

• int is 4 bytes
• a pointer is 8 bytes
• you are allocating your own memory for strings instead of using std::string (which is implementation-dependent)

Storage

• std::pair<int,int> requires 8 bytes
• your string requires 8 bytes for the pointer, plus additional memory for the string-representation of a value (up to 10 bytes per integer) and another byte for the separator

Speed

• Comparing std::pair<int,int> requires at most two integer comparisons, which is fast on most processors
• Comparing two strings is complex. Equality is easy, but less-than will be complicated. You could use a special padded syntax for your strings, requiring more storage, to make this less complex.

Initialization

• std::pair<int,int> initialization is simple and fast
• Creating a string representation of your two values requires memory allocation of some kind, possibly involving logic to determine the minimum amount of memory required, followed by the allocation itself (slow) and the actual numeric conversion (also slow). This is a double-whammy of "bottleneck".

---

Already you can see that at face value, using strings might be crazy... That is, unless you have some other important reason for it.

Now, should you even use std::pair<int,int>? It might be overkill. As an example, let's say you only store values that fit in the range [0,65535]. In that case, std::pair<uint16_t,uint16_t> would be sufficient, or you could pack the two values into a single uint32_t.

And then others have mentioned hashing, which is fine provided you require fast lookup but don't care about iteration order.

I said I'd keep this simplistic, so this is where I'll stop. Hopefully this has given you something to think about.

One final caution is this: Don't overthink your problem -- write it in the simplest way, and then TEST if it suits your needs.

Answer 2

1st, coordinate can be double number so I think pair< double , double > would be better choice.

2nd , if you really want to use int pair or string key, pair< int , int> would be better choice as string will always create more capacity than it's actual length. Basically, You will loose some unused memory for each string key. string.length() value can be equal to or less than string.capacity() value..