我在为这个SparseGraph类制作这个 const_iterator 时遇到了一些严重的问题
SparseGraph 类：
出于本文的意图和目的，aSparseGraph可以被视为边缘列表（或向量的向量）的列表（这通常称为邻接列表）。然后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++()给了我“非静态参考”错误：
错误：非静态数据成员“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} {}
//...
然后给了我错误
错误：“const_iterator”没有命名类型
为了
template <typename NodeType, typename EdgeType>
class SparseGraph
{
//...
public:
//...
const_iterator begin() const;
//...
}
和
错误：在“SparseGraph::const_iterator”之前需要“typename”，因为“SparseGraph”是一个依赖范围
为了
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());
然后更改为
错误：没有在类“SparseGraph”中声明的“typename SparseGraph::const_iterator SparseGraph::begin() const”成员函数
当我添加该类型名时。我怀疑如果我解决了第一个错误，这将得到解决，但是我不知道问题出在哪里。此外，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 类还是朋友的 const_iterator 类，或者，哪种方式是标准的？我应该如何实现 const_iterator 以避免这些问题？总的来说，我正在寻找一个双向 const_iterator，它将遍历 AdjacencyList（列表列表）中的每个 Edge，而不允许更改所述 AdjacencyList。
我查看了该站点上与“const_pointer implementation”相关的其他帖子，甚至提到了 Stroustrup 的“The C++ Programming Language”，但到目前为止，我还没有深入了解如何正确实现与此类似的 const_iterator。
我对如何正确地解决这个问题一点也不满意，所以对任何事情（可能与手头的主要问题无关）的任何帮助都将不胜感激。