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

When two std::map objects are identical

提问人:Frank Goods 提问时间:12/20/2019 更新时间:12/20/2019 访问量:86

问:

我有两个对象,我用相同的数据填充它们,但顺序不同: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

C++ 字典 相等

评论

0赞 alain 12/20/2019
这就是 a 的工作原理,它命令元素能够在 O(log(n)) 时间内查找它们。 另一方面,不对元素进行排序,而是使用哈希来查找它们。std::mapstd::unordered_map
0赞 Frank Goods 12/20/2019
@alain 有趣的是,使用而不是不会改变任何东西,它们仍然是相等的std::unordered_mapstd::map
0赞 463035818_is_not_an_ai 12/20/2019
fwiw,两张地图中的顺序是相同的。您可以通过第三个模板参数选择地图以不同的方式对元素进行排序
0赞 ChrisMM 12/20/2019
@FrankGoods,for 会比较地图的内容。顺序无关紧要。operator==unordered_map

答:

3赞 Paul Evans 12/20/2019 #1

...因此,无论以何种顺序填充,这两张地图都是相等的。但能保证是这样吗?

是的,因为是一个排序的关联容器(通常作为二叉树实现),所以它的元素可以保证被排序(无论其实现如何)。std::map

评论

0赞 Frank Goods 12/20/2019
好的,那么二叉树中的所有旋转最终都会产生完全相同的数据结构?
2赞 Paul Evans 12/20/2019
无论在引擎盖下发生什么,它们都会以同样的方式工作。以同样的方式工作的一件事是平等比较。如果你仔细想想,否则它们作为地图就不是很有用了。
4赞 Lightness Races in Orbit 12/20/2019
@FrankGoods 这与数据结构无关。这是关于要求的。要求是迭代地图的开始到结束为您提供排序视图。就是这样。
1赞 Aziuth 12/20/2019
@FrankGoods 你可能想看看这个:en.wikipedia.org/wiki/Tree_traversal,特别是有序横向。这将始终以相同的顺序生成树中的值,即按其排序顺序,无论实际的基础树如何形成(只要它是有效的二进制排序树)。或者用实际的话来说:您可以在地图中插入项目(仅使用键),然后通过在地图上使用 for-each 来按顺序排列它们(尽管效率更高)。std::sortstd::sort
3赞 rustyx 12/20/2019 #2

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

此外,由于是一个排序容器,因此所有键只能有一个可能的顺序,因此在没有重复项的情况下,插入顺序无关紧要。同样,内部的顺序由每个键的哈希值决定,同样不依赖于插入顺序。std::mapstd::mapstd::unordered_map

请注意,您随机播放一个(顺序容器),然后将值复制到 .不可能“洗牌”一个,因为你无法控制那里的元素的位置。vectormapmap