CODEWITHSUNDEEP
c++vectorstlpush-back
sol0invictus
sol0invictus

Reputation: 23

Operation of push_back on an element of Vector (C++)

I am a Python programmer trying to develop C++ proficiency. I have a silly question about vectors.

Suppose I have a vector like this

vector<int> adj;

Assume it contains some values. What does this operation do ?

adj[v].push_back(w)

Does it create vector of vectors ? How is it different from having a,

vector<vector<int>> adj

to begin with ?

Edit:: Associated code is a simple BFS on graph which compiles and runs perfectly.

class Graph 
{ 
    int V;  
    vector<int> *adj;    
public: 
    Graph(int V); 
    void addEdge(int v, int w);   
    void BFS(int s);   
}; 

Graph::Graph(int V) 
{ 
    this->V = V; 
    adj = new vector<int>[V]; 
} 

void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w); // Add w to v’s list. 
}

The BFS function is in GeeksForGeeks

Upvotes: 2

Views: 1869

Answers (5)

Vlad from Moscow
Vlad from Moscow

Reputation: 310910

In the provided class definition there is no vector.

class Graph 
{ 
    int V;  
    list<int> *adj;    
public: 
    Graph(int V); 
    void addEdge(int v, int w);   
    void BFS(int s);   
};

There is declared a data member that has the type pointer to std::list<int>.

In the constructor of the class

Graph::Graph(int V) 
{ 
    this->V = V; 
    adj = new list<int>[V]; 
}

there is allocated dynamically an array of objects of the type std::list<int> and the address of the first element of the array is assigned to the data member adj.

Thus in this statement

adj[v].push_back(w);

there is selected the element of the array with the index v, adj[v], that represents an object of the type std::list<int> and to this list is appended the object w using the member function push_back of the class template std::list.

As for vectors then you indeed can declare a vector of vectors like

std::vector<std::vector<int>> v;

To use the subscript operator you have to create a required number of elements of the vector.

You can do it for example when the vector is declared.

std::vector<std::vector<int>> v( 10 );

This declaration declares a vector of vectors with 10 elements. Now you may use the subscript operator to add sub-vectors to the vector using the member function push_back.

Here is a demonstrative program.

#include <iostream>
#include <vector>

int main() 
{
    std::vector<std::vector<int>> v( 10 );

    for ( size_t i = 0; i < v.size(); i++ )
    {
        int value = 0;
        for ( size_t j = 0; j < i + 1; j++ )
        {
            v[i]. push_back( value++ );
        }
    }

    for ( const auto &sub_vec : v )
    {
        for ( const auto &item : sub_vec )
        {
            std::cout << item << ' ';
        }

        std::cout << '\n';
    }

    return 0;
}

Its output is

0 
0 1 
0 1 2 
0 1 2 3 
0 1 2 3 4 
0 1 2 3 4 5 
0 1 2 3 4 5 6 
0 1 2 3 4 5 6 7 
0 1 2 3 4 5 6 7 8 
0 1 2 3 4 5 6 7 8 9

Upvotes: 1

Amir Kirsh
Amir Kirsh

Reputation: 13752

In the code that you present, adj is created as a new list<int>[V]. Which is not exactly what you ask about (i.e. it is not a vector, neither a list, it is a dynamically allocated array of lists).

Then:

adj[v].push_back(w)

Means: get the v element in the array of lists (as v == index of the element to retrieve), it would be a list, then push_back into this list w.

Upvotes: 2

Jesper Juhl
Jesper Juhl

Reputation: 31447

The code you posted tries to call push_back on a element of a vector of ints. That makes no sense since a int is not an object with a push_back member function. That code won't compile.

Upvotes: 1

Abhishek Bhagate
Abhishek Bhagate

Reputation: 5766

You have a 1-dimensional array. You can only add 1 element per index. What you are implying by adj[v].push_back(w) is that you want to push element w at index v which is not possible since you declared the vector as

vector<int> adj;

To implement 2-d vector you need to define it as -

vector<vector<int> >adj;

On this your operation adj[v].push_back(w) would work if v is a valid index.

Upvotes: 0

Marshall Clow
Marshall Clow

Reputation: 16670

Assuming vector<int> adj:

adj[v].push_back(w) will call the operator[] on adj, which will return an int & (assuming v is some scalar). Then it will try to call push_back on an int & which will fail to compile.

Assuming vector<vector<int>> adj:

adj[v].push_back(w) will call the operator[] on adj, which will return an vector<int> & (assuming v is some scalar). Then it will call push_back on that vector<int> &, appending the value w to that particular vector.

Upvotes: 2

Related Questions