1

我有以下代码：

#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文档 

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？我已经尝试过提升标题，不幸的是，实现太复杂了，我无法理解发生了什么。

4

2 回答 2

0

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

然而，经过长时间的阅读和测试，我看不出代码实际上是如何支持它的。更重要的是，还有这个签名：

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

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

在得出显然它不能工作的结论之后，我记得之前看到过同样的事情......：

WONTFIX为了处理散列索引的兼容键，您不仅需要透明的相等比较，还需要某种透明的散列函子，例如

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

但使用它很棘手（而且很危险）：

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

问题的原因是：散列 astd::string不会产生相同的值具有散列 const char*，因此c.find("hello")找不到 string "hello"。这就是为什么<a href="http://open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3657.htm" rel="nofollow noreferrer">N3657 仅适用于关联容器并且具有未扩展到无序关联容器。

至于std::less<void>，我对您的提议表示同情，但更愿意符合标准，该标准决定 std::less<void>由用户明确提供而不是默认提供。

我有点尴尬地从 2014 年那里找到我自己的评论 :)

于 2018-04-26T23:12:20.853 回答
0

我不了解 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 提交一张票（这对我来说绝对是一个错误）。

于 2018-04-27T11:29:58.657 回答