为什么在合并排序中出现向量下标超出范围错误?
题
void merge(vector<int> dst,vector<int> first,vector<int> second)
{
int i=0,j=0;
while(i<first.size()&&j<second.size())
{
if(first[i]<second[j])
{
dst.push_back(first[i]);
i++;
}
else
{
dst.push_back(second[j]);
j++;
}
}
while(i<first.size()
dst.push_back(first[i++]);
while(j<second.size())
dst.push_back(second[j++]);
}
void mergeSort(vector<int> &a)
{
size_t sz = a.size();
cin.get();
if(sz>1)
{
vector<int> first(&a[0],&a[sz/2]);
vector<int> second(&a[(sz/2)+1],&a[sz-1]);
mergeSort(first);
mergeSort(second);
merge(a,first,second);
}
}
void MergeSort(int* a,size_t size)
{
vector<int> s(&a[0],&a[size-1]);
mergeSort(s);
}
有人可以帮我看看这段代码有什么问题吗?我收到向量下标超出范围错误。
解决方案
您的子向量指定不正确。
请记住,迭代器指定从开始到结束。
所以这会错过向量中的中间元素和最后一个元素。
对于长度为 2 的非常短的向量也是未定义的
vector<int> first(&a[0],&a[sz/2]);
vector<int> second(&a[(sz/2)+1],&a[sz-1]);
想象一下,如果 a 是向量 { A, B, C, D}
first: {A,B} 0 -> 2 (where 2 is one past the end so index 0 and 1_
second: {} 3 -> 3 (Since one past the end equals the start it is empty}
或者尝试更大的向量:{ A、B、C、D、E、F、G、H、I}
first: {A, B, C, D} 0 -> 4 (4 is one past the end so index 0,1,2,3)
second: {F, G, H} 5 -> 8 (8 is one past the end so index 5,6,7)
或者尝试使用较小的向量:{A,B}
first: {A} 0 -> 1
second: {BANG} 2 -> 1
应该:
int* st = &a[0];
// Using pointer arithmatic because it was too late at night
// to work out if &a[sz] is actually legal or not.
vector<int> first (st, st+sz/2]); // sz/2 Is one past the end.
vector<int> second(st+sz/2, st+sz ); // First element is sz/2
// one past the end is sz
向量传递给 merge()。dst 参数必须通过引用传递,因为它是一个输出参数。但还要注意,第一个和第二个参数是 const,因此我们可以通过 const 引用传递(以避免复制步骤)。
void merge(vector<int>& dst,vector<int> const& first,vector<int> const& second)
还有合并功能:
正在将值推入 dst。但从传入的数据来看 dst 已经满了。因此,在进行合并之前,必须清除目的地。
mergeSort(first);
mergeSort(second);
// Must clear a before we start pushing stuff into.
a.clear(); // Add this line.
merge(a,first,second);
其他提示
如果sz == 2, &a[(sz/2)+1]
将尝试获取[2]的地址,这将为您带来此错误。
马丁是对的,问题是辅助向量的创造者:
原始矢量:1 9 7 9 2 7 2 1 9 8
iter1:2,iter2:8
vector<int> v( iter1, iter2 ); //new vector: 2 7 2 1 9
http://www.cppreference.com/wiki/stl/vector/Vector_Constructors
并谈论合并 - 选项和其他分类算法,我发现了一个非常有用的网络:
不隶属于 StackOverflow