我有一个使用字符串类型作为键的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,并且将迭代器返回到匹配值。
是否有任何变通方案?
9条答案
按热度按时间dfuffjeb1#
P0919R2 Heterogeneous lookup for unordered containers已被合并到C++2a的工作草案中!
摘要似乎与我最初的问题完全匹配:-)
摘要
该方案为C++标准库中的无序关联容器增加了异构查找支持。因此,当不同(但兼容)类型作为成员函数的键提供时,不需要创建临时键对象。这也使得无序和常规关联容器接口和功能彼此更加兼容。
使用本文建议的更改后,以下代码将正常工作,而不会对性能造成任何影响:
来自cppreference的完整示例
igsr9ssn2#
如上所述,C++14没有为
std::unordered_map
提供异构查找(不像std::map
)。你可以使用Boost.MultiIndex来定义一个相当接近std::unordered_map
的替代,它允许你查找string_view
而不需要分配临时的std::string
:**一个
产出
de90aj5v3#
我也面临同样的问题。
我们需要两个结构体:
对于无序Map:
对于无序集:
现在可以使用string_view了。
ryoqjall4#
看起来就在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
索引。brgchamk5#
这个解决方案有一些缺点,这些缺点可能会也可能不会使它不适合您的环境。
您可以创建一个 Package 类:
然后修改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插入),就会有一些缺点,同样,这可能会使这种方法太令人不快,以至于不可行,这取决于你的预期用途。
93ze6v8z6#
还有一种选择是通过使用多个容器来分离查找和数据管理:
查找是使用
string_view
来完成的,不需要分配。每当插入一个新的键时,我们需要先添加一个真实的字符串分配:在
mapKeyStore
中使用std::string
会直观得多,但是使用std::string
并不能保证字符串内存不变(例如,如果向量大小调整)。对于unique_ptr
,这是强制的。但是,我们需要一些特殊的转换/分配例程,如果你有一个自定义的字符串容器可以保证移动时的数据一致性(并且强制向量使用移动),那么你可以在这里使用它。缺点
上述方法的缺点是处理删除操作非常繁琐,如果不成熟的话,代价会很高。如果Map只创建一次或者只增长,这不是问题,上述模式工作得很好。
运行示例
下面的示例包括一个密钥的自然删除。
当然,这两个容器可以放在一个 Package 器中,该 Package 器自己处理插入和删除。
u91tlkcl7#
我只介绍我在github上发现的一个变体,它涉及到定义一个新的map类来 Package std。
重新定义一些密钥API来拦截我们想要的适配器,并使用静态字符串来复制密钥。
这不一定是一个好的解决方案,但知道它存在的人谁认为它足够有趣。
原件:
https://gist.github.com/facontidavide/95f20c28df8ec91729f9d8ab01e7d2df
代码要点:
学分:
Davide Faconti
r8uurelv8#
很抱歉回答了这个老问题,但它仍然出现在搜索引擎结果中...在本例中,您的unordered_map使用字符串类型作为其键,find方法正在寻找一个对字符串的引用,这个字符串不会生成分配。2你的string_view类存储了一个指向字符串的指针。3因此你的string_view类视图类可以将指针解引用到Map所需类型的ref中,而不会导致分配。该方法如下所示...
如果要将string_view与Map一起使用,则如下所示
注意这对于c++17 string_view类不起作用,因为它不内部存储std::string对象
ps.你的string_view类可能不适合CPU缓存,因为它存储了一个指向堆中某个位置的字符串的指针,而字符串本身存储了一个指向堆中其他位置的实际数据的指针。每次你访问string_view时,都会导致一个双重解引用。
pkwftd7m9#
您可以允许视图隐式转换为
std::string
: