Trouble with array doubling.

[cabbdeng]

error showed in terminal: Segmentation fault: 11.

Wanna double size the array when the array set before becomes full. But errors come up. Plz help me resolve this problem if possible, thank you.

#include<iostream>
#include<vector>
#include<string>
#include<sstream>
#include<fstream>
using namespace std;



// #pragma once
#define ROOT 1
typedef struct Job *job,j;
struct Job {
	int jobID;
	int execute_time;
	int total_time;
};
//job jobs[10000];
class minHeap {
public:
	job jobs[10];
	int len;
	int size;
	const static int multiple = 2;
	minHeap() {
		len = 0;
		for (int i = 0; i < 10; i++) {
			jobs[i] = new j;
			jobs[i]->jobID = jobs[i]->execute_time = jobs[i]->total_time = 0;
			size++;
		}
	}
	void ShiftDown(int);
	void ShiftUp(int);
	void InsertHeap(int, int);
	int Parent(int);
	int LeftChild(int);
	int RightChild(int);
	bool Empty();
	job Pop();
	void swap(int,int);
	job top();
	job empty_job() {return jobs[0];}
	job ArrayDynamicAllocation(job array[], int size);
	// void check_size();

private:
	int _v(int);
};
job minHeap::top() {
	return jobs[ROOT];
}

job minHeap::ArrayDynamicAllocation(job array[], int size)
{
	job new_array[size*2];
	job tmp_array[size];
	for(int k=0; k<size; k++)//Initial array copying.
		tmp_array[k] = array[k];

	for(int i=0; i<size; i++)//Array range 0 to n-1
	{
		new_array[i]=tmp_array[i];
		new_array[i+size] = new j;
		new_array[i+size]->jobID = new_array[i+size]->execute_time = new_array[i+size]->total_time = 0;
	}
	delete tmp_array[size]; //Deleting old array
  	return new_array[size*2];
};


void minHeap::InsertHeap(int jobID, int total_time) {
	job jo = new j;
	jo->jobID = jobID;
	jo->total_time = total_time;
	jo->execute_time = 0;
	if ((len+2) == size){
		job tmp;
		tmp = ArrayDynamicAllocation(jobs, size);
		size *= multiple;
		job jobs[size];

		for (int i = 0; i < size; ++i ){
			jobs[i] = tmp+i;
		}
	}
	jobs[++len] = jo;
	ShiftUp(len);
}
job minHeap::Pop() {
	job j = jobs[ROOT];
	swap(ROOT, len);
	jobs[len]->jobID = jobs[len]->execute_time = jobs[len]->total_time = 0;
	len--;
	ShiftDown(ROOT);
	return j;
}
void minHeap::swap(int a, int b) {
	job t = jobs[a];
	jobs[a] = jobs[b];
	jobs[b] = t;
}
int minHeap::_v(int index) {
	return jobs[index]->execute_time;
}
void minHeap::ShiftUp(int index) {
	while (_v(index) < _v(Parent(index)) && index > 1) {
		swap(index, Parent(index));
		index = Parent(index);
	}
}
void minHeap::ShiftDown(int index) {
	while (index < len) {
		int v = _v(index);
		int location = index;
		if (LeftChild(index) <= len) {
			if (_v(LeftChild(index)) <= _v(location)) {
				if (_v(LeftChild(index)) == _v(location)) {
					if (jobs[LeftChild(index)]->jobID < jobs[location]->jobID) {
						v = _v(LeftChild(index));
						location = LeftChild(index);
					}
				}
				else {
					v = _v(LeftChild(index));
					location = LeftChild(index);
				}
			}
		}

		if (RightChild(index) <= len) {
			if (_v(RightChild(index)) < _v(location)) {
				if (_v(RightChild(index)) == _v(location)) {
					if (jobs[RightChild(index)]->jobID < jobs[location]->jobID) {
						v = _v(RightChild(index));
						location = RightChild(index);
					}
				}
				else {
					v = _v(RightChild(index));
					location = RightChild(index);
				}
			}
		}

		if (location == index)break;
		swap(index, location);
		index = location;
	}
}

int minHeap::Parent(int index) {
	return index / 2;
}
int minHeap::LeftChild(int index) {
	return index * 2;
}

int minHeap::RightChild(int index) {
	return index * 2 + 1;
}
bool minHeap::Empty() {
	return len == 0;
}


int main() {
	minHeap min;

	int sz = 11;

 	for (int i = 1; i < sz; ++i){
		min.InsertHeap(i, i+20);
 	}

 	for (int i = 0; i < sz; ++i){
 		cout << min. jobs[i]->jobID << " " ;
 	}
 	cout << min.len << "," << min.size << endl;











}

[cabbdeng]

Guys, I change the array: job jobs[size] to a vector<job> jobs. it is easy to resize, but I still wanna know which problem I make in this array doubling operation above.

[tpb]

You did almost everything wrong.

1. You declared the jobs array as a static 10 element array even though you wanted to be able to resize it.

2. In ArrayDynamicAllocation you declared new_array and tmp_array to be Variable Length Arrays (which is not technically allowed in C++). You then are presumably trying to delete tmp_array which you aren't allowed to do but you're using the wrong syntax anyway, passing a random pointer, which is what caused the segfault.

3. You try to return a VLA (not allowed, they are automatically freed at the end of the function).

4. You try to assign a returned pointer to an array variable.

There's some other shady things going on, like hiding pointers behind typedefs, and having a (global!) typedef called j ! You don't need those typedefs at all. And hiding pointers usually confuses things.

Here's a toy example.

#include <iostream>

struct Job {
    int id;
public:
    Job() : id(0) { }
};

class MinHeap {
    int  size;     // number of elements in use
    int  capacity; // maximum capacity
    Job* jobs;
public:
    MinHeap() : size(0), capacity(10), jobs(new Job[capacity]) { }
    ~MinHeap() { delete [] jobs; }
    void extend();
    void insert(int n);
    void print();
};

void MinHeap::print() {
    for (int i = 0; i < size; i++)
        std::cout << jobs[i].id << '\n';
}

void MinHeap::insert(int n) {
    if (size == capacity)
        extend();
    jobs[size++].id = n;
}

void MinHeap::extend() {
    Job* newjobs = new Job[capacity *= 2];
    for (int i = 0; i < size; i++)
        newjobs[i] = jobs[i];
    delete [] jobs;
    jobs = newjobs;
}

int main() {
    MinHeap heap;

    for (int i = 0; i < 30; i++)    
        heap.insert(i);

    heap.print();

    return 0;
}