Std:: unordered_map:: find использует тип, отличный от типа ключа?

У меня есть unordered_map, который использует строковый тип в качестве ключа:

std::unordered_map<string, value> map;

A std::hash специализация предоставляется для string, а также подходящий operator==.

Теперь у меня также есть класс "string view", который является слабым указателем на существующую строку, избегая выделения кучи:

class string_view {
    string *data;
    size_t begin, len;
    // ...
};

Теперь я хотел бы проверить, существует ли ключ на карте с помощью объекта string_view. К сожалению, std::unordered_map::find принимает аргумент Key, а не общий аргумент T.

(Конечно, я могу "продвигать" один на string, но это вызывает выделение, которое я бы хотел избежать.)

То, что мне было бы лучше, было что-то вроде

template<class Key, class Value>
class unordered_map
{
    template<class T> iterator find(const T &t);
};

для чего требуется, чтобы operator==(T, Key) и std::hash<T>() были соответствующим образом определены и вернули итератор в соответствующее значение.

Есть ли способ обхода?

Ответы

Ответ 1

Как упоминалось выше, С++ 14 не обеспечивает гетерогенный поиск std::unordered_map (в отличие от std::map). Вы можете использовать Boost.MultiIndex, чтобы определить довольно близкую замену std::unordered_map, которая позволяет вам искать string_view без выделения временных std::string s:

Демо-версия Live Coliru

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

using namespace boost::multi_index;

struct string_view
{
  std::string *data;
  std::size_t begin,len;
};

template<typename T,typename Q>
struct mutable_pair
{
  T         first;
  mutable Q second;
};

struct string_view_hash
{
  std::size_t operator()(const string_view& v)const
  {
     return boost::hash_range(
       v.data->begin()+v.begin,v.data->begin()+v.begin+v.len);
  }
  std::size_t operator()(const std::string& s)const
  {
     return boost::hash_range(s.begin(),s.end());
  }
};

struct string_view_equal_to
{
  std::size_t operator()(const std::string& s1,const std::string& s2)const
  {
     return s1==s2;
  }
  std::size_t operator()(const std::string& s1,const string_view& v2)const
  {
     return s1.size()==v2.len&&
            std::equal(
              s1.begin(),s1.end(),
              v2.data->begin()+v2.begin);
  }
  std::size_t operator()(const string_view& v1,const std::string& s2)const
  {
     return v1.len==s2.size()&&
            std::equal(
              v1.data->begin()+v1.begin,v1.data->begin()+v1.begin+v1.len,
              s2.begin());
  }
};

template<typename Q>
using unordered_string_map=multi_index_container<
  mutable_pair<std::string,Q>,
  indexed_by<
    hashed_unique<
      member<
        mutable_pair<std::string,Q>,
        std::string,
        &mutable_pair<std::string,Q>::first
      >,
      string_view_hash,
      string_view_equal_to
    >
  >
>;

#include <iostream>

int main()
{
  unordered_string_map<int> m={{"hello",0},{"boost",1},{"bye",2}};

  std::string str="helloboost";
  auto it=m.find(string_view{&str,5,5});
  std::cout<<it->first<<","<<it->second<<"\n";
}

Выход

boost,1

Ответ 2

Похоже, что только С++ 14 даже базовый map получил такую шаблонную находку для типов is_transparent в сравнении. Скорее всего, правильная реализация хешированных контейнеров не была сразу очевидна.

Насколько я вижу два варианта:

Просто выполните распределение и профиль, чтобы увидеть, может быть, это не проблема.
Взгляните на boost::multi_index (http://www.boost.org/doc/libs/1_60_0/libs/multi_index/doc/index.html) и укажите в контейнере индексы string и string_view.

Ответ 3

Это решение имеет недостатки, которые могут или не могут сделать его непригодным для вашего контекста.

Вы можете создать класс-оболочку:

struct str_wrapper {
  const char* start, end;
};

И измените карту, чтобы использовать str_wrapper в качестве ее ключа. Вам нужно добавить 2 конструктора в str_wrapper, один для std::string и один для вашего string_view. Главное решение состоит в том, делать ли эти конструкторы глубокие или мелкие копии.

Например, если вы используете std::string только для вставок и str_view только для поиска, вы должны сделать конструктор std::string глубоким, а str_view - неглубоким (это можно выполнить во время компиляции, если вы используете пользовательскую оболочку вокруг unordered_map). Если вы хотите избежать утечек памяти в глубокой копии, вам понадобятся дополнительные поля для поддержки надлежащего уничтожения.

Если ваше использование будет более разнообразным, (глядя вверх std::string или вставкой str_view), будут недостатки, которые снова могут сделать этот подход слишком неприятным, чтобы быть нежизнеспособным. Это зависит от вашего предполагаемого использования.

Ответ 4

Вы можете разрешить неявное преобразование своего представления в std::string:

class StringView {
    // ...
    operator std::string() const
    {
        return data->substr(begin, len);
    }
    // ...
};