c++ - 通过与 bimap 键类型不同的类型在 boost::bimaps::bimap 中查找元素

Question

我有以下代码:

#include <boost/bimap/bimap.hpp>
#include <boost/bimap/unordered_multiset_of.hpp>
#include <string>

using namespace boost::bimaps;
using namespace boost;

struct Example
{
    uint64_t id;
};

struct ExampleHash
{
    uint64_t operator()(const Example& item) const
    {
        return item.id;
    }

    uint64_t operator()(const uint64_t item) const
    {
        return item;
    }
};

struct ExampleEq
{
    bool operator()(const Example& l, const Example& r) const
    {
        return l.id == r.id;
    }

    bool operator()(const uint64_t l, const Example& r) const
    {
       return l == r.id;
    }

    bool operator()(const Example& l, const uint64_t r) const
    {
        return operator()(r, l);
    }
};

using BM = bimaps::bimap<
    unordered_multiset_of<std::string>,
    unordered_multiset_of<Example, ExampleHash, ExampleEq>
>;

int main() {
    BM bm;
    bm.insert(BM::value_type("First", Example{1}));

    auto it = bm.right.find(1u);

    return 0;
}

根据 boost documentation

template< class CompatibleKey >
iterator find(const CompatibleKey & x);

如果 (CompatibleKey, Hash, Pred) 是 (Hash, Pred) 的兼容扩展，则称类型 CompatibleKey 是 (Hash, Pred) 的兼容键。这意味着 Hash 和 Pred 接受 CompatibleKey 类型的参数，这通常意味着它们有多个对应的 operator() 成员函数的重载。

所以我认为 auto it = bm.right.find(1u); 会起作用。不幸的是，这会产生一个编译错误:

error: no match for call to (boost::bimaps::container_adaptor::detail::key_to_base_identity<Example, const Example>) (const long unsigned int&)

我的问题是，是否可以使用与 bimap 键类型不同的 CompatibleKey？我已经尝试过 boost headers，不幸的是，实现太复杂了，我无法理解正在发生的事情。

Answer 1

我同意您的阅读，即描述似乎暗示应该允许这种用法。

但是在长时间阅读和测试之后，我看不出代码如何真正支持它。更何况还有这个签名:

template< class CompatibleKey >
  bool replace_key(iterator position, const CompatibleKey & x);

根据其文档要求“CompatibleKey 可以分配给 key_type”。这与之前看到的“最低要求”明显矛盾。

在得出明显行不通的结论后，我记得之前也看到过同样的...:

• want to efficiently overcome mismatch between key types in a map in Boost.Interprocess shared memory
• 评论让我回到How to overload the assignment operator for strings that use custom allocator , 其中也有一些评论导致
• https://svn.boost.org/trac10/ticket/10678具体来说:

WONTFIX In order to deal with compatible keys for hashed indices, you'd need not only transparent equality comparison but also some sort of transparent hash functor such as

struct generic_hash
{
  template<typename T>
  std::size_t operator()(const T& x)const
  {
     boost::hash<T> h;
     return h(x);
  }
};

but using this is tricky (and dangerous):

multi_index_container<
  std::string,
  indexed_by<
    hashed_unique<identity<std::string>,generic_hash,std::less<void>>
  >
> c{"hello"};

std::cout<<*(c.find("hello"))<<"\n"; // crash

The reason for the problem is: hashing a std::string does not yield the same value has hashing a const char*, so c.find("hello") does not find the string "hello". This is why ​N3657 applies only to associative containers and has not been extended to unordered associative containers.

As for std::less<void>, I'm sympathetic to your proposal but would prefer to go in line with the standard, which decided for std::less<void> to be explicitly provided by the user rather than the default.

我有点不好意思在那里找到我自己 2014 年的评论:)