0

I'm trying to solve a question in which I'm required to create an array of vectors, scan their elements, and fetch an element given two numbers a and b describing its position in the array of vectors. The problem is that I'm not sure how to scan the elements correctly. Just one vector is taking up all of the elements.

-----------------

If you want me to further clarify the problem, see below:

The question: https://www.hackerrank.com/challenges/variable-sized-arrays/problem?h_r=next-challenge&h_v=zen&h_r=next-challenge&h_v=zen&h_r=next-challenge&h_v=zen&h_r=next-challenge&h_v=zen&h_r=next-challenge&h_v=zen&h_r=next-challenge&h_v=zen&h_r=next-challenge&h_v=zen.

The code I wrote (throwing a seg fault):

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int n, q;
    cin >> n >> q;
    vector<int> v[n];

    int temp;
    for (int i=0; i<n; i++) {
        while (cin >> temp) {
            v[i].push_back(temp);
            // cout << v[i].size << endl;
            // increase in size would indicate that the element
            // got inserted properly
        }
    }

    int a, b;
    for (int j=0; j<q; j++) {
        cin >> a >> b;
        cout << v[a].at(b) << endl;
    } 

    return 0;
}

I tried commenting out code to see which line is at fault, and its this one: cout << v[a].at(b) << endl;. I'm guessing that it's a case of accessing elements that are out of bounds. This brings me to the conclusion to that the elements are not being scanned properly. What I think is that the array of vectors actually contains just one vector, which has all of the elements. So the input is not going into a number of vectors. It's just going into a single vector. How do I fix this?

I searched stack overflow for similar questions, and the closest one was this: Create an Array of vectors in C++. The answers there blame malloc for the segmentation fault, but mine doesn't even use malloc lol, so that's clearly not the culprit in my case. They also suggest using a vector of vectors, which is probably a better solution, but I want to find out what's wrong with my code. Also, vectors tend to waste memory in the form of empty cells, so there's that.

-----------------

Also, why does this line throw a compilation error: // cout << v[i].size << endl;

Anurag Baundwal
  • 128
  • 1
  • 10
  • Are you sure that `a` is less than `n`? – Yksisarvinen May 06 '20 at 13:53
  • "Also, vectors tend to waste memory in the form of empty cells, so there's that." What? Where did you hear that? `std::vector` is contiguous array, so there are no empty cells. Now, `std::vector>` will suffer from caching issues, but you may not even notice that. – Yksisarvinen May 06 '20 at 13:53
  • 1
    compilation error: `std::vector::size` is a function and must be called with brackets `v[i].size()` – stefaanv May 06 '20 at 13:55
  • @Yksisarvinen A vector is sort of like an array that gets reallocated with double the memory whenever it gets full, right? In doing this, many cells remain empty and the size of the vector is not always equal to its capacity. So some memory is being wasted, right? – Anurag Baundwal May 06 '20 at 14:58
  • 2
    To avoid the wasted memory, `std::vector` has `reserve()` and `shrink_to_fit()` but you shouldn't care unless you're working with a lot of big long living containers. – stefaanv May 06 '20 at 15:12

1 Answers1

1

First a remark: vector<int> v[n]; isn't standard C++, because only arrays with a fixed size on compile time are supported, so avoid it in production code. It does work with most compilers, so I'm just remarking.

For filling in your vectors, you forgot to read the size of the vector to fill.

To avoid 'out of bound' accesses, check that a is smaller than n and that 'b' is smaller than v[a].size() before actually accessing the vector.

stefaanv
  • 14,072
  • 2
  • 31
  • 53
  • Actually, the variable sized array what the lesson is about is not standard C++. A vector of vectors is indeed the best option. – stefaanv May 06 '20 at 14:11
  • Ah, that little k at the beginning of each line. I didn't see it. Thank you! Just out of curiosity, if k wasn't provided, is there any way to keep taking input until the line ends? – Anurag Baundwal May 06 '20 at 15:05
  • The input line `3 1 5 4` is 3 elements: 1, 5 and 4. So you know that vector should contain these elements. Now, you just put all the elements in the first vector (including the coordinates to access your vectors) and then there is nothing more to read. To read a line, first use `std::getline()`, but you don't need it because with well formed input, you know how many elements to read. (I see you figured it out before I submitted my reply) – stefaanv May 06 '20 at 15:06