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

Question

我目前正在编写一个程序，该程序使用Heap类来查找数组中正在移动的部分(部分大小为k(的最大值，直到到达末尾。它在数据集上崩溃：3.1 2 31.错误：malloc.c:2379:sysmalloc:Assertion`(old_top==initial_top(av(&amp；old_size==0(||((无符号长((old_size(>=MINSIZE&amp；prev_inuse(old_top(&amp；((无符号长(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;