std::map 与 std::unordered_map 迭代值类型的差异

Question

以下程序迭代 unordered_map 试图找到最佳元素，但不完全是 return 预期结果：

#include <iostream>
#include <unordered_map>
using namespace std;

struct Item
{
    int val;
};

int main() {
    unordered_map<int, Item> itemMap;
    itemMap[0] = {0};
    itemMap[1] = {1};
    itemMap[2] = {2};
    itemMap[3] = {3};
    const Item* bestItem = nullptr;
    int bestVal = -1;
    for (const pair<int, Item>& item : itemMap)
    {
        if (item.second.val > bestVal)
        {
            bestVal = item.second.val;
            bestItem = &item.second;
        }
    }
    cout << "best val: " << bestVal << " best item: " << bestItem->val;
    return 0;
}

ideone

运行这个程序打印出：

best val: 3 best item: 0

这似乎是因为 unordered_map 的 value_type 是 std::pair<const Key, T> 但我们正在迭代 const pair<int, Item>。果然将其更改为 const pair<const int, Item> 结果：

best val: 3 best item: 3

但是如果我们将 itemMap 的类型更改为 std::map:

map<int, Item> itemMap

那么无论我们遍历 const pair<int, Item> 还是 const pair<const int, Item> 都没有关系，我们得到相同的结果：

best val: 3 best item: 3

尽管 std::map 的 value_type 仍然是 std::pair<const Key, T>。但是为什么？

Answer 1

问题归结为 "Why does undefined behaviour gives different results for different containers?"，答案是 "Because it's undefined"。

不那么轻率：您可能会看到最后一次迭代的值，在有序 map 的情况下这将是最大的，但可以是 unordered_map 中的任何值。

根据你的描述，我想你明白为什么它是未定义的：const 引用可以绑定到一个临时的，所以如果类型不完全匹配，它会这样做而不是绑定到映射元素本身。引用，因此是临时的，在循环内的范围内，因此在外部不可用。你指向它的悬空指针最终将指向任何重用该内存的东西——在这种情况下，这很可能是循环的后续迭代中的同一个变量。

正如您在评论中所说，使用 auto &&（或者，也许更好，auto const &），以便类型推导确保类型匹配并且引用直接绑定到地图元素。然后指针会指向一个map元素，在循环外仍然有效

Answer 2

您的两个测试（使用 unordered_map 和 map）都表现出未定义的行为。一个似乎起作用而另一个不起作用的事实是偶然的，可能是因为它们以不同的顺序迭代。在地图中放置不同的值也会导致它失败并显示 std::map。

行为未定义的原因：如您所说，item 的类型与地图的 value_type 不同。因此，创建了一个 pair<int, Item> 类型的临时文件，并将 item （这是一个 const 引用）绑定到这个临时文件。临时的生命周期被延长以匹配 item.

的生命周期

您的 bestItem 指针指向此临时文件，但在您访问它时它的生命周期已过期，因此行为未定义。

如果 item 是匹配类型 (const pair<const int, Item>&)，则不需要创建临时文件，因为它可以直接引用地图的 value_type。 bestItem 因此是指向地图的指针，一切正常。

std::map 与 std::unordered_map 迭代值类型的差异

Difference in iterating over value type for std::map vs std::unordered_map

c++

stl

c++11