运行时移除向量元素时发生错误

huangapple go评论76阅读模式
英文:

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 &lt;int&gt; v; 
vector &lt;int&gt; 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 &quot;v&quot;&#39;s maximum element 
v.erase(v.begin()+v.size()-1); // removes that element 
while(v.size() &gt; 0) {
	num.push_back(v.back()); //adds num &quot;v&quot;&#39;s maximum element
	v.erase(v.begin()+v.size()-1); // removes that element
	for(int i = 0; i &lt; 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&lt;int&gt; 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&lt;int&gt;&amp; v, int x) // simply, finds
{
	int l = 0, r = sz(v), mid; 
	while(r-l &gt; 1)
	{
		mid = (l+r)/2; 
		if(v[mid] &lt; x) l = mid; 
		else if(v[mid] &gt; 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&lt;int&gt;::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)

huangapple
  • 本文由 发表于 2023年6月26日 13:12:33
  • 转载请务必保留本文链接:https://go.coder-hub.com/76553673.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定