如何实现一个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_tag ， std::output_iterator_tag ， std::forward_iterator_tag ， std::random_access_iterator_tag或std::random_access_iterator_tag ，具体取决于您的迭代器满足哪些要求。 根据你的迭代器，你可以select专门化std::next ， std::prev ， std::advance和std::distance ，但是这很less需要。 在极less数情况下，您可能希望专门化std::begin和std::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 。 除了学习大量容器以外，我从来没有学过使用容器或本科课程。 主要原因是EASTL比stl更可读（我发现这只是因为缺less所有的macros和直接的编码风格）。 那里有些琐碎的东西（比如#ifdefs的例外），但没有什么可以压倒你的。
正如其他人提到的，看看cplusplus.com对迭代器和容器的参考。
