我做了一个集合，我想为它提供一个stl风格的随机访问迭代器。我正在寻找迭代器的示例实现，但我没有找到任何。我知道需要对[]和*操作符进行const重载。“stl风格”的迭代器的要求是什么?还有哪些需要避免的陷阱(如果有的话)?
附加上下文:这是一个库，除非真的需要，否则我不想对它引入任何依赖。我编写了自己的集合，以便能够使用相同的编译器在c++ 03和c++ 11之间提供二进制兼容性(因此没有可能会损坏的STL)。
当前回答
https://cplusplus.com/reference/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;
};
contiguous_iterator : random_access_iterator { //C++17
}; //elements are stored contiguously in memory.
你可以专门化std::iterator_traits<youriterator>，或者在迭代器本身中放入相同的类型defs，或者从std::iterator继承(它有这些类型defs)。我更喜欢第二种选择，为了避免在std命名空间中更改内容，也为了可读性，但大多数人都继承了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。
你的容器可能还应该有一个const_iterator，它是一个指向常量数据的迭代器(可能是可变的)，与你的迭代器类似，只是它应该是隐式可从迭代器构造的，用户应该不能修改数据。它的内部指针通常是指向非常量数据的指针，并且iterator继承自const_iterator，以尽量减少代码重复。
我在写自己的STL容器的文章中有一个更完整的容器/迭代器原型。
其他回答
这是一个原始指针迭代器的示例。
你不应该使用迭代器类来处理原始指针!
#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); }
简单的测试
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);
}
}
首先，您可以在这里找到各个迭代器类型需要支持的各种操作的列表。
接下来，当你创建了你的迭代器类时，你需要为std::iterator_traits特化并提供一些必要的类型defs(如iterator_category或value_type)，或者从std::iterator派生它，它为你定义了所需的类型defs，因此可以与默认的std::iterator_traits一起使用。
免责声明:我知道有些人不太喜欢cplusplus.com，但是他们提供了一些非常有用的信息。
托马斯·贝克尔在这里写了一篇关于这个主题的有用文章。
还有一种(也许更简单)的方法出现在前面的SO:如何正确地实现自定义迭代器和const_iterators?
https://cplusplus.com/reference/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;
};
contiguous_iterator : random_access_iterator { //C++17
}; //elements are stored contiguously in memory.
你可以专门化std::iterator_traits<youriterator>，或者在迭代器本身中放入相同的类型defs，或者从std::iterator继承(它有这些类型defs)。我更喜欢第二种选择，为了避免在std命名空间中更改内容，也为了可读性，但大多数人都继承了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。
你的容器可能还应该有一个const_iterator，它是一个指向常量数据的迭代器(可能是可变的)，与你的迭代器类似，只是它应该是隐式可从迭代器构造的，用户应该不能修改数据。它的内部指针通常是指向非常量数据的指针，并且iterator继承自const_iterator，以尽量减少代码重复。
我在写自己的STL容器的文章中有一个更完整的容器/迭代器原型。
由于不同的原因(部分是教育，部分是限制)，我和你在同一条船上。我必须重写标准库的所有容器，并且容器必须符合标准。这意味着，如果我用stl版本替换我的容器，代码将工作相同。这也意味着我必须重写迭代器。
总之，我看了EASTL。除了在使用stl容器或在本科课程中学习了大量关于容器的知识之外。主要原因是EASTL比stl更具可读性(我发现这只是因为缺少所有的宏和直接的编码风格)。里面有一些讨厌的东西(比如异常的#ifdefs)，但没有什么能让你不知所措。
正如其他人提到的，查看cplusplus.com关于迭代器和容器的参考。
推荐文章
- 是否需要手动关闭ifstream?
- 为什么函数指针定义可以使用任意数量的&号或星号* ?
- 为什么我必须通过this指针访问模板基类成员?
- 什么是可重入函数?
- 什么是栈展开?
- 我如何读整个文件到性病::字符串在c++ ?
- 如何在c++中使用枚举
- 为什么512x512矩阵的转置比513x513矩阵的转置慢得多?
- 迭代Typescript Map
- 迭代器和可迭代器之间的区别是什么?如何使用它们?
- 通过引用传递数组
- 为什么非const引用不能绑定到临时对象?
- sizeof(某个指针)总是等于4吗?
- 在c++中使用数组或std::vector，性能差距是什么?
- 什么是std::decay ?什么时候应该使用它?
