double free or corruption（out）：0x0000000001a880a0 ***使用向量的组合算法***
问题描述：
我正在编程一个算法，通过计算每个顶点组合的最小树来计算给定图上的Steiner树，但是我的组合算法似乎没有管理内存使用权，但我看不到我无法做到这一点......double free or corruption（out）：0x0000000001a880a0 ***使用向量的组合算法***
它的工作原理如下，算法接收一个向量，其顶点必须始终包含在图形，所以首先要创建一个带有可选顶点的矢量，我们将结合这个顶点（我用10来测试porpouse），然后它计算从1个元素到k个元素的组合（k小于总大小可选顶点集合）。
我们将生成索引的组合（由于它更容易以这种方式分解直接元素），然后将这些元素包含在vComb向量中的这些索引中。
#include <iostream>
#include <vector>
using namespace std;
//Function that calculates the next combination
bool next_comb(vector<int>& indComb, const int k, const int n) {
int i = k - 1;
indComb[i]++;
while((i >= 0) && (indComb[i] >= n-k+1+i)){
i--;
indComb[i]++;
}
if (indComb[0] > n - k) //We've arrived to the combination (n-k, n-k+1, ..., n)
return false; //We can't generate more combinations
//Combination is in form(..., x, n, n, n, ..., n).
//We will put it in form (..., x, x + 1, x + 2, ...)
for (i = i + 1; i < k; ++i)
indComb[i] = indComb[i - 1] + 1;
return true;
}
//Checks if element is in vector
bool is_in(const int n,const vector<int> v){
for(int i=0; i<v.size(); i++)
if(n==v[i]) return true;
return false;
}
void ST(const vector<int> vMandatory){
cout << "V Mandatory: ";
for(int i=0;i<vMandatory.size();i++)
cout << vMandatory[i] << " ";
cout << " " << endl;
//Create and initializate the vector that contains the optional vertices
vector<int> vOptional(10-vMandatory.size());
int j=0;
for(int i=0;i<10;i++){
if(!is_in(i,vMandatory)){
vOptional[j] = i;
j++;
}
}
cout << "V Optional: ";
for(int i=0;i<vOptional.size();i++)
cout << vOptional[i] << " ";
cout << " " << endl;
int k = 1; //Initialize number of elements to combine
int n = vOptional.size(); //Number of elements inside de set to combine
vector<int> indComb; //Vector that will keep the combined indexes of the combination
vector<int> vComb; //Vector that will keep the combined elements
//We control that the number of elements in the combination can't exceed the number of elements in the set
while(k <= vOptional.size()){
indComb.resize(k);
vComb.resize(k);
//Preparare the first combination
for(int i=0;i<k;i++){
indComb[i] = i;
vComb[i] = vOptional[indComb[i]];
}
cout << "V Primera Combinación: ";
for(int i=0;i<vComb.size();i++)
cout << vComb[i] << " ";
cout << " " << endl;
//We make the rest of combinations
while(next_comb(indComb,k,n)){
for(int i=0;i<k;i++)
vComb[i] = vOptional[indComb[i]];
cout << "V Next Combinations: ";
for(int i=0;i<vComb.size();i++)
cout << vComb[i] << " ";
cout << " " << endl;
}
k++;
cout << k << endl;
}
}
int main(){
vector<int> vObligatorios(3);
vObligatorios[0] = 0;
vObligatorios[1] = 1;
vObligatorios[2] = 2;
ST(vObligatorios);
}
这是错误的编译器给我
*** Error in `./a.out': double free or corruption (out): 0x0000000001a880a0 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x777e5)[0x7f8f9a4c67e5]
/lib/x86_64-linux-gnu/libc.so.6(+0x7fe0a)[0x7f8f9a4cee0a]
/lib/x86_64-linux-gnu/libc.so.6(cfree+0x4c)[0x7f8f9a4d298c]
./a.out[0x402612]
./a.out[0x4022c4]
./a.out[0x401c98]
./a.out[0x40213e]
./a.out[0x401b78]
./a.out[0x401823]
./a.out[0x4010b4]
./a.out[0x40149c]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7f8f9a46f830]
./a.out[0x400bb9]
======= Memory map: ========
00400000-00404000 r-xp 00000000 08:06 14156577 /home/pedro/Desktop/a.out
00603000-00604000 r--p 00003000 08:06 14156577 /home/pedro/Desktop/a.out
00604000-00605000 rw-p 00004000 08:06 14156577 /home/pedro/Desktop/a.out
01a76000-01aa8000 rw-p 00000000 00:00 0 [heap]
7f8f94000000-7f8f94021000 rw-p 00000000 00:00 0
7f8f94021000-7f8f98000000 ---p 00000000 00:00 0
7f8f9a146000-7f8f9a24e000 r-xp 00000000 08:06 2621535 /lib/x86_64-linux-gnu/libm-2.23.so
7f8f9a24e000-7f8f9a44d000 ---p 00108000 08:06 2621535 /lib/x86_64-linux-gnu/libm-2.23.so
7f8f9a44d000-7f8f9a44e000 r--p 00107000 08:06 2621535 /lib/x86_64-linux-gnu/libm-2.23.so
7f8f9a44e000-7f8f9a44f000 rw-p 00108000 08:06 2621535 /lib/x86_64-linux-gnu/libm-2.23.so
7f8f9a44f000-7f8f9a60e000 r-xp 00000000 08:06 2621530 /lib/x86_64-linux-gnu/libc-2.23.so
7f8f9a60e000-7f8f9a80e000 ---p 001bf000 08:06 2621530 /lib/x86_64-linux-gnu/libc-2.23.so
7f8f9a80e000-7f8f9a812000 r--p 001bf000 08:06 2621530 /lib/x86_64-linux-gnu/libc-2.23.so
7f8f9a812000-7f8f9a814000 rw-p 001c3000 08:06 2621530 /lib/x86_64-linux-gnu/libc-2.23.so
7f8f9a814000-7f8f9a818000 rw-p 00000000 00:00 0
7f8f9a818000-7f8f9a82e000 r-xp 00000000 08:06 2625962 /lib/x86_64-linux-gnu/libgcc_s.so.1
7f8f9a82e000-7f8f9aa2d000 ---p 00016000 08:06 2625962 /lib/x86_64-linux-gnu/libgcc_s.so.1
7f8f9aa2d000-7f8f9aa2e000 rw-p 00015000 08:06 2625962 /lib/x86_64-linux-gnu/libgcc_s.so.1
7f8f9aa2e000-7f8f9aba0000 r-xp 00000000 08:06 5244862 /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
7f8f9aba0000-7f8f9ada0000 ---p 00172000 08:06 5244862 /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
7f8f9ada0000-7f8f9adaa000 r--p 00172000 08:06 5244862 /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
7f8f9adaa000-7f8f9adac000 rw-p 0017c000 08:06 5244862 /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
7f8f9adac000-7f8f9adb0000 rw-p 00000000 00:00 0
7f8f9adb0000-7f8f9add6000 r-xp 00000000 08:06 2621445 /lib/x86_64-linux-gnu/ld-2.23.so
7f8f9afb4000-7f8f9afb9000 rw-p 00000000 00:00 0
7f8f9afd2000-7f8f9afd5000 rw-p 00000000 00:00 0
7f8f9afd5000-7f8f9afd6000 r--p 00025000 08:06 2621445 /lib/x86_64-linux-gnu/ld-2.23.so
7f8f9afd6000-7f8f9afd7000 rw-p 00026000 08:06 2621445 /lib/x86_64-linux-gnu/ld-2.23.so
7f8f9afd7000-7f8f9afd8000 rw-p 00000000 00:00 0
7ffd45daf000-7ffd45dd0000 rw-p 00000000 00:00 0 [stack]
7ffd45de6000-7ffd45de8000 r--p 00000000 00:00 0 [vvar]
7ffd45de8000-7ffd45dea000 r-xp 00000000 00:00 0 [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]
Aborted (core dumped)
答
这里：
while((i >= 0) && (indComb[i] >= n-k+1+i)){
i--;
indComb[i]++;
}
你可以做i负，导致下一行是不确定的。
为该案例添加一些跟踪验证它确实发生。
（你很可能会改写内存管理器的内部数据为载体的分配的存储。）
编译所有的警告和调试信息：'G ++ -Wall -g'。使用[valgrind]（http://valgrind.org/），你的'gdb'调试器，和*想*你的错误。 –
*但我看不到我在哪里做不到。* - 您可以用'']替换您[]的用法，以使用'at（）'访问您的矢量元素，以便获得'out_of_range'异常错误，而不仅仅是seg故障。如果你这样做了，然后递增地放回'[]'，以查看哪个'at（）'调用导致异常，你会看到'i - indComb.at（i）++;'抛出'std :: out_of_range'异常，就像给出的答案显示你一样。 – PaulMcKenzie