如何实现一个stl风格的迭代器和避免常见的陷阱?

我做了一个集合，我想为它提供一个stl风格的随机访问迭代器。我正在寻找迭代器的示例实现，但我没有找到任何。我知道[]和*操作符需要const重载。“stl风格”的迭代器的要求是什么?还有哪些需要避免的陷阱(如果有的话)?

附加上下文:这是一个库，除非真的需要，否则我不想对它引入任何依赖。我编写了自己的集合，以便能够使用相同的编译器在c++ 03和c++ 11之间提供二进制兼容性(因此没有可能会损坏的STL)。

224057 次浏览
小开

Boost中的iterator_facade文档。Iterator提供了一个关于为链表实现迭代器的很好的教程。您是否可以将其作为在容器上构建随机访问迭代器的起点?

如果没有其他方法，你可以看看iterator_facade提供的成员函数和类型定义，并将其作为构建自己的成员函数和类型定义的起点。

小开

Thomas Becker写了一篇关于这个主题的有用的文章。

还有之前在SO: 如何正确实现自定义迭代器和const_iterators?中出现的这种(可能更简单)方法

小开

首先，你可以在在这里中找到各个迭代器类型需要支持的各种操作的列表。

接下来，当你创建了迭代器类后，你需要为它专门化std::iterator_traits并提供一些必要的__abc1(如iterator_category或value_type)，或者从std::iterator中派生它，后者为你定义了所需的__abc1，因此可以与默认的std::iterator_traits一起使用。

我知道有些人不喜欢cplusplus.com那么多，但他们提供了一些非常有用的信息。

小开
最佳答案

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::output_iterator_tag1的情况下，你可能希望特殊化std::begin和std::output_iterator_tag0。

你的容器可能也应该有一个const_iterator，它是一个(可能是可变的)迭代器，指向常量数据，类似于你的iterator，只是它应该是隐式可从iterator构造的，用户应该不能修改数据。它的内部指针通常是指向非常量数据的指针，并且iterator继承自const_iterator，以便最大限度地减少代码重复。

我在编写自己的STL容器的帖子有一个更完整的容器/迭代器原型。

小开

由于不同的原因(部分是教育，部分是限制)，我和你在同一条船上。我必须重写标准库的所有容器，并且容器必须符合标准。这意味着，如果我用stl版本替换我的容器，代码将工作相同。这也意味着我必须重写迭代器。

总之，我看了EASTL。除了学习了大量关于容器的知识，这些知识是我在使用stl容器或本科课程时从未学过的。主要原因是EASTL比stl更具可读性(我发现这只是因为缺少所有的宏和直接的编码风格)。里面有一些讨厌的东西(比如异常的#ifdefs)，但没有什么能让你不知所措。

正如其他人提到的，查看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); }

简单的测试

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);
}
}
小开

我试图解决能够遍历几个不同的文本数组的问题，所有这些文本数组都存储在内存常驻数据库中，该数据库是一个大型struct。

以下是使用Visual Studio 2017社区版在MFC测试应用程序上完成的。我把这篇文章作为一个例子，因为这篇文章是我遇到的几个提供了一些帮助的帖子之一，但仍然不足以满足我的需求。

包含内存常驻数据的struct看起来像下面这样。为了简洁起见，我删除了大部分元素，也没有包括所使用的Preprocessor定义(所使用的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文本字符串数组。二维数组有不同数量的助记符，这取决于助记符的类型(用途)，不同类型的助记符有不同的最大长度，在5个文本字符和20个文本字符之间变化。派生代理类的模板与每个助记符中要求最大字符数的模板非常适合。创建代理对象后，我们使用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文本字符串，可能恰好是数组元素的数量，因此我们将字符串复制到临时缓冲区中，以确保文本以0结尾。

    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++;
}
小开

现在是一个基于范围的for循环的keys迭代器。

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
}

这正是我要找的。但似乎没有人拥有它。

我给你的强迫症编码是额外奖励。

作为练习，编写你自己的values(my_map)


提交答案