c++ 如果没有std::contiguous_iterator_tag,如何检测连续迭代器?

mwg9r5ms  于 2023-10-21  发布在  其他
关注(0)|答案(1)|浏览(145)

C++17引入了ContiguousIterator http://en.cppreference.com/w/cpp/iterator的概念。然而,似乎没有计划让std::iterator_traits<It>::iterator_category报告contiguous_iterator_tag(就像我们现在有random_access_iterator_tag一样)。
为什么contiguous_iterator_tag不见了?
是否有一个传统的协议来确定一个迭代器是否是连续的?还是编译时测试?
在过去我提到过,* 对于容器 * 如果有一个.data()成员转换为::value类型的指针,并且有一个.size()成员转换为指针差异,那么应该假设容器是连续的,但我不能拉迭代器的类似功能。
一种解决方案是为连续迭代器提供data函数。
当然,如果&(it[n]) == (&(*it)) + n对所有n都有效,那么Contistance概念就可以工作,但是这在编译时无法检查。

编辑:我发现这个视频把它放在C++概念的更广泛的背景下。帕特里克·涅兹尔斯基的CppCon 2016: "Building and Extending the Iterator Hierarchy in a Modern, Multicore World"。解决方案使用了概念(Lite),但最终的想法是连续迭代器应该实现pointer_from函数(与我的data(...)函数相同)。

结论是,概念将有助于理论的形式化,但它们不是魔术,在某种意义上,某人,某处将在连续的迭代器上定义新的特别命名的函数。这篇文章推广到了分段迭代器(以及相应的函数segmentlocal),不幸的是,它没有提到任何关于跨步指针的事情。

编辑2020:

该标准目前已

struct contiguous_iterator_tag: public random_access_iterator_tag { };

https://en.cppreference.com/w/cpp/iterator/iterator_tags

fhg3lkii

fhg3lkii1#

原始答案

基本原理在N4284中给出,这是连续迭代器建议的采用版本:
本文引入了术语“连续迭代器”作为随机访问迭代器的改进,没有引入相应的contiguous_iterator_tag,在Nevin Liber的论文N3884“连续迭代器:随机存取迭代器的改进。
有些代码被破坏了,因为它假设std::random_access_iterator不能被细化,并对其进行了显式检查。基本上,它破坏了不依赖多态性来检查迭代器类别的坏代码,但它仍然破坏了代码,因此std::contiguous_iterator_tag被从提案中删除。
此外,std::reverse_iterator类还有一个额外的问题:反向连续迭代器不能是连续迭代器,而是常规随机访问迭代器。这个问题本来可以在std::reverse_iterator中得到解决,但是更多的用户定义的迭代器 Package 器在复制迭代器类别的同时增加了迭代器,这可能会撒谎或停止正常工作(例如Boost迭代器适配器)。

C++20更新

从我上面的原始答案开始,std::contiguous_iterator_tag被带回到TS范围,然后在C++20中采用。为了避免上述问题,std::iterator_traits<T>::iterator_category的行为没有改变。相反,std::iterator_traits的用户专门化现在可以定义一个额外的iterator_concept成员类型别名,该别名允许别名std::contiguous_iterator_tag或以前的迭代器标记。标准组件已相应更新,以便将指针和适当的迭代器标记为连续迭代器。
该标准定义了一个仅用于表达式的 ITER_CONCEPT(Iter),给定一个迭代器类型Iter,如果它存在,将别名std::iterator_traits<Iter>::iterator_concept,否则别名std::iterator_traits<Iter>::iterator_category。没有等价的标准的面向用户的类型trait,但是 ITER_CONCEPT 被新的迭代器概念使用。这是一个强有力的提示,你应该使用这些迭代器概念而不是老式的标记分派来实现行为取决于迭代器类别的新函数。也就是说,概念可以作为布尔特征使用,所以你可以简单地检查迭代器是否是连续迭代器,如下所示:

static_assert(std::contiguous_iterator<Iter>);

因此std::contiguous_iterator是C++20的概念,你应该使用它来检测一个给定的迭代器是一个随机访问迭代器(它也有一个范围对应物:std::contiguous_range)。值得注意的是,除了要求 ITER_CONCEPT 匹配std::contiguous_iterator_tag之外,std::contiguous_iterator还有一些额外的限制:最值得注意的是,它要求std::to_address(it)是返回原始指针类型的有效表达式。std::to_address是一个小的实用函数,旨在避免在尝试检索连续迭代器指向的地址时可能出现的一些陷阱-您可以阅读有关它在Helpful pointers for ContiguousIterator中解决的问题的更多信息。

  • 关于实施ITER_CONCEPT*:毫无意义的是,实现标准中描述的 ITER_CONCEPT 只有在you are the owner of std::iterator_traits的情况下才可能,因为它需要检测是否使用了std::iterator_traits的主示例化。

相关问题