如何正确实现自定义迭代器和const_iterators?

小开

我不知道Boost有没有什么有用的东西。

我更喜欢的模式很简单:取一个模板参数，它等于value_type，无论是否有const限定。如果需要，还可以使用节点类型。然后，好吧，一切都有条不紊了。

只要记住参数化(模板化)所有需要的东西，包括复制构造函数和operator==。在大多数情况下，const的语义将创建正确的行为。

template< class ValueType, class NodeType >
struct my_iterator
: std::iterator< std::bidirectional_iterator_tag, T > {
ValueType &operator*() { return cur->payload; }


template< class VT2, class NT2 >
friend bool operator==
( my_iterator const &lhs, my_iterator< VT2, NT2 > const &rhs );


// etc.


private:
NodeType *cur;


friend class my_container;
my_iterator( NodeType * ); // private constructor for begin, end
};


typedef my_iterator< T, my_node< T > > iterator;
typedef my_iterator< T const, my_node< T > const > const_iterator;

小开

最佳答案

选择适合容器的迭代器类型:输入、输出、转发等。
使用标准库中的基迭代器类。例如，std::iterator和random_access_iterator_tag。这些基类定义STL所需的所有类型定义，并完成其他工作。
为了避免代码重复，迭代器类应该是一个模板类，并通过“值类型”、“指针类型”、“引用类型”或全部参数化(取决于实现)。例如:
```
// iterator class is parametrized by pointer type
template <typename PointerType> class MyIterator {
// iterator class definition goes here
};


typedef MyIterator<int*> iterator_type;
typedef MyIterator<const int*> const_iterator_type;
```
注意iterator_type和const_iterator_type类型定义:它们是非const和const迭代器的类型

参见:标准库参考

编辑: std::iterator自c++ 17起已弃用。参见相关讨论在这里。

小开

他们经常忘记iterator必须转换为const_iterator，而不是反过来。这里有一个方法:

template<class T, class Tag = void>
class IntrusiveSlistIterator
: public std::iterator<std::forward_iterator_tag, T>
{
typedef SlistNode<Tag> Node;
Node* node_;


public:
IntrusiveSlistIterator(Node* node);


T& operator*() const;
T* operator->() const;


IntrusiveSlistIterator& operator++();
IntrusiveSlistIterator operator++(int);


friend bool operator==(IntrusiveSlistIterator a, IntrusiveSlistIterator b);
friend bool operator!=(IntrusiveSlistIterator a, IntrusiveSlistIterator b);


// one way conversion: iterator -> const_iterator
operator IntrusiveSlistIterator<T const, Tag>() const;
};

在上面注意IntrusiveSlistIterator<T>如何转换为IntrusiveSlistIterator<T const>。如果T已经是const，则此转换永远不会被使用。

小开

Boost可以提供帮助:Boost。迭代器库。

更准确地说，这一页:boost:: iterator_adaptor。

非常有趣的是教程的例子，它从头显示了自定义类型的完整实现。

template <class Value>
class node_iter
: public boost::iterator_adaptor<
node_iter<Value>                // Derived
, Value*                          // Base
, boost::use_default              // Value
, boost::forward_traversal_tag    // CategoryOrTraversal
>
{
private:
struct enabler {};  // a private type avoids misuse


public:
node_iter()
: node_iter::iterator_adaptor_(0) {}


explicit node_iter(Value* p)
: node_iter::iterator_adaptor_(p) {}


// iterator convertible to const_iterator, not vice-versa
template <class OtherValue>
node_iter(
node_iter<OtherValue> const& other
, typename boost::enable_if<
boost::is_convertible<OtherValue*,Value*>
, enabler
>::type = enabler()
)
: node_iter::iterator_adaptor_(other.base()) {}


private:
friend class boost::iterator_core_access;
void increment() { this->base_reference() = this->base()->next(); }
};

主要的一点，正如已经引用的，是使用一个模板实现和typedef它。

小开

我将向您展示如何轻松地为自定义容器定义迭代器，但以防万一，我已经创建了一个c++11库，允许您轻松地为任何类型的容器(连续或不连续)创建具有自定义行为的自定义迭代器。

你可以找到它Github上

下面是创建和使用自定义迭代器的简单步骤:

创建“自定义迭代器”类。
在“自定义容器”类中定义typedefs。
- 例如typedef blRawIterator< Type > iterator;
- 例如typedef blRawIterator< const Type > const_iterator;
- 定义begin和end函数
  - 例如iterator begin(){return iterator(&m_data[0]);};
  - 例如const_iterator cbegin()const{return const_iterator(&m_data[0]);};
  - 我们完成了! !

最后，定义我们的自定义迭代器类:

注意: 在定义自定义迭代器时，我们从标准迭代器类别派生，以让STL算法知道我们所创建的迭代器的类型。

在这个例子中，我定义了一个随机访问迭代器和一个反向随机访问迭代器:

<李> < pre > <代码 >//------------------------------------------------------------------- //随机访问的原始迭代器 //------------------------------------------------------------------- template< typename blDataType> 类blRawIterator ｛公众: 使用iterator_category = std::random_access_iterator_tag; using value_type = blDataType; 使用difference_type = std::ptrdiff_t; 使用指针= blDataType*; using reference = blDataType&; 公众: blRawIterator(blDataType* ptr = nullptr){m_ptr = ptr;} blRawIterator (const blRawIterator< blDataType>和rawIterator) = default; ~ blRawIterator () {} blRawIterator< blDataType>和运算符= (const blRawIterator< blDataType>和rawIterator) = default; blRawIterator< blDataType>和{m_ptr = ptr;return (*this);} 操作符 bool()常量｛如果(m_ptr) 返回true; 其他的返回错误; ｝ bool操作符==(const blRawIterator<blDataType>&rawIterator)const{返回(m_ptr == rawIterator. getconstptr ());} bool 运营商!= (const blRawIterator< blDataType>和rawIterator)const{返回(m_ptr != rawIterator. getconstptr ());} blRawIterator< blDataType>和操作符+ = (const difference_type&{m_ptr +=移动;return (*this);} blRawIterator< blDataType>和操作符- = (const difference_type&{m_ptr -=移动;return (*this);} blRawIterator< blDataType>和操作符+ + (){+ + m_ptr;返回(*);} blRawIterator< blDataType>和运营商——(){——m_ptr;返回(*);} blRawIterator< blDataType>运算符++(int){auto temp(*this); blRawIterator< blDataType>操作符——(int){auto temp(*this);——m_ptr;return temp;} blRawIterator< blDataType>操作符+ (const difference_type&移动){auto oldPtr = m_ptr;m_ptr+=移动;auto temp(*this);m_ptr = oldPtr;返回temp;} blRawIterator< blDataType>运营商(const difference_type&移动){auto oldPtr = m_ptr;m_ptr-=移动;auto temp(*this);m_ptr = oldPtr;返回temp;} difference_type operator-(const blRawIterator<blDataType>&rawIterator){返回std::距离(rawIterator.getPtr(),这个→getPtr ());} blDataType&操作符*(){返回* m_ptr;} const blDataType&操作符* ()const{返回* m_ptr;} blDataType*操作符->(){返回m_ptr;} blDataType* getPtr()const{返回m_ptr;} const blDataType* getConstPtr()const{返回m_ptr;} 保护: blDataType * m_ptr; }； //------------------------------------------------------------------- < /代码> < / pre > < /李> <李> < pre > <代码 >//------------------------------------------------------------------- //随机访问的原始反向迭代器 //------------------------------------------------------------------- template< typename blDataType> 类blRawReverseIterator: public blRawIterator< ｛公众: blRawReverseIterator(blDataType* ptr = nullptr):blRawIterator< bldatattype>(ptr){} blRawReverseIterator (const blRawIterator< blDataType>和rawIterator){this >m_ptr = rawIterator. getptr ();} blRawReverseIterator (const blRawReverseIterator< blDataType>和rawReverseIterator) = default; ~ blRawReverseIterator () {} blRawReverseIterator< blDataType>和运算符= (const blRawReverseIterator< blDataType>和rawReverseIterator) = default; blRawReverseIterator< blDataType>和运算符= (const blRawIterator< blDataType>和rawIterator){this->m_ptr = rawIterator. getptr ();return (*this);} blRawReverseIterator< blDataType>和setPtr(ptr);return (*this);} blRawReverseIterator< blDataType>和操作符+ = (const difference_type&移动){this->m_ptr -=移动;return (*this);} blRawReverseIterator< blDataType>和操作符- = (const difference_type&移动){this->m_ptr +=移动;return (*this);} blRawReverseIterator< blDataType>和操作符+ +(){——这→m_ptr;返回(*);} blRawReverseIterator< blDataType>和运营商——(){+ +这→m_ptr;返回(*);} blRawReverseIterator< blDataType>运算符++(int){auto temp(*this);——this->m_ptr;return temp;} blRawReverseIterator< blDataType>运算符——(int){auto temp(*this);++this->m_ptr;return temp;} blRawReverseIterator< blDataType>操作符+ (const int&移动){auto oldPtr = this->m_ptr;this->m_ptr-=移动; blRawReverseIterator< blDataType>运营商(const int&移动){auto oldPtr = this->m_ptr;this->m_ptr+=移动; difference_type operator-(const blRawReverseIterator<blDataType>&rawReverseIterator){返回std::距离(这→getPtr (), rawReverseIterator.getPtr ());} blRawIterator< blDataType>基地(){blRawIterator< blDataType>forwardIterator(这→m_ptr);+ + forwardIterator;返回forwardIterator;} }； //------------------------------------------------------------------- < /代码> < / pre > < /李>

现在在你的自定义容器类中:

template<typename blDataType>
class blCustomContainer
{
public: // The typedefs


typedef blRawIterator<blDataType>              iterator;
typedef blRawIterator<const blDataType>        const_iterator;


typedef blRawReverseIterator<blDataType>       reverse_iterator;
typedef blRawReverseIterator<const blDataType> const_reverse_iterator;


.
.
.


public:  // The begin/end functions


iterator                                       begin(){return iterator(&m_data[0]);}
iterator                                       end(){return iterator(&m_data[m_size]);}


const_iterator                                 cbegin(){return const_iterator(&m_data[0]);}
const_iterator                                 cend(){return const_iterator(&m_data[m_size]);}


reverse_iterator                               rbegin(){return reverse_iterator(&m_data[m_size - 1]);}
reverse_iterator                               rend(){return reverse_iterator(&m_data[-1]);}


const_reverse_iterator                         crbegin(){return const_reverse_iterator(&m_data[m_size - 1]);}
const_reverse_iterator                         crend(){return const_reverse_iterator(&m_data[-1]);}


.
.
.
// This is the pointer to the
// beginning of the data
// This allows the container
// to either "view" data owned
// by other containers or to
// own its own data
// You would implement a "create"
// method for owning the data
// and a "wrap" method for viewing
// data owned by other containers


blDataType*                                    m_data;
};

小开

有很多好的答案，但我创建了一个模板标题，我使用它是相当简洁和易于使用的。

要在类中添加迭代器，只需要编写一个小类，用7个小函数来表示迭代器的状态，其中2个是可选的:

#include <iostream>
#include <vector>
#include "iterator_tpl.h"


struct myClass {
std::vector<float> vec;


// Add some sane typedefs for STL compliance:
STL_TYPEDEFS(float);


struct it_state {
int pos;
inline void begin(const myClass* ref) { pos = 0; }
inline void next(const myClass* ref) { ++pos; }
inline void end(const myClass* ref) { pos = ref->vec.size(); }
inline float& get(myClass* ref) { return ref->vec[pos]; }
inline bool equals(const it_state& s) const { return pos == s.pos; }


// Optional to allow operator--() and reverse iterators:
inline void prev(const myClass* ref) { --pos; }
// Optional to allow `const_iterator`:
inline const float& get(const myClass* ref) const { return ref->vec[pos]; }
};
// Declare typedef ... iterator;, begin() and end() functions:
SETUP_ITERATORS(myClass, float&, it_state);
// Declare typedef ... reverse_iterator;, rbegin() and rend() functions:
SETUP_REVERSE_ITERATORS(myClass, float&, it_state);
};

然后你可以像使用STL迭代器一样使用它:

int main() {
myClass c1;
c1.vec.push_back(1.0);
c1.vec.push_back(2.0);
c1.vec.push_back(3.0);


std::cout << "iterator:" << std::endl;
for (float& val : c1) {
std::cout << val << " "; // 1.0 2.0 3.0
}
  

std::cout << "reverse iterator:" << std::endl;
for (auto it = c1.rbegin(); it != c1.rend(); ++it) {
std::cout << *it << " "; // 3.0 2.0 1.0
}
}

我希望这能有所帮助。

小开

检查下面的代码，它工作

#define MAX_BYTE_RANGE 255


template <typename T>
class string
{
public:
typedef char *pointer;
typedef const char *const_pointer;
typedef __gnu_cxx::__normal_iterator<pointer, string> iterator;
typedef __gnu_cxx::__normal_iterator<const_pointer, string> const_iterator;


string() : length(0)
{
}
size_t size() const
{
return length;
}
void operator=(const_pointer value)
{
if (value == nullptr)
throw std::invalid_argument("value cannot be null");
auto count = strlen(value);
if (count > 0)
_M_copy(value, count);
}
void operator=(const string &value)
{
if (value.length != 0)
_M_copy(value.buf, value.length);
}
iterator begin()
{
return iterator(buf);
}
iterator end()
{
return iterator(buf + length);
}
const_iterator begin() const
{
return const_iterator(buf);
}
const_iterator end() const
{
return const_iterator(buf + length);
}
const_pointer c_str() const
{
return buf;
}
~string()
{
}


private:
unsigned char length;
T buf[MAX_BYTE_RANGE];


void _M_copy(const_pointer value, size_t count)
{
memcpy(buf, value, count);
length = count;
}
};

小开

我偶然看到这篇文章，很惊讶这里没有提到一个简单的方法。像std::迭代器那样使用指向值的指针显然是一种非常通用的方法。但是你可以用一些更简单的方法。当然，这是一种简单的方法，可能并不总是足够的，但如果是的话，我将它发布给下一个读者。

类中的底层类型很可能是一个STL容器，它已经为你定义了迭代器。如果是这样的话，你可以简单地使用他们定义的迭代器，而不需要创建自己的迭代器。

这里有一个例子:

class Foo {


std::vector<int>::iterator begin() { return data.begin(); }
std::vector<int>::iterator end() { return data.end(); }


std::vector<int>::const_iterator begin() const { return data.begin(); }
std::vector<int>::const_iterator end() const { return data.end(); }




private:
std::vector<int> data


};

小开

我感兴趣的是如何正确的这是，但似乎工作作为一个滚动自己的迭代器内部数据存储

template<typename T>
struct iterator_type
{
using self_type             = iterator_type;
using iterator_category     = std::random_access_iterator_tag;
using difference_type       = std::ptrdiff_t;
using value_type            = std::remove_cv_t<T>;
using pointer               = T*;
using reference             = T&;


iterator_type( pointer ptr ) noexcept
: _ptr{ ptr }
{}


reference operator*() noexcept { return *_ptr; }
pointer operator->() noexcept { return _ptr; }


self_type operator++() noexcept { ++_ptr; return *this; }
self_type operator++(int) noexcept { self_type tmp = *this; ++_ptr; return tmp; }


self_type operator--() noexcept { --_ptr; return *this; }
self_type operator--(int) noexcept { self_type tmp = *this; --_ptr; return tmp; }


bool operator==( const self_type &other ) const noexcept { return _ptr == other._ptr; }
bool operator!=( const self_type &other ) const noexcept { return _ptr != other._ptr; }


private:
pointer _ptr;
};




template<typename T>
using const_iterator_type = iterator_type<std::add_const_t<T>>;

然后我只是把这些添加到我的类，似乎工作如预期。

template<typename T>
class Container
{
public:
using iterator               = iterator_type<T>;
using const_iterator         = const_iterator_type<T>;
using reverse_iterator       = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;


...


iterator begin() { return _begin; }
iterator end() { return _begin + _size; }


const_iterator cbegin() const { return _begin; }
const_iterator cend() const { return _begin + _size; }


reverse_iterator rbegin() { return reverse_iterator(_begin + _size); }
reverse_iterator rend() { return reverse_iterator(_begin); }


const_reverse_iterator crbegin() const { return const_reverse_iterator(_begin + _size); }
const_reverse_iterator crend() const { return const_reverse_iterator(_begin); }


private:
T*         _begin;
size_t     _size;
size_t     _capacity;
};

唯一的问题是，为了使用std::cbegin()， std::rcbegin()， std::cend()和std::rcend()函数，我必须扩展std命名空间:

namespace std
{
template<typename T>
typename Container<T>::const_iterator cbegin( Container<T> &c ) { return c.cbegin(); }


template<typename T>
typename Container<T>::const_iterator cend( Container<T> &c ) { return c.cend(); }


template<typename T>
typename Container<T>::const_reverse_iterator crbegin( Container<T> &c ) { return c.crbegin(); }


template<typename T>
typename Container<T>::const_reverse_iterator crend( Container<T> &c ) { return c.crend(); }
}