在复制的std :: list中出现垃圾 [英] Trashes in copied std::list
问题描述
class Graph {
public：
typedef unsigned int size_type;
typedef std :: list< size_type>邻居;
保护：
size_type m_nodes_count，m_edges_count;
$ b $ public：
Graph（size_type nodes_count = 0）：
m_nodes_count（nodes_count），m_edges_count（0）{}
virtual bool is_edge（size_type from，size_type to）= 0;
虚拟邻居邻居（size_type node）= 0;
虚拟图形& add_edge（size_type from，size_type to）= 0;
virtual void delete_edge（size_type from，size_type to）= 0;
size_type nodes_count（）{return m_nodes_count; }
size_type edges_count（）{return m_edges_count; }
virtual〜Graph（）{}
};
类AdjList：public Graph {
private：
typedef std :: list< size_type>行;
std :: vector< Row> m_list;
$ b $ public：
AdjList（size_type nodes_count）：Graph（nodes_count）{
m_list.resize（nodes_count）;
}
AdjList（const AdjList& g）：AdjList（g.m_nodes_count）{
for（int i = 0; i< nodes_count（）; i ++）
std :: copy（g.m_list [i] .begin（），g.m_list [i] .end（），std :: back_inserter（m_list [i]））;
$ b $ virtual bool is_edge（size_type from，size_type to）override {
return std :: find（m_list [from] .begin（），m_list [from] .end （），to）！= m_list [from] .end（）;
}
虚拟图& add_edge（size_type from，size_type to）覆盖{
if（！is_edge（from，to）&&！is_edge（to，from））{
m_list [from] .push_back（to）;
m_list [to] .push_back（from）;
m_edges_count ++;
}
return * this;
virtual void delete_edge（size_type from，size_type to）override {
m_list [from] .remove（to）;
m_list [to] .remove（to）;
m_edges_count--;
}
虚拟邻居邻居（size_type node）{
return m_list [node];
}
};
但是当我尝试获取 graph.neighbours（v）我收到大量的垃圾：
（gdb）p图
$ 1 = {< ;格拉夫> = {_vptr.Graph = 0x406210< vtable for AdjList + 16>，m_nodes_count = 3，m_edges_count = 3}，m_list = std ::长度为3的矢量，容量3 = {std :: list = {[0]
= 2，[1] = 1}，
std :: list = {[0] = 0，[1] = 2}，std :: list = {[0] = 0，[1] = 1}}}
（gdb）p graph.neighbours（0）
$ 2 = std :: list = {[0] = 2，[1] = 1，[2] = 4294956560，[ 3] = 2，[4] = 1，
[5] = 4294956560，[6] = 2，[7] = 1，[8] = 4294956560，[9] = 2，[10] = 1 ，
[11] = 4294956560，[12] = 2，[13] = 1，[14] = 4294956560，[15] = 2，
[16] = 1，[17] = 4294956560 ，[18] = 2，[19] = 1，[20] = 4294956560，
[21] = 2，[22] = 1，[23] = 4294956560，[24] = 2， = 1，...
如何解决？
可能会被实现细节弄糊涂 的std ::列表 。例如。旧的 SGI STL list 已作为循环列表实施。在 list 对象内，只有一个 _List_node< _Tp> 指针，称为 _M_node 。构造函数将最终节点元素的内部 _M_next 指针等于 _M_node 本身。 标准库实现 您应该在系统上标准库的 I have graph class that looks like: but when I try to get How to fix that? The reason Standard Library implementations of This circular implementation explains why your You should probably verify this in your own 这篇关于在复制的std :: list中出现垃圾的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！ std :: list 使用此通函实现的目的是避免特殊情况元素（例如，它们也可以使用一个带有 nullptr 下一个指针的标记元素）。 Matt Austern对此有一个很好的 ACCU演示文稿（但该链接目前为损坏的文件，请参阅此处存档的版本
$ b 这个通知解释了为什么 gdb 为 g输出.neighbors（）具有重复模式 [0] = 2，[1] = 1，[2] = 4294956560，/ * etcetera * / 。值4294956560只是 std :: list 的内部 _M_node 变量的内存地址，所以如果 gdb 只会执行简单的指针追踪，它会变得困惑。注意它小于 2 ^ 32 ，也就是说你可能要编译32位。
gdb 的错误报告也可能是有序的。class Graph {
public:
typedef unsigned int size_type;
typedef std::list<size_type> Neighbours;
protected:
size_type m_nodes_count, m_edges_count;
public:
Graph(size_type nodes_count = 0) :
m_nodes_count(nodes_count), m_edges_count(0) {}
virtual bool is_edge(size_type from, size_type to) = 0;
virtual Neighbours neighbours(size_type node) = 0;
virtual Graph& add_edge(size_type from, size_type to) = 0;
virtual void delete_edge(size_type from, size_type to) = 0;
size_type nodes_count() { return m_nodes_count; }
size_type edges_count() { return m_edges_count; }
virtual ~Graph() {}
};
class AdjList : public Graph {
private:
typedef std::list<size_type> Row;
std::vector<Row> m_list;
public:
AdjList(size_type nodes_count) : Graph(nodes_count) {
m_list.resize(nodes_count);
}
AdjList(const AdjList& g) : AdjList(g.m_nodes_count) {
for (int i = 0; i < nodes_count(); i++)
std::copy(g.m_list[i].begin(), g.m_list[i].end(), std::back_inserter(m_list[i]));
}
virtual bool is_edge(size_type from, size_type to) override {
return std::find(m_list[from].begin(), m_list[from].end(), to) != m_list[from].end();
}
virtual Graph& add_edge(size_type from, size_type to) override {
if (!is_edge(from, to) && !is_edge(to, from)) {
m_list[from].push_back(to);
m_list[to].push_back(from);
m_edges_count++;
}
return *this;
}
virtual void delete_edge(size_type from, size_type to) override {
m_list[from].remove(to);
m_list[to].remove(to);
m_edges_count--;
}
virtual Neighbours neighbours(size_type node) {
return m_list[node];
}
};
graph.neighbours(v) I get big amount of trash in it:(gdb) p graph
$1 = {<Graph> = {_vptr.Graph = 0x406210 <vtable for AdjList+16>, m_nodes_count = 3, m_edges_count = 3}, m_list = std::vector of length 3, capacity 3 = {std::list = {[0]
= 2, [1] = 1},
std::list = {[0] = 0, [1] = 2}, std::list = {[0] = 0, [1] = 1}}}
(gdb) p graph.neighbours(0)
$2 = std::list = {[0] = 2, [1] = 1, [2] = 4294956560, [3] = 2, [4] = 1,
[5] = 4294956560, [6] = 2, [7] = 1, [8] = 4294956560, [9] = 2, [10] = 1,
[11] = 4294956560, [12] = 2, [13] = 1, [14] = 4294956560, [15] = 2,
[16] = 1, [17] = 4294956560, [18] = 2, [19] = 1, [20] = 4294956560,
[21] = 2, [22] = 1, [23] = 4294956560, [24] = 2, [25] = 1,...
gdb is probably getting confused by an implementation detail the std::list. E.g. the old SGI STL list was implemented as a circular list. Inside the list object, there is only a singly _List_node<_Tp> pointer called _M_node. The constructor puts the internal _M_next pointer of the final node element equal to _M_node itself. std::list use this circular implementation is to avoid special cases for the final element (e.g. they could also use a a sentinel element with a nullptr next pointer). Matt Austern has a nice ACCU presentation about this (but the link is currently to a corrupted file, see archived version here).gdb output for g.neighbors() has the repeating pattern of [0] = 2, [1] = 1, [2] = 4294956560, /* etcetera */. The value 4294956560 is simply the memory address of the internal _M_node variable of your std::list, so if gdb only does simnple pointer chasing, it will get confused. Notice that it is less than 2^32, i.e. you are probably compiling this for 32-bits. <list> header of the Standard Library on your system. A bug report for gdb might also be in order.
