[c++] 如何实现一个STL风格的迭代器,并避免常见的陷阱?


Answers

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

如果没有别的,你可以看看iterator_facade提供的成员函数和类型定义,并用它作为构建你自己的起点。

Question

我做了一个集合,我想提供一个STL风格的随机访问迭代器。 我正在寻找一个迭代器的示例实现,但我没有找到任何。 我知道[]*运算符需要const重载。 迭代器对“STL风格”有什么要求,还有哪些其他陷阱可以避免(如果有的话)?

额外的上下文:这是一个图书馆,我不想介绍任何依赖它,除非我真的需要。 我编写自己的集合,以便能够使用相同的编译器提供C ++ 03和C ++ 11之间的二进制兼容性(因此没有STL可能会中断)。




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

无论如何,我看着EASTL 。 除了学习有关集装箱的知识外,我从来没有学过使用集装箱或通过本科课程学习的东西。 主要原因是EASTLstl更易读(我发现这仅仅是因为缺乏所有的宏和直接的编码风格)。 那里有一些奇怪的东西(比如#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);
    }
}



Links