Пользовательский итератор, использующий повышающий итератор

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 Iterator?

Кроме того, мне может понадобиться предикат, чтобы разрешить фильтрацию

Некоторые указатели для начала будут очень полезны. Одно уточнение: я не могу использовать флаги компилятора 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>, что очень вероятно, что вы хотите.

• Были некоторые проблемы с правильностью констант (методы equal_range принимают константные указатели). Я исправил все в сторону безопасного значения по умолчанию.

Жить на Колиру

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