使用pair<int, int>或string作为map<>键，哪个更高效？

Question

我想使用 map 来存储键-值对。

该地图的键应包含有关一个点坐标（int）的信息。

一种可能性是将 int 转换为 string。例如，坐标(x,y)可以表示为 "x#y"，并将此字符串 "x#y" 存储为键。

另一种可能性是使用一对儿将坐标作为 pair<int, int> 存储，并使用该 pair 作为键。

哪种方法更好，为什么？

- Bruce Feynman

---

你是如何存储坐标的？在程序的其他部分中，它们以什么形式存在？ - Galik

我会选择这对（pair）。不管怎样，如果你担心性能问题，可以考虑使用 unordered_map。 - Sid S

Answer 1

Creating a std::pair<int,int> is simple and requires only two integer values

Creating your own string representation will be more complex, requiring conversion of the integer value to a string and concatenation with the separator byte

所谓“高效”，取决于你的定义，我们很快陷入了所谓的“过早优化”。有很多因素在起作用，而且根据你提出问题的方式，我认为我们应该以非常简单的方式来看待：

您可能首先考虑的是：

• 存储：每个键使用多少内存
• 速度：键比较的复杂程度
• 初始化：创建一个键的复杂程度

让我们假设在您的系统上：

• int 是 4 字节
• 指针是 8 字节
• 您正在为字符串分配自己的内存，而不是使用std::string（这取决于实现）

存储

• std::pair<int,int> 需要8个字节
• 您的字符串需要8个字节的指针，加上另一个字节的分隔符和一个值的字符串表示形式的额外内存（每个整数最多可达10个字节）

速度

• 比较std::pair<int,int>最多需要两个整数比较，在大多数处理器上很快
• 比较两个字符串是复杂的。相等很容易，但小于则比较复杂。您可以使用特殊的填充语法来减少复杂性，从而需要更多存储空间。

初始化

• 创建一个std::pair<int,int>非常简单，只需要两个整数值
• 创建您自己的字符串表示将更加复杂，需要将整数值转换为字符串并与分隔符进行连接

std::pair<int,int>的初始化简单快速

创建两个值的字符串表示需要进行某种内存分配，可能涉及逻辑以确定所需内存的最小量，接着是分配（慢），然后是实际的数字转换（也很慢），这是“瓶颈”的双倍打击。

---

显然，仅凭外表来看，使用字符串可能有些疯狂...除非你有其他重要原因。

那么，你应该使用std::pair<int,int>吗？这可能过度了。例如，假设您只存储在范围[0,65535]内的值。在这种情况下，std::pair<uint16_t,uint16_t>就足够了，或者您可以将两个值打包成单个uint32_t。

还有其他人提到哈希，如果您需要快速查找但不关心迭代顺序，则可以使用哈希。

我说过我会保持简单，这就是我要停止的地方。希望这给了您一些思考的东西。

最后一个警告是：不要过度思考问题——用最简单的方式编写它，然后测试是否适合您的需求。

- paddy

Answer 2

首先，坐标可以是双精度数字，因此我认为使用pair<double, double>会是更好的选择。

其次，如果你真的想使用int pair或string key，那么pair<int, int>会是更好的选择，因为string会比它实际长度创建更多的容量。 基本上，每个字符串键都会损失一些未使用的内存。 string.length()的值可以等于或小于string.capacity()的值。

- Bhaskar