Manipulating listint in c ++

0

My Class

class Grafo{
int numeroVertice;
list<int> *arestas;

public:
Grafo(int vertices);
int addVertice(int quantidade);
void addAresta(int verticeOrigem, int verticeDestino);
void remAresta(int verticeOrigem, int verticeDestino);
void verificaAresta(int verticeOrigem, int verticeDestino);
int grauVertice(int vertice);
void percorreLista(int v);
bool existeLigacao(int origem, int destino);
};

My builder:

Grafo::Grafo(int vertices){
 this->numeroVertice = vertices;
 arestas = new list<int>[vertices];
}

My problem:

int Grafo::addVertice(int quantidade){
arestas = new list<int>[vertices];
return this->numeroVertice = this->numeroVertice + quantidade;

}

How to make when this addVertice method, increase the amount of allocations to my list 'edges'?

I was thinking of using something like:

  it=std::set_union (first, first+5, second, second+5, v.begin());
  v.resize(it-v.begin());

But I'm using a pointer there, I lose, anyone willingly there? The final goal is the list that has 5 allocations, could be increased to 10 for example.

    
asked by anonymous 23.09.2016 / 21:26

1 answer

1

It seems like you are implementing a graph through a list of adjacencies. My suggestion is, instead of using dynamic allocation for the list, use a std::vector . And for the list of edges of each vertex, I also suggest using std::vector instead of std::list . It would look something like this, more or less:

class Grafo {
    using ListaAdjacencias = std::vector<int>;
    std::vector<ListaAdjacencias> arestas;
}

In this way, you can control the number of vertices by size() of std::vector . All memory allocation and release is abstracted and you can focus on the actual problem you want to solve.

Your builder would look simpler:

Grafo::Grafo(int vertices) : arestas(vertices) {
}

To add a new vertex simply add a new item to the list:

int addVertice() {
    arestas.push_back( {} ); 
    return arestas.size() - 1; //Retorna o índice do novo vértice;
}

It is not necessary to set the number of edges of that vertex in advance. Let the container classes take care of this for you. To add a new edge would suffice:

void addAresta(int verticeOrigem, int verticeDestino) {
    arestas[verticeOrigem].push_back(verticeDestino);
}
    
27.09.2016 / 14:47