我有一个自定义容器类,我想为它写iterator类和const_iterator类。
我以前从来没有这样做过,我也没有找到合适的操作方法。关于创建迭代器的指导原则是什么?我应该注意什么?
我还希望避免代码重复(我觉得const_iterator和iterator共享很多东西;一个应该子类化另一个吗?)
脚注:我很确定Boost有一些东西可以缓解这个问题,但由于许多愚蠢的原因,我不能在这里使用它。
我有一个自定义容器类,我想为它写iterator类和const_iterator类。
我以前从来没有这样做过,我也没有找到合适的操作方法。关于创建迭代器的指导原则是什么?我应该注意什么?
我还希望避免代码重复(我觉得const_iterator和iterator共享很多东西;一个应该子类化另一个吗?)
脚注:我很确定Boost有一些东西可以缓解这个问题,但由于许多愚蠢的原因,我不能在这里使用它。
当前回答
检查下面的代码,它工作
#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;
}
};
其他回答
我有兴趣知道这是如何正确的,但似乎工作作为一个滚动您自己的迭代器内部数据存储
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(); }
}
我偶然看到这篇文章,很惊讶这里没有提到一个简单的方法。使用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
};
他们经常忘记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(); } };
正如前面提到的,要点是使用单个模板实现并对其进行类型定义。
Choose type of iterator which fits your container: input, output, forward etc. Use base iterator classes from standard library. For example, std::iterator with random_access_iterator_tag.These base classes define all type definitions required by STL and do other work. To avoid code duplication iterator class should be a template class and be parametrized by "value type", "pointer type", "reference type" or all of them (depends on implementation). For example: // 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; Notice iterator_type and const_iterator_type type definitions: they are types for your non-const and const iterators.
参见:标准库参考
EDIT: std::iterator自c++ 17起已弃用。请在这里查看相关讨论。