STL set 구조체 활용(3) - set에 구조체 포인터 담기

 

이전 글

2023.03.13 - [STL] - STL set 구조체활용(1) - 사용법(set은 만능이다?)

STL set 구조체활용(1) - 사용법(set은 만능이다?)

2023.03.30 - [STL] - STL set 구조체 활용 (2)- 정렬 기준 바꾸기

STL set 구조체 활용 (2)- 정렬 기준 바꾸기

 

지금까지는 set에 구조체 데이터 자체를 저장하는 방식에 대해 알아봤습니다. 이번에는 set에 구조체 포인터를 저장하는 방식에 대해서 알아보도록 하겠습니다.

 

(1) 성능 비교

구조체는 여러 멤버 변수들이 포함되어 있습니다. 그래서 메모리를 많이 차지합니다. 즉 무겁습니다. 반면 구조체 포인터는 포인터 자체 메모리만 있습니다. 그래서 가볍습니다. 그래서 set에 직접 데이터를 담기 보다는 포인터를 담는것이 훨씬 성능이 좋습니다(빠릅니다)

 

(2) 메모리 풀 방식

set에 포인터를 담는다고 하더라도 그 포인터가 가리키는 실제 데이터들은 어딘가에 존재해야 합니다. 일반적으로는 malloc()을 통해 동적할당을 하는데, 알고리즘문제 풀이에 있어서는 동적할당을 사용하면 매우 불리합니다. 일일이 동적할당을 할 때마다 시간이 소요가 되는데, 동적할당하는 횟수가 몇만, 몇십만이 되면 누적된 소요시간이 상당히 커서 불리합니다.

그래서 그 대신에  메모리 풀 방식을 사용합니다. 메모리 풀 방식은 미리 전역변수로 사용할 데이터들을 만들어 놓고 하나씩 필요할 때마다 사용하는 방식입니다. 자세한 사용법은 코드를 보면서 설명드리겠습니다.

#include<stdio.h>
#include<set>
using namespace std;

const int MAXN = 1000;

struct Data {
	int p;
	int id;
	int num;
};
Data dataPool[MAXN];
int poolCnt = 0;

Data* getData() {
	return &dataPool[poolCnt++];
}

int main(void) {
	Data* newData = getData();	newData->p = 1;	newData->id = 2;	newData->num = 10;	
	return 0;
}

위 코드처럼 Data가 필요할 때마다 getData()함수를 통해서 dataPool[poolCnt]의 주소값을 얻어와서 사용하면 됩니다. 메모리 풀 방식으로 구현할 때 주의할 점은 몇개의 데이터를 미리 만들어 놓을지(위 코드의 경우 MAXN)를 잘 정해야 한다는 것입니다. 꼭 문제의 요구사항을 잘 읽고 안전하게 최대 데이터 개수를 정하시기를 추천드립니다!!

 

(3) set에 삽입하기 및 set의 데이터에 접근하기

아래 코드처럼 사용해주시면 됩니다.

#include<stdio.h>
#include<set>
using namespace std;

const int MAXN = 1000;

struct Data {
	int p;
	int id;
	int num;
};
Data dataPool[MAXN];
int poolCnt = 0;

Data* getData() {
	return &dataPool[poolCnt++];
}

struct DataCmp {
	//p 큰게 앞으로, p가 같다면 id작은게 앞으로
	bool operator () (Data* const &first, Data* const &second) const {
		if (first->p == second->p) return first->id < second->id;
		else return first->p > second->p;
	}
}; 

set<Data*,DataCmp> mySet;

int main(void) {
	Data* newData = getData();	newData->p = 1;	newData->id = 2;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 1;	newData->id = 1;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 2;	newData->id = 1;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 2;	newData->id = 5;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 3;	newData->id = 3;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 3;	newData->id = 1;	newData->num = 10;	mySet.insert(newData);
	
	for (auto it = mySet.begin(); it != mySet.end(); it++) {
		Data* temp = *it;
		printf("p: %d, id: %d, num: %d\n", temp->p, temp->id, temp->num);
	}

	/* //결과
	p: 3, id : 1, num : 10
	p : 3, id : 3, num : 10
	p : 2, id : 1, num : 10
	p : 2, id : 5, num : 10
	p : 1, id : 1, num : 10
	p : 1, id : 2, num : 10
	*/
	return 0;
}

 

(4) set의 특정 키값에 해당하는 원소 찾기 및 삭제하기

기존의 구조체 set에서 찾던 방식과 똑같이 해주면 되는데 find(), erase()의 매개변수로 target의 주소값을 넣어준다는 점만 차이가 있습니다.

#include<stdio.h>
#include<set>
using namespace std;

const int MAXN = 1000;

struct Data {
	int p;
	int id;
	int num;
};
Data dataPool[MAXN];
int poolCnt = 0;

Data* getData() {
	return &dataPool[poolCnt++];
}

struct DataCmp {
	//p 큰게 앞으로, p가 같다면 id작은게 앞으로
	bool operator () (Data* const &first, Data* const &second) const {
		if (first->p == second->p) return first->id < second->id;
		else return first->p > second->p;
	}
}; 

set<Data*,DataCmp> mySet;

int main(void) {
	Data* newData = getData();	newData->p = 1;	newData->id = 2;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 1;	newData->id = 1;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 2;	newData->id = 1;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 2;	newData->id = 5;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 3;	newData->id = 3;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 3;	newData->id = 1;	newData->num = 10;	mySet.insert(newData);
	
	for (auto it = mySet.begin(); it != mySet.end(); it++) {
		Data* temp = *it;
		printf("p: %d, id: %d, num: %d\n", temp->p, temp->id, temp->num);
	}

	/* //결과
	p: 3, id : 1, num : 10
	p : 3, id : 3, num : 10
	p : 2, id : 1, num : 10
	p : 2, id : 5, num : 10
	p : 1, id : 1, num : 10
	p : 1, id : 2, num : 10
	*/


	printf("특정 원소 찾기\n");
	Data target;	target.p = 3;	target.id = 3;
	auto iter = mySet.find(&target);
	Data* found = *iter;
	printf("p: %d, id: %d, num: %d\n", found->p, found->id, found->num);	//p: 3, id: 3, num: 10
	iter++;
	found = *iter;
	printf("p: %d, id: %d, num: %d\n", found->p, found->id, found->num);	//p: 2, id: 1, num: 10


	printf("특정 원소 지우기\n");
	target.p = 1;	target.id = 1;
	mySet.erase(&target);
	for (auto it = mySet.begin(); it != mySet.end(); it++) {
		Data* temp = *it;
		printf("p: %d, id: %d, num: %d\n", temp->p, temp->id, temp->num);
	}

	/*
	p: 3, id : 1, num : 10
	p : 3, id : 3, num : 10
	p : 2, id : 1, num : 10
	p : 2, id : 5, num : 10
	p : 1, id : 2, num : 10
	*/

	return 0;
}

 

(5) 특정 원소 수정하기

왠지 포인터를 set에 넣었기 때문에 포인터로 접근해서 값을 수정해주면 set에서도 정상적으로 반영될 것 같다는 느낌이 들 수도 있습니다. 하지만 아래 코드를 실행해보시면 그렇지 않다는 걸 알 수 있습니다.

#include<stdio.h>
#include<set>
using namespace std;

const int MAXN = 1000;

struct Data {
	int p;
	int id;
	int num;
};
Data dataPool[MAXN];
int poolCnt = 0;

Data* getData() {
	return &dataPool[poolCnt++];
}

struct DataCmp {
	//p 큰게 앞으로, p가 같다면 id작은게 앞으로
	bool operator () (Data* const &first, Data* const &second) const {
		if (first->p == second->p) return first->id < second->id;
		else return first->p > second->p;
	}
}; 

set<Data*,DataCmp> mySet;

int main(void) {
	Data* newData = getData();	newData->p = 1;	newData->id = 2;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 1;	newData->id = 1;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 2;	newData->id = 1;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 2;	newData->id = 5;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 3;	newData->id = 3;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 3;	newData->id = 1;	newData->num = 10;	mySet.insert(newData);
	
	for (auto it = mySet.begin(); it != mySet.end(); it++) {
		Data* temp = *it;
		printf("p: %d, id: %d, num: %d\n", temp->p, temp->id, temp->num);
	}

	/* //결과
	p: 3, id : 1, num : 10
	p : 3, id : 3, num : 10
	p : 2, id : 1, num : 10
	p : 2, id : 5, num : 10
	p : 1, id : 1, num : 10
	p : 1, id : 2, num : 10
	*/


	printf("\n특정 원소 수정하기\n");
	Data target;	target.p = 2;	target.id = 5;
	auto it = mySet.find(&target);
	Data* found = *it;
	found->p = 10;	//이렇게 하면 p : 10, id : 5, num : 10이 맨 앞에 올 거 같은데? !!안 움직여진다!!

	for (auto it = mySet.begin(); it != mySet.end(); it++) {
		Data* temp = *it;
		printf("p: %d, id: %d, num: %d\n", temp->p, temp->id, temp->num);
	}
	//결과: p값은 10으로 변했지만, 정렬된 위치는 변하지 않았다!!
	/*
	p: 3, id : 1, num : 10
	p : 3, id : 3, num : 10
	p : 2, id : 1, num : 10
	p : 10, id : 5, num : 10
	p : 1, id : 1, num : 10
	p : 1, id : 2, num : 10
	*/

	return 0;
}

포인터라서 값은 수정되었지만, 위치는 변하지 않았습니다. 결론적으로 포인터를 저장한 경우에도 set에서 기존의 포인터 데이터를 삭제 시킨뒤, 값을 수정하고, 그 포인터를 다시 set에 삽입해줘야 정상적으로 수정됩니다!!

 

아래 코드는 정상적으로 수정까지 완료한 코드입니다.

#include<stdio.h>
#include<set>
using namespace std;

const int MAXN = 1000;

struct Data {
	int p;
	int id;
	int num;
};
Data dataPool[MAXN];
int poolCnt = 0;

Data* getData() {
	return &dataPool[poolCnt++];
}

struct DataCmp {
	//p 큰게 앞으로, p가 같다면 id작은게 앞으로
	bool operator () (Data* const &first, Data* const &second) const {
		if (first->p == second->p) return first->id < second->id;
		else return first->p > second->p;
	}
}; 

set<Data*,DataCmp> mySet;

int main(void) {
	Data* newData = getData();	newData->p = 1;	newData->id = 2;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 1;	newData->id = 1;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 2;	newData->id = 1;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 2;	newData->id = 5;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 3;	newData->id = 3;	newData->num = 10;	mySet.insert(newData);
	newData = getData();	newData->p = 3;	newData->id = 1;	newData->num = 10;	mySet.insert(newData);
	
	for (auto it = mySet.begin(); it != mySet.end(); it++) {
		Data* temp = *it;
		printf("p: %d, id: %d, num: %d\n", temp->p, temp->id, temp->num);
	}

	/* //결과
	p: 3, id : 1, num : 10
	p : 3, id : 3, num : 10
	p : 2, id : 1, num : 10
	p : 2, id : 5, num : 10
	p : 1, id : 1, num : 10
	p : 1, id : 2, num : 10
	*/


	printf("\n특정 원소 수정하기\n");
	//수정할 원소 찾기
	Data target;	target.p = 2;	target.id = 5;
	auto it = mySet.find(&target);	
	Data* found = *it;
	
	//해당 원소 삭제
	mySet.erase(it);

	//값 수정
	found->p = 10;

	//다시 set에 넣어주기
	mySet.insert(found);

	for (auto it = mySet.begin(); it != mySet.end(); it++) {
		Data* temp = *it;
		printf("p: %d, id: %d, num: %d\n", temp->p, temp->id, temp->num);
	}
	/*
	p: 10, id: 5, num: 10
	p: 3, id: 1, num: 10
	p: 3, id: 3, num: 10
	p: 2, id: 1, num: 10
	p: 1, id: 1, num: 10
	p: 1, id: 2, num: 10
	*/

	return 0;
}

 

다음 글에서는 조금 더 성능을 개선한 set 사용법에 대해 알아보도록 하겠습니다.