¿Cómo realizar una implementación personalizada de un iterador estándar?

Question

He escrito un archivo muy simple gestión de base de datos que básicamente es el siguiente:

class FileDB 
{ 
public: 
    FileDB(std::string dir) : rootDir(dir) { } 

    void loadFile(std::string filename, File &file) const; 
    void saveFile(std::string filename, const File &file) const; 

private: 
    std::string rootDir; 
} 

Ahora me gustaría iterar a través de todos los archivos contenidos en la base de datos como el uso de un std::iterator: Me

void iterateFiles() 
{ 
    FileDB filedb("C:\\MyFiles"); 

    for (FileDB::iterator file_it = filedb.begin(); file_it != filedb.end(); ++file_it) 
    { 
     File f = *file_it; 
     // do something with file 
    } 
} 

He leído respuestas a preguntas similares, algunas sugiriendo derivar std::iterator, algunas para usar std::iterator_traits, pero realmente no entiendo cómo hacerlo. ¿Qué puede salir mal al intentar implementar un iterador personalizado? ¿Y cuál es una forma simple pero elegante de hacerlo?

EDITAR: Por favor, no considere usar boost, mi pregunta es de naturaleza más conceptual.

EDIT 2:

El FileDB funciona así:

• RootDir

  • foo1
    • Bar1
      • foo1bar1_1.txt
      • foo1bar1_2.txt
    • bar2
      • foo1bar2_1.txt
      • foo1bar2_2.txt

  • foo2

  • Foon

    • barM

      • fooNBarM_x.txt

Así que, básicamente, no puedo encontrar un archivo por su nombre.

Como mi contenedor no está en la memoria, no tengo punteros a sus datos. Entonces mi idea era almacenar la ruta del archivo en el iterador. De esta forma, puedo implementar operator== con una comparación de cadenas, ya que las rutas deben ser únicas. El iterador devuelto desde fileDB.end() sería una cadena vacía y operator* llamaría al fileDB::loadFile() con su ruta de archivo.

Mi mayor preocupación es acerca de operator++.Al tener el nombre de archivo, puedo encontrar el directorio que lo contiene y buscar el siguiente archivo, pero esto es realmente ineficaz. ¿Alguna idea sobre cómo hacer eso? ¿O estoy completamente equivocado con todo mi concepto?

Answer 1

class FileDB 
{ 
class iterator; 

public: 
    FileDB(std::string dir) : m_rootDir(dir) { m_files = getFileTreeList(); } 

    void loadFile(std::string filename, File &file) const; 
    void saveFile(std::string filename, const File &file) const; 


    iterator begin() 
    { 
     return iterator(m_files.begin(), *this); 
    } 
    iterator end() 
    { 
     return iterator(m_files.end(), *this); 
    } 

private: 
    std::list<std::string> getFileTreeList() const; 

private:  
    std::string m_rootDir; 
    std::list<std::string> m_files; 
} 



class FileDB::iterator 
{ 
public: 
    iterator(std::list<std::string>::iterator pos, FileDB& owner) : m_pos(pos), m_owner(owner){} 

    bool operator==(const iterator& rhs) {return m_pos == rhs.m_pos;} 
    bool operator!=(const iterator& rhs) {return m_pos != rhs.m_pos;} 
    //etc 

    void operator++() {++m_pos;} 

    File operator*() 
    { 
    return openFile(*m_pos); // for example open some file descriptor 
    } 

    ~iterator() 
    { 
    closeFile(*m_pos); // clean up! 
    } 

private: 
    std::list<std::string>::iterator& m_pos; 
    FileDB& m_owner; 
}; 

Answer 2

Escribir iteradores usted mismo casi nunca es bonito. La forma más pretendida de agregar un iterador a sus clases es reutilizar una existente. Debe tener en cuenta que los punteros, por ejemplo, son tan buenos como los iteradores en C++, por lo que hay muchas formas de proporcionar un iterador sin tener que escribir el suyo.

Esto es básicamente cómo funciona C++ de muchas maneras. Trata de hacer que el lenguaje sea prescindible y simple para los usuarios finales al poner una gran carga en los escritores de la biblioteca. Es decir. los escritores de bibliotecas pueden escribir todo lo poco atractivo, por lo que el usuario final no tiene que hacerlo. Los iteradores son usualmente parte de una biblioteca.

Dicho esto, aquí viene la parte fea real:

Para ser capaz de escribir sus propios iteradores, aquí hay algunas cosas que hay que tener en cuenta.

rasgos

Tipo:

rasgos de tipo son un mecanismo simple para añadir información adicional a los tipos en C++ que funciona incluso con tipos que no pueden cambiarse a sí mismos. Por ejemplo, para un iterador es importante saber qué itera (es decir, el tipo contenido). La forma de obtener esta información para un iterador dado depende mucho del iterador. Para los iteradores que en realidad son objetos, puede agregar typedefs en la clase y usarlos, pero para los iteradores que son punteros, debe deducirlo del tipo de puntero. Para que esto sea posible, la información se almacena en un rasgo de tipo, de modo que hay un solo lugar donde un código puede ver esta información. Este es el rasgo de tipo std::iterator_traits.

std::iterator_traits funcionan en cualquier cosa, que se deriva de la plantilla std::iterator, así como en cualquier tipo de puntero, sin ningún ajuste. Muy a menudo lo mejor es usar std::iterator como base para evitar tener que escribir su propia especialización de rasgos. En caso de que no pueda hacer esto, aún es posible proporcionar los rasgos necesarios, pero será más difícil.

clases y tipos de etiquetas de iterador:

Hay varios tipos diferentes de iteradores disponibles en C++ que tienen un comportamiento diferente y puede/no se puede hacer un montón de cosas diferentes. Eche un vistazo al http://cplusplus.com/reference/std/iterator/ para ver qué tipo de iteradores están disponibles y qué pueden hacer. Los diagramas no están destinados a ser orientados a objetos (es decir, un input_iterator no es una subclase ni una clase base de forward_iterator), sino más bien como un tipo de derivación de API. Es decir. puede usar todos los algoritmos que se escribieron para un iterador de entrada también con un iterador directo. La tabla en la página le dirá qué métodos debe proporcionar para cada categoría.

Dado que estas categorías no son realmente subcategorías entre sí (no deberían serlo, especialmente cuando proceden de diferentes tipos de colecciones), se utiliza otro mecanismo para identificar las capacidades de cada iterador. También se incluye una clase de etiqueta vacía en el std::iterator_traits que describe cada iterador, que indica qué puede hacer este iterador y qué no puede hacer. Si no escribe sus propios rasgos, debe proporcionar esta clase de etiqueta a la plantilla std::iterator al crear instancias.

Ejemplo:

Este ejemplo se toma de la cplusplus.com en la sección iteradores:

class myiterator : public iterator<input_iterator_tag, int> 
{ 
    int* p; 
public: 
    myiterator(int* x) :p(x) {} 
    myiterator(const myiterator& mit) : p(mit.p) {} 
    myiterator& operator++() {++p;return *this;} 
    myiterator operator++(int) {myiterator tmp(*this); operator++(); return tmp;} 
    bool operator==(const myiterator& rhs) {return p==rhs.p;} 
    bool operator!=(const myiterator& rhs) {return p!=rhs.p;} 
    int& operator*() {return *p;} 
}; 

Este iterador no tiene mucho sentido, ya que sólo se ajusta un puntero, que también podría haber sido utilizado directamente. Sin embargo, puede servir como una explicación. El iterador se deriva de std::iterator como input_iterator proporcionando la etiqueta adecuada. También se le dice a la plantilla que este iterador está iterando sobre int s. Todos los demás tipos, que son necesarios difference_type, reference, poiner etc. son automáticamente introducidos por la plantilla. En algunos casos, puede tener sentido cambiar algunos de estos tipos manualmente (por ejemplo, un std::shared_ptr se debe usar a veces como pointer). Además, los rasgos necesarios para este iterador existirán automáticamente, dado que ya se derivan de std::iterator y std::iterator_traits saben dónde encontrar toda la información necesaria.

Answer 3

Aquí está el iterador que calcula los subnodos durante el recorrido. Lo escribí para Windows, pero creo que no es difícil convertirlo para otras plataformas.

#include <list> 
#include <windows.h> 
#include <assert.h> 
#include <iostream> 
#include <string> 

class File{}; 

class Iterator 
{ 
public: 
    virtual bool isDone() = 0; 
    virtual void next() = 0; 

    virtual std::string getFileName() = 0; 

    virtual ~Iterator(){}; 
}; 

bool operator== (Iterator& lhs, Iterator& rhs); 

class EndIterator : public Iterator 
{ 
public: 
    virtual bool isDone() {return true;} 
    virtual void next(){}; 
    virtual std::string getFileName() {return "end";}; 
}; 

class DirectoryIterator : public Iterator 
{ 
public: 
    DirectoryIterator(const std::string& path); 

    virtual bool isDone(); 
    virtual void next(); 

    virtual std::string getFileName(); 

    virtual ~DirectoryIterator(); 

private: 
    std::list<Iterator*> getSubelementsList(const std::string& path) const; 
    void init(); 

private: 
    bool m_wasInit; 
    std::string m_path; 
    std::list<Iterator*> m_leaves; 
    std::list<Iterator*>::iterator m_current; 
}; 

class FilesIterator : public Iterator 
{ 
public: 
    FilesIterator(const std::string& fileName); 

    virtual bool isDone(){return true;}; 
    virtual void next(){}; 

    virtual std::string getFileName(); 

    virtual ~FilesIterator(){}; 

private: 
    std::string m_fileName; 
}; 


class DbItertor 
{ 
public: 
    DbItertor(Iterator* iterator) : m_ptr(iterator){} 
    DbItertor(const DbItertor& rhs) {*m_ptr = *rhs.m_ptr;} 

    std::string operator*() 
    { 
    if(m_ptr->isDone()) 
     return "end"; 
    return m_ptr->getFileName(); 
    } 
    //File operator->(){return FileOpen(m_ptr->getFileName());} 

    void operator++() {m_ptr->next();} 

    ~DbItertor(){delete m_ptr;} 
private: 
    Iterator* m_ptr; 
}; 


class FileDB 
{ 
public: 
    FileDB(std::string dir) : m_rootDir(dir){} 


    DbItertor begin() 
    { 
    return DbItertor(new DirectoryIterator(m_rootDir)); 
    } 
    DbItertor end() 
    { 
    return DbItertor(new EndIterator()); 
    } 

private: 
    std::string m_rootDir; 
};  

FilesIterator::FilesIterator(const std::string& fileName) : 
    m_fileName(fileName) 
{} 


std::string FilesIterator::getFileName() 
{ 
    return m_fileName; 
} 

DirectoryIterator::DirectoryIterator(const std::string& path) : 
    m_wasInit(false), 
    m_path(path) 
{} 

void DirectoryIterator::init() 
{ 
    m_leaves = getSubelementsList(m_path); 
    m_current = m_leaves.begin(); 
    m_wasInit = true; 

    next(); 
} 

DirectoryIterator::~DirectoryIterator() 
{ 
    for(std::list<Iterator*>::iterator i = m_leaves.begin(); i != m_leaves.end(); ++i) 
    delete *i; 
} 

void DirectoryIterator::next() 
{ 
    if(!m_wasInit) 
    init(); 

    if(isDone()) 
    return; 

    if((*m_current)->isDone()) 
    ++m_current; 
    else 
    (*m_current)->next(); 
} 

bool DirectoryIterator::isDone() 
{ 
    if(!m_wasInit) 
    init(); 

    return (m_leaves.size() == 0) || (m_current == --m_leaves.end()); 
} 

std::string DirectoryIterator::getFileName() 
{ 
    if(!m_wasInit) 
    init(); 

    return (*m_current)->getFileName(); 
} 


std::list<Iterator*> DirectoryIterator::getSubelementsList(const std::string& path) const 
{ 
    std::list<Iterator*> result; 

    WIN32_FIND_DATA fdFile; 
    HANDLE hFind = NULL; 

    char sPath[2048] = {0}; 

    sprintf(sPath, "%s\\*.*", path.c_str()); 

    hFind = FindFirstFile(sPath, &fdFile); 
    assert(hFind != INVALID_HANDLE_VALUE); 

    do 
    { 
    if(strcmp(fdFile.cFileName, ".") != 0 && strcmp(fdFile.cFileName, "..") != 0) 
    { 
     std::string fullName = path; 
     fullName += std::string(fdFile.cFileName); 

     if(fdFile.dwFileAttributes &FILE_ATTRIBUTE_DIRECTORY) 
     { 
     fullName += "\\"; 
     result.push_back(new DirectoryIterator(fullName)); 
     } 
     else 
     { 
     result.push_back(new FilesIterator(fullName)); 
     } 
    } 
    } 
    while(FindNextFile(hFind, &fdFile)); 

    FindClose(hFind); 

    return result; 
} 

bool operator== (Iterator& lhs, Iterator& rhs) 
{ 
    return lhs.getFileName() == rhs.getFileName(); 
} 

bool operator!= (DbItertor& lhs, DbItertor& rhs) 
{ 
    return *lhs != *rhs; 
} 

int main() 
{ 
    FileDB db("C:\\456\\"); 
    for(DbItertor i = db.begin(); i != db.end(); ++i) 
    { 
    std::cout << *i << std::endl; 
    } 

    return 0; 
}