c++ - 使用 pair 或 string 作为 map<> 键，哪个更高效？

Question

我想使用 map存储键值对。

map 的key应该包含一个点的坐标(int)信息。

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

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

哪种方法更好，为什么？

Answer 1

这取决于您对高效 的定义，我们很快就会转向可能被视为过早优化 的内容。有很多因素在起作用，顺便说一句，你表达问题的方式我认为我们应该看一个非常简单的问题:

您的主要考虑因素可能是:

• Storage:每个键占用多少内存
• 速度:关键比较的复杂程度
• 初始化:创建 key 有多复杂

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

• int是4个字节
• 一个指针是8个字节
• 你正在为字符串分配你自己的内存而不是使用 std::string (这取决于实现)

存储

• std::pair<int,int>需要 8 个字节
• 您的字符串需要 8 个字节用于指针，外加用于字符串表示值的额外内存(每个整数最多 10 个字节)和另一个字节用于分隔符

速度

• 比较 std::pair<int,int>最多需要两次整数比较，这在大多数处理器上都很快
• 比较两个字符串很复杂。平等很容易，但小于会很复杂。您可以为您的字符串使用特殊的填充语法，需要更多存储空间，以降低复杂性。

初始化

• std::pair<int,int>初始化简单快速
• 创建两个值的字符串表示形式需要某种内存分配，可能涉及确定所需最小内存量的逻辑，然后是分配本身(慢)和实际的数字转换(也慢)。这是“瓶颈”的双重打击。

---

从表面上看，您已经可以看出，使用字符串可能是疯狂的……也就是说，除非您有其他重要原因。

现在，你是否应该使用 std::pair<int,int> ？这可能有点矫枉过正。例如，假设您只存储适合范围 [0,65535] 的值。在这种情况下，std::pair<uint16_t,uint16_t>就足够了，或者您可以将这两个值打包成一个 uint32_t .

然后其他人提到了散列，如果您需要快速查找但不关心迭代顺序，这很好。

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

最后一个警告是:不要想太多你的问题 - 以最简单的方式编写它，然后测试是否适合你的需要。