使用自定义迭代器升压迭代

Question

我有一个自定义的数据结构，就像下面：

class Node; 

class GraphDM { 
public: 
    GraphDM(); 
    // these are to iterate on all items of _faninNodes 
    // like all elements in multimap 
    FaninIter faninBegin(); 
    FaninIter faninEnd(); 

    // these are to iterate on all items of _fanoutNodes 
    FanoutIter fanoutBegin(); 
    FanoutIter fanoutEnd(); 

    // these should work like equal_range of multimap 
    std::pair<FaninIter, FaninIter > getFanins (const Node *node_); 
    std::pair<FaninIter, FaninIter > getFanouts(const Node *node_); 

private: 
    typedef std::vector< Node* > NodeList; 
    typedef boost::unordered_map< Node*, 
            NodeList > Map; 

    Map  _faninNodes; 
    Map  _fanoutNodes; 
}; 

我需要实现这些API。我怎样才能实现这些使用boost迭代器库？

此外，我可能需要采取谓词允许过滤

一些指针上手会有很大的帮助。一个解释：我不能使用C++ 0x编译器标志，因为我只需要使用C++ 98。所以，请建议一个不需要C++ 11或C++ 03编译器标志的解决方案。另外，如果我设计一个像下面这样的迭代器（嵌套在GraphDM类中），我基本上公开了详细的数据结构。有没有办法让迭代器只迭代地图上的键（而不是数值）？然后，我可以为getFanins（）和getFanout（）返回不同类型的迭代器，它们将是值列表中的迭代器。

class Iter : public boost::iterator_adaptor< Iter, 
               Map::iterator, 
               boost::use_default > 
    { 
    public: 
     Iter() : Iter::iterator_adaptor_() {} 


    private: 
     friend class GraphDM; 

     Iter(Map::iterator it) 
       : Iter::iterator_adaptor_(it) {} 

     friend class boost::iterator_core_access; 

    }; 

Answer 1

我在您的文本中看不到任何要求创建自定义迭代器。你只需从内部映射中键入迭代器即可。

在这里，我固定的一些事情：

• 你通常不能适用boost::hash<Node>到Node const*。如果你不指定散列，它将默认boost::hash<key_type>，这很可能是你想要的。

• 有一些const正确性问题（equal_range方法采用const指针）。我已经纠正了一切，以保证安全的默认设置。

Live On Coliru

#include <utility> 
#include <boost/unordered_map.hpp> 
#include <vector> 

struct Node {}; 

class GraphDM { 
    typedef std::vector<Node const*> NodeList; 
    typedef boost::unordered_map<Node const *, NodeList/*, boost::hash<Node const*>*/ > Id2NodeListMap; 

    public: 
    typedef Id2NodeListMap::const_iterator FaninIter; 
    typedef Id2NodeListMap::const_iterator FanoutIter; 

    GraphDM() {} 

    FaninIter faninBegin() const; 
    FaninIter faninEnd() const; 

    FanoutIter fanoutBegin() const; 
    FanoutIter fanoutEnd() const; 

    // these should work like equal_range of multimap 
    std::pair<FaninIter, FaninIter> getFanins(Node const *node_) const; 
    std::pair<FaninIter, FaninIter> getFanouts(Node const *node_) const; 

    private: 
    Id2NodeListMap _faninNodes; 
    Id2NodeListMap _fanoutNodes; 
}; 

GraphDM::FaninIter GraphDM::faninBegin() const { 
    return _faninNodes.begin(); 
} 

GraphDM::FaninIter GraphDM::faninEnd() const { 
    return _faninNodes.end(); 
} 

GraphDM::FanoutIter GraphDM::fanoutBegin() const { 
    return _fanoutNodes.begin(); 
} 

GraphDM::FanoutIter GraphDM::fanoutEnd() const { 
    return _fanoutNodes.end(); 
} 

// these should work like equal_range of multimap 
std::pair<GraphDM::FaninIter, GraphDM::FaninIter> GraphDM::getFanins(Node const *node_) const { 
    return _faninNodes.equal_range(node_); 
} 
std::pair<GraphDM::FaninIter, GraphDM::FaninIter> GraphDM::getFanouts(Node const *node_) const { 
    return _fanoutNodes.equal_range(node_); 
} 

int main() { 
    GraphDM demo; 
}