我制作了一个集合，想要提供STL风格的随机访问迭代器。我搜寻了一些迭代器实现的示例，但没有找到合适的。我知道需要重载[]和*运算符的const版本。一个迭代器成为"STL-style"所需满足什么要求？还有其他需要避免的陷阱吗？
额外背景：这是为一个库而做的，我不想引入任何依赖，除非确实需要。我编写自己的集合以在同一编译器下提供C++03和C++11之间的二进制兼容性（因此不能使用可能会使其崩溃的STL）。
如何实现一个类似STL的迭代器并避免常见问题？
361
- Tamás Szelei
3
20+1！好问题。我也想知道这个。基于Boost.Iterator来快速构建一个迭代器很容易，但是如果你要从头开始实现，想要找到所需的要求列表却很难。 - jalf
2请记住，您的迭代器必须是 SCARY 的。http://www.boost.org/doc/libs/1_55_0/doc/html/intrusive/scary_iterators.html - alfC
1相关：https://dev59.com/Y3A65IYBdhLWcg3w4C2j - Ciro Santilli OurBigBook.com
8个回答
266
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>，或者将相同的typedef放在迭代器本身中，或者继承自 std::iterator（它具有这些typedef）。我更喜欢第二个选项，以避免更改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
};
请注意，迭代器类别应该是以下之一：
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，除了它应该可以从iterator中隐式构造，并且用户无法修改数据。它的内部指针通常是指向非常量数据的指针，并且iterator继承自const_iterator，以尽量减少代码重复。我的帖子在编写自己的STL容器中有一个更完整的容器/迭代器原型。
- Mooing Duck
16
2除了专门化
std::iterator_traits或自己定义typedef，您还可以从std::iterator派生，它根据其模板参数为您定义这些内容。 - Christian Rau3@LokiAstari 的回复中提到完整的文档十分详尽（草案中有40页左右），不适合在 Stack Overflow 上讨论。但是，我补充了更多关于迭代器标签和
const_iterator 的信息。我的帖子还缺少什么？你好像暗示这个类还有其他需要添加的内容，但是问题特别涉及实现迭代器。 - Mooing Duck8
std::iterator曾被建议在C++17中弃用；尽管它没有被弃用，但我不会指望它能够继续存在很长时间。 - einpoklum4更新 @einpoklum 的评论：
std::iterator 最终已经被弃用。 - scry显示剩余11条评论
16
Boost.Iterator的迭代器外观(iterator facade)文档提供了一个实现链表迭代器的良好教程。你可以以此为基础构建一个随机访问迭代器，如果没有更好的选择。
如果没有更好的选择，你可以查看
如果没有更好的选择，你可以查看
iterator_facade 提供的成员函数和类型定义，并以此为起点构建自己的迭代器。- Michael Kristofik
13
这里是原始指针迭代器的示例。
您不应该使用迭代器类来处理原始指针！
#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);
}
}
- Valdemar_Rudolfovich
5
首先，您可以查看此处以获取各个迭代器类型需要支持的操作列表。
接下来，当您创建了迭代器类后，您需要为其专门化std::iterator_traits并提供一些必要的typedef（如iterator_category或value_type），或者从std::iterator中派生它，该类定义了所需的typedef，因此可以与默认的std::iterator_traits一起使用。
免责声明: 我知道有些人不太喜欢cplusplus.com，但他们提供了一些非常有用的信息。
- Christian Rau
5
我真的不理解cplusplus与cppreference之争，它们都很好，但都缺少很多东西。然而，C++是唯一一个实现标准库迭代器非常困难的语言XD。大多数情况下，编写一个包装类来覆盖stl容器比实现一个迭代器更简单XD。 - CoffeDeveloper
@GameDeveloper 请看一下我为实现迭代器编写的模板库：https://github.com/VinGarcia/Simple-Iterator-Template/。它非常简单，只需要大约10行代码就可以编写一个迭代器。 - VinGarcia
不错的类，我很欣赏它，也许值得将其移植到编译时也能与非STL容器（EA_STL、UE4）一起使用。考虑一下吧！ :) - CoffeDeveloper
无论如何，如果唯一的原因是cplusplus.com提供了一些非常有用的信息，cppreference.com提供了更多更有用的信息... - L. F.
1@L.F. 那么请随意回到过去，将该信息添加到2011年版本的网站中。;-) - Christian Rau
3
我因不同原因（部分是教育，部分是限制）与你处于同一船上。我必须重新编写标准库的所有容器，并使容器符合标准。这意味着，如果我使用stl版本替换我的容器，则代码将正常工作。这也意味着我必须重新编写迭代器。
无论如何，我看了EASTL。除了通过使用stl容器或本科课程从未学到过的大量有关容器的知识外，主要原因是EASTL比stl对应物更易读（我发现这仅仅是因为缺乏所有宏和直接的编码风格）。里面有一些讨厌的东西（例如异常的#ifdefs），但没有什么会使你不堪重负。
正如其他人提到的那样，请查看cplusplus.com上有关迭代器和容器的参考资料。
无论如何，我看了EASTL。除了通过使用stl容器或本科课程从未学到过的大量有关容器的知识外，主要原因是EASTL比stl对应物更易读（我发现这仅仅是因为缺乏所有宏和直接的编码风格）。里面有一些讨厌的东西（例如异常的#ifdefs），但没有什么会使你不堪重负。
正如其他人提到的那样，请查看cplusplus.com上有关迭代器和容器的参考资料。
- Samaursa
3
我试图解决的问题是能够迭代遍历存储在内存数据库中的多个文本数组，该数据库是一个大型的
包含内存驻留数据的
我感兴趣的是为包含助记符文本字符串的各种二维
代理对象工厂根据助记符标识符确定要创建的对象。代理对象被创建并返回指针作为标准基类类型，以便具有统一的接口，无论访问哪个不同的助记符部分。使用
使用代理类和迭代器
如下的循环中使用了代理类及其迭代器来填充一个
这段源代码的作用是为与指定助记符标识符对应的
struct。以下是在 MFC 测试应用程序上使用 Visual Studio 2017 Community Edition 工作出来的结果。我将其包含在此处作为示例，因为这篇帖子是我遇到的几篇提供了一些帮助但仍不足以满足我的需求。包含内存驻留数据的
struct 大致如下。为了简洁起见，我删除了大部分元素，并且没有包含使用的预处理器定义（使用的 SDK 是 C 和 C++ 的旧版本）。我感兴趣的是为包含助记符文本字符串的各种二维
WCHAR 数组创建迭代器。typedef struct tagUNINTRAM {
// stuff deleted ...
WCHAR ParaTransMnemo[MAX_TRANSM_NO][PARA_TRANSMNEMO_LEN]; /* prog #20 */
WCHAR ParaLeadThru[MAX_LEAD_NO][PARA_LEADTHRU_LEN]; /* prog #21 */
WCHAR ParaReportName[MAX_REPO_NO][PARA_REPORTNAME_LEN]; /* prog #22 */
WCHAR ParaSpeMnemo[MAX_SPEM_NO][PARA_SPEMNEMO_LEN]; /* prog #23 */
WCHAR ParaPCIF[MAX_PCIF_SIZE]; /* prog #39 */
WCHAR ParaAdjMnemo[MAX_ADJM_NO][PARA_ADJMNEMO_LEN]; /* prog #46 */
WCHAR ParaPrtModi[MAX_PRTMODI_NO][PARA_PRTMODI_LEN]; /* prog #47 */
WCHAR ParaMajorDEPT[MAX_MDEPT_NO][PARA_MAJORDEPT_LEN]; /* prog #48 */
// ... stuff deleted
} UNINIRAM;
目前的方法是使用模板来定义每个数组的代理类，然后使用代表数组的代理对象来使用单个迭代器类来迭代特定数组。
内存驻留数据的副本存储在一个对象中，该对象处理从/到磁盘的内存驻留数据的读写。这个类，CFilePara包含了模板化的代理类(MnemonicIteratorDimSize和它所派生的子类MnemonicIteratorDimSizeBase)以及迭代器类MnemonicIterator。
创建的代理对象附加到一个迭代器对象上，通过由所有代理类派生的基类描述的接口访问必要的信息。结果是拥有一种可以与多个不同的代理类一起使用的单一类型的迭代器类，因为不同的代理类都公开相同的接口，即代理基类的接口。
首先要做的是创建一组标识符，这些标识符将提供给一个类工厂来生成该类型助记符的具体代理对象。这些标识符用作用户界面的一部分，以识别用户感兴趣的特定配置数据，可能会修改。
const static DWORD_PTR dwId_TransactionMnemonic = 1;
const static DWORD_PTR dwId_ReportMnemonic = 2;
const static DWORD_PTR dwId_SpecialMnemonic = 3;
const static DWORD_PTR dwId_LeadThroughMnemonic = 4;
代理类
模板代理类及其基类如下所述。我需要适应几种不同的wchar_t文本字符串数组。二维数组包含不同数量的助记符，取决于助记符的类型（目的）以及不同类型的助记符具有不同的最大长度，介于五个文本字符和二十个文本字符之间。为派生代理类提供模板是自然而然的选择，其中模板要求每个助记符具有最多的字符数。创建代理对象之后，我们使用SetRange()方法来指定实际的助记符数组及其范围。
// proxy object which represents a particular subsection of the
// memory resident database each of which is an array of wchar_t
// text arrays though the number of array elements may vary.
class MnemonicIteratorDimSizeBase
{
DWORD_PTR m_Type;
public:
MnemonicIteratorDimSizeBase(DWORD_PTR x) { }
virtual ~MnemonicIteratorDimSizeBase() { }
virtual wchar_t *begin() = 0;
virtual wchar_t *end() = 0;
virtual wchar_t *get(int i) = 0;
virtual int ItemSize() = 0;
virtual int ItemCount() = 0;
virtual DWORD_PTR ItemType() { return m_Type; }
};
template <size_t sDimSize>
class MnemonicIteratorDimSize : public MnemonicIteratorDimSizeBase
{
wchar_t (*m_begin)[sDimSize];
wchar_t (*m_end)[sDimSize];
public:
MnemonicIteratorDimSize(DWORD_PTR x) : MnemonicIteratorDimSizeBase(x), m_begin(0), m_end(0) { }
virtual ~MnemonicIteratorDimSize() { }
virtual wchar_t *begin() { return m_begin[0]; }
virtual wchar_t *end() { return m_end[0]; }
virtual wchar_t *get(int i) { return m_begin[i]; }
virtual int ItemSize() { return sDimSize; }
virtual int ItemCount() { return m_end - m_begin; }
void SetRange(wchar_t (*begin)[sDimSize], wchar_t (*end)[sDimSize]) {
m_begin = begin; m_end = end;
}
};
迭代器类
迭代器类本身如下所示。该类仅提供基本的前向迭代器功能，这是目前所需的全部功能。但是，当我需要更多的功能时，我预计这将会发生变化或扩展。
class MnemonicIterator
{
private:
MnemonicIteratorDimSizeBase *m_p; // we do not own this pointer. we just use it to access current item.
int m_index; // zero based index of item.
wchar_t *m_item; // value to be returned.
public:
MnemonicIterator(MnemonicIteratorDimSizeBase *p) : m_p(p) { }
~MnemonicIterator() { }
// a ranged for needs begin() and end() to determine the range.
// the range is up to but not including what end() returns.
MnemonicIterator & begin() { m_item = m_p->get(m_index = 0); return *this; } // begining of range of values for ranged for. first item
MnemonicIterator & end() { m_item = m_p->get(m_index = m_p->ItemCount()); return *this; } // end of range of values for ranged for. item after last item.
MnemonicIterator & operator ++ () { m_item = m_p->get(++m_index); return *this; } // prefix increment, ++p
MnemonicIterator & operator ++ (int i) { m_item = m_p->get(m_index++); return *this; } // postfix increment, p++
bool operator != (MnemonicIterator &p) { return **this != *p; } // minimum logical operator is not equal to
wchar_t * operator *() const { return m_item; } // dereference iterator to get what is pointed to
};
代理对象工厂根据助记符标识符确定要创建的对象。代理对象被创建并返回指针作为标准基类类型，以便具有统一的接口，无论访问哪个不同的助记符部分。使用
SetRange() 方法指定代理对象表示的特定数组元素和数组元素的范围。CFilePara::MnemonicIteratorDimSizeBase * CFilePara::MakeIterator(DWORD_PTR x)
{
CFilePara::MnemonicIteratorDimSizeBase *mi = nullptr;
switch (x) {
case dwId_TransactionMnemonic:
{
CFilePara::MnemonicIteratorDimSize<PARA_TRANSMNEMO_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_TRANSMNEMO_LEN>(x);
mk->SetRange(&m_Para.ParaTransMnemo[0], &m_Para.ParaTransMnemo[MAX_TRANSM_NO]);
mi = mk;
}
break;
case dwId_ReportMnemonic:
{
CFilePara::MnemonicIteratorDimSize<PARA_REPORTNAME_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_REPORTNAME_LEN>(x);
mk->SetRange(&m_Para.ParaReportName[0], &m_Para.ParaReportName[MAX_REPO_NO]);
mi = mk;
}
break;
case dwId_SpecialMnemonic:
{
CFilePara::MnemonicIteratorDimSize<PARA_SPEMNEMO_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_SPEMNEMO_LEN>(x);
mk->SetRange(&m_Para.ParaSpeMnemo[0], &m_Para.ParaSpeMnemo[MAX_SPEM_NO]);
mi = mk;
}
break;
case dwId_LeadThroughMnemonic:
{
CFilePara::MnemonicIteratorDimSize<PARA_LEADTHRU_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_LEADTHRU_LEN>(x);
mk->SetRange(&m_Para.ParaLeadThru[0], &m_Para.ParaLeadThru[MAX_LEAD_NO]);
mi = mk;
}
break;
}
return mi;
}
使用代理类和迭代器
如下的循环中使用了代理类及其迭代器来填充一个
CListCtrl对象的助记符列表。我使用std::unique_ptr，这样当代理类不再需要且std::unique_ptr超出范围时，内存将被清理。这段源代码的作用是为与指定助记符标识符对应的
struct中的数组创建一个代理对象。然后为该对象创建一个迭代器，使用区间for填充CListCtrl控件，最后清理工作。这些都是原始的wchar_t文本字符串，可能正好是数组元素的数量，因此我们将字符串复制到临时缓冲区中以确保文本以零终止。 std::unique_ptr<CFilePara::MnemonicIteratorDimSizeBase> pObj(pFile->MakeIterator(m_IteratorType));
CFilePara::MnemonicIterator pIter(pObj.get()); // provide the raw pointer to the iterator who doesn't own it.
int i = 0; // CListCtrl index for zero based position to insert mnemonic.
for (auto x : pIter)
{
WCHAR szText[32] = { 0 }; // Temporary buffer.
wcsncpy_s(szText, 32, x, pObj->ItemSize());
m_mnemonicList.InsertItem(i, szText); i++;
}
- Richard Chambers
3
现在为范围-based for 循环提供一个键迭代器。
template<typename C>
class keys_it
{
typename C::const_iterator it_;
public:
using key_type = typename C::key_type;
using pointer = typename C::key_type*;
using difference_type = std::ptrdiff_t;
keys_it(const typename C::const_iterator & it) : it_(it) {}
keys_it operator++(int ) /* postfix */ { return it_++ ; }
keys_it& operator++( ) /* prefix */ { ++it_; return *this ; }
const key_type& operator* ( ) const { return it_->first ; }
const key_type& operator->( ) const { return it_->first ; }
keys_it operator+ (difference_type v ) const { return it_ + v ; }
bool operator==(const keys_it& rhs) const { return it_ == rhs.it_; }
bool operator!=(const keys_it& rhs) const { return it_ != rhs.it_; }
};
template<typename C>
class keys_impl
{
const C & c;
public:
keys_impl(const C & container) : c(container) {}
const keys_it<C> begin() const { return keys_it<C>(std::begin(c)); }
const keys_it<C> end () const { return keys_it<C>(std::end (c)); }
};
template<typename C>
keys_impl<C> keys(const C & container) { return keys_impl<C>(container); }
使用方法：
std::map<std::string,int> my_map;
// fill my_map
for (const std::string & k : keys(my_map))
{
// do things
}
这是我一直在寻找的内容，但似乎没有人有它。
您将获得我的OCD代码对齐作为奖励。
作为练习，编写自己的values(my_map)。
- Gabriel
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接