Trashes in copied std::list

Question

I have graph class that looks like:

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];
    }
};

but when I try to get 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,...

How to fix that?

Answer 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.

The reason Standard Library implementations of 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).

This circular implementation explains why your 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.

You should probably verify this in your own <list> header of the Standard Library on your system. A bug report for gdb might also be in order.

Answer 2

I think that the problem is on the copy constructor, just do this:

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

The operator=() method should create a new Vector<Row> with the same nodes that g.m_list has.