Поиск элемента в boost :: bimaps :: bimap по типу, отличному от типа ключа bimap - PullRequest
Новая
       27

Поиск элемента в boost :: bimaps :: bimap по типу, отличному от типа ключа bimap

0 голосов
/ 26 апреля 2018

У меня есть следующий код: 

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

Согласно форсированной документации 

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

Тип CompatibleKey называется совместимым ключом (Hash, Pred), если (CompatibleKey, Hash, Pred) является совместимым расширением (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&)

У меня вопрос: возможно ли использовать CompatibleKey другого типа, чем тип ключа bimap? Я уже пытался обойти заголовки наддува, к сожалению, реализация слишком сложна для меня, чтобы понять, что происходит.

Ответы [ 2 ]

0 голосов
/ 27 апреля 2018

Я не знаю о 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 (для меня это определенно похоже на ошибку).

0 голосов
/ 27 апреля 2018

Я согласен с вашим прочтением, что описание казалось , чтобы предположить, что такое использование должно быть разрешено.

Однако после long чтения и тестирования я не могу понять, как код на самом деле его поддерживает. Более того, есть эта подпись: 

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

Причина проблемы: хеширование std::string не дает то же значение имеет хэширование const char *, поэтому c.find("hello") не найти строку "hello". Вот почему N3657 относится только к ассоциативные контейнеры и не были распространены на неупорядоченные ассоциативные контейнеры.

Что касается std::less<void>, я сочувствую вашему предложению, но буду предпочитаю идти в соответствии со стандартом, который решил для std::less<void> должен быть явно предоставлен пользователем, а не по умолчанию.

Я был немного смущен, когда нашел там свой комментарий от 2014 года:)

...