通过不同于 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

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

然而，在 long 阅读和测试之后，我看不出代码如何真正支持它。更何况还有这个签名：

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

根据其文档，这需要 "CompatibleKey can be assigned to key_type"。这与之前看到的 "minimal requirements" 明显矛盾。

得出明显不行的结论后，想起以前看到过一样的...:[=22=]

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 年的评论:)

Answer 2

我不知道 Boost.Bimap，但使用 Boost.MultiIndex 的等效构造按预期工作：

Live On Coliru

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <iostream>
#include <string>
#include <utility>

using namespace boost::multi_index;
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_value_type=std::pair<std::string,Example>;

using BM = multi_index_container<
    BM_value_type,
    indexed_by<
        hashed_non_unique<member<BM_value_type, std::string, &BM_value_type::first>>,
        hashed_non_unique<
          member<BM_value_type,Example,&BM_value_type::second>,
          ExampleHash,ExampleEq
        >
    >
>;

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

    auto it = bm.get<1>().find(1u);

    std::cout<<it->second.id<<"\n"; // 1

    return 0;
}

您可能想使用 Boost.Bimap 提交工单（这对我来说绝对是个错误）。

通过不同于 bimap 键类型的类型查找 boost::bimaps::bimap 中的元素

Finding an element in boost::bimaps::bimap by different type than bimap key type

c++

boost

boost-bimap