search by a compatible key and default predicates

[maxim.yegorushkin@…]

Ordered and hashed indexes require predicates for comparing elements, which default to std::equal_to<Key> and std::less<Key> respectively.

At the same time find functions take a compatible key, that does not need to be convertible to Key.

Using std::equal_to<Key> and std::less<Key> breaks find when the compatible key is not convertible to Key because these predicates require both arguments to be of type Key.

Something like C++14 std::equal_to<void> and std::less<void> should be used as the default predicates.

[Joaquín M López Muñoz]

Hi Maxim,

std::equal_to<void>: 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.

[bugs@…]

@joaquin

Thanks for the insightful explanations.

I love boost multi index containers and I'm continuously surprised just how much effort went into not creating arbitrary limitations.