Trashes в скопированном std :: list

У меня есть класс графика, который выглядит так:

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) Я получаю большое количество мусора в нем:

(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,...

Как это исправить?

2

Решение

gdb вероятно запутывается детали реализации std::list, Например. Старый SGI STL list был реализован как круговой список. Внутри list объект, есть только один _List_node<_Tp> указатель называется _M_node, Конструктор ставит внутренний _M_next указатель конечного элемента узла, равный _M_node сам.

Причина внедрения Стандартной библиотеки std::list использовать эту циклическую реализацию, чтобы избежать особых случаев для конечного элемента (например, они могли бы также использовать элемент стража с nullptr следующий указатель). Мэтт Аустерн имеет хороший Презентация ACCU об этом (но ссылка в настоящее время на поврежденный файл, см. архивная версия здесь).

Эта круговая реализация объясняет, почему ваш gdb выход для g.neighbors() имеет повторяющийся узор [0] = 2, [1] = 1, [2] = 4294956560, /* etcetera */, Значение 4294956560 — это просто адрес памяти внутреннего _M_node переменная вашего std::list, так что если gdb только преследование одного указателя, оно запутается. Обратите внимание, что это меньше, чем 2^32вы, вероятно, компилируете это для 32-битных.

Вы, вероятно, должны проверить это по-своему <list> заголовок стандартной библиотеки в вашей системе. Отчет об ошибке для gdb также может быть в порядке.

3

Другие решения

Я думаю, что проблема в конструкторе копирования, просто сделайте это:

AdjList(const AdjList& g) : AdjList(g.m_nodes_count) {
m_list = g.m_list ;
}

operator=() метод должен создать новый Vector<Row> с теми же узлами, которые g.m_list есть.

0

По вопросам рекламы [email protected]