double free 또는 corruption (out) : 0x0000000001a880a0 *** 벡터를 사용하는 결합 알고리즘

Question

각 결합의 최소 트리를 계산하여 주어진 그래프에서 스타이너 트리를 계산하는 알고리즘을 프로그래밍하고 있지만 결합 알고리즘 메모리 사용 권리를 관리하는 것처럼 보이지 않지만 어디서 그 작업을 수행하지 못하는지 알 수 없습니다 ...

다음과 같이 작동합니다. 알고리즘은 다음과 같이 작동합니다. 그래프에서 첫 번째로 선택 버텍스, 즉 우리가 결합 할 하나의 꼭지점 (나는 porpouse를 테스트하기 위해 10 개 사용)을 가진 벡터를 생성 한 다음 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) 

Answer 1

를 제공하는 오류입니다 :

이

while((i >= 0) && (indComb[i] >= n-k+1+i)){ 
    i--; 
    indComb[i]++; 
} 

당신이 다음 라인이 정의되지 않은 원인, i 부정적인 할 수 있습니다.
해당 사례에 대한 일부 추적을 추가하면 해당 사례가 발생하는지 확인합니다.

(당신은 가능성이 벡터의 할당 된 저장을위한 메모리 관리자의 내부 데이터를 덮어 쓰는 것입니다.) 모든 경고 및 디버그 정보와