CS/Data Structure

[C++] set

Mirab 2021. 4. 4. 22:06

특징

집합은 요소의 값이 요소를 식별하기 때문에 각 요소가 고유(유니크) 해야 하는 연관 컨테이너 유형이다.

 

1. 중복 값이 올 수 없다. (유니크하다, -> 중복 제거 기능)

2. 삽입하는 순서에 상관없이 무조건 정렬된다.

3. Balanced Tree(균형 이진 트리) 중 R-B Tree를 통해 구현되어 있다.

4. 연관 컨테이너이며 key를 변경할 수 없다.

5. 삽입, 삭제, 검색 O(lgN)의 성능을 가지고 있다.

추가적으로 count(), lower_bound(), upper_bound(), equal_range()도 O(lgN)에 수행된다.

자주 사용하는 멤버 함수

empty() 비어있다면 true, 아니면 false
size() 저장된 원소의 개수 리턴
max_size() set이 가질 수 있는 최대 크기를 반환 (214748364)
   
insert() 삽입
erase() 삭제
swap() 스왑
clear() 저장된 요소들을 모두 삭제
emplace() move()를 사용해 객체를 저장
emplace_hint() 삽입될 위치에 대한 힌트를 제공해서 더 빠르게 삽입한다.
   
find() 찾는 값이 있다면 해당 위치의 iterator 를 반환하고,
없다면 end()를 반환한다.
count() size()와 동일하게 저장된 요소의 개수를 리턴
lower_bound() value와 같거나 큰 것의 iterator 반환
찾는 원소의 시작 반복자 리턴
upper_bound() value를 초과하는 iterator 반환
찾는 원소의 다음 원소 반복자 리턴
equal_range() [lower_bound, upper_bound) pair 리턴

너무 많으니까 하나씩 예제를 따라 하면서 배워보자.

삽입

기본적으로 삽입은 insert()를 이용한다.

insert(숫자);

insert(반복자, 숫자);

#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int> s; // less <
	// left node < parent node < right node

	s.insert(50);
	s.insert(30);
	s.insert(80);
	s.insert(40);
	s.insert(10);
	s.insert(70);
	s.insert(90);

	set<int>::iterator iter; // set의 양방향 반복자 (왼쪽도 갈 수 있고, 오른쪽도 갈 수 있고)
	for (iter = s.begin(); iter != s.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';

	s.insert(50); // 중복된 원소를 삽입하지만 실패.

	auto p = s.insert(50); // pair<iter, boo> 타입
	if (p.second)
		cout << "50 삽입 성공!\n";
	else
		cout << "50 삽입 실패!\n";
	
	for (iter = s.begin(); iter != s.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';
	return 0;
}
10 30 40 50 70 80 90
50 삽입 실패!
10 30 40 50 70 80 90
#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int> s;
	pair<set<int>::iterator, bool> pr;

	s.insert(50);
	s.insert(30);
	s.insert(80);
	s.insert(40);
	s.insert(10);
	s.insert(70);
	pr = s.insert(90);

	set<int>::iterator iter;
	for (iter = s.begin(); iter != s.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';

	s.insert(pr.first, 85); // 해당 위치에 빠르게 원소를 넣을 수 있다.
	for (iter = s.begin(); iter != s.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';
	return 0;
}
10 30 40 50 70 80 90
10 30 40 50 70 80 85 90

정렬 기준

기본적인 정렬 기준은 less이며 < 연산으로 한다.

less 기준이면 left child node < parent node < right child node

greater 기준이면 left child node > parent node > right child node

#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int, greater<int>> s; // greater >
	// left node > parent node > right node

	s.insert(50);
	s.insert(30);
	s.insert(80);
	s.insert(40);
	s.insert(10);
	s.insert(70);
	s.insert(90);
	
	for (auto iter = s.begin(); iter != s.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';
	return 0;
}
90 80 70 50 40 30 10

검색(찾기)

set에서 자주 사용하는 find() 연산이다.

find(key) : key를 검색해서 key를 가리키는 반복자를 리턴한다.

만약에 찾는 key가 없으면 end() 반복자를 리턴한다.

#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int> s;

	s.insert(50);
	s.insert(30);
	s.insert(80);
	s.insert(40);
	s.insert(10);
	s.insert(70);
	s.insert(90);

	for (auto iter = s.begin(); iter != s.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';

	int target = 30;
	auto iter = s.find(target);
	if (iter != s.end())
		cout << target << " exist\n";
	else
		cout << target << " not exist\n";

	target = 100;
	iter = s.find(target);
	if (iter != s.end())
		cout << target << " exist\n";
	else
		cout << target << " not exist\n";
	return 0;
}
10 30 40 50 70 80 90
30 exist
100 not exist

Count()

검색과 비슷한 성격을 가지고 있다.

count(key) : key 가 연관 컨테이너에 몇 개가 있는지를 리턴한다.

set에서는 key들이 중복을 허용하지 않기 때문에 0 or 1이지만

multiset에서는 key들이 중복을 허용하기 때문에 0 or N 이 된다.

#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int> s;

	s.insert(50);
	s.insert(30);
	s.insert(80);
	s.insert(40);
	s.insert(10);
	s.insert(70);
	s.insert(90);

	for (auto iter = s.begin(); iter != s.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';

	cout << "s.count(50) : " << s.count(50) << '\n';
	cout << "s.count(100) : " << s.count(100) << '\n';
	return 0;
}
10 30 40 50 70 80 90
s.count(50) : 1
s.count(100) : 0

Upper_bound() Lower_bound()

특정 구간을 한 번에 리턴 하고 싶을 때?

혹은 해당 key가 존재하는지 검사할 때도 사용한다.

중요한 점은 upper_bound() == lower_bound 이면 내가 찾는 key는 존재하지 않는 것이다.

[lower_bound(), upper_bound()) 닫힌 구간, 열린 구간을 표시하기도 한다.

#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int> s;

	s.insert(50);
	s.insert(30);
	s.insert(80);
	s.insert(40);
	s.insert(10);
	s.insert(70);
	s.insert(90);

	for (auto iter = s.begin(); iter != s.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';

	set<int>::iterator iter_lower = s.lower_bound(30);
	set<int>::iterator iter_upper = s.upper_bound(30);
	cout << *iter_lower << '\n';
	cout << *iter_upper << '\n';

	iter_lower = s.lower_bound(55);
	iter_upper = s.upper_bound(55);
	// lower_bound() == upper_bound() 이면
	// 찾는 원소가 존재하지 않는다는 것을 의미함.
	if (iter_lower != iter_upper)
		cout << "55 exist\n";
	else
		cout << "55 not exist\n";

	return 0;
}
10 30 40 50 70 80 90
30
40
55 not exist

equal_range()

위에서 연습했듯이 lower_bound와 upper_bound 쌍을 리턴해준다.

#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int> s;

	s.insert(50);
	s.insert(30);
	s.insert(80);
	s.insert(40);
	s.insert(10);
	s.insert(70);
	s.insert(90);

	for (auto iter = s.begin(); iter != s.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';

	// equal_range 는 lower_bound() 와 upper_bound() 쌍으로 반환
	auto iter = s.equal_range(30);
	cout << *iter.first << '\n';
	cout << *iter.second << '\n';

	iter = s.equal_range(55);
	if (iter.first != iter.second)
		cout << "55 exist\n";
	else
		cout << "55 not exist\n";

	return 0;
}
10 30 40 50 70 80 90
30
40
55 not exist

다양하게 연습해보기

#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int> s{ 1,2,3,4,5 };

	s.insert(3); // 1 2 3 4 5
	s.insert(5); // 1 2 3 4 5
	s.insert(7); // 1 2 3 4 5 7
	s.insert(-1);// -1 1 2 3 4 5 7

	if (s.find(7) != s.end())
		cout << "7 found!\n";
	else
		cout << "7 not found!\n";

	cout << "s.empty() : " << s.empty() << endl;
	cout << "s.size() : " << s.size() << endl;
	cout << "s.max_size() : " << s.max_size() << endl << endl;

	set<int> s2 = { 1,2,3,4,5,6,7,8,9,10 };
	pair<set<int>::iterator, set<int>::iterator> iter = s2.equal_range(4);
	cout << "s2.equal_range(4) : " << *iter.first << ' ' << *iter.second << endl;

	set<int>::iterator lower_iter = s2.lower_bound(3);
	set<int>::iterator upper_iter = s2.upper_bound(3);
	cout << "lower_iter : " << *lower_iter << endl;
	cout << "upper_iter : " << *upper_iter << endl;

	// 3 ~ 7 삭제
	lower_iter = s2.lower_bound(3);
	upper_iter = s2.upper_bound(7);
	s2.erase(lower_iter, upper_iter);
	for (int n : s2) cout << n << ' ';
	cout << endl << endl;

	set<int> s3;

	s3.emplace(10);
	s3.emplace(20);
	s3.emplace(-1);
	s3.emplace(-5);
	s3.emplace(7);

	set<int>::iterator s3_iter = s3.emplace_hint(s3.end(), 21); // 삽입 속도 빠름
	s3.emplace_hint(s3_iter, 1); // 삽입 속도 느림
	for (int n : s3) cout << n << ' ';
	cout << endl << endl;

	// insert와 emplace 반환값은 pair<iterator, bool>
	// pair.first 삽입한 위치에 대한 iterator
	// pair.second 삽입 성공 여부에 대한 bool
	set<int> s4;
	pair<set<int>::iterator, bool> chk = s4.insert(10);
	if (chk.second)
		cout << "10 insert success!\n";
	else
		cout << "10 insert failure!\n";

	set<pair<int, int>> s5;
	s5.insert({ 2,3 });
	s5.insert({ 1,5 });
	s5.insert({ 1,2 });
	s5.emplace(5, 6);
	for (auto n : s5) cout << n.first << ' ' << n.second << endl;

	return 0;
}
7 found!
s.empty() : 0
s.size() : 7
s.max_size() : 214748364

s2.equal_range(4) : 4 5
lower_iter : 3
upper_iter : 4
1 2 8 9 10

-5 -1 1 7 10 20 21

10 insert success!
1 2
1 5
2 3
5 6
저작자표시 비영리 변경금지

'CS > Data Structure' 카테고리의 다른 글

[C++] multimap  (0) 2021.04.28
[C++] map  (0) 2021.04.28
[C++] unordered_set  (0) 2021.04.12
[C++] multiset  (0) 2021.04.12
스택의 응용 - 후위 표기식  (0) 2021.04.09

'CS/Data Structure'의 다른글

  • 현재글[C++] set

관련글

티스토리툴바