我有一个自定义容器类，我想为其编写iterator和const_iterator类。
我以前从未这样做过，也没有找到合适的方法。关于迭代器创建的指导方针是什么，我应该注意什么？
我还想避免代码重复（我觉得const_iterator并iterator分享了很多东西；一个应该继承另一个吗？）。
脚注：我很确定 Boost 可以缓解这种情况，但由于许多愚蠢的原因，我不能在这里使用它。
问问题
236548 次
9 回答
169
- 选择适合您容器的迭代器类型：输入、输出、转发等。
- 使用标准库中的基迭代器类。例如，
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 以来已弃用。请参阅此处的相关讨论。
于 2010-08-27T09:11:28.430 回答
75
我将向您展示如何轻松地为您的自定义容器定义迭代器，但以防万一我创建了一个 c++11 库，它允许您轻松地为任何类型的容器创建具有自定义行为的自定义迭代器，连续或不连续的。
以下是创建和使用自定义迭代器的简单步骤：
- 创建您的“自定义迭代器”类。
- 在“自定义容器”类中定义 typedef。
- 例如
typedef blRawIterator< Type > iterator; - 例如
typedef blRawIterator< const Type > const_iterator;
- 例如
- 定义“开始”和“结束”功能
- 例如
iterator begin(){return iterator(&m_data[0]);}; - 例如
const_iterator cbegin()const{return const_iterator(&m_data[0]);};
- 例如
- 我们完成了！！！
最后，定义我们的自定义迭代器类：
注意： 在定义自定义迭代器时，我们从标准迭代器类别派生，让 STL 算法知道我们创建的迭代器类型。
在这个例子中，我定义了一个随机访问迭代器和一个反向随机访问迭代器：
//------------------------------------------------------------------- // Raw iterator with random access //------------------------------------------------------------------- template<typename blDataType> class blRawIterator { public: using iterator_category = std::random_access_iterator_tag; using value_type = blDataType; using difference_type = std::ptrdiff_t; using pointer = blDataType*; using reference = blDataType&; public: blRawIterator(blDataType* ptr = nullptr){m_ptr = ptr;} blRawIterator(const blRawIterator<blDataType>& rawIterator) = default; ~blRawIterator(){} blRawIterator<blDataType>& operator=(const blRawIterator<blDataType>& rawIterator) = default; blRawIterator<blDataType>& operator=(blDataType* ptr){m_ptr = ptr;return (*this);} operator bool()const { if(m_ptr) return true; else return false; } bool operator==(const blRawIterator<blDataType>& rawIterator)const{return (m_ptr == rawIterator.getConstPtr());} bool operator!=(const blRawIterator<blDataType>& rawIterator)const{return (m_ptr != rawIterator.getConstPtr());} blRawIterator<blDataType>& operator+=(const difference_type& movement){m_ptr += movement;return (*this);} blRawIterator<blDataType>& operator-=(const difference_type& movement){m_ptr -= movement;return (*this);} blRawIterator<blDataType>& operator++(){++m_ptr;return (*this);} blRawIterator<blDataType>& operator--(){--m_ptr;return (*this);} blRawIterator<blDataType> operator++(int){auto temp(*this);++m_ptr;return temp;} blRawIterator<blDataType> operator--(int){auto temp(*this);--m_ptr;return temp;} blRawIterator<blDataType> operator+(const difference_type& movement){auto oldPtr = m_ptr;m_ptr+=movement;auto temp(*this);m_ptr = oldPtr;return temp;} blRawIterator<blDataType> operator-(const difference_type& movement){auto oldPtr = m_ptr;m_ptr-=movement;auto temp(*this);m_ptr = oldPtr;return temp;} difference_type operator-(const blRawIterator<blDataType>& rawIterator){return std::distance(rawIterator.getPtr(),this->getPtr());} blDataType& operator*(){return *m_ptr;} const blDataType& operator*()const{return *m_ptr;} blDataType* operator->(){return m_ptr;} blDataType* getPtr()const{return m_ptr;} const blDataType* getConstPtr()const{return m_ptr;} protected: blDataType* m_ptr; }; //-------------------------------------------------------------------//------------------------------------------------------------------- // Raw reverse iterator with random access //------------------------------------------------------------------- template<typename blDataType> class blRawReverseIterator : public blRawIterator<blDataType> { public: blRawReverseIterator(blDataType* ptr = nullptr):blRawIterator<blDataType>(ptr){} blRawReverseIterator(const blRawIterator<blDataType>& rawIterator){this->m_ptr = rawIterator.getPtr();} blRawReverseIterator(const blRawReverseIterator<blDataType>& rawReverseIterator) = default; ~blRawReverseIterator(){} blRawReverseIterator<blDataType>& operator=(const blRawReverseIterator<blDataType>& rawReverseIterator) = default; blRawReverseIterator<blDataType>& operator=(const blRawIterator<blDataType>& rawIterator){this->m_ptr = rawIterator.getPtr();return (*this);} blRawReverseIterator<blDataType>& operator=(blDataType* ptr){this->setPtr(ptr);return (*this);} blRawReverseIterator<blDataType>& operator+=(const difference_type& movement){this->m_ptr -= movement;return (*this);} blRawReverseIterator<blDataType>& operator-=(const difference_type& movement){this->m_ptr += movement;return (*this);} blRawReverseIterator<blDataType>& operator++(){--this->m_ptr;return (*this);} blRawReverseIterator<blDataType>& operator--(){++this->m_ptr;return (*this);} blRawReverseIterator<blDataType> operator++(int){auto temp(*this);--this->m_ptr;return temp;} blRawReverseIterator<blDataType> operator--(int){auto temp(*this);++this->m_ptr;return temp;} blRawReverseIterator<blDataType> operator+(const int& movement){auto oldPtr = this->m_ptr;this->m_ptr-=movement;auto temp(*this);this->m_ptr = oldPtr;return temp;} blRawReverseIterator<blDataType> operator-(const int& movement){auto oldPtr = this->m_ptr;this->m_ptr+=movement;auto temp(*this);this->m_ptr = oldPtr;return temp;} difference_type operator-(const blRawReverseIterator<blDataType>& rawReverseIterator){return std::distance(this->getPtr(),rawReverseIterator.getPtr());} blRawIterator<blDataType> base(){blRawIterator<blDataType> forwardIterator(this->m_ptr); ++forwardIterator; return forwardIterator;} }; //-------------------------------------------------------------------
现在在您的自定义容器类中的某个位置：
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;
};
于 2014-04-02T04:35:24.093 回答
27
他们经常忘记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这个转换永远不会被使用。
于 2010-08-27T09:45:58.780 回答
24
Boost 有一些帮助：Boost.Iterator 库。
更准确地说，这个页面：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它。
于 2010-08-27T09:47:21.770 回答
16
我不知道 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;
于 2010-08-27T09:07:08.200 回答
14
有很多好的答案，但我创建了一个我使用的模板标题，它非常简洁且易于使用。
要将迭代器添加到您的类中，只需编写一个小类来表示具有 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 cmp(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
}
}
我希望它有所帮助。
于 2017-06-06T02:13:12.157 回答
2
我遇到了这篇文章，很惊讶这里没有真正提到一个简单的方法。使用指向值的指针（如std::iterator描述的方式）显然是一种非常通用的方法。但是你也许可以摆脱一些更简单的事情。当然，这是一种简单的方法，可能并不总是足够的，但如果是这样，我会将其发布给下一位读者。
很可能你的类中的底层类型是一个 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
};
于 2021-03-31T20:27:17.920 回答
1
我很想知道这是多么正确，但似乎可以作为内部数据存储的滚动您自己的迭代器
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(); }
}
于 2021-10-29T18:03:21.793 回答
-3
检查下面的代码，它可以工作
#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;
}
};
于 2020-11-28T19:54:14.777 回答