Search code examples
c++debuggingvectorruntime-errorbinary-search

Runtime error while removing vector elements


[problem solved, thx for answering] I have a sorted vector v and a vector num, this is how I delete elements in vector v:

vector <int> v; 
vector <int> num; 
//gets input
//for an example: v = {1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 6} 
//num.size() = 0 

num.push_back(v[v.size()-1]); //adds num "v"'s maximum element 
v.erase(v.begin()+v.size()-1); // removes that element 
while(v.size() > 0) {
    num.push_back(v.back()); //adds num "v"'s maximum element
    v.erase(v.begin()+v.size()-1); // removes that element
    for(int i = 0; i < num.size()-1; i++) // checkes all elements of num except the last one added 
    {
        int ggcd = __gcd(num[num.size()-1], num[i]); 
        int fnd = findv(v, ggcd); // finds GCD of maximum element and element i of num 
        v.erase(v.begin()+fnd); // removes
        fnd = findv(v, ggcd); //repeats one more time 
        v.erase(v.begin()+fnd);
    }
}

where function findv(vector<int> v, int x) is a function that finds the index of smallest element that is not less than x by binary search:

int findv(const vector<int>& v, int x) // simply, finds
{
    int l = 0, r = sz(v), mid; 
    while(r-l > 1)
    {
        mid = (l+r)/2; 
        if(v[mid] < x) l = mid; 
        else if(v[mid] > x) r = mid; 
        else return mid; 
    }
    return l; 
}

size of vector v in the start is always square of some n (4 here) so the vector size never reaches 0 in middle of the while. The runtime error is from the v.erase(v.begin()+fnd) in the for as when I delete them, there is no runtime error and the v.erase(v.begin()+v.size()-1)s before the while/for work perfectly

after I found out the problem is about erasing in the for, I replaced them with v.erase(v.begin()+0) to see if the problem is in function findv. but that also gave me a runtime error, I replaced it with many other numbers, size-1 and everything but still, there was a runtime error. I searched a lot in internet and even tried to change how I delete elements from v but they had other errors/didnt do what I want. for an example this:

v.erase(remove(v.begin(), v.end(), __gcd(num[sz(num)-1], num[i])), v.end());

deletes by value, but it deletes all elements of that value which isnt what I want. and tried this:

vector<int>::iterator it = find(v.begin(), v.end(), __gcd(num[sz(num)-1], num[i]));
int index = distance(v.begin(), it);
v.erase(v.begin()+index);
it = find(v.begin(), v.end(), __gcd(num[sz(num)-1], num[i]));
index = distance(v.begin(), it);
v.erase(v.begin()+index);

But this one also gave me a runtime error. the elements dont run out while in the while cause n^2 + 2*n + 1 = (n+1)^2 which is n^2 for another n. its provable by a mathematical induction. Btw, if u want to know what I am exactly doing in the code, its a solution for this problem: https://codeforces.com/problemset/problem/582/A and this is a full version of my code: https://ideone.com/suu0GG


Solution

  • I did not exactly find out what was actually wrong in my code but, seems like my problem was not about the erasing part and other things were wrong. I dont know why there was no runtime after removing the erase part, maybe it was a compiler error. these are things I changed to make it work:

    • replaced '__gcd' function with a handmade one
    • replaced unnecessarily complicated parts like 'v[v.size()-1]' with simpler and cleaner ones like 'v.back()' to avoid unwanted mistakes
    • passed vector to the 'findv' function by const reference to avoid copy
    • I also tried changing my compiler in case the problem isnt from me, and weirdly I faced different reactions from different compilers
    • the alternative code that I used instead of what I wrote first also works perfectly after fixing these (the one which works with iterator)

    also one user here asked me why did I use a hand made function 'findv' while lowerband and upperband exist and well that's a valid problem for my code. (I had reasons for it, but I am saying it generally)