什么是透明比较器？

Question

在C++ 14中,关联容器似乎已从C++ 11改变 - [associative.reqmts]/13说:

成员函数模板find,count,lower_bound,upper_bound,并且equal_range不得,除非类型参与重载决议Compare::is_transparent存在.

使比较器"透明"的目的是什么？

C++ 14还提供了这样的库模板:

template <class T = void> struct less {
    constexpr bool operator()(const T& x, const T& y) const;
    typedef T first_argument_type;
    typedef T second_argument_type;
    typedef bool result_type;
};

template <> struct less<void> {
    template <class T, class U> auto operator()(T&& t, U&& u) const
    -> decltype(std::forward<T>(t) < std::forward<U>(u));
    typedef *unspecified* is_transparent;
};

因此,例如,std::set<T, std::less<T>>将不会有一个透明的比较,而是std::set<T, std::less<>> 将有一个.

这解决了什么问题,这会改变标准容器的工作方式吗？例如,模板参数std::set依然Key, Compare = std::less<Key>, ...,所以没有默认设置失去了find,count等会员？

Answer 1

这解决了什么问题,

见Dietmar和remyabel的回答.

这会改变标准容器的工作方式吗？

不,不是默认的.

新的成员函数模板重载find等允许您使用与容器的键相当的类型,而不是使用键类型本身.请参阅JoaquínMªLópezMuñoz撰写的N3465以及添加此功能的详细,精心编写的提案.

在布里斯托尔会议上,LWG同意异端查找功能是有用且可取的,但我们无法确定Joaquín的提议在所有情况下都是安全的.N3465提案会对某些程序造成严重问题(请参阅对现有代码的影响部分).Joaquín准备了一份更新的草案提案,其中包含一些具有不同权衡的替代实施方案,这对于帮助LWG了解优缺点非常有用,但它们都有可能以某种方式破坏某些程序,因此没有就增加该功能达成共识.我们决定尽管无条件地添加该功能是不安全的,但如果默认情况下禁用该功能并且仅"选择加入"将是安全的.

N3657提案(这是我自己和STL基于N3465的最后一刻修订以及后来Joaquín未发表的草案)的主要区别在于将is_transparent类型添加为可用于选择新功能的协议.

如果你不使用"透明函子"(即定义is_transparent类型的那个),那么容器的行为与它们一直以来的行为相同,而且仍然是默认值.

如果您选择使用std::less<>(这是C++ 14的新功能)或其他"透明仿函数"类型,那么您将获得新功能.

使用std::less<>别名模板很容易:

template<typename T, typename Cmp = std::less<>, typename Alloc = std::allocator<T>>
  using set = std::set<T, Cmp, Alloc>;

这个名字is_transparent来自STL的N3421,它为C++ 14增加了"钻石操作员"."透明函子"是接受任何参数类型(不必相同)并简单地将这些参数转发给另一个运算符的函数.这样的仿函数正好是您想要在关联容器中进行异构查找的内容,因此该类型is_transparent被添加到所有菱形运算符并用作标记类型以指示应在关联容器中启用新功能.从技术上讲,容器不需要"透明函子",只需支持使用异构类型调用它(例如,根据STL的定义,https ://stackoverflow.com/a/18940595/981959中的pointer_comp类型不透明,但是定义允许它用于解决问题).如果你永远只能在你的查找与类型的键或则仅需要调用同类型的参数和(以任何顺序),它并不需要真正的透明.我们之所以使用这个名称,部分是因为我们无法想出一个更好的名字(我更喜欢这个因为这样的仿函数使用静态多态,但是已经存在一个引用动态多态的类型特征).pointer_comp::is_transparentstd::set<T, C>TintCTintis_polymorphicstd::is_polymorphic

Answer 2

在C++ 11有没有成员模板find(),lower_bound()等等.也就是说,没有被这种变化丢失.使用n3657引入了成员模板,以允许异构密钥与关联容器一起使用.除了好的和坏的例子之外,我没有看到任何具体的例子.

该is_transparent用途旨在避免不必要的转换.如果成员模板不受约束,则现有代码可以直接传递直接对象,这些对象在没有成员模板的情况下进行转换.来自n3657的示例用例是std::set<std::string>使用字符串文字定位对象:使用C++ 11定义,std::string在将字符串文字传递给相应的成员函数时构造对象.通过更改,可以直接使用字符串文字.如果底层比较函数对象是专门实现的std::string那么糟糕,因为现在std::string将为每个比较创建一个.另一方面,如果底层比较函数对象可以采用a std::string和字符串文字,则可以避免构造临时对象.

is_transparent比较函数对象中的嵌套类型提供了一种指定是否应使用模板化成员函数的方法:如果比较函数对象可以处理异构参数,则它定义此类型以指示它可以有效地处理不同的参数.例如,新的操作符函数对象只是委托operator<()并声称是透明的.至少,std::string这种方法的工作量超过了运营商的char const*参数.由于这些函数对象也是新的,即使它们做错了(即需要某种类型的转换),它至少也不会是一个静默的变化,导致性能下降.

Answer 3

_{以下是来自n3657的所有复制面食.}

问:使比较器"透明"的目的是什么？

A.关联容器查找函数(find,lower_bound,upper_bound,equal_range)仅接受key_type的参数,要求用户构造(隐式或显式)key_type的对象以进行查找.这可能是昂贵的,例如,当比较器功能仅查看对象的一个​​字段时,构造大对象以在集合中搜索.用户之间强烈希望能够使用与key_type相当的其他类型进行搜索.

问:这解决了什么问题

答:LWG关注的代码如下:

std::set<std::string> s = /* ... */;
s.find("key");

在C++ 11中,这将构造一个单独的std :: string临时,然后将其与元素进行比较以找到密钥.

随着N3465提出的更改,std :: set :: find()函数将是一个无约束的模板,它将const char*传递给比较器函数std :: less,它将构造一个std :: string临时函数.每一次比较.LWG认为这个性能问题是一个严重的问题.模板find()函数也会阻止在指针容器中找到NULL,这会导致以前有效的代码不再编译,但这被认为是一个比静默性能回归更不严重的问题

问:这会改变标准容器的工作方式

答:此提议通过使用成员函数模板重载查找成员函数来修改关联容器.没有语言变化.

问:默认设置也会丢失其查找,计数等成员

答:几乎所有现有的C++ 11代码都不受影响,因为除非使用新的C++ 14库特性作为比较函数,否则不存在成员函数.

引用Yakk,

在C++ 14中,如果Compare :: is_transparent存在,则std :: set :: find是一个模板函数.传入的类型不需要是Key,只需在比较器下等效.

和n3657,

在23.2.4 [associative.reqmts]中添加第13段:除非Compare :: is_transparent类型不存在,否则成员函数模板find,lower_bound,upper_bound和equal_range不应参与重载解析.

n3421提供了"透明运算符函数"的示例.

该完整的代码是在这里.

Answer 4

Stephan T Lavavej谈到编译器不断创建临时代码的问题,以及他的透明运算符函数的提议将如何在c ++ 1y中解决这个问题

GoingNative 2013 - 不要帮助编译器(大约小时标记)