Multiple elements at one vector index

Question

I was looking at a basic implementation of a graph with an adjacency list, and I noticed to represent the addition of an edge between two nodes, push_back could be used multiple times on a single index. I tried it myself with this:

int V = 3;
vector<int> vec[V];
vec[0].push_back(23);
vec[0].push_back(24);
vec[1].push_back(52);
vec[2].push_back(4);
vec[2].push_back(-1);

I printed them out and it all worked fine:

for(int i=0; i<V; ++i) {
    for(auto p : vec[i])
        cout << p << ' ';
    cout << '\n';
}

How come multiple p can come from the same index i? Am I over/under-thinking something and this behavior should be expected? I thought that a vector was just an array that could change size, not that one of its positions could hold many elements.

`vec[V]` is *array of vector*. So each element is a `vector`. And btw variable-length-array is non-standard. — 김선달, Jul 08 '21 at 02:24
You have an array of the vectors. In your code sample, you're pushing two elements into the first vector, one into the second, and two more into the third. Each element is being pushed to a new entry at the back of the vector, not to the same initial, positional element. In your printout, you then iterate across the three vectors, and print all the elements in each. Did I understand your question correctly? — cyberbisson, Jul 08 '21 at 02:28
@김선달 what do you mean by "variable length array is nonstandard"? — cyberbisson, Jul 08 '21 at 02:30
@cyberbisson https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard — 김선달, Jul 08 '21 at 02:34
@cyberbisson See [here](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard) for example. `int V = 3; int foo[V];` is a nonstandard extension of C++ — Nathan Pierson, Jul 08 '21 at 02:34
@김선달 & Nathan Pierson: ah, true! I glossed over it, thinking it was intended to be constexpr based on the capitalization. Thanks. — cyberbisson, Jul 08 '21 at 02:44
While none of these are duplicate questions, their answers might be illuminating: [A:How to print vector's data](https://stackoverflow.com/a/13800773), [C++ vector::begin not working](https://stackoverflow.com/questions/51729585/c-vectorbegin-not-working), and [array of vectors or vector of arrays?](https://stackoverflow.com/questions/35501439/array-of-vectors-or-vector-of-arrays) — JaMiT, Jul 08 '21 at 02:45
@OP `vector vec[V];` -- I guess you do not fully realize what the purpose of a vector is. It is to have a dynamic array of `N` items,. So why are you not using vector here fully? Use `std::vector> vec(V);` You now have a vector of `V` vectors. — PaulMcKenzie, Jul 08 '21 at 03:25

score 0 · Answer 1 · answered Jul 08 '21 at 03:58

Well, you might be misunderstanding the workings of the output code

for(int i=0; i<V; ++i) { // for each vector element in the array vec[3]
    for(auto p : vec[i]) // for each element in the vector. 
        cout << p << ' ';
    cout << '\n';
}

Each p is a vector, holding many elements. vec is an array holding 3 elements.

If you have lots of edges this might be an optimization, otherwise you can just do a

struct edge{ int from; int to; double weight; };
std::vector<edge> E;

This will simplify your implementation of algorithms.

Multiple elements at one vector index

1 Answers1