STL set 구조체 활용(4) - 특정 원소에 빠르게 찾기

이전글

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

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

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

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

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

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

 

지금까지 기본적인 set 사용법을 익혔고 포인터를 활용해서 약간의 성능을 개선시켰습니다.

이번 글에서는 지난 시간에 배웠던 "set에 구조체 포인터 탐기"를 기본적으로 알고 있다는 전제로 작성했습니다. stl에 구조체 포인터 담는 내용은 정말 중요하니까 아직 안 보셨으면 꼭 보시고 오시길 추천드립니다!!

 

(1) 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");
	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
	return 0;
}

기존에는 이처럼 find(키값) 을 활용해서 특정 원소를 찾았습니다. 이 과정에서 O(logN)만큼의 비용을 사용하게 됩니다. 

 

(2) set에서 특정원소 찾기 O(1)

특정원소를 O(1)만에 찾을 수 있는 방법이 존재합니다. 이전에 "heap 특정원소, 수정 및 삭제" 게시물에서 데이터의 id마다 heap에서의 인덱스를 따로 저장해놓는 방법을 사용했습니다. 이것과 비슷합니다.

특정 데이터를 id로 구분할 수 있다면, id별로 iterator를 따로 저장해놓으면 됩니다(배열 또는 unordered_map 이용). 특정원소를 찾아야 할 때 찾아야 하는 원소의 id는 알고 있으니까, id를 이용해서 iterator를 받아오면 set의 해당 원소에 바로 접근 가능합니다.

 

코드부터 먼저 보신 뒤 밑에서 코드 설명드리겠습니다.

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

const int MAXN = 1000;
const int MAXID = 10000;

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;

set<Data*>::iterator itTable[MAXID];	//itTable[i]:id=i인 데이터를 가리키는 iterator 저장

int main(void) {
	Data* newData = getData();	newData->p = 1;	newData->id = 1;	newData->num = 10;
	auto temp = mySet.insert(newData);
	itTable[newData->id] = temp.first;	//iterator 저장

	newData = getData();	newData->p = 1;	newData->id = 2;	newData->num = 10;	mySet.insert(newData);
	temp = mySet.insert(newData);
	itTable[newData->id] = temp.first;	//iterator 저장

	newData = getData();	newData->p = 2;	newData->id = 3;	newData->num = 10;	mySet.insert(newData);
	temp = mySet.insert(newData);
	itTable[newData->id] = temp.first;	//iterator 저장

	newData = getData();	newData->p = 2;	newData->id = 4;	newData->num = 10;	mySet.insert(newData);
	temp = mySet.insert(newData);
	itTable[newData->id] = temp.first;	//iterator 저장

	newData = getData();	newData->p = 3;	newData->id = 5;	newData->num = 10;	mySet.insert(newData);
	temp = mySet.insert(newData);
	itTable[newData->id] = temp.first;	//iterator 저장

	newData = getData();	newData->p = 3;	newData->id = 6;	newData->num = 10;	mySet.insert(newData);
	temp = mySet.insert(newData);
	itTable[newData->id] = temp.first;	//iterator 저장


	for (auto it = mySet.begin(); it != mySet.end(); it++) {
		Data* data = *it;
		printf("p: %d, id: %d, num: %d\n", data->p, data->id, data->num);
	}

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


	printf("id로 특정원소 바로 찾기\n");
	auto it = itTable[5];
	Data* found = *it;
	printf("p: %d, id: %d, num: %d\n", found->p, found->id, found->num);	//p: 3, id: 5, num: 10
	return 0;
}

먼저 itTable배열을 이용해서 iterator를 저장해두었습니다. 그리고 사실 insert 함수는 리턴값이 존재합니다. insert 함수는 pair<iterator,bool>을 리턴합니다. 리턴값의 의미는 다음과 같습니다.

- insert 성공한 경우(키 중복x) : <삽입된 데이터의 이터레이터, true>

- insert 실패한 경우(키 중복o) : <중복인(이미 존재하는) 데이터의 이터레이터, false>

insert 함수의 리턴값 덕분에 삽입과 동시에 해당 데이터의 이터레이터도 바로 얻어올 수 있습니다!!

 

itTable 덕분에 O(logN)만에 특정 원소를 찾을 수 있었던 것을 O(1)로 줄였습니다. 

이것을 활용하면 특정원소 수정 및 삭제시에도 성능을 개선할 수 있습니다.

 

(3) set에서 특정 데이터 삭제하기 - 성능개선

기존에 특정 원소를 삭제하려면 set.erase(특정 데이터)를 하거나,  set.find(특정데이터)로 iterator를 구한 뒤 set.erase(iterator)를 해줬어야 합니다. 즉 O(logN)의 시간을 사용해야 했습니다. 하지만 위에서 배운 방식을 활용 하면 O(1)만에 특정 데이터를 삭제할 수 있습니다.

 

- 특정 데이터 O(1)만에 삭제하기

1) 특정 데이터의 id로 itTable에서 iterator 얻어오기 O(1)

2) 얻은 iterator로 set.erase(iterator) 해주기 O(1)

 

아래 코드는 set에서 O(1)만에 데이터 삭제하는 예시입니다.

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

const int MAXN = 1000;
const int MAXID = 10000;

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;

set<Data*>::iterator itTable[MAXID];	//itTable[i]:id=i인 데이터를 가리키는 iterator 저장

int main(void) {
	Data* newData = getData();	newData->p = 1;	newData->id = 1;	newData->num = 10;
	auto temp = mySet.insert(newData);
	itTable[newData->id] = temp.first;	//iterator 저장

	newData = getData();	newData->p = 1;	newData->id = 2;	newData->num = 10;	mySet.insert(newData);
	temp = mySet.insert(newData);
	itTable[newData->id] = temp.first;	//iterator 저장

	newData = getData();	newData->p = 2;	newData->id = 3;	newData->num = 10;	mySet.insert(newData);
	temp = mySet.insert(newData);
	itTable[newData->id] = temp.first;	//iterator 저장

	newData = getData();	newData->p = 2;	newData->id = 4;	newData->num = 10;	mySet.insert(newData);
	temp = mySet.insert(newData);
	itTable[newData->id] = temp.first;	//iterator 저장

	newData = getData();	newData->p = 3;	newData->id = 5;	newData->num = 10;	mySet.insert(newData);
	temp = mySet.insert(newData);
	itTable[newData->id] = temp.first;	//iterator 저장

	newData = getData();	newData->p = 3;	newData->id = 6;	newData->num = 10;	mySet.insert(newData);
	temp = mySet.insert(newData);
	itTable[newData->id] = temp.first;	//iterator 저장


	for (auto it = mySet.begin(); it != mySet.end(); it++) {
		Data* data = *it;
		printf("p: %d, id: %d, num: %d\n", data->p, data->id, data->num);
	}

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

	printf("\nid=5인 원소 바로 삭제하기\n");
	auto iter = itTable[5];	//id=5에 해당하는 이터레이터 받아오기 O(1)
	mySet.erase(iter);	//그 이터레이터로 바로 mySet에서 삭제하기 O(1)
	for (auto it = mySet.begin(); it != mySet.end(); it++) {
		Data* data = *it;
		printf("p: %d, id: %d, num: %d\n", data->p, data->id, data->num);
	}
	/*	//결과
	p: 3, id: 6, num: 10
	p: 2, id: 3, num: 10
	p: 2, id: 4, num: 10
	p: 1, id: 1, num: 10
	p: 1, id: 2, num: 10
	*/
	return 0;
}

 

(4) set에서 특정 데이터 수정하기 - 성능 개선

기존에 set에서 특정 데이터를 수정하려면, 특정 데이터를 찾고 O(logN), 그 데이터 삭제하고O(1), 새 데이터 수정해서 삽입O(logN) 해줘야 합니다.

하지만, 수정의 경우에도 idTable을 이용해서 성능 개선이 가능합니다.

 

-특정 데이터 수정하기(성능 개선 버전)

1) 특정 데이터의 id로 itTable에서 iterator 얻어오기 O(1)

2) 얻은 iterator로 set.erase(iterator) 해주기 O(1)

3) 해당 데이터 수정하기 O(1)

4) 해당 데이터 삽입하기 O(logN)

 

아래 코드는 특정 데이터 수정하기(개선된 버전) 예시입니다.

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

const int MAXN = 1000;
const int MAXID = 10000;

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;

set<Data*>::iterator itTable[MAXID];	//itTable[i]:id=i인 데이터를 가리키는 iterator 저장

int main(void) {
	Data* newData = getData();	newData->p = 1;	newData->id = 1;	newData->num = 10;
	auto temp = mySet.insert(newData);
	itTable[newData->id] = temp.first;	//iterator 저장

	newData = getData();	newData->p = 1;	newData->id = 2;	newData->num = 10;	mySet.insert(newData);
	temp = mySet.insert(newData);
	itTable[newData->id] = temp.first;	//iterator 저장

	newData = getData();	newData->p = 2;	newData->id = 3;	newData->num = 10;	mySet.insert(newData);
	temp = mySet.insert(newData);
	itTable[newData->id] = temp.first;	//iterator 저장

	newData = getData();	newData->p = 2;	newData->id = 4;	newData->num = 10;	mySet.insert(newData);
	temp = mySet.insert(newData);
	itTable[newData->id] = temp.first;	//iterator 저장

	newData = getData();	newData->p = 3;	newData->id = 5;	newData->num = 10;	mySet.insert(newData);
	temp = mySet.insert(newData);
	itTable[newData->id] = temp.first;	//iterator 저장

	newData = getData();	newData->p = 3;	newData->id = 6;	newData->num = 10;	mySet.insert(newData);
	temp = mySet.insert(newData);
	itTable[newData->id] = temp.first;	//iterator 저장


	for (auto it = mySet.begin(); it != mySet.end(); it++) {
		Data* data = *it;
		printf("p: %d, id: %d, num: %d\n", data->p, data->id, data->num);
	}

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

	printf("\nid=4인 원소 바로 수정하기\n");
	auto iter = itTable[4];	//id=4에 해당하는 이터레이터 받아오기 O(1)
	Data* modifyData = *iter;	mySet.erase(iter);	//그 이터레이터로 바로 mySet에서 삭제하기 O(1)
	modifyData->p = 100;	//해당 데이터 수정하기 O(1)
	auto insertRes = mySet.insert(modifyData);	//해당 데이터 삽입하기 O(logN)
	itTable[modifyData->id] = insertRes.first;	//itTable에 해당 iterator 저장하기

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

	printf("\nid=4인 원소 바로 찾기\n");
	auto iter2 = itTable[4];
	Data* found = *iter2;
	printf("p: %d, id: %d, num: %d\n", found->p, found->id, found->num);	//p: 100, id: 4, num: 10

	return 0;
}

 

지금까지 set으로 설명드린 내용들 모두 다 multiset, map, multimap에도 적용 가능 합니다. 나중에 따로 정리하시기를 추천드립니다.