c++ - std::vector 析构函数中的段错误

Question

我试图解决 SPOJ ( http://www.spoj.com/problems/GSS1) 上的一个问题，并最终使用线段树编写了以下代码。代码工作得很好。但是在某些输入上，它给出了一个段错误，特别是在程序结束时，当它试图从堆栈中释放 vector 的内存时。我已经花了很多时间，但找不到任何错误。任何帮助将不胜感激。

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

struct Node{
    int bend;
    int bsum;

    int ebeg;
    int esum;
    int maxSum;

    Node(): bend(0), bsum(0), ebeg(0), esum(0), maxSum(0){}
    Node(const Node& other): bend(other.bend), bsum(other.bsum), ebeg(other.ebeg), esum(other.esum), maxSum(other.maxSum){}
    ~Node(){}
};

class SegmentTree{
    int N;
    vector<Node> M;
    vector<int> A;

    public:

    SegmentTree(int N){
        this -> N = N;
        Node temp;
        M.resize((1 << ((int)log(N)+2))+1, temp);
    }

    SegmentTree(const SegmentTree& other): N(other.N), M(other.M), A(other.A) {}

    ~SegmentTree(){
        M.clear();
        A.clear();
    }


    void put(int a){
        A.push_back(a);
    }

    void initialize(int node, int b, int e)
    {
        if (b == e){
            M[node].bsum = M[node].esum = A[b];
            M[node].bend = M[node].ebeg = b;
            if (A[b] > 0) M[node].maxSum = A[b];
            else M[node].maxSum = 0;
        }

        else
        {
            //compute the values in the left and right subtrees
            int boundary = (b+e)/2;
            initialize(2 * node, b, boundary);
            initialize(2 * node + 1, boundary + 1, e);

            //maxSum
            M[node].maxSum = max( M[2*node].esum+M[2*node+1].bsum, max(M[2*node].maxSum, M[2*node+1].maxSum));

            //bsum
            M[node].bsum = M[2*node].bsum;
            if(M[2*node].bend == boundary && M[2*node+1].bsum >= 0) M[node].bsum += M[2*node+1].bsum, M[node].bend = M[2*node+1].bend;
            else M[node].bend = M[2*node].bend;

            //esum
            M[node].esum = M[2*node+1].esum;
            if(M[2*node+1].ebeg == boundary + 1 && M[2*node].esum >= 0) M[node].esum += M[2*node].esum, M[node].ebeg = M[2*node].ebeg;
            else M[node].ebeg = M[2*node+1].ebeg;
        }
    } 

    Node query(int node, int b, int e, int i, int j)
    {
        Node ret;
        ret.maxSum = -1;

        //if the current interval doesn't intersect
        //the query interval return -1
        if (i > e || j < b)
            return ret;

        //if the current interval is included in 
        //the query interval return M[node]
        if (b >= i && e <= j)
            return M[node];

        //use left and right part of the interval
        Node p1, p2;
        int boundary = (b+e)/2;
        p1 = query(2 * node, b, boundary, i, j);
        p2 = query(2 * node + 1, boundary + 1, e, i, j);
        if (p1.maxSum == -1)
            return p2;
        if (p2.maxSum == -1)
            return p1;

        //maxSum
        ret.maxSum = max(p1.esum + p2.bsum, max(p1.maxSum, p2.maxSum));
        //bsum
        ret.bsum = p1.bsum;
        if(p1.bend == boundary && p2.bsum >= 0) ret.bsum += p2.bsum, p1.bend = p2.bend;
        else ret.bend = p1.bend;
        //esum
        ret.esum = p2.esum;
        if(p2.ebeg == boundary + 1 && p1.esum >= 0) ret.esum += p1.esum, M[node].ebeg = p1.ebeg;
        else ret.ebeg = p2.ebeg;
        return ret;
    }
};

int main(){
    int N;
    cin >> N;
    SegmentTree tree(N);
    for (int i = 0; i < N; i++){
        int a;
        cin >> a;
        tree.put(a);
    }

    tree.initialize(1, 0, N-1);
    int M;
    cin >> M;
    while(M--){
        int x, y;
        cin >> x >> y;
        Node ans;
            ans = tree.query(1, 0, N-1, x-1, y-1);
        cout << ans.maxSum << endl;
    }
}

例如，在输入时:

9
-2 1 -3 4 -1 2 1 -5 4
1
1 9

程序在程序末尾给出段错误。回溯如下:

(gdb) backtrace
#0  0x4e584494 in malloc_consolidate () from /lib/libc.so.6
#1  0x4e584f1d in _int_free () from /lib/libc.so.6
#2  0x4eb54500 in operator delete(void*) () from /lib/libstdc++.so.6
#3  0x0804a581 in __gnu_cxx::new_allocator<int>::deallocate (this=0xbfffee68, __p=0x804f1c0) at /usr/lib/gcc/i686-redhat-linux/4.7.2/../../../../inclu
de/c++/4.7.2/ext/new_allocator.h:100
#4  0x08049e21 in std::_Vector_base<int, std::allocator<int> >::_M_deallocate (this=0xbfffee68, __p=0x804f1c0, __n=16) at /usr/lib/gcc/i686-redhat-lin
ux/4.7.2/../../../../include/c++/4.7.2/bits/stl_vector.h:175
#5  0x080498ff in std::_Vector_base<int, std::allocator<int> >::~_Vector_base (this=0xbfffee68, __in_chrg=<optimized out>) at /usr/lib/gcc/i686-redhat
-linux/4.7.2/../../../../include/c++/4.7.2/bits/stl_vector.h:161
#6  0x08049628 in std::vector<int, std::allocator<int> >::~vector (this=0xbfffee68, __in_chrg=<optimized out>) at /usr/lib/gcc/i686-redhat-linux/4.7.2
/../../../../include/c++/4.7.2/bits/stl_vector.h:404
#7  0x08048dcb in SegmentTree::~SegmentTree (this=0xbfffee58, __in_chrg=<optimized out>) at test.cpp:35
#8  0x08048b7b in main () at test.cpp:134

如您所见，错误发生在调用 ~SegmentTree() 时。控件甚至没有转移到 M.clear() (理想情况下应该取消分配内存)并导致段错误。那么，这个段错误的原因是什么？

感谢您的帮助!

Answer 1

最可能的原因是您的程序某处出现了内存损坏。如果我不得不猜测，我会说您可能对 M[] 进行了越界写入。

尝试在 valgrind 下运行程序.