Unable to access elements in a 2-D Vector

Question

I am trying to solve the following problem using C++ and I am facing an unusual error (in the sense that I am unable to access the elements in a 2-D Vector using indices whose values are stored in variables.)

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <utility>
#include <algorithm>

using namespace std;

int main()
{
    int tc; cin >> tc;
    while(tc--)
    {
        int n; cin >> n;
        
        vector<int> f(n+1, 0);
        for(int i=0; i<n; i++) cin >> f[i+1];
        f[0] = -1;

        vector<int> p(n+1, 0);
        for(int i=0; i<n; i++) cin >> p[i+1];
        p[0] = -1;

        vector<vector<int>> graph(n+1, vector<int>());
        map<int, vector<int>> levels;

        for(int i=1; i<n+1; i++) graph[p[i]].push_back(i);

        queue<pair<int, int>> Q;
        for(int i=0; i<graph[0].size(); i++) Q.push({graph[0][i], 0});

        while(!Q.empty())
        {
            int p = Q.front().first;
            int lv = Q.front().second;

            levels[lv].push_back(p);

            for(int i=0; i<graph[p].size(); i++) Q.push({graph[p][i], lv+1});
            Q.pop();
        }

        int x = levels.size() - 2;
        int ans = 0;

        while(x >= 0)
        {
            for(int k=0; k<levels[x].size(); k++)
            {
                int root = levels[x][k];
                // cout << root << '-'; // works
                // cout << graph[root].size() << ' '; // works
                // cout << graph[root][0] << ' '; // doesnt work

                // for(int i=1; i<graph[root].size(); i++)
                // {
                //     mn = min(mn, f[graph[root][i]]);
                //     tmp += f[graph[root][i]];
                // }

                // tmp -= mn;
                // ans += tmp;

                // if(f[root] < mn) f[root] = mn;
            }
            x -= 1;
            cout << endl;
        }

        // for(int i=0; i<levels[0].size(); i++)
        //     ans += levels[0][i];

        // cout << ans << '\n';
    }
}

I am specifically getting error at lines 54, 55 and 56. (which I have commented out above).

cout << root << '-'; // works
cout << graph[root].size() << ' '; // works
cout << graph[root][0] << ' '; // doesnt work

The first 2 statements seem to work. However the 3rd statement doesn't seem to give me any output when I try accessing an element. I have also tried to use cout << graph[3][0] in place of cout << graph[root][0] when root takes the value of 3. And the former seems to work.

I wanted to know what could be the reason for graph[root][0] to not show any output, although when I use constants such as graph[3][0], it seems to work.

Logic aside, what could be the syntax error in my code ?

Which line is 54, 55, and 56? -- `cout << graph[root][0] << ' ';` --> `cout << graph.at(root).at(0) << ' '`. What happens if you did that? Do you get an exception thrown? — PaulMcKenzie, Aug 11 '22 at 14:23
*what could be the syntax error in my code ?* -- If there is a syntax error, then the compiler would have emitted an error. If so, you should post the exact error message. If it isn't a syntax error, then it is indeed a logic error, which you say we should "set aside". — PaulMcKenzie, Aug 11 '22 at 14:26
@PaulMcKenzie I have written those lines separately below. Upon uncommenting, lines 54 and 55 work fine, however Line 56, `cout << graph[root][0]` does not work (does not give any output. It does not throw any kind of exception as such. — spookymath, Aug 11 '22 at 14:30
Did you change the code to what I stated, and that is to use the `at()` function? The `at()` is guaranteed to throw an exception on boundary errors -- using `[]` to access elements in a vector is not guaranteed to throw any exception if you go out-of-bounds. — PaulMcKenzie, Aug 11 '22 at 14:31
@PaulMcKenzie yes, the problem lies in my logic when implementing it, apologies. It isn't a syntax error. The compiler does not throw any error message, — spookymath, Aug 11 '22 at 14:33
The other issue is - we don't have the test data. If you have test data that duplicates the issue, you should put it directly into the variables themselves instead of `cin` statements. — PaulMcKenzie, Aug 11 '22 at 14:34
@PaulMcKenzie when i change the code to the one you stated, it throws an error. The error says - terminate called after throwing an instance of 'std::out_of_range' what(): vector::_M_range_check: __n (which is 0) >= this->size() (which is 0) — spookymath, Aug 11 '22 at 14:35
Well, that's the issue -- you are going out-of-bounds. You are accessing element 0 of an empty vector. Time to go back and redo your plan. Using `[]` to access vector elements does not guarantee anything if you go out-of-bounds. The code could have crashed right there, instead of giving any output. Using `at()` it checks the index to ensure it is in bounds, and if not, throws the `std::out_of_range` exception. — PaulMcKenzie, Aug 11 '22 at 14:36
[Does this help?](https://stackoverflow.com/questions/9376049/vectorat-vs-vectoroperator). The top answer details the difference between `at()` and `[]`. — PaulMcKenzie, Aug 11 '22 at 14:51
@PaulMcKenzie the problem indeed was accessing elements of an empty vector, when I put a condition to proceed further only if vectors aren't empty, the code does give me a result. — spookymath, Aug 11 '22 at 14:54
Always run code under `valgrind` and fix all problems reported there. If `valgrind` spots errors, then further debugging makes no sense. This would have revealed the accesses beyond the vector’s end. — Andrej Podzimek, Aug 11 '22 at 15:42

Unable to access elements in a 2-D Vector

0 Answers0