How to increase the size of an array of C++ std::list which was previous allocated by new operator?

Question

I was trying to implement some graph related problem. To represent the graph, I used adjacency list using std::list, something like this,

list<int> *adj;
adj = new list<int>[V];

where V is the total vertices.

then I took all the edges(directed) and store them using the function,

void addEdge(int u, int v) {   //  when u points to v
     adj[u].push_back(v);
}

So the graph looks like this:

Graph Theory

Everything works fine, but I want to add a new vertex. I was trying to adjust my adj list, but I can't do that. What I did, I make a copy of it, then delete adj and make a new adj with higher size, and finally copy back all the previous adjacency list into it.

Here is my code:

void addVertex() {

        //  backing up the current adjacency list to adj2
        list<int> *adj2 = new list<int>[V];

        for(int s=0; s<V; s++) {
            for(list<int>::iterator i = adj[s].begin(); i != adj[s].end(); i++) {
                adj2[s].push_back(*i);
            }
        }

        delete[] adj;   //  deleting original adjacency list

        ++V;    //  add one vertex.

        adj = new list<int>[V];     //  allocating new adjacency list

        //  resoting adjacency lists back to adj
        for(int s=0; s<V-1; s++) {
            for(list<int>::iterator i = adj2[s].begin(); i != adj2[s].end(); i++) {
                adj[s].push_back(*i);
            }
        }
    }

It works correctly, but I was just wondering if there is any smart way to do that, because every time I want to add a vertex it needs lots of operations.

I tried a lot of things, but didn't find similar question/answer here.

XY problem."The smart way" is to not use a dynamically-allocated array in the first place. — DevSolar, Oct 09 '18 at 21:38
Sidenote. Don't dynamically allocate the `vector`. `vector`'s job is to manage memory for you and as soon as you dynamically allocate one, you're taking that responsibility back upon yourself. With references and modern C++'s skill at finding opportunities to take advantage of [copy elision](https://en.wikipedia.org/wiki/Copy_elision) and [move semantics](https://stackoverflow.com/questions/3106110/what-are-move-semantics) you can pass and return `vector`s with a minimum of copying. There is almost never a need to dynamically allocate one or any other library container. — user4581301, Oct 09 '18 at 22:06
I'm thinking class Vertex has-a adjacency list. But either way, the problem is the new/delete. It's not as big an issue __which__ std container you are dynamically allocating. — Kenny Ostrom, Oct 09 '18 at 23:02
@user4581301 I disagree re `vector`. It's quite common to use `resize()` when the size of a `vector` is known. Faster than just `push_back` and avoids a series of allocates and moves as the `vector` grows. It also avoids excess memory allocation as `vector` reserved memory is resized automatically to in relatively large increments usually done as some fraction of the existing size. — doug, Oct 09 '18 at 23:04
@Doug I think you are misinterpreting what I wrote. My warning is to not is to not allocate containers with `new`. If you need an unknown number of containers, as the Asker does, make a `vector` of them. After that, you can let the container resize itself as best fits your use case. — user4581301, Oct 09 '18 at 23:15
@user4581301. Indeed. Appreciate the clarification. When you used the words "dynamically allocate the vector" I took it to mean the automatic process `vector<>` uses rather than using new to dynamically allocate an array. — doug, Oct 09 '18 at 23:44

Caleth · Accepted Answer · 2018-10-09T23:38:43.387

Don't use new anywhere (with the sole exception: constructors of a class named something_ptr).

What you probably want is something like

class Vertex
{
    std::vector<std::vector<int>> adjacency;

    void addEdge(int u, int v) 
    {
        adjacency[u].push_back(v);
        // If it's an undirected graph, also ?
        // adjacency[v].push_back(u);
    }

    void addVertex() 
    {
        adjacency.emplace_back();
        // do something with adjacency.back()
    }
};

How to increase the size of an array of C++ std::list which was previous allocated by new operator?

1 Answers1