连续迭代器检测
Contiguous iterator detection
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
不见了?
有没有一种约定俗成的协议来判断一个迭代器是否是连续的?
还是编译时测试?
过去我提到 for 容器 如果有一个 .data()
成员转换为指向 ::value
类型的指针并且有 .size()
成员可转换为指针差异,那么应该假定容器是连续的,但我无法提取迭代器的类似功能。
一个解决方案可能是也有一个用于连续迭代器的 data
函数。
如果 &(it[n]) == (&(*it)) + n
,对于所有 n
,Contiguous 概念当然有效,但这无法在编译时检查。
编辑:我发现这个视频将其置于更广泛的 C++ 概念上下文中。 CppCon 2016: "Building and Extending the Iterator Hierarchy in a Modern, Multicore World" 作者:Patrick Niedzielski。该解决方案使用概念(精简版),但最后的想法是连续迭代器应该实现一个 pointer_from
函数(与我的 data(...)
函数相同)。
结论是概念将有助于形式化理论,但它们并不是魔术,因为某个地方的某个人会在连续的迭代器上定义新的特别命名的函数。
谈话概括为分段迭代器(具有相应的函数 segment
和 local
),不幸的是它没有说任何关于跨步指针的内容。
2020 年编辑:
标准现在有
struct contiguous_iterator_tag: public random_access_iterator_tag { };
原回答
基本原理在 N4284 中给出,这是连续迭代器提案的采用版本:
This paper introduces the term "contiguous iterator" as a refinement of random-access iterator, without introducing a corresponding contiguous_iterator_tag
, which was found to break code during the Issaquah discussions of Nevin Liber's paper N3884 "Contiguous Iterators: A Refinement of Random Access Iterators".
一些代码被破坏是因为它假设 std::random_access_iterator
不能被改进,并且有明确的检查。基本上它破坏了不依赖多态性来检查迭代器类别的错误代码,但它仍然破坏了代码,因此 std::contiguous_iterator_tag
从提案中删除。
此外,std::reverse_iterator
-like 类 还有一个问题:反向连续迭代器不能是连续迭代器,而是常规随机访问迭代器。 std::reverse_iterator
本可以解决此问题,但更多在复制迭代器类别时扩充迭代器的用户定义的迭代器包装器可能会撒谎或停止正常工作(例如 Boost 迭代器适配器)。
C++20 更新
由于我上面的原始回答,std::contiguous_iterator_tag
在 Ranges 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
。没有等效的面向用户的标准类型特征,但是 ITER_CONCEPT 被新的迭代器概念使用。这是一个强烈的提示,您应该使用这些迭代器概念而不是旧式标记分派来实现其行为取决于迭代器类别的新函数。上述概念可用作布尔特征,因此您可以简单地检查迭代器是否为连续迭代器,如下所示:
static_assert(std::contiguous_iterator<Iter>);
std::contiguous_iterator
is thus the C++20 concept that you should use to detect that a given iterator is a random-access iterator (it also has a ranges counterpart: std::contiguous_range
). It is worth noting that std::contiguous_iterator
has a few additional constraints besides requiring that ITER_CONCEPT matches std::contiguous_iterator_tag
: most notably it requires std::to_address(it)
to be a valid expression returning a raw pointer type. std::to_address
is a small utility function meant to avoid a few pitfalls that can occur when trying to retrieve the address where a contiguous iterator points - you can read more about the issues it solves in Helpful pointers for ContiguousIterator
.
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
不见了?
有没有一种约定俗成的协议来判断一个迭代器是否是连续的? 还是编译时测试?
过去我提到 for 容器 如果有一个 .data()
成员转换为指向 ::value
类型的指针并且有 .size()
成员可转换为指针差异,那么应该假定容器是连续的,但我无法提取迭代器的类似功能。
一个解决方案可能是也有一个用于连续迭代器的 data
函数。
如果 &(it[n]) == (&(*it)) + n
,对于所有 n
,Contiguous 概念当然有效,但这无法在编译时检查。
编辑:我发现这个视频将其置于更广泛的 C++ 概念上下文中。 CppCon 2016: "Building and Extending the Iterator Hierarchy in a Modern, Multicore World" 作者:Patrick Niedzielski。该解决方案使用概念(精简版),但最后的想法是连续迭代器应该实现一个 pointer_from
函数(与我的 data(...)
函数相同)。
结论是概念将有助于形式化理论,但它们并不是魔术,因为某个地方的某个人会在连续的迭代器上定义新的特别命名的函数。
谈话概括为分段迭代器(具有相应的函数 segment
和 local
),不幸的是它没有说任何关于跨步指针的内容。
2020 年编辑:
标准现在有
struct contiguous_iterator_tag: public random_access_iterator_tag { };
原回答
基本原理在 N4284 中给出,这是连续迭代器提案的采用版本:
This paper introduces the term "contiguous iterator" as a refinement of random-access iterator, without introducing a corresponding
contiguous_iterator_tag
, which was found to break code during the Issaquah discussions of Nevin Liber's paper N3884 "Contiguous Iterators: A Refinement of Random Access Iterators".
一些代码被破坏是因为它假设 std::random_access_iterator
不能被改进,并且有明确的检查。基本上它破坏了不依赖多态性来检查迭代器类别的错误代码,但它仍然破坏了代码,因此 std::contiguous_iterator_tag
从提案中删除。
此外,std::reverse_iterator
-like 类 还有一个问题:反向连续迭代器不能是连续迭代器,而是常规随机访问迭代器。 std::reverse_iterator
本可以解决此问题,但更多在复制迭代器类别时扩充迭代器的用户定义的迭代器包装器可能会撒谎或停止正常工作(例如 Boost 迭代器适配器)。
C++20 更新
由于我上面的原始回答,std::contiguous_iterator_tag
在 Ranges 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
。没有等效的面向用户的标准类型特征,但是 ITER_CONCEPT 被新的迭代器概念使用。这是一个强烈的提示,您应该使用这些迭代器概念而不是旧式标记分派来实现其行为取决于迭代器类别的新函数。上述概念可用作布尔特征,因此您可以简单地检查迭代器是否为连续迭代器,如下所示:
static_assert(std::contiguous_iterator<Iter>);
std::contiguous_iterator
is thus the C++20 concept that you should use to detect that a given iterator is a random-access iterator (it also has a ranges counterpart: std::contiguous_range
). It is worth noting that std::contiguous_iterator
has a few additional constraints besides requiring that ITER_CONCEPT matches std::contiguous_iterator_tag
: most notably it requires std::to_address(it)
to be a valid expression returning a raw pointer type. std::to_address
is a small utility function meant to avoid a few pitfalls that can occur when trying to retrieve the address where a contiguous iterator points - you can read more about the issues it solves in Helpful pointers for ContiguousIterator
.