c++ - español - ¿Cómo implementar un iterador de estilo STL y evitar las trampas comunes?

map c++

Question

Hice una colección para la que quiero proporcionar un iterador de acceso aleatorio de estilo STL. Estaba buscando un ejemplo de implementación de un iterador, pero no encontré ninguno. Sé de la necesidad de sobrecargas const de operadores [] y * . ¿Cuáles son los requisitos para que un iterador sea "estilo STL" y cuáles son algunos otros escollos que se deben evitar (si los hay)?

Contexto adicional: esto es para una biblioteca y no quiero introducir ninguna dependencia en ella 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 (así que no hay STL que probablemente se rompería).

Answer 1

Aquí hay una muestra de iterador de puntero en bruto.

¡No debes usar la clase iterador para trabajar con punteros en bruto!

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

Rango de puntero en bruto basado en la solución de bucle. Por favor, corríjame, si hay una mejor manera de hacer un bucle basado en rango desde el puntero en bruto.

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

Answer 2

En primer lugar, puede buscar http://www.cplusplus.com/reference/std/iterator/ una lista de las diversas operaciones que deben admitir los tipos de iteradores individuales.

A continuación, cuando haya realizado su clase de iterador, debe especializarse en std::iterator_traits y proporcionar algunos typedefs necesarios (como la categoría del iterador o el tipo de valor) o alternativamente derivarlo de std::iterator , que define los typedefs necesarios para usted. y, por lo tanto, se puede utilizar con el estándar std::iterator_traits .

descargo de responsabilidad: sé que a algunas personas no les gusta mucho cplusplus.com , pero brindan información realmente útil sobre esto.

Answer 3

Estaba tratando de resolver el problema de poder iterar sobre varios arrays de texto diferentes, todos los cuales se almacenan en una base de datos residente en memoria que es una struct grande.

Lo siguiente se desarrolló utilizando Visual Studio 2017 Community Edition en una aplicación de prueba MFC. Incluyo esto como un ejemplo, ya que esta publicación fue una de las varias que encontré que proporcionaron algo de ayuda, pero aún eran insuficientes para mis necesidades.

La struct contiene los datos residentes de la memoria era similar a la siguiente. He eliminado la mayoría de los elementos en aras de la brevedad y tampoco he incluido las definiciones de preprocesador utilizadas (el SDK en uso es para C y C ++ y es antiguo).

Lo que me interesaba era tener iteradores para las diversas matrices bidimensionales de WCHAR que contenían cadenas de texto para mnemotécnicas.

typedef struct tagUNINTRAM {
// stuff deleted ...
WCHAR ParaTransMnemo[MAX_TRANSM_NO][PARA_TRANSMNEMO_LEN]; /* prog #20 */
WCHAR ParaLeadThru[MAX_LEAD_NO][PARA_LEADTHRU_LEN]; /* prog #21 */
WCHAR ParaReportName[MAX_REPO_NO][PARA_REPORTNAME_LEN]; /* prog #22 */
WCHAR ParaSpeMnemo[MAX_SPEM_NO][PARA_SPEMNEMO_LEN]; /* prog #23 */
WCHAR ParaPCIF[MAX_PCIF_SIZE]; /* prog #39 */
WCHAR ParaAdjMnemo[MAX_ADJM_NO][PARA_ADJMNEMO_LEN]; /* prog #46 */
WCHAR ParaPrtModi[MAX_PRTMODI_NO][PARA_PRTMODI_LEN]; /* prog #47 */
WCHAR ParaMajorDEPT[MAX_MDEPT_NO][PARA_MAJORDEPT_LEN]; /* prog #48 */
// ... stuff deleted
} UNINIRAM;

El enfoque actual es usar una plantilla para definir una clase de proxy para cada una de las matrices y luego tener una sola clase de iterador que se pueda usar para iterar sobre una matriz en particular usando un objeto proxy que represente la matriz.

Una copia de los datos residentes de la memoria se almacena en un objeto que maneja la lectura y la escritura de los datos residentes de la memoria desde / hacia el disco. Esta clase, CFilePara contiene la clase de proxy con plantilla ( MnemonicIteratorDimSize y la subclase de la que se deriva, MnemonicIteratorDimSizeBase ) y la clase de iterador, MnemonicIterator .

El objeto proxy creado se adjunta a un objeto iterador que accede a la información necesaria a través de una interfaz descrita por una clase base de la que se derivan todas las clases proxy. El resultado es tener un solo tipo de clase de iterador que se puede usar con varias clases de proxy diferentes porque las diferentes clases de proxy exponen la misma interfaz, la interfaz de la clase base de proxy.

Lo primero fue crear un conjunto de identificadores que se proporcionarían a una fábrica de clases para generar el objeto proxy específico para ese tipo de mnemónico. Estos identificadores se utilizan como parte de la interfaz de usuario para identificar los datos de aprovisionamiento particulares que el usuario está interesado en ver y posiblemente modificar.

const static DWORD_PTR dwId_TransactionMnemonic = 1;
const static DWORD_PTR dwId_ReportMnemonic = 2;
const static DWORD_PTR dwId_SpecialMnemonic = 3;
const static DWORD_PTR dwId_LeadThroughMnemonic = 4;

La clase de proxy

La clase de proxy con plantilla y su clase base son las siguientes. Necesitaba acomodar varios tipos diferentes de wchar_t de wchar_t texto wchar_t . Las matrices bidimensionales tenían diferentes números de mnemónicas, dependiendo del tipo (propósito) de la mnemotécnica y los diferentes tipos de mnemónicas tenían diferentes longitudes máximas, que variaban entre cinco caracteres de texto y veinte caracteres de texto. Las plantillas para la clase de proxy derivada fueron un ajuste natural con la plantilla que requiere el número máximo de caracteres en cada mnemónico. Después de crear el objeto proxy, usamos el método SetRange() para especificar la matriz mnemónica real y su rango.

// proxy object which represents a particular subsection of the
// memory resident database each of which is an array of wchar_t
// text arrays though the number of array elements may vary.
class MnemonicIteratorDimSizeBase
{
DWORD_PTR m_Type;
public:
MnemonicIteratorDimSizeBase(DWORD_PTR x) { }
virtual ~MnemonicIteratorDimSizeBase() { }
virtual wchar_t *begin() = 0;
virtual wchar_t *end() = 0;
virtual wchar_t *get(int i) = 0;
virtual int ItemSize() = 0;
virtual int ItemCount() = 0;
virtual DWORD_PTR ItemType() { return m_Type; }
};
template <size_t sDimSize>
class MnemonicIteratorDimSize : public MnemonicIteratorDimSizeBase
{
wchar_t (*m_begin)[sDimSize];
wchar_t (*m_end)[sDimSize];
public:
MnemonicIteratorDimSize(DWORD_PTR x) : MnemonicIteratorDimSizeBase(x), m_begin(0), m_end(0) { }
virtual ~MnemonicIteratorDimSize() { }
virtual wchar_t *begin() { return m_begin[0]; }
virtual wchar_t *end() { return m_end[0]; }
virtual wchar_t *get(int i) { return m_begin[i]; }
virtual int ItemSize() { return sDimSize; }
virtual int ItemCount() { return m_end - m_begin; }
void SetRange(wchar_t (*begin)[sDimSize], wchar_t (*end)[sDimSize]) {
m_begin = begin; m_end = end;
}
};

La clase de iterador

La propia clase de iterador es la siguiente. Esta clase proporciona una funcionalidad básica de iterador directo, que es todo lo que se necesita en este momento. Sin embargo, espero que esto cambie o se extienda cuando necesite algo más de él.

class MnemonicIterator
{
private:
MnemonicIteratorDimSizeBase *m_p; // we do not own this pointer. we just use it to access current item.
int m_index; // zero based index of item.
wchar_t *m_item; // value to be returned.
public:
MnemonicIterator(MnemonicIteratorDimSizeBase *p) : m_p(p) { }
~MnemonicIterator() { }
// a ranged for needs begin() and end() to determine the range.
// the range is up to but not including what end() returns.
MnemonicIterator & begin() { m_item = m_p->get(m_index = 0); return *this; } // begining of range of values for ranged for. first item
MnemonicIterator & end() { m_item = m_p->get(m_index = m_p->ItemCount()); return *this; } // end of range of values for ranged for. item after last item.
MnemonicIterator & operator ++ () { m_item = m_p->get(++m_index); return *this; } // prefix increment, ++p
MnemonicIterator & operator ++ (int i) { m_item = m_p->get(m_index++); return *this; } // postfix increment, p++
bool operator != (MnemonicIterator &p) { return **this != *p; } // minimum logical operator is not equal to
wchar_t * operator *() const { return m_item; } // dereference iterator to get what is pointed to
};

La fábrica de objetos proxy determina qué objeto crear basándose en el identificador mnemónico. El objeto proxy se crea y el puntero devuelto es el tipo de clase base estándar para tener una interfaz uniforme independientemente de a cuál de las diferentes secciones mnemónicas se accede. El método SetRange() se utiliza para especificar al objeto proxy los elementos de la matriz específica que representa el proxy y el rango de los elementos de la matriz.

CFilePara::MnemonicIteratorDimSizeBase * CFilePara::MakeIterator(DWORD_PTR x)
{
CFilePara::MnemonicIteratorDimSizeBase *mi = nullptr;
switch (x) {
case dwId_TransactionMnemonic:
{
CFilePara::MnemonicIteratorDimSize<PARA_TRANSMNEMO_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_TRANSMNEMO_LEN>(x);
mk->SetRange(&m_Para.ParaTransMnemo[0], &m_Para.ParaTransMnemo[MAX_TRANSM_NO]);
mi = mk;
}
break;
case dwId_ReportMnemonic:
{
CFilePara::MnemonicIteratorDimSize<PARA_REPORTNAME_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_REPORTNAME_LEN>(x);
mk->SetRange(&m_Para.ParaReportName[0], &m_Para.ParaReportName[MAX_REPO_NO]);
mi = mk;
}
break;
case dwId_SpecialMnemonic:
{
CFilePara::MnemonicIteratorDimSize<PARA_SPEMNEMO_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_SPEMNEMO_LEN>(x);
mk->SetRange(&m_Para.ParaSpeMnemo[0], &m_Para.ParaSpeMnemo[MAX_SPEM_NO]);
mi = mk;
}
break;
case dwId_LeadThroughMnemonic:
{
CFilePara::MnemonicIteratorDimSize<PARA_LEADTHRU_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_LEADTHRU_LEN>(x);
mk->SetRange(&m_Para.ParaLeadThru[0], &m_Para.ParaLeadThru[MAX_LEAD_NO]);
mi = mk;
}
break;
}
return mi;
}

Usando la clase Proxy y el iterador

La clase proxy y su iterador se usan como se muestra en el siguiente bucle para completar un objeto CListCtrl con una lista de mnemotécnicas. Estoy usando std::unique_ptr para que cuando la clase de proxy ya no sea necesaria y std::unique_ptr fuera del alcance, se limpie la memoria.

Lo que hace este código fuente es crear un objeto proxy para la matriz dentro de la struct que corresponde al identificador mnemónico especificado. Luego crea un iterador para ese objeto, usa un rango for completar el control CListCtrl y luego se limpia. Estas son todas las wchar_t texto wchar_t sin wchar_t que pueden ser exactamente el número de elementos de la matriz, por lo que copiamos la cadena en un búfer temporal para asegurarnos de que el texto termina en cero.

 std::unique_ptr<CFilePara::MnemonicIteratorDimSizeBase> pObj(pFile->MakeIterator(m_IteratorType));
CFilePara::MnemonicIterator pIter(pObj.get()); // provide the raw pointer to the iterator who doesn''t own it.
int i = 0; // CListCtrl index for zero based position to insert mnemonic.
for (auto x : pIter)
{
WCHAR szText[32] = { 0 }; // Temporary buffer.
wcsncpy_s(szText, 32, x, pObj->ItemSize());
m_mnemonicList.InsertItem(i, szText); i++;
}

Answer 4

La documentación de iterator_facade de Boost.Iterator proporciona lo que parece un buen tutorial sobre cómo implementar iteradores para una lista enlazada. ¿Podría usar eso como punto de partida para construir un iterador de acceso aleatorio sobre su contenedor?

Si no hace nada más, puede echar un vistazo a las funciones miembro y las definiciones de tipo proporcionadas por iterator_facade y utilizarlas como punto de partida para crear su propio dispositivo.

Answer 5

Thomas Becker escribió un artículo útil sobre el tema here .

También hubo este enfoque (quizás más sencillo) que apareció anteriormente en SO: ¿Cómo implementar correctamente iteradores y const_iterators personalizados?

Answer 6

Yo estaba / estoy en el mismo bote que tú por diferentes razones (en parte educativa, en parte restricciones). Tuve que volver a escribir todos los contenedores de la biblioteca estándar y los contenedores tuvieron que ajustarse a la norma. Eso significa que, si cambio mi contenedor con la versión estándar , el código funcionará igual. Lo que también significaba que tenía que volver a escribir los iteradores.

De todos modos, miré a EASTL . Además de aprender mucho sobre los contenedores que nunca aprendí todo este tiempo utilizando los contenedores STL o a través de mis cursos de pregrado. La razón principal es que EASTL es más legible que la contraparte de stl (encontré que esto se debe simplemente a la falta de todas las macros y al estilo de codificación directa). Hay algunas cosas espeluznantes allí (como #ifdefs para excepciones) pero nada que te abrume.

Como han mencionado otros, consulte la referencia de cplusplus.com en iteradores y contenedores.

Answer 7

http://www.cplusplus.com/reference/std/iterator/ tiene un gráfico ú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. A continuación 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;
};

Puede especializar std::iterator_traits<youriterator> , o poner los mismos typedefs en el mismo iterador, o heredar de std::iterator (que tiene estos typedefs). Prefiero la segunda opción, para evitar cambiar las cosas en el std nombres std , y para facilitar la lectura, pero la mayoría de las personas heredan 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 std::input_iterator_tag , std::output_iterator_tag , std::forward_iterator_tag , std::random_access_iterator_tag o std::random_access_iterator_tag , dependiendo de los requisitos que satisfaga su iterador. Dependiendo de su iterador, puede elegir especializar también std::next , std::prev , std::advance , y std::distance , pero esto rara vez es necesario. En casos extremadamente raros es posible que desee especializarse std::begin y std::end .

Probablemente, su contenedor también debe tener un const_iterator , que es un iterador (posiblemente mutable) para datos constantes que es similar a su iterator excepto que debe ser implícitamente construible desde un iterator y los usuarios no deberían poder modificar los datos. Es común que su puntero interno sea un puntero a datos no constantes y que el iterator herede de const_iterator para minimizar la duplicación de código.

Mi publicación en Writing your own STL Container tiene un prototipo de contenedor / iterador más completo.