如何实现 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 output 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 decrement
    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;
};

contiguous_iterator : random_access_iterator { //C++17
}; //elements are stored contiguously in memory.

您可以专门化 std::iterator_traits，或者将相同的 typedefs 放入迭代器本身，或者从 std::iterator 继承(它有这些类型定义).我更喜欢第二个选项，以避免更改 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 ptrdiff_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，但它应该可以隐式构造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屋！