如何实现一个STL风格的迭代器,并避免常见的陷阱?

我做了一个集合,我想提供一个STL风格的随机访问迭代器。 我正在寻找一个迭代器的示例实现,但我没有find任何。 我知道[]*运算符需要const重载。 迭代器对STL风格有什么要求,还有什么其他的陷阱可以避免(如果有的话)?

额外的上下文:这是一个图书馆,我不想引入任何依赖它,除非我真的需要。 我写我自己的集合,以提供相同的编译器之间的C + + 03和C + + 11之间的二进制兼容性(所以没有STL可能会中断)。

http://www.cplusplus.com/reference/std/iterator/有一个方便的图表,详细说明了C ++ 11标准的第24.2.2节的规范。 基本上,迭代器具有描述有效操作的标签,并且标签具有层次结构。 下面是纯粹的象征,这些类实际上并不存在。

 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; }; 

您可以专门化std::iterator_traits<youriterator> ,或者将相同的std::iterator_traits<youriterator>放入迭代器本身,或者从std::iterator (具有这些typedef)inheritance。 我更喜欢第二种select,以避免改变std命名空间中的东西,并为了可读性,但大多数人从std::iteratorinheritance。

 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_tagstd::output_iterator_tagstd::forward_iterator_tagstd::random_access_iterator_tagstd::random_access_iterator_tag ,具体取决于您的迭代器满足哪些要求。 根据你的迭代器,你可以select专门化std::nextstd::prevstd::advancestd::distance ,但是这很less需要。 在极less数情况下,您可能希望专门化std::beginstd::end

你的容器应该也可以有一个const_iterator ,它是一个(可能是可变的)迭代器,用来处理和你的iterator类似的常量数据,除非它可以从iterator隐式地构造出来,用户应该无法修改数据。 内部指针是一个指向非常量数据的指针,并且具有从const_iteratorinheritance的iterator ,以尽量减less代码重复。

我在写你自己的STL容器的文章有一个更完整的容器/迭代器原型。

Boost.Iterator的iterator_facade文档提供了一个关于实现链表的迭代器的好教程。 你可以使用它作为在你的容器上构build一个随机访问迭代器的起点吗?

如果没有别的,你可以看看iterator_facade提供的成员函数和typedef,并用它作为构build你自己的起点。

托马斯·贝克尔(Thomas Becker)在这里写了一篇有用的文章

还有这个(也许更简单)的方法出现在以前的SO: 如何正确地实现自定义迭代器和const_iterator?

首先,您可以在这里查看各个迭代器types需要支持的各种操作的列表。

接下来,当你创build了你的迭代器类时,你需要为它专门化std::iterator_traits ,并提供一些必要的types定义(比如迭代器类或者值types),或者从std::iterator派生出来,它定义了你需要的typedef因此可以使用默认的std::iterator_traits

免责声明:我知道有些人不太喜欢cplusplus.com ,但他们提供了一些非常有用的信息。

这是原始指针迭代器的示例。

你不应该使用迭代器类来处理原始指针!

 #include <iostream> #include <vector> #include <list> #include <iterator> #include <assert.h> template<typename T> class ptr_iterator : public std::iterator<std::forward_iterator_tag, T> { typedef ptr_iterator<T> iterator; pointer pos_; public: ptr_iterator() : pos_(nullptr) {} ptr_iterator(T* v) : pos_(v) {} ~ptr_iterator() {} iterator operator++(int) /* postfix */ { return pos_++; } iterator& operator++() /* prefix */ { ++pos_; return *this; } reference operator* () const { return *pos_; } pointer operator->() const { return pos_; } iterator operator+ (difference_type v) const { return pos_ + v; } bool operator==(const iterator& rhs) const { return pos_ == rhs.pos_; } bool operator!=(const iterator& rhs) const { return pos_ != rhs.pos_; } }; template<typename T> ptr_iterator<T> begin(T *val) { return ptr_iterator<T>(val); } template<typename T, typename Tsize> ptr_iterator<T> end(T *val, Tsize size) { return ptr_iterator<T>(val) + size; } 

基于原始指针范围的循环解决方法。 请纠正我,如果有更好的方法从原始指针做基于范围的循环。

 template<typename T> class ptr_range { T* begin_; T* end_; public: ptr_range(T* ptr, size_t length) : begin_(ptr), end_(ptr + length) { assert(begin_ <= end_); } T* begin() const { return begin_; } T* end() const { return end_; } }; template<typename T> ptr_range<T> range(T* ptr, size_t length) { return ptr_range<T>(ptr, length); } 

和简单的testing

 void DoIteratorTest() { const static size_t size = 10; uint8_t *data = new uint8_t[size]; { // Only for iterator test uint8_t n = '0'; auto first = begin(data); auto last = end(data, size); for (auto it = first; it != last; ++it) { *it = n++; } // It's prefer to use the following way: for (const auto& n : range(data, size)) { std::cout << " char: " << static_cast<char>(n) << std::endl; } } { // Only for iterator test ptr_iterator<uint8_t> first(data); ptr_iterator<uint8_t> last(first + size); std::vector<uint8_t> v1(first, last); // It's prefer to use the following way: std::vector<uint8_t> v2(data, data + size); } { std::list<std::vector<uint8_t>> queue_; queue_.emplace_back(begin(data), end(data, size)); queue_.emplace_back(data, data + size); } } 

由于不同的原因,我和你在同一条船上(部分受教育,部分受到限制)。 我不得不重新编写标准库的所有容器,容器必须符合标准。 这意味着,如果我换出我的容器与STL版本,代码将工作相同。 这也意味着我不得不重写迭代器。

无论如何,我看着EASTL 。 除了学习大量容器以外,我从来没有学过使用容器或本科课程。 主要原因是EASTLstl更可读(我发现这只是因为缺less所有的macros和直接的编码风格)。 那里有些琐碎的东西(比如#ifdefs的例外),但没有什么可以压倒你的。

正如其他人提到的,看看cplusplus.com对迭代器和容器的参考。