来自 valgrind 的错误（Treap）

Question

Valgrind 在实现 Treap 数据结构时在此程序中抛出错误。无法弄清楚如何解决这个问题。试图写一个析构函数，没有任何改变。为简单起见，不包含其余代码。错误在这部分代码。

#include <iostream>
#include <fstream>

using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");

class vertex{
    public:
    int x, y, label;
    struct vertex *parent, *left, *right;
    vertex() {}
};

typedef vertex *pvertex;

class decTree{
    private:
    int treeSize;
    vertex *vertexs;
    pvertex *ordered;
    pvertex root;
    int vertexCount;

    public:
    decTree(){
        int a , b;
        vertexCount = 0;
        in >> treeSize;
        vertexs = new vertex[treeSize];
        ordered = new pvertex[treeSize];
        for (int i = 0; i < treeSize; i++ ){
            in >> a >> b;
            ordered[vertexCount] = vertexs + vertexCount;
            vertexCount++;
        }
    }
};

int main(){
    decTree *mytree = new decTree;
    delete mytree;
}

/////////////////////////////////////////// /////////////////////

==20464== HEAP SUMMARY:
==20464==     in use at exit: 336 bytes in 2 blocks
==20464==   total heap usage: 8 allocs, 6 frees, 90,408 bytes allocated
==20464== 
==20464== 336 (56 direct, 280 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==20464==    at 0x483E217: operator new[](unsigned long) (vg_replace_malloc.c:579)
==20464==    by 0x1094A3: decTree::decTree() (in a.out)
==20464==    by 0x1092AC: main (in a.out)
==20464== 
==20464== LEAK SUMMARY:
==20464==    definitely lost: 56 bytes in 1 blocks
==20464==    indirectly lost: 280 bytes in 1 blocks
==20464==      possibly lost: 0 bytes in 0 blocks
==20464==    still reachable: 0 bytes in 0 blocks
==20464==         suppressed: 0 bytes in 0 blocks
==20464== 
==20464== For lists of detected and suppressed errors, rerun with: -s
==20464== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from

Answer 1

我加了

~ decTree () { 
   delete [] vertices; 
   delete [] ordered; 
}

一切正常。

Answer 2

显式使用运算符 new 和 delete（或 new[] 和 delete[]）被认为是一种不好的做法（因为正在使用 C++11）。推荐使用RAII模式

在你的情况下，一切都可以通过使用 std;:vector.

来处理

class decTree {
   private:
    int treeSize;
    std::vector<vertex> vertexs;
    std::vector<pvertex> ordered;
    pvertex root;
    int vertexCount;

   public:
    decTree(std::istream &in) {
        int a, b;
        vertexCount = 0;
        in >> treeSize;
        vertexs.resize(treeSize);
        ordered.resize(treeSize);
        for (int i = 0; i < treeSize; i++) {
            in >> a >> b;
            ordered[vertexCount] = &vertexs[vertexCount];
            vertexCount++;
        }
    }
};

https://godbolt.org/z/co4jbcbvW

来自 valgrind 的错误（Treap）

Errors from valgrind (Treap)

c++

valgrind

treap