std :: unordered_map :: find使用与Key类型不同的类型？

我有一个unordered_map使用字符串类型作为键:

std::unordered_map map;

提供std::hash专业化,也提供string合适的专业化operator==.

现在我还有一个"字符串视图"类,它是一个指向现有字符串的弱指针,避免了堆分配:

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

现在,我希望能够使用string_view对象检查地图中是否存在密钥.不幸的是, std::unordered_map::find需要一个Key参数,而不是一般T参数.

(当然,我可以"推广"一个到一个string,但这会导致我想避免的分配.)

我喜欢的是类似的东西

template
class unordered_map
{
    template iterator find(const T &t);
};

这将需要operator==(T, Key)并std::hash()适当地定义,并将迭代器返回到匹配值.

有没有解决方法？

如上所述,C++ 14不提供异构查找std::unordered_map(不像std::map).你可以使用Boost.MultiIndex来定义一个非常接近的替代品,std::unordered_map它允许你在string_view不分配临时std::strings 的情况下查找s:

Live Coliru Demo

#include 
#include 
#include 
#include 

using namespace boost::multi_index;

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

template
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
using unordered_string_map=multi_index_container<
  mutable_pair,
  indexed_by<
    hashed_unique<
      member<
        mutable_pair,
        std::string,
        &mutable_pair::first
      >,
      string_view_hash,
      string_view_equal_to
    >
  >
>;

#include 

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

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

产量

boost,1

P0919R2对无序容器的异构查找已合并到C ++ 2a的工作草案中！

我的原始问题似乎很合适：-)

抽象

该建议为C ++标准库中的无序关联容器添加了异构查找支持。结果，当提供不同（但兼容）类型作为成员函数的键时，不需要创建临时键对象。这也使无序和规则的关联容器接口和功能彼此更加兼容。

通过本文提出的更改，以下代码将可以正常工作，而不会影响任何性能：

template
using h_str_umap = std::unordered_map;
h_str_umap map = /* ... */;
map.find("This does not create a temporary std::string object :-)"sv);

它看起来就像最近C++ 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索引放入容器中.