Как увеличить размер массива C ++ std :: list, который был ранее выделен оператором new?

Question

Я пытался реализовать некоторую проблему, связанную с графиком.Чтобы представить график, я использовал список смежности, используя std::list, что-то вроде этого,

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

, где V - общее количество вершин.

, затем я взял все ребра (направленные) и сохраните их, используя функцию,

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

Итак, график выглядит следующим образом:

Теория графика

Все работает нормально, но яхочу добавить новую вершину.Я пытался изменить свой список adj, но я не могу этого сделать.Что я сделал, я делаю копию этого, затем удаляю adj и создаю новый adj с большим размером, и, наконец, копирую в него весь предыдущий список смежности.

Вот мой код:

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

Это работает правильно, но мне просто интересно, есть ли какой-нибудь умный способ сделать это, потому что каждый раз, когда я хочу добавить вершину, нужно много операций.

Iмного чего перепробовал, но не нашел подобного вопроса / ответа здесь.

Answer 1

Никогда не используйте new (за исключением sole : конструкторы класса с именем something_ptr).

То, что вы, вероятно, хотите, это что-то вроде

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()
    }
};