Inserting elements into 2D vector

Question

so I'm creating a class that implements an adjacency list. Currently in my class definition I initialized two vectors:

vector<vector<int>> adjList;
vector<int> neighbors;

and I declared two functions that I plan to use to make it:

bool constructAdjList();
bool insertIntoAdjList(int, int);

It's getting difficult wrapping my head around 2D vectors. I understand that it is essentially a vector of vectors, but I'm confused about how to insert a new value into one of the "subvectors". For example, I am able to create an adjacency list in createAdjList that is empty with the following loop:

for (int i = 0; i < numOfValues; i++){
    neighbors.push_back(0);
    adjList.push_back(neighbors);
    neighbors.clear();
}

But how can I say, push_back the value 5 to the 4th vector in adjList, which would be represented in my insertIntoAdjList function as

insertIntoAdjList(4, 5);

I know I can access a specific value in a 2D vector by saying adjList[4][1], but how can I push one onto it?

Thanks!

Triglyceride

I don't get it, can't you do this: adjList[4][1] = 987 ? – Geographer

That works if I already have a value in the [4][1] position, but if I want to actually push a value onto the end of vector 4, I have to push_back somehow right? – Triglyceride

I think a std::unordered_map<int, std::unordered_map<int,int>> may serve you better. just my opinion. – Anastos

Then do this adjList[4].push_back() – Geographer

Answer 1

To push on the vector that is an element of another vector, you simply do this

adjList[x].push_back();

Geographer

Oh wow, I didn't know you could specify only one of the coordinates in the 2D vector. That makes it a lot easier, thank you! – Triglyceride

@Mardo I think it's important to understand, that adjList[x] returns a reference to the vector that is stored at position x. So, adjList[x][y] is the same as (adjList[x])[y] and means: First, give me a reference to the vector at position x in adjList (let's call it V), then give me a reference to the integer at position y in V. – Stotinka

Answer 2

If initially you do not have any values in the vector - You can push values into one vector and then push this vector into the 2D vector. For example:

  vector< vector<int> > vt1;
  vector<int> vt2;

  vt2.push_back(value);
  vt1.push_back(vt2);

If your vector is already populated then -

vt1[index].push_back(value);

Forgotten

Answer 3

A couple of notes here.

Your loop can be significantly shortened just be using the constructors of your two members:

vector<int> neighbors(1, 0); // set to length 1, value is zero
vector<vector<int>> adjList(numOfValues,neighbors); // "outer" vector is numOfValues long
.                                                   // each row is a *COPY* of neighbor

If you can't do this at construction time (maybe numOfValues isn't known yet), then there's still a better loop phrasing we can use:

// neighbors object can be reused
neighbors.clear(0);
neighbors.push_back(0);
adjList.reserve(numOfValues); // reserving memory ahead of time will prevent allocations
for (int i = 0; i < numOfValues; i++){
    adjList.push_back(neighbors); // push_back is by *COPY*
}

In your example, by using clear and push_back to essentially build the same vector every loop iteration, you are risking an allocation and deallocation each iteration. In practice, most implementations won't do this, but if we can both shorten and potentially make things more efficient, we may as well.

Lastly, if the number of neighbors is relatively small and similar row to row (for instance a finite elements code with tetrahedral elements, where each element connects to ~5 others), then as others have suggested you may be better off with a different structure than vector-of-vector. For instance, a single vector that is logically organized such that a new "row" begins every N elements.

Francisfrancisca

is that snippet inside a for loop? – Marcellamarcelle