malloc.c:2379: sysmalloc:Assertion...失败

Question

我正在写一个使用Heap类的程序，在数组的一部分(部分的大小是k)中找到最大值，它在数组中移动，直到到达末尾。它在数据集上崩溃:3 1 2 3 1，错误: malloc.c:2379: sysmalloc:Assertion`(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) 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

Answer 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;
}

首先，您分配的内存少于所需的内存(在示例中，k为1)，然后尝试在内存中分配一个超出已分配动态内存界限的值：

extracted[extractedIndex++] = result;