问题标签 [bimap]

我最近看到 boost 有一个名为 bimap 的双向映射实现。

我最初的 STL 地图使用以下两种类型：

• int作为关键类型
• std::weak_ptr<void>作为值类型（我们称之为X）

方案 1

要创建具有这些类型的 bimap，声明将类似于

boost::bimap<int, boost::bimaps::set_of<X, std::owner_less<X>>>

因为std::weak_ptr需要一个 less 运算符（由 提供std::owner_less）并链接到boost::bimaps::set_of可用的类型（如果我理解正确的话）。

方案 2

我希望int地图中的 type 键指向 type 的多个值X。

对于标准映射，将值类型从 更改X为std::list<X>可以，如下所示： std::map<int, std::list<X>>

如何定义双向地图（或可以使用什么），以便正确的地图视图将被解释为 a map<X,int>（展平 的列表X），而正确的地图仍然是 a map<int,list<X>>？

我在编译 boost.bimap 库时遇到问题。我的测试程序是一个空白的主要功能，只有一个包含指令（如#include <boost/bimap.hpp>）。经过一番调查，我发现预处理器从头文件中做了一些有趣的构造，例如：

我不知道这是否正确，但 gcc 接受它，而 clang 和 icc 不接受。谁是对的，我该怎么做才能用 bimap 库编译程序？不幸的是，在这种情况下我不能使用 gcc。

Ok, so I a boost::bimap declared as so:

Where object and position are a class and a struct, respectively.

Within the current object stored in the bimap, I want to find its own entry.

I am currently trying to do so like this:

I have trouble parsing the error output, but it seems like the at function of the bimap doesn't like the const-ness and/or reference-ness of this (and yes, I know this is an rvalue).

What would be the proper/suggested way to do this search?

Here is a snippet of the error:

(Edit added to address sehe's comments and to point out the problem)

Apologies if my post was in bad etiquette, I am both new to posting on SO and I was under the assumption that just dumping all of my code (just to include the custom objects and templates for this section of code is hundreds of lines) would be considered bad form, so I trimmed it down to (what I thought was) the bare minimum to still get the issue.

And just to address the test-cases link, I do write test cases. In this case I was swapping out a vector for a bimap to add in the position code, and this actually fails to compile (though I will say I was not very explicit on it being a compilation error, and not a stack trace). I'm assuming you (sehe), thought I was talking about a runtime error, because otherwise I don't see how the link was relevant.

Anyway, I was trimming out code down to the actual minimum to reproduce the error so I could post it here, and then realized the actual issue. As shown above, the bimap holds values <object*, position> But the class trying to insert itself into the bimap is an order class: voidorder::do_thing() {

So it turned out to be a simple type error. Sorry, everyone, for asking a really dumb question. I guess that is what I get for working on projects at 3 AM.

我为活动实现了自定义 ShowCase

我正在尝试在画布蒙版上绘画：http: //i.stack.imgur.com/u23kQ.png

遵循此代码：

但它看起来像这样：

http://i.stack.imgur.com/MhcOt.png

我正在做一个项目，我有两组独特的元素。一组中的任何元素都可能与另一组中的任何元素相关。

例子：

第 1 组：{A、B、C}

第 2 组：{1、2、3、4}

允许的关系：

(A, 1) (A, 3)

(B, 1) (B, 4)

(C, 1) (C, 3) (C, 4)

单个关系表示为一对括号内的两个集合元素。

在我的特定项目中，两个集合的元素都是对象，我希望对存储的所有对象的所有引用都解析为一个对象（例如，所有包含 A 的关系都将引用同一个对象 A，同样适用于对关系另一端的其他集合的引用）。

我正在考虑使用 Boostbimap来解决这个问题。我正在查看用于 bimap 左右半部分的潜在集合类型以及两组之间的关系，并一直在尝试确定哪些是正确的。

对于. bimap_ set_of CollectionType_bimap

但是，当我在实践中尝试过时，在插入关系 (A, 1) 后，我最终无法插入关系 (B, 1)，因为插入必须在左侧都有效以及让它发生的正见。为了纠正这个问题，我将CollectionType两半的multiset_of. 但是，所有值都已正确插入，这是否意味着我bimap现在拥有原始集合元素的重复副本？

为了尝试纠正这一点，我开始考虑更改bimap. 由于关系类型的集合类型默认为左半边的集合类型bimap，我认为multiset_of不正确，将其指定为set_of。但是，我不确定这是否解决了我的原始问题，即我的原始集合中有多个对象副本。

我真正需要的是查看 Set 2 中与 Set 1 中的元素相关的所有对象。Boostbimap对我来说是正确的路线吗？我选择的收藏和关系类型是否正确？顺便说一句，我正在尝试自定义我的地图以具有快速搜索时间，而不用担心插入时间（永远不会发生删除和修改，地图已初始化，然后仅用于之后的查找）。我应该只写一个自定义数据结构吗？

我有一个映射，其中多个键可以映射到相同的值。我想做反向查找，这样给定一个值，我得到一个映射到这个值的所有键的列表。请注意，与 Data.Bimap我的地图不同的是，不是 1:1 而是n :1。

此外，反向查找不应该像遍历所有映射条目那样花费O(n)，而是像使用反向索引那样花费 O (log n)或更好。该映射将包含数以万计的条目，这些条目具有高负载的添加/删除/查找操作。

这种数据结构是否以函数形式提供（首选 Haskell 或 Frege）？

Racket 有双向哈希表吗？

也就是说，可以在恒定时间内给定一个键并查找值，或者给定值并查找键的哈希映射？我会为看起来像这样的 API 感到高兴：

符号在哪里，key并val告诉哈希映射它正在被赋予一个 val，并寻找一个键，或者给定一个键，并寻找一个 val。在这两种情况下，我都希望在恒定的 O(1) 时间内完成。

我知道您可以通过使用两个相互反转的哈希表来实现这一点，但我想要一种内置于 Racket（或现有库）中的结构。

我承认这个问题之前已经问过，但现在是 4 年前，所以我敢要求更新：

我需要一种将元组/对添加到容器并有效搜索左右元素的方法。

Boost 具有bimap并且multi_index完全符合我的要求，但我想知道在普通的现代 C++-11/14 中推荐的替代方案是什么，以防你不想引入对 boost 的依赖（无论出于何种原因）。

链接中的一个答案表明不需要 s.th。由于透明的比较器，不再像 bimap 了。接受的答案建议将std::maps 与key1->key2和key2->结合起来的实现key1。

我真的不知道透明比较器如何帮助我，我只是好奇是否有一些这是你应该如何做以及为什么- 解决方案。你能提供一些提示/链接吗？

kotlin 有双向哈希图吗？如果不是 - 在 kotlin 中表达这一点的最佳方式是什么？包括番石榴从那里获取 BiMap 感觉就像用一把非常大的枪在一个很小的目标上射击 - 我可以想象目前没有正确的解决方案 - 我想到的最好的事情是为它编写一个自定义类

我需要为我的项目实现以下数据结构。我有一个关系

至

对于每个指针，我想保存一个与之连接的计数器，它可以随着时间的推移而改变（实际上只是递增）。这没问题，我可以简单地将它存储在 std::map 中。问题是我需要快速访问具有最高值的指针。

这就是为什么我得出使用 boost::bimap 的结论。它为我的项目定义如下：

这可以正常工作，但是我不能修改插入一次的对上的 uint64_t 是对的吗？文档说 multiset_of 是常量，因此我无法更改 bimap 中的 pair 值。

我能做些什么？更改此 bimap 中一个键的值的正确方法是什么？或者对于这个问题是否有更简单的数据结构？