使用自定義迭代器升壓迭代

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