英文:
Do C++ iterators need to be trivially copyable?
问题
我在考虑创建一个用于解析二进制格式的迭代器。后来我意识到，为了正确解析它，这个迭代器需要不时地堆叠一些上下文。由于 std::stack 不是平凡复制的，我现在有以下问题：
是否拥有非平凡复制的迭代器只是一个坏主意，还是迭代器作为一个概念的要求？
英文:
I was thinking about creating an iterator to parse a binary format. Then I realized that in order to parse it properly, the iterator would need, from time to time, to stack up some context. Since a std::stack is not trivially copyable, I now have the following question:
Is it just a bad idea to have non trivially copyable iterators, or is it a requirement of Iterator as a concept?
答案1
得分: 3
不，迭代器 不必是可平凡复制的：
如果类型
X满足 Cpp17Iterator 要求，那么：
X满足 Cpp17CopyConstructible、Cpp17CopyAssignable、Cpp17Swappable 和 Cpp17Destructible 要求 (utility.arg.requirements, swappable.requirements)，以及iterator_traits<X>::difference_type是有符号整数类型或 void，并且- 表 86 中的表达式有效且具有指定的语义。
C++20 迭代器概念也不强制要求这样的要求。
迭代器不是可平凡复制的，但应尽量轻量化
然而，迭代器通常应尽量轻量化，算法会假定复制迭代器是廉价的操作。当您为自己的容器设计迭代器时，应尽量使它们紧凑且便于复制。
如何使迭代器更轻量化的示例
如果您需要一个迭代器来存储 std::stack，那么可能出现了问题，但您可能能够消除它。例如，假设您的迭代器在树中执行深度优先遍历。如果该图中的节点没有指向其父节点的指针，那么迭代器需要保持一个父节点的堆栈，以便可以返回上去。但是，如果每个节点都存储指向其父节点的指针，那么迭代器就不需要父节点堆栈了。此外，我们可以查看返回到父节点时来自哪个方向，并确定下一个要去的子节点。这样，我们不需要跟踪每个堆栈帧中的位置。
如果这些方法都不起作用，您仍然可以在没有任何迭代器的情况下遍历数据结构，例如编写一个接受执行某些操作的函数对象的 for_each 函数。
总结一下：
- 在数据结构中保留更多状态
- 使遍历更智能化（即在
operator++中添加更多逻辑） - 在某些情况下完全避免使用迭代器
英文:
No, an Iterator does not have to be trivially copyable:
> A type X meets the Cpp17Iterator requirements if:
> - X meets the Cpp17CopyConstructible, Cpp17CopyAssignable, Cpp17Swappable, and Cpp17Destructible requirements ([utility.arg.requirements], [swappable.requirements]), and
> - iterator_traits<X>::difference_type is a signed integer type or void, and
> - the expressions in Table 86 are valid and have the indicated semantics.
The C++20 iterator concepts also don't impose such a requirement.
Iterators are not trivially copyable, but should be lightweight
However, an iterator is generally supposed to be as lightweight as possible, and algorithms will assume that copying an iterator is a cheap operation. When you are designing iterators for your own container, you should make them as compact and cheap to copy as you can.
Example of how to make an iterator more lightweight
If you need an iterator to store a std::stack, something has probably gone wrong, but you might be able to eliminate it. For example, say your iterator performs depth-first traversal in a tree. If nodes in this graph don't have a pointer to their parent node, you need the iterator to keep a stack of parents so that it can go back up. However, if each node stores a pointer to its parent, the iterator doesn't need a parent stack. Also, we can look at the direction where we came from when going back up to a parent, and determine which child to go to next. This way, we don't need to track our own position within each stack frame.
If none of these things work, you could still traverse the data structure without any iterators, e.g. by writing a for_each function which accepts a function object that does something for every element.
In summary:
- keep more state in your data structure
- make traversal more intelligent (i.e. more logic in
operator++) - avoid use of iterators in some cases completely
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论