¿Cómo implementar un iterador estilo STL y evitar errores comunes?
Hice una colección para la que quiero proporcionar un iterador de acceso aleatorio estilo STL. Estaba buscando un ejemplo de implementación de un iterador pero no encontré ninguno. Conozco la necesidad de sobrecargas constantes de operadores []y *. ¿Cuáles son los requisitos para que un iterador sea "estilo STL" y cuáles son algunos otros errores que se deben evitar (si los hay)?
Contexto adicional: esto es para una biblioteca y no quiero introducir ninguna dependencia a menos que realmente lo necesite. Escribo mi propia colección para poder proporcionar compatibilidad binaria entre C++03 y C++11 con el mismo compilador (por lo que no hay STL que probablemente se rompa).
https://cplusplus.com/reference/iterator/ tiene un cuadro útil que detalla las especificaciones del § 24.2.2 del estándar C++11. Básicamente, los iteradores tienen etiquetas que describen las operaciones válidas y las etiquetas tienen una jerarquía. Lo siguiente es puramente simbólico, estas clases en realidad no existen como tales.
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.
Puede especializarse std::iterator_traits<youriterator>, poner los mismos tipos de definición en el iterador o heredar de std::iterator(que tiene estos tipos de definición). Prefiero la segunda opción, para evitar cambiar cosas en el stdespacio de nombres y para facilitar la lectura, pero la mayoría de la gente hereda de 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
};
Tenga en cuenta que iterator_category debe ser una de std::input_iterator_tag, std::output_iterator_tag, std::forward_iterator_tag, std::bidirectional_iterator_tago std::random_access_iterator_tag, según los requisitos que satisfaga su iterador. Dependiendo de su iterador, puede optar por especializarse std::next, std::prev, std::advancey std::distancetambién, pero esto rara vez es necesario. En casos extremadamente raros, es posible que desee especializarse std::beginy std::end.
Su contenedor probablemente también debería tener un const_iterator, que es un iterador (posiblemente mutable) para datos constantes que es similar al suyo iteratorexcepto que debería ser implícitamente construible desde a iteratory los usuarios no deberían poder modificar los datos. Es común que su puntero interno sea un puntero a datos no constantes y herede iteratorpara const_iteratorminimizar la duplicación de código.
Mi publicación en Escribiendo tu propio contenedor STL tiene un prototipo de contenedor/iterador más completo.
A continuación se muestra un ejemplo de iterador de puntero sin formato.
¡No deberías usar la clase iterador para trabajar con punteros sin formato!
#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; }
Solución alternativa de bucle basada en el rango del puntero sin formato. Por favor, corríjame si hay una mejor manera de hacer un bucle basado en rango desde un puntero sin formato.
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); }
Y prueba sencilla
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);
}
}
Thomas Becker escribió aquí un útil artículo sobre el tema .
También existía este enfoque (quizás más simple) que apareció anteriormente en SO: ¿ Cómo implementar correctamente iteradores personalizados y const_iterators?
En primer lugar, puede buscar aquí una lista de las diversas operaciones que los tipos de iteradores individuales deben admitir.
A continuación, cuando haya creado su clase de iterador, deberá especializarse std::iterator_traitsen ella y proporcionar algunos typedefs necesarios (como iterator_categoryo value_type) o, alternativamente, derivarlos de std::iterator, que define los s necesarios typedefpara usted y, por lo tanto, puede usarse con el valor predeterminado std::iterator_traits.
Descargo de responsabilidad: sé que a algunas personas no les gusta cplusplus.commucho, pero brindan información realmente útil sobre esto.
