如何实现STL式迭代器和避免常见的陷阱? [英] How to implement an STL-style iterator and avoid common pitfalls?
问题描述
我制作了一个集合,我想为其提供一个STL风格的随机访问迭代器。我正在搜索一个迭代器的示例实现,但我没有找到任何。我知道需要const重载 []
和 *
运算符。迭代器的要求是STL风格还是其他一些要避免的陷阱(如果有)?
I made a collection for which I want to provide an STL-style, random-access iterator. I was searching around for an example implementation of an iterator but I didn't find any. I know about the need for const overloads of []
and *
operators. What are the requirements for an iterator to be "STL-style" and what are some other pitfalls to avoid (if any)?
其他上下文:这是一个库并且我不想引入任何依赖,除非我真的需要。我写了我自己的集合,以便能够提供C ++ 03和C ++ 11与相同的编译器之间的二进制兼容性(所以没有STL可能会破坏)。
Additional context: This is for a library and I don't want to introduce any dependency on it unless I really need to. I write my own collection to be able to provide binary compatibility between C++03 and C++11 with the same compiler (so no STL which would probably break).
推荐答案
http://www.cplusplus.com/reference/std/iterator/ 有一个方便的图表,详细说明了C ++ 11标准第24.2.2节的规范。基本上,迭代器具有描述有效操作的标签,并且标签具有层次结构。下面是纯粹的符号,这些类实际上不存在。
http://www.cplusplus.com/reference/std/iterator/ has a handy chart that details the specs of § 24.2.2 of the C++11 standard. Basically, the iterators have tags that describe the valid operations, and the tags have a hierarchy. Below is purely symbolic, these classes don't actually exist as such.
iterator {
iterator(const iterator&);
~iterator();
iterator& operator=(const iterator&);
iterator& operator++(); //prefix increment
reference operator*() const;
friend void swap(iterator& lhs, iterator& rhs); //C++11 I think
};
input_iterator : public virtual iterator {
iterator operator++(int); //postfix increment
value_type operator*() const;
pointer operator->() const;
friend bool operator==(const iterator&, const iterator&);
friend bool operator!=(const iterator&, const iterator&);
};
//once an input iterator has been dereferenced, it is
//undefined to dereference one before that.
output_iterator : public virtual iterator {
reference operator*() const;
iterator operator++(int); //postfix increment
};
//dereferences may only be on the left side of an assignment
//once an input iterator has been dereferenced, it is
//undefined to dereference one before that.
forward_iterator : input_iterator, output_iterator {
forward_iterator();
};
//multiple passes allowed
bidirectional_iterator : forward_iterator {
iterator& operator--(); //prefix increment
iterator operator--(int); //postfix decrement
};
random_access_iterator : bidirectional_iterator {
friend bool operator<(const iterator&, const iterator&);
friend bool operator>(const iterator&, const iterator&);
friend bool operator<=(const iterator&, const iterator&);
friend bool operator>=(const iterator&, const iterator&);
iterator& operator+=(size_type);
friend iterator operator+(const iterator&, size_type);
friend iterator operator+(size_type, const iterator&);
iterator& operator-=(size_type);
friend iterator operator-(const iterator&, size_type);
friend difference_type operator-(iterator, iterator);
reference operator[](size_type) const;
};
您可以专门 std :: iterator_traits< youriterator>
,或者将相同的typedef放在迭代器本身,或者继承 std :: iterator
(它有这些typedefs)。我喜欢第二个选项,以避免改变 std
命名空间中的内容,并且为了可读性,但大多数人继承 std :: iterator
。
You can either specialize std::iterator_traits<youriterator>
, or put the same typedefs in the iterator itself, or inherit from std::iterator
(which has these typedefs). I prefer the second option, to avoid changing things in the std
namespace, and for readability, but most people inherit from std::iterator
.
struct std::iterator_traits<youriterator> {
typedef ???? difference_type; //almost always ptrdif_t
typedef ???? value_type; //almost always T
typedef ???? reference; //almost always T& or const T&
typedef ???? pointer; //almost always T* or const T*
typedef ???? iterator_category; //usually std::forward_iterator_tag or similar
};
请注意,iterator_category应该是 std :: input_iterator_tag
, std :: output_iterator_tag
, std :: forward_iterator_tag
, std :: bidirectional_iterator_tag
或 std :: random_access_iterator_tag
,具体取决于迭代器满足的要求。根据您的迭代器,您可以选择专门化 std :: next
, std :: prev
, std :: advance
和 std :: distance
,但这是很少需要的。在非常罕见的情况下,您可能希望专门化 std :: begin
和 std :: end
。
Note the iterator_category should be one of std::input_iterator_tag
, std::output_iterator_tag
, std::forward_iterator_tag
, std::bidirectional_iterator_tag
, or std::random_access_iterator_tag
, depending on which requirements your iterator satisfies. Depending on your iterator, you may choose to specialize std::next
, std::prev
, std::advance
, and std::distance
as well, but this is rarely needed. In extremely rare cases you may wish to specialize std::begin
and std::end
.
你的容器应该还有一个 const_iterator
,这是一个它类似于你的迭代器
,除了它应该可以从迭代器
隐式构造,用户应该无法修改数据。它的内部指针通常是指向非常量数据的指针,并且 iterator
从 const_iterator
继承以尽量减少代码重复。
Your container should probably also have a const_iterator
, which is a (possibly mutable) iterator to constant data that is similar to your iterator
except it should be implicitly constructable from a iterator
and users should be unable to modify the data. It is common for its internal pointer to be a pointer to non-constant data, and have iterator
inherit from const_iterator
so as to minimize code duplication.
我的帖子在编写自己的STL容器具有更完整的容器/迭代器原型。
My post at Writing your own STL Container has a more complete container/iterator prototype.
这篇关于如何实现STL式迭代器和避免常见的陷阱?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!