Variable sized arrays without using vector !

[sail456852]

//https://www.hackerrank.com/challenges/variable-sized-arrays //original challenge
//How should I avoid memory leak ,just delete the pointers declared by new keyword ?
//Any better hint for this challenge ? instead of using int *p = new int strategy
//I can't use vector here ,because the requirements

@kbw Thanks ,My own class idea is good ,but it's harder than simply implementing the code in main ,besides the algorithm ,I have to think about parameters and the access privilege and so many things ,
@dhayden ,Thank you , I managed to find many bugs including this one you mentioned this morning ,I think I got lost when coding yesterday .

*update:
my code was so buggy ,so I deleted it ,I can't stand it so I start writing new one now

my question is : is there any way other than using new keyword can build a variable sized array ?
There are only two ways coming to my mind now :
1.vector which is not allowed
2.using new keyword to allocate raw memory ,which is prone to bugs I guess.
3.What about the third way ?
4. Can someone here demonstrate a sample solution to this challenge ?

[kbw]

I think you're expected to write your own vector class rather than embed the code in main. That's why you can't use any other header files.

EDIT: I read the question, and it doesn't make any sense to me.

[Chervil]

I think you are supposed to make your own variable-sized arrays, rather than relying upon a non-standard compiler extension.

Lines 10, 11 and 29 all give a compiler error because N is not a compile-time constant.

[dhayden]

Line 6 points p at a single integer. Line 21 increments p, which causes it to point to whatever happens to come after that integer.

Lines 17-19 are wrong:

            int count = 1;
            count++ ;  // count is now 2
            Size[i] += count ;  // same as Size[i] += 2; 

In the lines that contain the data, the first number tells how many additional numbers are on the line. You don't do anything special with this number when clearly you need to.

I think you're getting lost in the details. rewrite the code and start with comments that describe each step. Then fill in the code under the comments:

// read N and Q
// Allocate N arrays
// for each N
    // Read k
    // allocate array of k numbers
    // for 1 to k
    // read number and store in array
// for each Q
    // read a and b
    // print array[a][b] 

[sail456852]

#include<iostream>

using namespace std;
int main()
{
    int *p = new int ;
    int temp ;
    int N ,Q ;
    cin >> N >> Q;
    int* BP[N-1];
    int Size[N-1] ;
    for(int AN = 0; AN < N ; AN++)
    {
        BP[AN] = p ;  //storing the base pointer for each row which has been inputted .
        Size[AN] = 0 ; //storing the size of each row ,e.g. input 1,9,9,1,6 then the size is 5

        while(cin >> temp)
        {

            Size[AN]++ ;      //counting the max size of this row
            *p = temp ;       //storing inputting integers on the raw memory
            p++ ;             //moving the pointer ,so the data doesn't overlap on each other .

            if(cin.get() == '\n')  //detecting if enter key is triggered .
            {
                break;
            }
        }
    }

    int Display[Q-1];           //storing the searching results
    int row[Q - 1],No[Q - 1] ;  //for storing the Query a,b combinations .

    for(int i=0; i < Q ; i++)  //the query rows .
    {

        cin >> row[i] >> No[i] ; //storing arbitrary row No.in row and its corresponding search No.
        //calculating parts:
        if(No[i] == (Size[row[i]]-1))
            Display[row[i]] = *BP[row[i]];   //pointers operation case 1
        else
            Display[row[i]] = *(BP[row[i]]+ No[i] +1); //case 2
    }

     //displaying the results
    for(int i=0; i < Q ; i++)
    {
        cout << Display[row[i]] << endl ;
    }
  delete p ;
}

Still full of bugs . but can pass the sample input now . can't pass the test .
I'd like to share my idea on this problem with you guys ,
I don't think they should put it in the category of easy ,it really frustrates me ..
but I still like what I do..
I have to admit this code is kind of complex ,overwhelming complexity ..I got lost again :P

[cire]

Line 6 allocates memory for a single int.
Lines 10 and 11 are illegal in C++ (as well as allocating the wrong number of elements.)
Lines 21 and 22 result in undefined behavior.
Lines 31 and 32 are illegal in C++ and you don't need to store any of that information anyway.

Here's one way to do the thing by defining a not-so-smart smart pointer (and note that I don't feel constrained to use variable names like N and Q):

#include <iostream>
using namespace std;

int main()
{
    void do_work();
    do_work();
}

template <typename T>
struct v_ptr
{
    v_ptr(const v_ptr&) = delete;
    void operator=(const v_ptr&) = delete;

    v_ptr() : _data(nullptr) {}
    v_ptr(std::size_t size) : _data(new T[size]) {}
    ~v_ptr() { delete []_data; }

    void resize(std::size_t sz) { delete [] _data; _data = new T[sz]; }
    T& operator[](std::size_t index) { return _data[index]; }

private:
    T* _data;
};

void do_work()
{
    std::size_t n_sequences;
    std::size_t n_queries;

    std::cin >> n_sequences >> n_queries;
    v_ptr<v_ptr<unsigned>> seq(n_sequences);

    for (std::size_t i = 0; i < n_sequences; ++i)
    {
        std::size_t sz;
        std::cin >> sz;
        seq[i].resize(sz);

        for (std::size_t j = 0; j < sz; ++j)
            std::cin >> seq[i][j];
    }

    for (std::size_t i = 0; i < n_queries; ++i)
    {
        std::size_t a, b;
        std::cin >> a >> b;
        std::cout << seq[a][b] << '\n';
    }
}

[Chervil]

sail456852 wrote:

can't pass the test

Almost certainly this is because your code uses non-legal variable-length arrays. That is subverting the whole point of the challenge - it is no challenge at all.

So the first thing to do is to set your compiler to follow the standards. If using g++ add this to the compiler options:

-std=c++11 -Wextra  -Wall -pedantic-errors

Then the compiler will issue messages something like this.

10	16	test.cpp	[Error] ISO C++ forbids variable length array 'BP' [-Wvla]
11	17	test.cpp	[Error] ISO C++ forbids variable length array 'Size' [-Wvla]
31	20	test.cpp	[Error] ISO C++ forbids variable length array 'Display' [-Wvla]
32	18	test.cpp	[Error] ISO C++ forbids variable length array 'row' [-Wvla]
32	28	test.cpp	[Error] ISO C++ forbids variable length array 'No' [-Wvla]

Only then will you be ready to begin the challenge.

[Chervil]

There are some useful comments and code examples on the discussion page:
https://www.hackerrank.com/challenges/variable-sized-arrays/forum

[dhayden]

Allocate an array of k ints using new int[k]. Delete it with delete[].
Allocate an array of N pointers to ints using new int *[N]. Delete it with delete[].

#include <iostream>
using std::cin;
using std::cout;


int
main()
{
    int N, Q;

    // Read N and Q
    cin >> N >> Q;

    // Allocate array of N pointers
    int ** arr = new int *[N];

    // Read N sequences
    for (int i=0; i<N; ++i) {
        int k;

        // Read k and set arr[i] to array of k ints
        cin >> k;
        arr[i] = new int[k];

        // read k ints
        for (int j = 0; j < k; ++j) {
            cin >> arr[i][j];
        }
    }

    // Read and process the queries
    for (int i = 0; i < Q; ++i) {
        int a,b;
        cin >> a >> b;
        cout << arr[a][b] << '\n';
    }

    // clear up
    for (int i = 0; i < N; ++i) {
        delete [] arr[i];
    }
    delete[] arr;

    return 0;
}

[sail456852]

@dhayden
Thanks for offering me a good example ,yours is the most popular solution to this problem,I finally understand how it works now :)
@cire
Gave me a new view of how to implement a user defined "vector" .That's absolutely cool ,but I spent a week trying to understand it .and failed ...
I understand you want to create something like vector<vector<int>> multidimensional container to store the data . but why

Line 33 v_ptr<v_ptr<unsigned>> seq(n_sequences);

why use unsigned instead of std::size_t
why

Line 13 v_ptr(const v_ptr&) = delete;
Line 14 void operator=(const v_ptr&) = delete;

have to not be called or defined , I Googled the delete keyword .
So complex , but It did work ,:) thanks for reviewing my problem

update:
Thanks everyone :) , you really helped me out , I think I need time to summarize what I've learnt from this problem .:) have a good day !

[cire]

why use unsigned instead of std::size_t

Because I was dealing with an unsigned value and not a size.

have to not be called or defined , I Googled the delete keyword .

I did not wish to provide copying functionality, and the defaulted version would've been incorrect. = delete ensured anyone playing with the code would have to go out of his or her way to screw things up in regards to copying.

[ne555]

#include <iostream>
using namespace std;

int main()
{
    void do_work();
    do_work();
}

#include <vector>
void do_work(){
   //...
   std::vector<std::vector<unsigned> > seq(n_sequences);
   //...
}