英文:
Runtime error while removing vector elements
问题
[问题已解决,感谢您的回答]
我有一个已排序的向量v
和一个向量num
,这是我如何删除向量v
中的元素的方式:
vector<int> v;
vector<int> num;
// 获取输入
// 举个例子: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]); // 添加num "v"的最大元素
v.erase(v.begin() + v.size() - 1); // 删除该元素
while (v.size() > 0) {
num.push_back(v.back()); // 添加num "v"的最大元素
v.erase(v.begin() + v.size() - 1); // 删除该元素
for (int i = 0; i < num.size() - 1; i++) // 检查除了最后添加的元素外的所有num元素
{
int ggcd = __gcd(num[num.size() - 1], num[i]);
int fnd = findv(v, ggcd); // 查找最大元素和num的元素i的GCD
v.erase(v.begin() + fnd); // 删除
fnd = findv(v, ggcd); // 再次重复一次
v.erase(v.begin() + fnd);
}
}
其中函数findv(vector<int> v, int x)
是一个通过二分查找找到不小于x
的最小元素的函数:
int findv(const vector<int>& v, int x) // 简单地找到
{
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;
}
在开始时,向量v的大小始终是某个n的平方(这里是4),因此在while/for循环中向量大小永远不会变为0。
运行时错误出现在for
循环中的v.erase(v.begin() + fnd)
,因为当我删除它们时,没有运行时错误,而在while/for之前的v.erase(v.begin() + v.size() - 1)
正常工作。
在我发现问题出在for
中删除元素时,我用v.erase(v.begin() + 0)
替换它们,以查看问题是否出在findv
函数中。但这仍然给我一个运行时错误,我尝试用许多其他数字替换它,包括size-1
等,但仍然出现运行时错误。我在互联网上进行了大量搜索,甚至尝试更改从v中删除元素的方式,但它们都出现其他错误/不符合我的要求。例如,这个:
v.erase(remove(v.begin(), v.end(), __gcd(num[sz(num) - 1], num[i])), v.end());
按值删除,但删除所有该值的元素,这不是我想要的。我尝试了这个:
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);
但这个也给我一个运行时错误。
这些元素在while循环中不会用尽,因为n^2 + 2*n + 1 = (n+1)^2,这对于另一个n也成立。这可以通过数学归纳法证明。
顺便说一下,如果您想知道我在代码中确切在做什么,这是一个解决这个问题的方案:https://codeforces.com/problemset/problem/582/A,这是我的完整代码版本:https://ideone.com/suu0GG。
英文:
[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
答案1
得分: 0
我没有确切找出我的代码中到底出了什么问题,但似乎我的问题不在于擦除部分,其他方面出了问题。我不知道为什么删除擦除部分后没有运行时错误,也许是编译器错误。以下是我所做的更改以使其正常工作:
- 用手工制作的函数替换了'__gcd'函数
- 替换了不必要复杂的部分,如'v[v.size()-1]',用更简单和更清晰的部分,如'v.back()',以避免不必要的错误
- 通过const引用将向量传递给'findv'函数,以避免复制
- 我还尝试更改了我的编译器,以防问题不是源自我的代码,但奇怪的是,不同编译器的反应也不同
- 在修复这些问题后,我使用了替代代码,与我最初编写的代码一样完美运行(使用迭代器的代码)
还有一个用户在这里问我为什么在存在'lowerband'和'upperband'的情况下我还使用了手工制作的函数'findv',这对我的代码来说是一个有效的问题。(我有我的原因,但我只是一般性地说一下。)
英文:
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)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论