使用 string_view 进行地图查找

Question

以下代码无法在最近的编译器（g++-5.3、clang++-3.7）上构建。

#include <map>
#include <functional>
#include <experimental/string_view>

void f()
{
    using namespace std;
    using namespace std::experimental;
    map<string, int> m;
    string s = "foo";
    string_view sv(s);
    m.find(sv);
}

clang 返回的错误：

error: no matching member function for call to 'find'
    m.find(sv);
    ~~^~~~

但是 find 不应该能够使用可比较的类型吗？ Cppreference 提到以下重载：

template< class K > iterator find( const K& x );

同样的错误发生在boost::string_ref。

Answer 1

您需要指定一个transparent comparator explicitly (like std::less<>):

std::map<std::string, int, std::less<>> m;
//                         ~~~~~~~~~~^

std::map<K,V> 默认其比较器为 std::less<K> (i.e., a non-transparent one), and since ([associative.reqmts]/p13):

The member function templates find, count, lower_bound, upper_bound, and equal_range shall not participate in overload resolution unless the qualified-id Compare::is_transparent is valid and denotes a type (14.8.2).

模板成员函数 find 不是一个可行的候选者。

Heterogeneous comparison lookup for associative containers was added to c++14。最初的提案有破坏现有代码的风险。例如：

c.find(x);

在语义上等同于：

key_type key = x;
c.find(key);

特别是，x 和 key_type 之间的转换 只发生一次 ，并且 在实际调用之前 .

异构查找取代了此转换，以支持 key 和 x 之间的比较。这可能会导致现有代码的性能下降（由于每次比较之前的附加转换）甚至中断编译（如果比较运算符是成员函数，它将不会对左侧操作数应用转换）：

#include <set>
#include <functional>

struct A
{
    int i;

    A(int i) : i(i) {}
};

bool operator<(const A& lhs, const A& rhs)
{
    return lhs.i < rhs.i;
}

int main()
{
    std::set<A, std::less<>> s{{1}, {2}, {3}, {4}};
    s.find(5);
}

DEMO

为了解决这个问题，我们通过添加 linked question.

中描述的透明比较器的概念来选择加入新行为。

使用 string_view 进行地图查找

Use of string_view for map lookup

c++

dictionary

c++14

string-view