当两个 std::map 对象相同时

Question

我有两个 std::map 对象，我用相同的数据填充但顺序不同：

using TMap = std::map<int, std::wstring>;
using TSourceData = std::vector< std::pair<int, std::wstring> >;

TSourceData gen_source_data(int size)
{
    TSourceData result;
    result.reserve(size);

    for(int i = 0; i < size; ++i)
    {
        result.push_back( std::make_pair(i, std::to_wstring(i)) );
    }

    return result;
}

TMap fill_map(const TSourceData& source)
{
    TMap result;

    auto randomized = source;
    std::random_shuffle(randomized.begin(), randomized.end());

    for(const auto &e : randomized)
    {
        result[e.first] = e.second;
    }

    return result;
}

int main()
{
    auto source = gen_source_data(1000);

    auto m1 = fill_map(source);
    auto m2 = fill_map(source);

    std::wcout << (m1 == m2) << std::endl;
}

在 VS2017 中，它似乎总是打印 1，因此无论以何种顺序填充，这两个映射都是相等的。但它能保证如此吗？如果是这样，你能解释一下为什么吗？

Answer 1

... so the two maps are equal no matter in what order they were filled. But is it guaranteed to be so?

是的，因为 std::map 是一个排序的关联容器（通常实现为二叉树），它的元素保证排序（无论其实现如何）。

Answer 2

std::map 是一个关联容器。顺序容器和关联容器的区别在于：

a sequential container 让你决定元素的位置
一个associative container本身就决定了元素的位置

此外，由于 std::map 是一个排序容器，所有键只能有一个可能的顺序，因此在没有重复项的情况下，std::map 的插入顺序无关紧要。类似地，std::unordered_map 中的顺序由每个键的哈希值决定，并且再次不依赖于插入顺序。

请注意，您打乱了 vector（顺序容器），然后将值复制到 map。 "shuffle" 是不可能的 map，因为你无法控制那里元素的位置。

当两个 std::map 对象相同时

When two std::map objects are identical

c++

dictionary

equality