在std::unordered_set中使用std::string_view和std::string

13
假设你有一个 std::unordered_set<std::string>
你有一个 std::string_view 对象想要在容器中搜索。问题是,你不想从你的 std::string_view 创建一个 std::string,因为这会有点违背使用 std::string_view 的初衷。
然而,似乎 std::string_view 应该可以用作键;应该有一些方法来比较 std::string_viewstd::string>,因为它们基本上代表相同的东西。但在 STL 中并没有这种方法。
这是个死结,我必须为我的 std::unordered_set 编写自己的比较对象,以便使用 std::string_viewstd::string 对象吗?
编辑:这个问题特定于 string_view 对象。重复的问题与此无关。我得到了一个独特问题的独特答案,正如所预期的那样。

1
您要查找的属性通常被称为“透明查找”,恐怕自那个答案以来没有任何变化。 :( - Max Langhof
1
@MaxLanghof: 那个问题 仅限于C++11,并涵盖了使用char*和长度的工作。 std::string_view是C++17的一个特性,因此即使有解决方案,该问题也不太可能吸引它们。人们希望string_view的发明包括解决这种用例(尽管如果没有也不会感到惊讶)。 - ShadowRanger
1
@ShadowRanger,除非std::unordered_map/set被专门用于std::string类型的键,否则在这些类型上进行异构查找是不可用的(并且在不久的将来也将如此)。我承认前一个条件在重复问题中没有明确说明,但我通过简单地搜索问题标题就可以轻松找到所需的信息,以便得出这样的结论。 - Max Langhof
1
@ShadowRanger更重要的是,我在这里提出的问题的最佳答案将是副本中的逐字复制(好吧,它的前两段)。 - Max Langhof
1
@MaxLanghof:等等,我有点糊涂了。我以为C++14的异构查找正是为这种情况设计的?为什么这里不起作用呢?https://dev59.com/m1wZ5IYBdhLWcg3wC8f4 - Mooing Duck
显示剩余2条评论
1个回答

5
我没有一个完美的解决方案,但有一个可能的变通方法,需要一些自定义代码,代价是增加内存使用量。您可以将std::unordered_set<std::string>替换为具有键视图和字符串值(支持视图的字符串)的std::unordered_map

不幸的是,由于小字符串优化,我们不能依赖std::move保留底层string数据的原始地址,所以像这样的操作:

std::string to_insert(...);
mymap.try_emplace(to_insert, std::move(to_insert));

不会起作用。 相反,它必须是一个std :: unordered_map >,以便我们可以保留字符串字符的唯一地址,使代码更像:
auto to_insert = std::make_unique<std::string>(...);
mymap.try_emplace(*to_insert, std::move(to_insert));

虽然插入操作可能会有些丑陋,但简单的成员测试仍然很简单,因为std::string定义了一个隐式的operator std::string_view,而std::string_view具有将char*隐式构造函数,因此成员测试仍然保持简单:

if (mymap.count(some_string)) { ... }

判断some_stringchar*std::string_view还是std::string

注:我不确定基于两行的try_emplace插入代码是否合法,因为我对C++有点生疏,并且非常担心在使用unique_ptr的表达式中进行move; 在g++ 7.2上似乎可以工作,而且我认为传递给构造值的参数是安全的, 因为try_emplace的键参数是立即构造的,但我承认我的C++评估顺序的理解(或缺乏理解)并不完美。如果我做了违法的事情,而不仅仅是丑陋,那么修复它将需要稍微更丑陋的(但绝对有序的):

auto to_insert = std::make_unique<std::string>(...);
std::string_view key{*to_insert};
mymap.try_emplace(std::move(key), std::move(to_insert));

附加说明:仅有使用emplace/emplace_hint/try_emplace函数可以在这个设计中安全地更新mymap中的条目。如果在构建映射时遇到相同的键,则使用mymap[key] = std::move(to_insert);insert_or_assign会出现问题,因为原始的string_view(引用原始string的数据)将被保留,而值将被替换为新的string,从而使string_view的指针失效。虽然insert不会替换值,但我认为使用它需要更像try_emplace的三行代码设计,因为如果你试图在pair构造的过程中构造视图和unique_ptr,则会发生无序构造。


注意:阅读了我的问题的回答并仔细思考后,虽然mymap.try_emplace(*to_insert, std::move(to_insert));是合法和安全的(由于try_emplace对键进行急切评估,但值的构造是懒惰的),但是这是一种代码异味(code smell),所以我建议使用将string_view转换从try_emplace中分离出来的解决方案,即使它稍微慢一些。 - ShadowRanger
在我的上一条评论中,我建议将string_view转换从try_emplace中分离可能会“微不足道地变慢”。我进行了测试,结果发现在-Os下,g++ 7.2.0为我的测试案例生成的输出是相同的,并且在-O3下几乎相同(到了一个我相当确定它会执行相同的代码路径,因为修改后的代码路径看起来涉及异常处理并且永远不会在成功时运行)。重点是,通过牺牲一行额外的代码,并且不会影响性能,你可以避免代码味道,所以请这样做;你的维护者会感谢你的。 :-) - ShadowRanger

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接