Manipulating list<int> in c++

Asked

Viewed 332 times

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 do for when this addVertice method, increase the amount of allocations to my 'edge' list'?

I was thinking about using something like:

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

It’s just that I’m using a pointer, and then I get lost, someone who’s willing to do it? The ultimate goal is the list that has 5 allocations, could be increased to 10 for example.

c++ pointer list
  • 1

    It wouldn’t just be the case to use one push_back()?

  • I think this here edges = new list<int>[vertices]; is creating an array of lists, is that what you want ? Or did you want to create a list with n vertices ? In this case I think it should be edges = new list<int>(vertices);

1 answer

1


It seems that 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;
}

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 real problem you want to solve.

Your builder would be simpler:

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

To add a new vertex just 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 define beforehand the number of edges of that vertex. Let the container classes take care of this for you. Adding a new edge would be enough:

void addAresta(int verticeOrigem, int verticeDestino) {
    arestas[verticeOrigem].push_back(verticeDestino);
}

Browser other questions tagged c++ pointer list

You are not signed in. Login or sign up in order to post.