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

Question

I have the following code:

#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;
}

According to boost documentation

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

A type CompatibleKey is said to be a compatible key of (Hash, Pred) if (CompatibleKey, Hash, Pred) is a compatible extension of (Hash, Pred). This implies that Hash and Pred accept arguments of type CompatibleKey, which usually means they have several overloads of their corresponding operator() member functions.

So I thought that auto it = bm.right.find(1u); will work. Unfortunately this generates an compilation error:

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

My question is if it is even possible to use CompatibleKey of a diffrent type than bimap key type? I have already tried to go over the boost headers, unfortunately the implmentation is too complicated for me to comprehend what is going on.

Answer 1

I agree with your reading that the description seemed to suggest that this usage should be allowed.

However after long reading and testing, I cannot see how the code would actually support it. What's more, there's this signature:

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

Which according to its docs requires "CompatibleKey can be assigned to key_type". That's a clear contradiction of the "minimal requirements" seen earlier.

After coming to the conclusion that apparently it can't work, I remembered seeing the same before...:

• want to efficiently overcome mismatch between key types in a map in Boost.Interprocess shared memory
• The comments lead me back to How to overload the assignment operator for strings that use custom allocator, which also had some comments leading to
• https://svn.boost.org/trac10/ticket/10678 Which says, specifically:

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.

I was a little embarrassed to find my own comment from 2014 there :)

Answer 2

I don't know about Boost.Bimap, but the equivalent construct using Boost.MultiIndex works as intended:

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;
}

You might want to file a ticket with Boost.Bimap (this definitely looks like a bug to me).