使用 boost 迭代器的自定义迭代器

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 迭代器库实现这些？

此外，我可能需要使用 Predicate 来允许过滤

一些入门指南会很有帮助。一个澄清：我不能使用 c++0x 编译器标志，因为我只需要使用 c++98。所以，请提出一个不需要 c++11 或 c++03 编译器标志的解决方案。

另外，如果我设计一个像下面这样的迭代器（嵌套在 GraphDM class 中），我实际上是在公开我的数据结构的细节。有没有办法让迭代器只迭代地图的键（而不是值）？然后我可以 return 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 指针）。我已将所有内容更正为 const-ness 的安全默认值。

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

使用 boost 迭代器的自定义迭代器

Custom Iterator using boost iterator

boost

iterator

boost-iterators

c++03