c++ - const_iterator : nested class or friend class?

Question

我在为这个 SparseGraph 类制作这个 const_iterator 时遇到了一些严重的问题

稀疏图类:

出于本文的意图和目的，SparseGraph 可以被视为边列表(或 vector 的 vector )的列表(这通常称为邻接列表)。 const_iterator 然后遍历列表列表中的每条边。

考虑:

template <typename NodeType, typename EdgeType>
class SparseGraph
{
public:
    //...
    using EdgeList = std::vector<EdgeType>;
    using AdjacencyList = std::vector<EdgeList>;
    //...
private:
    //...
    AdjacencyList m_adj_list;
    //...
}

const_iterator(嵌套类)的初始尝试

//----SparseGraph
template <typename NodeType, typename EdgeType>
class SparseGraph
{
public:
    class const_iterator; //nested
    //...
}

//----SparseGraph::const_iterator
template <typename NodeType, typename EdgeType>
class SparseGraph<NodeType, EdgeType>::const_iterator
{
private:
    using NodeIterator = typename SparseGraph<NodeType, EdgeType>::AdjacencyList::const_iterator;
    using EdgeIterator = typename SparseGraph<NodeType, EdgeType>::EdgeList::const_iterator;

    //this is used to iterate through each edge list corresponding to each node
    NodeIterator m_node_it;

    //this is used to iterate through each edge in each edge list.
    EdgeIterator m_edge_it;

public:
    const_iterator(const NodeIterator& node_it, const EdgeIterator& edge_it)
        : m_node_it{node_it}, m_edge_it{edge_it} {}

    const_iterator& operator++(int)
    {
        //TODO
        return *this;
    }
    //...

人们可能会注意到，operator++() 给出了“非静态引用”错误:

error: invalid use of non-static data member 'SparseGraph::m_adj_list'

来自:

//...
if(m_node_it == m_adj_list.end()) { //<--here,
    //loop back around to the beginning
    m_node_it = m_adj_list.begin(); //<--here,
}
m_edge_it = m_node_it.begin();//<--and here.
//...

---

const_iterator(友元类)的初始尝试

现在我们有一些类似的东西:

//----SparseGraph
template <typename NodeType, typename EdgeType>
class SparseGraph
{
public:
    friend class const_iterator; //friend
    //as before...
}

//----SparseGraph::const_iterator-------------------------------------------------------------------------------------------------------------
template <typename NodeType, typename EdgeType>
class const_iterator
{
private:
    using NodeIterator = typename SparseGraph<NodeType, EdgeType>::AdjacencyList::const_iterator;
    using EdgeIterator = typename SparseGraph<NodeType, EdgeType>::EdgeList::const_iterator;

    const SparseGraph<NodeType, EdgeType>& m_graph;
    NodeIterator m_node_it;
    EdgeIterator m_edge_it;

public:
    const_iterator(const SparseGraph<NodeType, EdgeType>& graph,
                   const NodeIterator& node_it,
                   const EdgeIterator& edge_it)
        : m_graph{graph} {}
    //...

然后给了我错误

error: 'const_iterator' does not name a type

对于

template <typename NodeType, typename EdgeType>
class SparseGraph
{
//...
public:
//...
    const_iterator begin() const;
//...
}

和

error: need 'typename' before 'SparseGraph::const_iterator' because 'SparseGraph' is a dependent scope

对于

template <typename NodeType, typename EdgeType> typename 
SparseGraph<NodeType, EdgeType>::const_iterator SparseGraph<NodeType, EdgeType>::begin() const
{
    return const_iterator(*this, m_adj_list.begin(), m_adj_list.begin() >begin());

然后变为

error: no 'typename SparseGraph::const_iterator SparseGraph::begin() const' member function declared in class 'SparseGraph'

当我添加那个类型名称时。我怀疑如果我解决了第一个错误就会解决这个问题，但是我不知道问题出在哪里。此外，friend 类现在正在污染包含它的任何翻译单元的范围。

我的当前代码

#ifndef SPARSE_GRAPH_H
#define SPARSE_GRAPH_H

#include <iostream>
#include <vector>

enum
{
    invalid_node_index=-1
};

template <typename NodeType, typename EdgeType>
class SparseGraph
{
public:
    class const_iterator;
    using Node = NodeType;
    using Edge = EdgeType;
    using NodeList = std::vector<Node>;
    using EdgeList = std::vector<Edge>;
    using AdjacencyList = std::vector<EdgeList>;

private:
    //...

    //Similarly to the NodeList, each node index is analogous
    //to its index in this list. Each element of this list contains
    //a sub-list of edges associated with a particular node.
    //For example, the list at index 3 will contain all edges associated
    //with the node with an index of 3. This is so we can have an O(1) lookup time.
    AdjacencyList m_adj_list;

    //...

public:
    SparseGraph() {}

    //...

    const_iterator begin() const;
    const_iterator end() const;

    //...
};










//----SparseGraph::const_iterator-------------------------------------------
template <typename NodeType, typename EdgeType>
class const_iterator
{
private:
    using NodeIterator = typename SparseGraph<NodeType, EdgeType>::AdjacencyList::const_iterator;
    using EdgeIterator = typename SparseGraph<NodeType, EdgeType>::EdgeList::const_iterator;

    NodeIterator m_node_it;
    EdgeIterator m_edge_it;
    const NodeIterator m_begin;
    const NodeIterator m_end;

public:
    const_iterator(NodeIterator node_it,
                   EdgeIterator edge_it,
                   NodeIterator begin,
                   NodeIterator end)
        : m_node_it{node_it}, m_edge_it{edge_it}, m_begin{begin}, m_end{end} {}

    const_iterator& operator++(int)
    {
        //are we at the end of a valid edge list?
        if(m_node_it != end && m_edge_it == m_node_it->end()) {
            //move to the next non-empty edge list or to the end of the adjacency list
            while(m_node_it != end && m_node_it->empty()) {
                m_node_it++;
            }
            if(m_node_it != end) {
                m_edge_it = m_node_it->begin();
            }
        }
        else {
            m_edge_it++;
        }
        return *this;
    }

    const_iterator& operator--(int)
    {
        //TODO
        return *this;
    }

    const typename SparseGraph<NodeType, EdgeType>::Edge& operator*() const
    {
        return *m_edge_it;
    }

    const typename SparseGraph<NodeType, EdgeType>::Edge* operator->() const
    {
        return &(*m_edge_it);
    }

    bool operator==(const const_iterator& other) const
    {
        return m_node_it == other.m_node_it &&
               m_edge_it == other.m_edge_it;
    }

    bool operator!=(const const_iterator& other) const
    {
        return !(*this == other);
    }
};










//----SPARSE_GRAPH----------------------------------------------------------

//----PUBLIC FUNCTIONS------------------------------------------------------

//----begin()
template <typename NodeType, typename EdgeType>
typename SparseGraph<NodeType, EdgeType>::const_iterator SparseGraph<NodeType, EdgeType>::begin() const
{
    return const_iterator(m_adj_list.begin(),
                          m_adj_list.begin()->begin(),
                          m_adj_list.begin(),
                          m_adj_list.back().end());
}

//----end()
template <typename NodeType, typename EdgeType>
typename SparseGraph<NodeType, EdgeType>::const_iterator SparseGraph<NodeType, EdgeType>::end() const
{
    return const_iterator(m_adj_list.end(),
                          m_adj_list.end()->end(),
                          m_adj_list.begin(),
                          m_adj_list.back().end());
}

#endif // SPARSE_GRAPH_H

我的问题是，我应该怎么做？我应该使用嵌套的 const_iterator 类还是 friend const_iterator 类，或者，哪种方式是标准的？我应该如何实现 const_iterator 来避免这些问题？总的来说，我正在寻找一个双向 const_iterator，它将遍历 AdjacencyList(列表的列表)中的每个边，而不允许更改所述 AdjacencyList。

我查看了该站点上与“const_pointer 实现”相关的其他帖子，甚至提到了 Stroustrup 的“C++ 编程语言”，但到目前为止，还没有任何内容让我深入了解如何正确实现与此类似的 const_iterator .

我对如何正确处理这个问题一点也不满意，因此非常感谢对任何事情(可能与手头的主要问题无关)的任何帮助。

Answer 1

你的原创

error: invalid use of non-static data member 'SparseGraph::m_adj_list'

表示在获取m_adj_list.begin() 的范围内没有SparseGraph。你不需要调用它，只需将 SparseGraph::m_adj_list 的开始和结束存储在你的 const_iterator

template <typename NodeType, typename EdgeType>
class SparseGraph<NodeType, EdgeType>::const_iterator
{
private:
    using NodeIterator = typename SparseGraph<NodeType, EdgeType>::AdjacencyList::const_iterator;
    using EdgeIterator = typename SparseGraph<NodeType, EdgeType>::AdjacencyList::const_iterator;

    const_iterator(NodeIterator node_it, EdgeIterator edge_it, NodeIterator adjacent_begin, NodeIterator adjacent_end) : m_node_it{node_it}, m_edge_it{edge_it}, m_adjacent_begin{adjacent_begin}, m_adjacent_end{adjacent_end} {}

    const NodeIterator m_adjacent_begin;
    const NodeIterator m_adjacent_end;
    NodeIterator m_node_it;
    EdgeIterator m_edge_it;

    const_iterator& operator++(int)
    {
        //are we at the end of this edge list?
        if(m_edge_it == m_node_it->end()) {
            //move to the next node's edge list.
            m_node_it++;
            //are we past the last node's edge list?
            if(m_node_it == m_adjacent_end) {
                //loop back around to the beginning
                m_node_it = m_adjacent_begin;
            }
            m_edge_it = m_node_it.begin();
        }
        else {
            m_edge_it++;
        }
        return *this;
    }
}