[C++ Data Structure] set

set

#include <set>로 사용할 수 있습니다.

키만 저장가능한 연관 컨테이너입니다.

std::set은 내부적으로 레드 블랙 트리(Red-Black Tree)를 사용해 데이터를 저장합니다.

값은 중복될 수 없고, 중복된 값을 삽입하려고 하면 삽입이 무시됩니다.
중복 키를 허용하려면 std::multiset을 사용해야 합니다.

기본적으로 오름차순으로 정렬한 상태에서 데이터가 저장됩니다.
사용자 정의 비교 함수로 정렬 기준을 변경할 수도 있습니다.

효율적으로 데이터 검색, 삽입, 삭제가 가능합니다.
검색, 삽입, 삭제 작업은 $O(log \ n)$의 시간 복잡도를 가집니다.

인덱스를 이용한 직접적인 접근이 불가능합니다.
대신 반복자(iterator)를 통해 접근할 수 있습니다.

다양한 데이터 타입을 지원하며, 사용자 정의 타입도 사용할 수 있습니다.

초기화

선언은 다음과 같습니다.

std::set<[DataType]> [변수이름]

// 기본 생성 및 초기화 없이 정의
std::set<int> s;
// 오른쪽 변수 값으로 초기화
std::set<int> s2 = {1, 2, 3, 4, 5};
// 다른 set를 기반으로 복사 초기화
std::set<int> s3(s2);
// 다른 컨테이너 기반으로 초기화
std::vector<int> vec = {1, 2, 3, 4, 5};
std::set<int> s4(vec.begin(), vec.end());

주요 함수

insert

새로운 요소를 삽입하거나 기존 객체를 복사하거나 이동합니다.

삽입하는 값이 복사 또는 이동 할 때 복사 또는 이동 생성자가 필요합니다.

삽입 결과에 따라 std::pair<iterator, bool>형태로 반환합니다. true라면 새 요소가 삽입된 것이고, false라면 이미 존재하는 키로 인해 삽입이 실패한 것입니다.

insert(value);
insert(first, last);

std::set<int> s;
s.insert(10);   // 삽입 성공
s.insert(10);   // 삽입 실패 (이미 존재)

// 기존 set을 다른 set에 복사
std::set<int> copiedSet;
copiedSet.insert(s.begin(), s.end());

$O(log n)$의 시간 복잡도를 가집니다.

emplace

insert함수와 비슷하지만 요소를 “직접 생성”하여 추가합니다.

복사나 이동 연산을 피하고 싶을 때 사용합니다.
객체 생성 과정에서 성능 최적화가 중요한 경우 사용합니다.

emplace은 객체를 생성하는 데 필요한 정확한 인자를 전달해야 합니다.
생성자가 없는 객체나 초기화 인자가 잘못된 경우 컴파일 에러가 발생할 수 있습니다.

삽입 결과에 따라 std::pair<iterator, bool>형태로 반환합니다.
true라면 새 요소가 삽입된 것이고, false라면 이미 존재하는 키로 인해 삽입이 실패한 것입니다.

emplace(value);
emplace(first, last);

std::set<int> s;
s.emplace(10);

// std::pair<int, int>(10, 20)를 직접 생성
std::set<std::pair<int, int>> s;
s.emplace(10, 20);

$O(log n)$의 시간 복잡도를 가집니다.

swap

두 std::set객체 간에 요소를 서로 교환합니다.

swap(other);

std::set<int> s1 = {10, 20};
std::set<int> s2 = {30, 40};
s1.swap(s2);  // s1은 {30, 40}, s2는 {10, 20}

erase

특정 위치나 범위의 요소를 제거합니다.

erase(value);
erase(pos);
erase(first, last);

s.erase(20);    // 20 삭제
s.erase(s.begin()); // 0번 위치에 값 제거
s.erase(s.begin() + 1); // 1번 위치에 값 제거
s.erase(s.begin(), s.begin() + 2);  // 0번 위치부터 2번 위치 값 제거

clear

모든 요소를 제거합니다.

요소만 제거하며, 메모리는 남아있습니다.
즉, size만 줄어들고 capacity는 변하지 않습니다.

std::set<int> s = {10, 20, 30};
s.clear();  // 모든 요소 제거
std::cout << s.size() << std::endl;  // 0

find

특정 값의 요소를 찾아 해당 요소를 가리키는 반복자를 반환합니다.
요소가 없으면 end()를 반환합니다.

std::set<int> s = {10, 20, 30};
auto it = s.find(20);
if (it != s.end())
{
    std::cout << *it << std::endl; // 20
}

count

특정 요소가 존재하는지 확인해 0 또는 1을 반환합니다.

count(value);

std::set<int> s = {10, 20, 30};
std::cout << s.count(20) << std::endl;  // 1
std::cout << s.count(40) << std::endl;  // 0

lower_bound

주어진 값 이상의 첫 번째 요소의 반복자를 반환합니다.
주어진 값 이상의 요소가 없으면 end()를 반환합니다.

lower_bound(value);

std::set<int> s = {10, 20, 30, 40};
auto it = s.lower_bound(20);  // 20을 가리키는 반복자
std::cout << *it << std::endl;  // 20

upper_bound

주어진 값 보다 큰 첫 번째 요소의 반복자를 반환합니다.
주어진 값 초과의 요소가 없으면 end()를 반환합니다.

upper_bound(value);

std::set<int> s = {10, 20, 30, 40};
auto it = s.upper_bound(20);  // 30을 가리키는 반복자
std::cout << *it << std::endl;  // 30

equal_range

지정된 값 이상의 값 중 가장 가까운 요소의 반복자와 그 다음 요소의 반복자(std::pair<iterator, iterator>)를 반환합니다.

equal_range(value);

std::set<int> s = {10, 20, 30, 40};
auto range = s.equal_range(25);
std::cout << *range.first << ", " << *range.second << std::endl;  // 30, 40

size

현재 저장된 요소의 개수를 반환합니다.

반환 자료형은 size_t입니다.

std::set<int> s = {10, 20, 30};
std::cout << "Size: " << s.size() << std::endl;  // 3

empty

std::set이 비었으면 true값을 반환하고, 그렇지 않으면 false를 반환합니다.

std::set<int> s;
std::cout << s.empty() << std::endl;  // true
s.insert(10);
std::cout << s.empty() << std::endl;  // false

begin & end

begin은 첫 번째 요소를 가리키는 반복자를 반환합니다.
end는 마지막 요소의 바로 다음 위치를 가리키는 반복자를 반환합니다.

std::set의 요소를 순회하거나 반복자(Iterator)를 사용할 때 사용됩니다.

std::set<int> s = {20, 10, 30};
for (auto it = s.begin(); it != s.end(); ++it)
{
    std::cout << *it << " "; // 10 20 30
}

rbegin & rend

rbegin은 마지막 요소를 가리키는 역방향 반복자를 반환합니다.
rend는 첫 번째 요소의 이전 위치를 가리키는 역방향 반복자를 반환합니다.

std::set의 요소를 순회하거나 반복자(Iterator)를 사용할 때 사용됩니다.

std::set<int> s = {10, 20, 30};
for (auto it = s.rbegin(); it != s.rend(); ++it)
{
    std::cout << *it << " "; // 30 20 10
}

cbegin & cend

cbegin은 첫 번째 요소를 가리키는 상수 반복자를 반환합니다.
cend는 마지막 요소의 바로 다음 위치를 가리키는 상수 반복자를 반환합니다.

std::set의 요소를 수정하지 않고, 순회하거나 반복자(Iterator)를 사용할 때 사용됩니다.

std::set<int> s = {10, 20, 30};
for (auto it = s.cbegin(); it != s.cend(); ++it)
{
    std::cout << *it << " "; // 10 20 30
}