Lendo um vetor C ++ por valor vs por referência

Question

Esta é uma questão fundamental do ponteiro, mas isso está me desconcertante por um tempo agora. Eu implementei um gráfico ponderado, usando C ++ map Como umaestrutura subjacente da seguinte maneira:

std::map<int, std::vector<Edge> > edgeList;

Este mapa contém o ID do nó (um int) como a chave e a lista de arestas neste nó usando um vector como um valor

Eu inicializei a lista de arestas para cada nó da seguinte forma:

for(int i = 0; i< n; i++){
        std::vector<Edge> vi;
        edgeList.insert(std::make_pair(i,vi)); // initialize with empty vector (at least, that's the intent)
    }

Agora, ao adicionar uma vantagem ao gráfico, quando tento recuperar a lista de arestas vector correspondente a cada nó da seguinte forma:

std::vector<Edge> vList = edgeList.at(v); // v is the node id here

um vazio vector O VLIST é devolvido, mesmo assim, adicionei as bordas a esse VLIST anteriormente.

Por outro lado,

std::vector<Edge> &vList = edgeList.at(v);

parece estar funcionando bem para o meu propósito. Alguém pode explicar por que a primeira implementação não funciona e a segunda?

Editar: o código para adicionar as bordas ao gráfico é o seguinte:

void Graph::addEdge(Edge e){

    // retrieve start and end node for this edge
    int v = e.either(); // returns either end of the edge
    int w = e.other(v);

    // retrieve edge lists for these nodes
    std::vector<Edge> vList = edgeList.at(v); // doesn't work
    std::vector<Edge> wList = edgeList.at(w); // doesn't work

    // add this edge to the list of edges
    vList.push_back(e);
    wList.push_back(e);
}

Answer 1

o std::map::at função retorna uma referência ao std::vector no índice dado. Quando você atribui isso a uma variável de não referência, você fará uma cópia do vetor. Quaisquer operações de inserção que você fizer estarão na cópia do vetor, que sai do escopo no final do método, enquanto o vetor que você pretendia ficar apenas no mapa e não é afetado.

Em vez disso, se você adicionar o &, então vList Realmente se tornará um pseudônimo do vetor real que é armazenado em seu mapa. Agora, quaisquer alterações feitas para vList são realmente feitos para o elemento de mapa. Se desejar, você pode considerar a referência como um ponteiro disfarçado. Nesse caso, você escreveria explicitamente

std::vector<Edge> *vList = &edgeList.at(v);

E não, por exemplo,

std::vector<Edge> *vList = new std::vector();
*vList = edgeList.at(v);

Na verdade, o exemplo a seguir demonstra o ponto mais claramente:

using namespace std;

int i = 0;

int& get_i()
{
    return i;
}

int main()
{
   cout << "i = " << i << ", &i = " << &i << endl;

   int j = get_i();
   j++;
   cout << "i = " << i << ", j = " << j << ", &j = " << &j << endl; 

   int& k = get_i();
   k++;
   cout << "i = " << i << ", k = " << k << ", &k = " << &k << endl; 

   return 0;
}

Answer 2

Quando você faz isso:

std::vector<Edge> vList = edgeList.at(v);

Você está criando um cópia de do vetor no mapa.

Quando você faz isso:

std::vector<Edge> &vList = edgeList.at(v);

Você está recebendo uma referência a esse vetor.

Se você adicionar elementos à cópia, eles não serão adicionados ao mapa (já que é apenas uma cópia e não terá mais relação com o original). Se você adicionar elementos à referência, ele será adicionado ao mapa, porque é o mesmo vetor.