Nagie's DevStory
[STL] 10. std::set 본문
728x90
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) |
728x90
Comments