c++ std::unordered_map::使用与Key类型不同的类型查找?

epfja78i  于 2023-03-20  发布在  其他
关注(0)|答案(9)|浏览(177)

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

std::unordered_map<string, value> map;

string提供了std::hash专门化,以及合适的operator==
现在我还有一个“string view”类,它是指向现有字符串的弱指针,避免了堆分配:

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

现在我希望能够使用string_view对象检查map中是否存在键,不幸的是,std::unordered_map::find接受Key参数,而不是通用的T参数。
(Sure,我可以将其“提升”为string,但这会导致我希望避免的分配。)
我更喜欢的是

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

这将需要适当地定义x1M9N1x和x1M10N1x,并且将迭代器返回到匹配值。
是否有任何变通方案?

dfuffjeb

dfuffjeb1#

P0919R2 Heterogeneous lookup for unordered containers已被合并到C++2a的工作草案中!
摘要似乎与我最初的问题完全匹配:-)

摘要

该方案为C++标准库中的无序关联容器增加了异构查找支持。因此,当不同(但兼容)类型作为成员函数的键提供时,不需要创建临时键对象。这也使得无序和常规关联容器接口和功能彼此更加兼容。
使用本文建议的更改后,以下代码将正常工作,而不会对性能造成任何影响:

template<typename Key, typename Value>
using h_str_umap = std::unordered_map<Key, Value, string_hash>;
h_str_umap<std::string, int> map = /* ... */;
map.find("This does not create a temporary std::string object :-)"sv);

来自cppreference的完整示例

#include <cstddef>
#include <functional>
#include <iostream>
#include <string>
#include <string_view>
#include <unordered_map>
 
using namespace std::literals;
 
struct string_hash
{
    using hash_type = std::hash<std::string_view>;
    using is_transparent = void;
 
    std::size_t operator()(const char* str) const        { return hash_type{}(str); }
    std::size_t operator()(std::string_view str) const   { return hash_type{}(str); }
    std::size_t operator()(std::string const& str) const { return hash_type{}(str); }
};
 
int main()
{
    // simple comparison demo
    std::unordered_map<int,char> example = {{1, 'a'}, {2, 'b'}};
 
    if (auto search = example.find(2); search != example.end())
        std::cout << "Found " << search->first << " " << search->second << '\n';
    else
        std::cout << "Not found\n";
 
    // C++20 demo: Heterogeneous lookup for unordered containers (transparent hashing)
    std::unordered_map<std::string, size_t, string_hash, std::equal_to<>> map{{"one"s, 1}};
    std::cout << std::boolalpha
        << (map.find("one")   != map.end()) << '\n'
        << (map.find("one"s)  != map.end()) << '\n'
        << (map.find("one"sv) != map.end()) << '\n';
}
igsr9ssn

igsr9ssn2#

如上所述,C++14没有为std::unordered_map提供异构查找(不像std::map)。你可以使用Boost.MultiIndex来定义一个相当接近std::unordered_map的替代,它允许你查找string_view而不需要分配临时的std::string

**一个

#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
de90aj5v

de90aj5v3#

我也面临同样的问题。
我们需要两个结构体:

struct string_equal {
    using is_transparent = std::true_type ;

    bool operator()(std::string_view l, std::string_view r) const noexcept
    {
        return l == r;
    }
};

struct string_hash {
    using is_transparent = std::true_type ;

    auto operator()(std::string_view str) const noexcept {
        return std::hash<std::string_view>()(str);
    }
};

对于无序Map:

template <typename Value>
using string_unorderd_map = std::unordered_map<std::string, Value, string_hash, string_equal>;

对于无序集:

using string_unorderd_set = std::unordered_set<std::string, string_hash, string_equal>;

现在可以使用string_view了。

ryoqjall

ryoqjall4#

看起来就在C++14中,基本的map在比较中也得到了is_transparent类型的模板化查找,很可能散列容器的正确实现并不明显。
据我所知你有两个选择:

brgchamk

brgchamk5#

这个解决方案有一些缺点,这些缺点可能会也可能不会使它不适合您的环境。
您可以创建一个 Package 类:

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

然后修改map,使用str_wrapper作为它的键,你必须给str_wrapper添加2个构造函数,一个用于std::string,一个用于string_view,主要的决定是让这些构造函数执行深度复制还是浅复制。
例如,如果你使用std::string只用于插入,str_view只用于查找,那么你需要让std::string构造函数成为深构造函数,而str_view构造函数成为浅构造函数(如果你在unordered_map周围使用自定义 Package 器,这可以在编译时强制执行)。
如果你的用法更多样化(查找std::string或通过str_view插入),就会有一些缺点,同样,这可能会使这种方法太令人不快,以至于不可行,这取决于你的预期用途。

93ze6v8z

93ze6v8z6#

还有一种选择是通过使用多个容器来分离查找和数据管理:

std::unordered_map<string_view, value> map;
std::vector<unique_ptr<const char[]>> mapKeyStore;

查找是使用string_view来完成的,不需要分配。每当插入一个新的键时,我们需要先添加一个真实的字符串分配:

mapKeyStore.push_back(conv(str)); // str can be string_view, char*, string... as long as it converts to unique_ptr<const char[]> or whatever type
map.emplace(mapKeyStore.back().get(), value)

mapKeyStore中使用std::string会直观得多,但是使用std::string并不能保证字符串内存不变(例如,如果向量大小调整)。对于unique_ptr,这是强制的。但是,我们需要一些特殊的转换/分配例程,如果你有一个自定义的字符串容器可以保证移动时的数据一致性(并且强制向量使用移动),那么你可以在这里使用它。

缺点

上述方法的缺点是处理删除操作非常繁琐,如果不成熟的话,代价会很高。如果Map只创建一次或者只增长,这不是问题,上述模式工作得很好。

运行示例

下面的示例包括一个密钥的自然删除。

#include <vector>
#include <unordered_map>
#include <string>
#include <string_view>
#include <iostream>
#include <memory>
#include <algorithm>

using namespace std;
using PayLoad = int;

unique_ptr<const char[]> conv(string_view str) {
    unique_ptr<char[]> p (new char [str.size()+1]);
    memcpy(p.get(), str.data(), str.size()+1);
    return move(p);
}

int main() {
    unordered_map<string_view, PayLoad> map;
    vector<unique_ptr<const char[]>> mapKeyStore;
    // Add multiple values
    mapKeyStore.push_back(conv("a"));
    map.emplace(mapKeyStore.back().get(), 3);
    mapKeyStore.push_back(conv("b"));
    map.emplace(mapKeyStore.back().get(), 1);
    mapKeyStore.push_back(conv("c"));
    map.emplace(mapKeyStore.back().get(), 4);
    // Search all keys
    cout << map.find("a")->second;
    cout << map.find("b")->second;
    cout << map.find("c")->second;
    // Delete the "a" key
    map.erase("a");
    mapKeyStore.erase(remove_if(mapKeyStore.begin(), mapKeyStore.end(),
        [](const auto& a){ return strcmp(a.get(), "a") == 0; }),
        mapKeyStore.end());
    // Test if verything is OK.
    cout << '\n';
    for(auto it : map)
        cout << it.first << ": " << it.second << "\n";

    return 0;
}

当然,这两个容器可以放在一个 Package 器中,该 Package 器自己处理插入和删除。

u91tlkcl

u91tlkcl7#

我只介绍我在github上发现的一个变体,它涉及到定义一个新的map类来 Package std。
重新定义一些密钥API来拦截我们想要的适配器,并使用静态字符串来复制密钥。
这不一定是一个好的解决方案,但知道它存在的人谁认为它足够有趣。
原件:
https://gist.github.com/facontidavide/95f20c28df8ec91729f9d8ab01e7d2df
代码要点:

template <typename Value>
class StringMap: public std::unordered_map<std::string, Value>
{
public:
    typename std::unordered_map<string,Value>::iterator find(const nonstd::string_view& v )
    {
        tmp_.reserve(  v.size() );
        tmp_.assign( v.data(), v.size() );
        return std::unordered_map<string, Value>::find(tmp_);
    }

    typename std::unordered_map<std::string,Value>::iterator find(const std::string& v )
    {
        return std::unordered_map<std::string, Value>::find(v);
    }

    typename std::unordered_map<std::string,Value>::iterator find(const char* v )
    {
        tmp_.assign(v);
        return std::unordered_map<std::string, Value>::find(v);
    }

private:
    thread_local static std::string tmp_;
};

学分:
Davide Faconti

r8uurelv

r8uurelv8#

很抱歉回答了这个老问题,但它仍然出现在搜索引擎结果中...在本例中,您的unordered_map使用字符串类型作为其键,find方法正在寻找一个对字符串的引用,这个字符串不会生成分配。2你的string_view类存储了一个指向字符串的指针。3因此你的string_view类视图类可以将指针解引用到Map所需类型的ref中,而不会导致分配。该方法如下所示...

string &string_view::getRef() const
{
    return *_ptr;
}

如果要将string_view与Map一起使用,则如下所示

auto found=map.find(string_view_inst.getRef());

注意这对于c++17 string_view类不起作用,因为它不内部存储std::string对象
ps.你的string_view类可能不适合CPU缓存,因为它存储了一个指向堆中某个位置的字符串的指针,而字符串本身存储了一个指向堆中其他位置的实际数据的指针。每次你访问string_view时,都会导致一个双重解引用。

pkwftd7m

pkwftd7m9#

您可以允许视图隐式转换为std::string

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

相关问题