[C++] 이중포인터와 주소값 비교

오늘은 버그리포팅이다.

기존에 다양한 자료구조를 직접 구현하며 익숙해졌다 싶을때 하나의 버그를 만났다.

버그가 났던 문제는 생략하고 간단하게 작성했던 내용과 상황을 재연하여 리포팅 하겠다.

template<typename T>
struct Heap {
	T* data;
	int size;
	int capasity;

	Heap(int init_capa = 2) :size(0), capasity(init_capa) {
		data = new T[init_capa];
	}

	~Heap() {
		delete[] data;
	}

	void clear() {
		size = 0;
	}
	void resize(int new_capa) {
		T* new_data = new T[new_capa];
		for (int i = 0; i < size; ++i) {
			new_data[i] = data[i];
		}
		delete[] data;
		data = new_data;
		capasity = new_capa;
	}

	void upswap(int child) {
		T value = data[child];

		while (child > 0) {
			int paridx = (child - 1) >> 1;
			T par = data[paridx];

			if (*value < *par) {
				data[child] = par;
				// 요소 자체에 heap index를 저장하기 위함
				// T자체에 index는 반드시 있을 예정이며,
				// 포인터로 힙을 생성예정
				par->index = child;
				child = paridx;
				continue;
			}

			break;
		}

		data[child] = value;
		value->index = child;
	}

	void downswap(int par) {
		T value = data[par];

		int child = (par << 1) + 1;

		while (child < size) {
			int right = child + 1;
			if (right < size && !(*data[child] < *data[right])) child = right;

			if (*data[child] < *value) {
				data[par] = data[child];
				// 요소 자체에 heap index를 저장하기 위함
				// T자체에 index는 반드시 있을 예정이며,
				// 포인터로 힙을 생성예정
				data[par]->index = par;
				par = child;
				child = (par << 1) + 1;
				continue;
			}

			break;
		}

		data[par] = value;
		data[par]->index = par;
	}

	void push(T value) {
		if (size == capasity) resize(capasity * 2);

		data[size++] = value;
		upswap(size-1);
	}

	T pop() {
		if(size == 0 ){/*error*/ }

		T returnvalue = data[0];
		data[0] = data[--size];
		data[0]->index = 0;
		downswap(0);

		return returnvalue;
	}
};

struct User {
	int index;
	char name[MAXL + 1];
	int point;

	
	bool operator<(const User& other) {
		if (point != other.point) {
			//최대힙을 위한 부호 반대.
			return point > other.point;
		}

		for (int i = 0; i < 10; ++i) {
			if (name[i] == other.name[i]) continue;
			return name[i] < other.name[i];
		}
		
	}
}

Heap<User*> heap_user;

int main(){
 return 0;
}

작성된 heap구조는 기존과 비슷한데, heap의 요소가 변경되고, 이후에 다시 heap정렬을 해줘야 해서 push, pop, up, down을 구분 해주고, up down시 요소에 인덱스값을 저장해준 것이다.(기존에는 push할때 up을, pop할때 down을 해줬다.

여기서 특이한 점은 객체를 생성할때 템플릿으로 포인터를 넘겨 줬는데

Heap<User*> heap_user;

이로 인해 Heap내부에서 비교를 할때 포인터 주소값 자체를 비교했다.

즉 내가 설정한 User의 operator<이 아닌
단순히 포인터 주소값의 숫자 비교를 통해 heap정렬을 하고 있었던 것이다.

문제 해결 과정은 값을 비교할때마다 요소들을 확인했는데, 비교하는 값이 일정하지 않게 결과가 나왔고, 테스트 삼아 operator첫번째 줄에

return true;

라고 지정을 해줘도 false가 나왔으며,
무엇보다 비교연산자를 <가 아닌 >로 설정해도 컴파일에 문제가 없었다(User에 operator>함수를 안 만들었기에 컴파일이 안되어야 정상)

이로인해 다른 요소로 비교되고 있음을 알았고,
주소라는 추측을 통해 역참조를 시도하자 무사히 의도대로 돌아갔다.