У меня есть класс графика, который выглядит так:
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,...
Как это исправить?
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
также может быть в порядке.
Я думаю, что проблема в конструкторе копирования, просто сделайте это:
AdjList(const AdjList& g) : AdjList(g.m_nodes_count) {
m_list = g.m_list ;
}
operator=()
метод должен создать новый Vector<Row>
с теми же узлами, которые g.m_list
есть.