是否有任何按键和值排序的关联容器？我想要 C++ 中的这个数据结构。在 Java 中，有方法containsKey和containsValue. 我需要这个关联数据结构的迭代器（containsKey和containsValue）在尽可能短的时间内。它必须几乎接近 log(n)。
问问题
571 次
2 回答
1
您所描述的内容听起来很像Boost.Bimap容器框架，它允许您构建双向映射，让您同样高效地查找键和值。这可能不是您正在寻找的内容，但该库已经过充分测试，可能是一个很好的起点。
希望这可以帮助！
于 2012-08-29T03:24:20.547 回答
0
It might be that you want all the T1s for a given T2 and vice versa. That's not exactly what you said, but if that's what you want boost::bimap is the way to go.
std::set < std::pair < Tkey, Tvalue > > will do what you want in a basic kind of way. Auxiliary std::set < Tkey > and std::set < Tvalue > give you global contains_key and contains_value in O(log(n)), if that's what you want.
std::map < Tkey, std::set < Tvalue> > gives you convenient O(log(n)) access to the values for a key. Maintaining an inverted copy gives you convenient O(log(n)) access to the keys for a value.
It really all depends on what you want to do, and whether the data is an arbitrary set of key, value pairs or somehow restricted.
于 2012-08-29T06:57:27.303 回答