У меня есть представление графа в видеstd::vector<std::unordered_set<unsigned>> neighborsвершины являются целыми числами, и для каждой вершины мы сохраняем множество ее соседей. Таким образом, чтобы пройти все края, я бы сделал что-то вроде

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

Теперь я хотел бы получить тот же эффект от

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

гдеg из класса, инкапсулирующегоneighbors вектор.

Однако все, что я пробовал, кажется чрезвычайно сложным, лучшая версия, которую я могу придумать, имеет 50 строк, и трудно понять, что это правильно. Есть ли простой способ сделать это?

Вот моя уродливая версия:

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