[STL] 10. std::set

std::set은 C++ 표준 라이브러리(STL)에서 제공하는 중복을 허용하지 않는 정렬된 집합을 나타내는 컨테이너다. 

<set> 헤더 파일에 정의되어 있으며 내부적으로 레드-블랙 트리와 같은 자료 구조를 기반으로 구현되어 있다.

 

 

특징

 

1. 중복을 허용하지 않음 : 각 요소는 유일해야 하며, 중복된 값을 저장하지 않는다.

2. 자동 정렬 : 오름차순으로 요소들이 정렬되어 저장된다.

3. 이진 탐색 트리 기반 : 대부분의 구현에서는 이진 탐색 트리나 비슷한 데이터 구조를 기반으로 하여

빠른 삽입, 삭제, 검색을 지원한다. (이진 탐색 트리의 일종인 레드-블랙 트리로 구현되어 있음)

4. 반복자(iterator) 제공 : begin()과 end()를 통해 반복자를 얻을 수 있어서 반복문을 통해 접근할 수 있다.

5. 검색, 삽입, 삭제가 빠름 : 중복을 허용하지 않고 정렬된 특성을 가지기 때문에 검색이나 삽입, 삭제 연산이 효율적임

 

 

사용법

 

#include <iostream>
#include <set>

int main() {

	std::set<int> nums { 4, 5, 3, 1, 2 }; //오름차순 정렬
	std::set<int, std::greater<>> se_nums { 4, 5, 3, 1, 2}; //내림차순 정렬

	//데이터 삽입
	nums.insert(10);
	nums.insert(8);

	se_nums.insert(10);
	se_nums.insert(8);

	//데이터 삭제
	nums.erase(5);
	se_nums.erase(5);

	//데이터 조회
	if (nums.find(5) != nums.end()) {

		std::cout << "5를 찾았습니다!" << std::endl;
	}

	if (se_nums.find(3) != se_nums.end()) {

		std::cout << "3을 찾았습니다!" << std::endl;
	}

	//데이터 출력
	for (const auto& e : nums) {

		std::cout << e << ", ";
	}

	std::cout << std::endl;

	for (const auto& e : se_nums) {

		std::cout << e << ", ";
	}
}

 

또는 std::pair를 사용해 다음과 같이 key와 value를 저장할 수도 있다.

 

#include <iostream>
#include <set>
#include <string>

int main() {

	std::set<std::pair<std::string, int>> person {
	
		{"Amy", 30}, {"Noah", 21}, {"Olivia", 41}
	};

	person.insert({"Sophia", 15}); //중괄호를 사용해 값을 넣는 방법
	person.insert(std::make_pair("George", 35)); //make_pair를 사용해 값을 넣는 방법

	if (person.find({"Noah",21}) != person.end()) {
	
		std::cout << "Noah를 발견했습니다." << std::endl;
	}

	person.erase({"Noah",21});

	for (const auto& p : person) {

		std::cout << p.first << "(" << p.second << ")" << std::endl;
	}
}

 

 

주요 멤버 함수와 기능

 

멤버 함수	설명	시간 복잡도
begin(), end() rbegin(), rend()	순방향 및 역방향 반복자 반환	O(1)
insert()	(중복되지 않는) 새로운 원소 삽입 최신 C++에서는 emplace()도 사용할 수 있음	O(log n)
erase()	특정 원소를 삭제	O(log n)
find()	특정 키 값을 갖는 원소를 찾아 반복자를 반환. 원소를 찾지 못하면 end()에 해당하는 반복자를 반환한다.	O(log n)
clear()	모든 원소를 삭제	O(n)
size()	원소의 개수를 반환	O(1)
empty()	set이 비어 있다면 true를 반환.	O(1)