如何实现std-like迭代器的自定义实现？

Question

我写了一个很简单的文件管理数据库basicly看起来是这样的：

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

现在我想通过包含在数据库就像使用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 
    } 
} 

我已经阅读过类似问题的答案，一些人建议派生std::iterator，一些人使用std::iterator_traits，但我并不真正了解如何做到这一点。尝试实现自定义迭代器时可能会出错的是什么？什么是简单而优雅的方式来做到这一点？

编辑： 请不要考虑使用助推，我的问题是更具概念性。

编辑2：

的FileDB是这样的：

• ROOTDIR

  • foo1
    • BAR1
      • foo1bar1_1.txt
      • foo1bar1_2.txt
    • BAR2
      • foo1bar2_1.txt
      • foo1bar2_2.txt

  • foo2的

  • FOON

    • barM中

      • fooNBarM_x.txt

所以基本上，我可以找到它的名称的文件。

由于我的容器不在内存中，因此我没有指向其数据的指针。所以我的想法是将文件的路径存储在迭代器中。这样，我可以用字符串比较来实现operator==，因为路径应该是唯一的。从fileDB.end()返回的迭代器将是一个空字符串，operator*将调用fileDB::loadFile()及其文件路径。

我最大的担心是关于operator++。有文件名，我可以找到包含的目录并搜索下一个文件，但这实际上是无效的。任何想法如何做到这一点？或者我完全错了我的整个概念？

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

自己写迭代器很难。将迭代器添加到类中的最好方法是重用现有类。你应该知道，例如指针和C++中的迭代器一样好，所以有很多方法可以提供一个迭代器，而无需真正编写自己的迭代器。

这基本上是C++在很多方面的工作原理。它试图通过给图书馆编写者带来很大的负担，使终端用户的语言变得易消耗和简单。即图书馆编写者可以编写所有不重要的东西，所以最终用户不需要。迭代器通常是图书馆的一部分。

说了这么多，来这里的实际丑陋的部分：

为了能够编写自己的迭代器，这里有一些事情你需要知道的。

类型性状：

型性状是一个简单的机制来aditional的信息在C++与不能改变自己的作品类型，甚至添加到类型。例如，对于一个迭代器来说，知道它迭代的重要性（即包含的类型）很重要。获取给定迭代器的这些信息的方式在很大程度上取决于迭代器。对于实际上是对象的迭代器，可以在类中添加typedef并使用它们，但对于需要从指针类型推断它的指针的迭代器。为了使这成为可能，信息被存储在类型特征中，所以代码可以查看这个信息。这是std::iterator_traits型特质。

std::iterator_traits可以处理任何东西，这些东西是从std::iterator模板以及任何类型的指针派生而来的，没有任何调整。所以经常最好使用std::iterator作为避免编写自己的特质专业化的基础。如果你不能做到这一点，仍然有可能提供必要的特征，但它会更难。

标签类和迭代器类型：

有几种不同的类型在C++中提供的迭代器具有不同的行为和可以/不可以做很多不同的事情的。看看http://cplusplus.com/reference/std/iterator/，看看有什么样的迭代器可用以及它们可以做什么。这些图不意味​​着以面向对象的方式（即，input_iterator既不是子类也不是基类forward_iterator），而是作为API类型的派生。即你可以使用所有为输入迭代器编写的算法，也可以使用前向迭代器。页面上的表格会告诉您必须为每个类别提供哪些方法。由于这些类别实际上并不是彼此的子类（它们不应该是，特别是当来自不同类型的集合时），因此使用另一种机制来识别每个迭代器的功能。描述每个迭代器的std::iterator_traits中还包含一个空标记类，它说明了此迭代器可以做什么以及不能做什么。如果您没有编写自己的特征，则需要在实例化时将此标记类提供给std::iterator模板。

实施例：

这个例子是从CPLUSPLUS服用。在迭代器Com部分：

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

这个迭代器并没有真正意义，因为它只是一个包装指针，这也已经被直接使用。但它可以作为解释。通过提供适当的标签，迭代器从std::iterator衍生为input_iterator。此外，该模板被告知，该迭代器正在迭代ints。需要的所有其他类型difference_type,reference,poiner等都由模板自动传递。在某些情况下，手动更改某些类型可能是有意义的（例如std::shared_ptr有时必须用作pointer）。此迭代器所需的特征也将自动存在，因为它已经从std::iterator派生出来，并且std::iterator_traits知道在哪里可以找到所有必要的信息。

Answer 3

这里是遍历期间计算子节点的迭代器。 我是为windows编写的，但我认为它不是很难在其他平台上使用。

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