如何实现STL样式的迭代器并避免常见的陷阱？

Question

我创建了一个集合,我想提供一个STL风格的随机访问迭代器.我正在寻找迭代器的示例实现,但我没有找到任何.我知道需要const重载[]和*运算符.迭代器有什么要求是"STL风格",还有哪些其他缺陷需要避免(如果有的话)？

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

Answer 1

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;
};

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
};

注意的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除非它应该从a隐式构造iterator,用户应该无法修改数据.它的内部指针通常是指向非常量数据的指针,并且具有iterator继承性,const_iterator以便最小化代码重复.

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

Answer 2

Boost.Iterator中的iterator_facade文档提供了一个关于为链表实现迭代器的精彩教程.你可以用它作为在容器上构建随机访问迭代器的起点吗？

如果不出意外,您可以查看由其提供的成员函数和typedef,iterator_facade并将其用作构建自己的成员函数和typedef 的起点.

Answer 3

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

先前在SO上出现了这种(也许更简单)的方法:如何正确实现自定义迭代器和const_iterators？

Answer 4

这是原始指针迭代器的示例.

你不应该使用iterator类来处理原始指针!

#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);
    }
}

Answer 5

首先，您可以在此处查找各个迭代器类型需要支持的各种操作的列表。

接下来，当您创建了迭代器类后，您需要对其进行专门化std::iterator_traits并提供一些必要typedef的（如iterator_category或value_type），或者从其派生它std::iterator，后者typedef为您定义了所需的，因此可以与default一起使用std::iterator_traits。

免责声明：我知道有些人不太喜欢cplusplus.com，但是他们提供了一些非常有用的信息。