3

本质上，我想要一个容器，其中一个元素可以通过许多键访问。这可以通过定义一些多键类用作映射的键​​类型来完成，但由于这种解决方案不允许修改已插入元素的键，因此我无法为现有条目。

我很欣赏 withstd::map键需要保持不变以进行排序，但为什么这个限制应该存在于std::unordered_map?

如果需要，我想我可以只使用指针映射，但有没有更好、更优雅的解决方案？

编辑：感谢您清理 Andrei，Xeo。Nicol，关于我应该使用什么容器有什么建议吗？

4

3 回答 3

8

好吧，std::unordered_map不允许您修改密钥的原因与其他关联容器不允许您修改它的原因几乎相同：它会破坏该数据结构的内部组织。

在 anunordered_map中，密钥用于获取散列，该散列告诉容器将元素放置在哪个桶中（当然还有从哪个桶中检索它）。如果您修改密钥，则修改哈希，这意味着您的元素应该移动到不同的存储桶。这就像删除它并再次插入它，基本上。

另一方面，关联容器的整个想法是，任何元素都由一个固定的值表示，因此可以根据该值快速计算其在容器中的位置。如果允许使用多个键，您将使用哪一个来快速确定元素的存储位置或将要存储的位置？

您想要的可能是具有与标准库不同的复杂性保证的临时数据结构。

但是，就我个人而言，在我看来，您只是在寻找引用语义，因为您打算共享一个对象的多个视图。这自然会导致我使用（智能）指针，尤其是当我听到世界“别名”时。我建议您使用shared_ptrs 作为值的地图。

于 2013-02-14T20:38:48.617 回答
2

在关联容器（例如map，unordered_map）中， 的值key决定了元素在数据结构中的位置。在非多关联容器中，键也必须是唯一的。

如果key允许修改，那么这将危及上述设计不变量。

  • 中map，元素在二叉搜索树中的位置

  • 在unordered_map，将元素链接到哈希桶

如果我理解 OP 的要求，那么它可以通过在容器上编写一个包装器来实现insert()，例如以下 C++-ish 伪代码：

Iterator insert_wrapper( Container & cont, Element const & elem ) {

    if elem in cont {
       cont.erase( elem );
    }

    return cont.insert( elem );
}
于 2013-02-14T20:46:20.023 回答
1

你会发现参考地图比指针地图更有品味吗？

int value = 6;

std::unordered_map<int, int&> m;

for(int i=0; i<5; ++i)
    m.emplace(i, value);

value = 4;

for(auto const& i: m)
    std::cout<<i.second<<' ';

当然，您必须将实际值存储在其他地方，如示例所示。

于 2013-02-14T20:45:24.497 回答