Jak zrealizować niestandardową implementację iteratora typu std?

Question

Napisałem bardzo prosty plik zarządzania bazą danych, która w zasadzie wygląda tak:

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

Teraz chciałbym iterację wszystkich plików zawartych w bazie danych jak przy użyciu std::iterator:

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

I "Czytałem odpowiedzi na podobne pytania, niektóre sugerują wyprowadzenie std::iterator, niektóre z nich używają std::iterator_traits, ale tak naprawdę nie rozumiem, jak to zrobić. Co może pójść źle podczas próby implementacji niestandardowego iteratora? A jaki jest prosty, ale elegancki sposób na zrobienie tego?

EDIT: Proszę nie rozważyć użycie impuls, moje pytanie jest bardziej koncepcyjny charakter.

EDIT 2:

FileDB działa tak:

• rootDir

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

  • foo2

  • Foon

    • barm

      • fooNBarM_x.txt

Więc w zasadzie mogę znaleźć plik przez jego nazwę.

Ponieważ mój pojemnik nie jest w pamięci, nie mam wskaźników do jego danych. Więc moim pomysłem było przechowywanie ścieżki pliku w iteratorze. W ten sposób mogę zaimplementować operator== z porównaniem ciągów, ponieważ ścieżki powinny być unikalne. Iterator zwrócony z fileDB.end() byłby pustym ciągiem, a operator* wywołałby fileDB::loadFile() z jego ścieżką do pliku.

Mój największy problem dotyczy operator++.Mając nazwę pliku, mogę znaleźć katalog zawierający i wyszukać następny plik, ale jest to naprawdę nieskuteczne. Wszelkie pomysły, jak to zrobić? Czy jestem całkowicie w błędzie z całą moją koncepcją?

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

Samo pisanie iteratorów prawie nigdy nie jest piękne. Najprostszym sposobem dodania iteratora do twoich zajęć jest ponowne użycie istniejącego. Powinieneś być świadomy, że wskaźniki są na przykład tak samo dobre jak iteratory w C++, więc istnieje wiele sposobów na zapewnienie iteratora bez konieczności pisania własnych.

Jest to zasadniczo sposób działania C++ na wiele sposobów. Próbuje uczynić język łatwym i łatwym dla użytkowników końcowych, nakładając wiele obciążeń na autorów bibliotek. To znaczy. autorzy bibliotek mogą pisać wszystkie niepretetyczne rzeczy, więc użytkownik końcowy nie musi tego robić. Iteratory są zwykle częścią biblioteki.

Mimo, że tutaj jest rzeczywisty udział brzydki:

Aby móc pisać własne iteratory, oto kilka rzeczy, które trzeba znać.

Rodzaj cechy:

typu cechy są prostym mechanizmem, aby dodać aditional informacji typów w C++, która działa nawet z typów, które nie mogą być zmieniane siebie. Na przykład dla iteratora ważne jest, aby wiedzieć, co on iteruje (tj. Typ zamknięty). Sposób uzyskania tej informacji dla danego iteratora zależy w dużej mierze od iteratora. W przypadku iteratorów, które w rzeczywistości są obiektami, można dodać typedefs do klasy i używać ich, ale w przypadku iteratorów będących wskaźnikami, które należy wywnioskować z typu wskaźnika. Aby było to możliwe, informacja jest przechowywana w typie cechy, a więc istnieje jedno miejsce, w którym kod może wyglądać na tę informację. Jest to cecha typu std::iterator_traits.

std::iterator_traits pracować na wszystko, co pochodzi od szablonu std::iterator, a także na każdym rodzaju wskaźnika, bez żadnych zmian. Tak często najlepiej jest używać std::iterator jako podstawy, aby uniknąć konieczności pisania specjalizacji własnych cech. Jeśli nie możesz tego zrobić, nadal możesz podać niezbędne cechy, ale będzie to trudniejsze.

Tag klasy i typy iteracyjnej:

Istnieje kilka różnych rodzajów iteratorów dostępnych w języku C++, które mają różne zachowania i może/nie może zrobić wiele różnych rzeczy. Spójrz na http://cplusplus.com/reference/std/iterator/, aby zobaczyć, jakie rodzaje iteratorów są dostępne i co mogą zrobić. Schematy nie mają być zorientowane obiektowo (tj. input_iterator nie jest ani podrzędną, ani podstawową klasą forward_iterator), ale raczej jako rodzaj derywacji API. To znaczy. możesz użyć wszystkich algorytmów zapisanych dla iteratora wejściowego również z iteratorem forward. W tabeli na stronie dowiesz się, jakie metody musisz podać dla każdej kategorii.

Ponieważ te kategorie nie są w rzeczywistości podklasami od siebie (nie powinny być, szczególnie gdy pochodzą z różnych typów kolekcji), inny mechanizm służy do określenia możliwości każdego iteratora. Pusta klasa znaczników jest również zawarta w std::iterator_traits opisującej każdy iterator, która mówi, co ten iterator może zrobić i czego nie może zrobić. Jeśli nie piszesz własnych cech, musisz dostarczyć tę klasę znaczników do szablonu std::iterator po utworzeniu instancji.

przykład:

Przykład pochodzi z cplusplus.Sekcja com na iteratorów:

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

ten iterator naprawdę nie ma sensu, ponieważ tylko owija wskaźnik, który może również być stosowany bezpośrednio. Jednak może służyć jako wyjaśnienie. Iterator wywodzi się z std::iterator jako input_iterator, dostarczając odpowiedni znacznik. Również szablon jest informowany, że iterator iteruje ponad int s. Wszystkie pozostałe typy, które są potrzebne, są automatycznie wnioskowane przez szablon za pomocą następujących szablonów: difference_type, reference, poiner. W niektórych przypadkach może być sens ręczna zmiana niektórych z tych typów (np. std::shared_ptr musi być czasem używana jako pointer). Również cechy potrzebne do tego iteratora będą istniały automatycznie, ponieważ są już wyprowadzone z std::iterator, a std::iterator_traits wie, gdzie znaleźć wszystkie niezbędne informacje.

Answer 3

Tutaj jest iterator który podwęzełki kasatetes podczas przejścia. Napisałem go dla systemu Windows, ale myślę, że nie jest to trudne do castomizacji na inne platformy.

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