Understanding vector implementation

[Student555]

// A simple representation of graph using STL
#include <vector>
#include <iostream>
using namespace std;

// A utility function to add an edge in an
// undirected graph.
void addEdge(vector<int>  adj[], int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);

}

// A utility function to print the adjacency list
// representation of graph
void printGraph(vector<int> adj[], int V)
{
    for (int v = 0; v < V; ++v)
    {
        cout << "\n Adjacency list of vertex "
             << v << "\n head ";
        for (auto x : adj[v])
           cout <<  "-> " << x;
        printf("\n");
    }
}

// Driver code
int main()
{
    const int V = 5;
    vector<int> adj[V];
    addEdge(adj, 0, 1);
    addEdge(adj, 0, 4);
    addEdge(adj, 1, 2);
    addEdge(adj, 1, 3);
    addEdge(adj, 1, 4);
    addEdge(adj, 2, 3);
    addEdge(adj, 3, 4);

    printGraph(adj, V);




	system("Pause");
    return 0;
}

The above implementation is used in an implementation of a undirected graph. The main point of confusion for me is the vector[]. Specifically how it is adding elements and outputting. The vector in this case looks like its an array of linked lists. But my understanding of vectors is that they are essentially just dynamic arrays in contiguous memory.

Its my understanding that passing by value sends a copy to a local function. In this case, when adj is passed to addEdge 5 new contiguous memory locations (20 bytes in total) are allocated. These newly allocated memory blocks will retain the same values that the original adj had from the main function, but will be located at different memory addresses. If addEdge processes/manipulates data, the data at the newly allocated addresses will change. But the data from the original address (in main) will stay the same. Once execution ends at addEdge, and returns to main, adj will be referring to its original addresses. This is of course different from passing by reference or pointer, where data from the original addresses can be modified (Unless const is used).

adj in printGraph gets iterated through, and it behaves like an array of linked lists. Where the first element 0 outputs 0: 1, 4 1: 2, 3, 4
etc...

To make a long story short, what is going on here?

[lastchance]

You are passing a pointer to an ordinary array (of vector<int>). No copy is made and it does not allocate 5 new memory locations. Each element of the array, a vector, and hence expansible, may grow, but the pointer to its "start" does not change. Ideally, if implemented like this, you would also have passed the size of the array (here, 5) so that you could take action to avoid exceeding array bounds.

It would have been different if you had been passing a vector <vector<int> >, in which case you would have had to pass by reference to make the program work.

Fundamentally, the program is mixing "normal" fixed-size arrays with expansible vector arrays.

[Student555]

@lastchance, thanks for the explanation