malloc.c:2379:sysmalloc:断言...失败

malloc.c:2379: sysmalloc: Assertion... failed

提问人:Top_Waifu 提问时间:11/5/2020 最后编辑:Top_Waifu 更新时间:9/15/2021 访问量:6424

问:

我目前正在编写一个使用 Heap 类的程序,以查找数组部分(部分的大小为 k)中的最大值,该数组在数组中移动,直到到达末尾。它压垮了数据集: 3 1 2 3 1 with misstake: malloc.c:2379: sysmalloc: 断言 '(old_top == initial_top (av) && old_size == 0) ||((无符号长) (old_size) >= MINSIZE && prev_inuse (old_top) && ((无符号长) old_end & (pagesize - 1)) == 0)' 失败。 当它尝试关闭 temp.value 变量时,它会崩溃。如果我坚持下去,一切都很好

这是我的代码:

#include <iostream>
#include <cstring>
#include <cassert>

#define DEFAULT_GROW 2

template<class T>
class IsLess {
public:
    bool operator()(const T& lhs, const T& rhs) const {
        return lhs < rhs;
    }
};

template<class T>
struct Node {
    T value;
    size_t index;
};


template <class T, class H = IsLess<T>>
class Heap {
public:
    Heap();
    Heap(const T* arr, size_t dataSize, H func = IsLess<T>());
    Heap(const Heap&) = delete;
    Heap(Heap&&) = delete;
    Heap operator = (const Heap&) = delete;
    Heap operator = (Heap&&) = delete;
    ~Heap();
    bool IsEmpty();
    void Insert(const T &k);
    Node<T> ExtractMax();
    Node<T> ExtractMaxByIndex(const size_t &i, const size_t &k);
    void InsertNode(const Node<T> &);

private:
    void Grow();
    void BuildHeap();
    void SiftDown(const int &i);
    void SiftUp(int i);
    size_t capacity;
    size_t size;
    Node<T>* data;
    H comparator;
};

template<class T, class H>
Heap<T, H>::Heap():
capacity(0),
size(0),
data(nullptr),
comparator(IsLess<T>())
{}

template<class T, class H>
Heap<T, H>::Heap(const T* arr, size_t dataSize, H func) {
    assert(arr != nullptr);
    assert(dataSize > 0);
    data = new Node<T>[dataSize];
    capacity = dataSize;
    size = dataSize;
    comparator = func;
    // std::memcpy(data->value, arr, dataSize * sizeof(T) - 1);
    for (size_t i = 0; i < dataSize; ++i) {
        data[i].value = arr[i];
        data[i].index = i;
    }
    BuildHeap();
}

template<class T, class H>
Heap<T, H>::~Heap() {
    delete[] data;
}

template<class T, class H>
void Heap<T, H>::Grow() {
    if (capacity == 0) {
        data = new Node<T>[++capacity];
        return;
    }
    if (size < capacity) {
        return;
    }
    capacity *= DEFAULT_GROW;
    Node<T> *buf = new Node<T>[capacity];
    std::memcpy(buf, data, sizeof(Node<T>) * size - 1);
    delete[] data;
    data = buf;
}

template<class T, class H>
void Heap<T, H>::SiftDown(const int &i) {
    size_t leftChild = i * 2 + 1;
    size_t rightChild = i * 2 + 2;
    size_t largest = i;
    if(leftChild < size
    && comparator(data[largest].value, data[leftChild].value)) {
        largest = leftChild;
    }
    if(rightChild < size
    && comparator(data[largest].value, data[rightChild].value)) {
        largest = rightChild;
    }
    if(largest != i) {
        std::swap(data[i], data[largest]);
        SiftDown(largest);
    }
}

template<class T, class H>
void Heap<T, H>::SiftUp(int i) {
    while(i > 0) {
        int parent = (i - 1) / 2;
        if(comparator(data[i].value, data[parent].value)) {
            return;
        }
        std::swap(data[i], data[parent]);
        i = parent;
    }
}

template<class T, class H>
void Heap<T, H>::BuildHeap() {
    for (int i = size / 2 - 1 ; i >= 0 ; --i) {
        SiftDown(i);
    }
}

template<class T, class H>
bool Heap<T, H>::IsEmpty() {
    return size == 0;
}

template<class T, class H>
void Heap<T, H>::Insert(const T &k) {
    if (IsEmpty() || size == capacity) {
        Grow();
    }
    data[size].value = k;
    data[size].index = size;
    SiftUp(size++);
}

template<class T, class H>
Node<T> Heap<T, H>::ExtractMax() {
    assert(!IsEmpty());
    Node<T> result = data[0];
    data[0] = data[--size];
    if (!IsEmpty()) {
        SiftDown(0);
    }
    return result;
}

template<class T, class H>
void Heap<T, H>::InsertNode(const Node<T> &node) {
    if (IsEmpty() || size == capacity) {
        Grow();
    }
    data[size] = node;
    SiftUp(size++);
}

template<class T, class H>
Node<T> Heap<T, H>::ExtractMaxByIndex(const size_t &i, const size_t &k) {
    assert(!IsEmpty());
    Node<T> result = {0, i + k + 1}; //  чтобы условие не выполнилось с 1 раза
    Node<T> *extracted = new Node<T>[k];
    size_t extractedIndex = 0;
    while(result.index < i || result.index > i + k - 1) {
        result = ExtractMax();
        extracted[extractedIndex++] = result;
    }
    for (size_t j = 0 ; j < extractedIndex ; ++j) {
        InsertNode(extracted[j]);
    }
    delete [] extracted;
    return result;
}

void Answer (unsigned int *arr, const size_t &n, const size_t &i, const size_t &k) {
    assert(arr != nullptr);
    Heap<unsigned> heap(arr, n);
    //size_t resSize = n - k + 1;

    Node<unsigned int> temp = heap.ExtractMaxByIndex(i, k);
    std::cout << temp.value << " ";  // This line causes the misstake
}

int main() {
    size_t n = 0;
    std::cin >> n;
    unsigned int *arr = new unsigned int[n];
    for (size_t i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }
    size_t k = 0;
    std::cin >> k;
    for (size_t i = 0 ; i < 1 ; ++i) {
        Answer(arr, n, i, k);
    }
    delete[] arr;
    return 0;
}

Input: 
3
1 2 3
1

Output:
1 2 3
C++ 内存 malloc 新运算符 cout

评论

0赞 Nate Eldredge 11/5/2020
这是很多代码。你能把它简化为一个最小的可重复的例子吗?
1赞 Ken Y-N 11/5/2020
要么使用 ,要么看 - 永远大于?另外,请您输入的数据编辑到您的问题中。std::vector<Node<T>>Node<T> *extracted = new Node<T>[k];extractedIndexk
1赞 Nate Eldredge 11/5/2020
请注意,有许多工具可以查找动态内存错误 - 几乎总是溢出数组或在删除对象后使用对象。Valgrind 在许多系统上都很流行。如果您要使用 C++ 编写代码,尤其是使用原始指针,则需要尽早熟悉这些指针。
0赞 Nate Eldredge 11/5/2020
顺便说一句,valgrind 立即表明 @KenY-N 对这个错误是完全正确的。通过使用正确的工具,您可以在几秒钟内找到它。

答:

0赞 user86 9/14/2021 #1

您的问题出在代码的这一部分:

template<class T, class H>
Node<T> Heap<T, H>::ExtractMaxByIndex(const size_t& i, const size_t& k)
{
    assert(!IsEmpty());
    Node<T> result = { 0, i + k + 1 }; //  чтобы условие не выполнилось с 1 раза
    Node<T>* extracted = new Node<T>[k]; <- right here
    size_t extractedIndex = 0;
    while (result.index < i || result.index > i + k - 1)
    {
        result = ExtractMax();
        extracted[extractedIndex++] = result; <- and right here
    }
    for (size_t j = 0; j < extractedIndex; ++j)
    {
        InsertNode(extracted[j]);
    }
    delete[] extracted;
    return result;
}

首先,您分配的内存少于所需内存(在您的示例中为 1),然后您尝试在内存中分配一个超出此处分配的动态内存范围的值:k

extracted[extractedIndex++] = result;