0

私は次のようなカスタムデータ構造を持っています:

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 を実装する必要があります。ブースト反復子ライブラリを使用してこれらを実装するにはどうすればよいですか?

また、フィルタリングを可能にするために述語を取る必要があるかもしれません

開始するためのいくつかのポインターは非常に役立ちます。明確化の 1 つ: c++98 のみを使用する必要があるため、c++0x コンパイラ フラグは使用できません。したがって、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;

    };
4

1 に答える 1

0

あなたのテキストには、カスタム イテレータを作成するという要件はありません。内部マップからイテレータを型定義するだけです。

ここで、いくつか修正しました。

  • boost::hash<Node>通常、 に適用することはできませんNode const*。ハッシュを指定しない場合、 defaultboost::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;
}
于 2016-03-05T13:53:19.393 に答える