Ich habe eine Darstellung eines Graphen alsstd::vector<std::unordered_set<unsigned>> neighborsDas heißt, Scheitelpunkte sind ganze Zahlen, und für jeden Scheitelpunkt behalten wir eine Reihe seiner Nachbarn bei. Also, um alle Kanten zu gehen, würde ich so etwas tun

for (unsigned u = 0; u < neighbors.size(); ++u)
    for (unsigned v : neighbors[u])
        if (u <= v)
            std::cout << u << ' ' << v << std::endl;

Jetzt möchte ich in der Lage sein, den gleichen Effekt von zu erhalten

for (auto e: g.edges())
    std::cout << e.first << ' ' << e.second << std::endl;

woherg ist aus einer Klasse, die dasneighbors Vektor.

Alles, was ich ausprobiert habe, scheint jedoch äußerst kompliziert zu sein. Die beste Version, die ich finden kann, hat 50 Zeilen, und es ist schwer zu erkennen, dass es richtig ist. Gibt es eine einfache Möglichkeit, dies zu tun?

Hier ist meine hässliche Version:

#include <iostream>
#include <unordered_set>
#include <vector>
typedef unsigned Vertex;
class Graph {
public:
    typedef std::unordered_set<Vertex> Neighbors;
    std::size_t numVertices() const { return neighbors_.size(); }
    Graph(std::size_t n = 0) : neighbors_(n) { }
    void addEdge(Vertex u, Vertex v) {
        neighbors_[u].insert(v);
        neighbors_[v].insert(u);
    }
    class EdgeIter {
        friend Graph;
    public:
        bool operator!=(const EdgeIter& other) { return u_ != other.u_; }
        void operator++() {
            do {
                ++it_;
                while (it_ == it_end_) {
                    u_++;
                    if (u_ >= neighbors_.size())
                        break;
                    it_     = neighbors_[u_].cbegin();
                    it_end_ = neighbors_[u_].cend();
                }
            } while (u_ < neighbors_.size() && *it_ < u_);
        }
        std::pair<Vertex, Vertex> operator*() { return {u_, *it_}; }
    private:
        EdgeIter(const std::vector<std::unordered_set<Vertex> >& neighbors, size_t u)
            : u_(u), neighbors_(neighbors) {
            if (u < neighbors_.size()) {
                it_     = neighbors_[u_].cbegin();
                it_end_ = neighbors_[u_].cend();
                while (it_ == it_end_) {
                    u_++;
                    if (u_ >= neighbors_.size())
                        break;
                    it_     = neighbors_[u_].cbegin();
                    it_end_ = neighbors_[u_].cend();
                }
            }
        }
        Vertex u_;
        const std::vector<std::unordered_set<Vertex> >& neighbors_;
        std::unordered_set<Vertex>::const_iterator it_, it_end_;
    };
    EdgeIter edgesBegin() const { return EdgeIter(neighbors_, 0); }
    EdgeIter edgesEnd()   const { return EdgeIter(neighbors_, neighbors_.size()); }
    class Edges {
    public:
        Edges(const Graph& g) : g_(g) { }
        EdgeIter begin() const { return g_.edgesBegin(); }
        EdgeIter end  () const { return g_.edgesEnd();   }
    private:
        const Graph& g_;
    };
    Edges edges() { return Edges(*this); }
    std::vector<Neighbors> neighbors_;
};
int main() {
    Graph g(5);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(1, 3);    
    for (unsigned u = 0; u < g.numVertices(); ++u)
        for (unsigned v : g.neighbors_[u])
            if (u <= v)
                std::cout << u << ' ' << v << std::endl;
    for (auto e: g.edges())
        std::cout << e.first << ' ' << e.second << std::endl;
}