STL에서 이진 트리의 구체적인 구현은 고유한 원소들의 정렬된 집합을 지원하는 set 구조로 제공됩니다.
#기본 연산
set<T> 구조는 비교 연산자가 구현된 모든 타입에 대해 선언할 수 있습니다. 특히 페어와 튜플의 경우 비교 연산자가 사전식 정렬로 자동 구현되어 있습니다.
set<int> s;
s.insert(3); // s = {3}
s.insert(2); // s = {2, 3}
s.size(); // вернет |s| = 2
s.insert(3); // 3 не будет добавлено ещё раз, так как уже присутствует в множестве
s.size(); // |s| = 2
// присутствует ли в множестве элемент:
s.count(3); // вернет 1
s.count(5); // вернет 0
s.erase(3); // s = {2}
s.insert(6); // s = {2, 6}
set은 균형 이진 탐색 트리, 구체적으로는 레드-블랙 트리로 구현되어 있으므로, 원소에 대한 모든 연산은 $O(\log n)$에 동작합니다.
#반복자
또한 set은 모든 STL 컨테이너와 마찬가지로 반복자를 지원합니다.
set의 시작(가장 작은 원소)은 .begin()으로, 끝은 .end()로 얻을 수 있습니다. .end()는 모든 반복자와 마찬가지로 반열린 구간의 끝, 즉 마지막 원소 다음에 오는 존재하지 않는 원소를 가리킨다는 점에 유의하십시오.
auto it = s.find(2); // возвращает итератор на элемент или `end`, если элемента нет
++it; // найти следующий элемент
int x = *it; // x = 6
s.lower_bound(1); // вернет 2, так как это первый элемент >= 1
s.upper_bound(2); // вернет 6, так как это первый элемент > 2
auto it = s.upper_bound(10);
if (it == s.end()) {
// аккуратно: если разыменуете it, получите undefined behavior!
}
// вывод всех элементов сета в порядке возрастания с использованием итераторов
for (auto it = s.begin(); it != s.end(); ++it)
cout << *it << " ";
// но для таких целей лучше использовать range-based for loop
for (int x : s)
cout << x << " ";
반복자의 증가와 감소는 로그 시간에 동작합니다.
#관련 구조
STL에는 비슷한 기능을 가진 구조가 몇 가지 있습니다.
map은 키에 값을 연관시키며, 마치 무한 배열처럼m[x] = y와 같은 방식으로 값을 다룰 수 있게 해 줍니다.multiset은 중복 원소를 지원합니다. 이 자료구조의.count(x)는 단순히 0 또는 1이 아니라 주어진 키를 가진 원소의 개수를 반환합니다. 이는 원소의 개수를 값으로 저장하는map으로 구현할 수 있습니다.multimap은 키 하나에 대해 하나의 값 대신 여러 개의 서로 다른 값을 반환하며, 그 값들을 순회할 수 있게 해 줍니다(사용하는 것과 같습니다). 이는map<A, vector<B>>로 구현할 수 있습니다.
또한 이 모든 컨테이너에는 트리 대신 해시 테이블로 동작하는 대응 컨테이너가 있습니다: unordered_set, unordered_map, unordered_multiset, unordered_multimap. 이들에서는 탐색, 삭제, 삽입이 평균적으로 상수 시간에 동작하지만, lower_bound와 순서대로 순회하는 기능은 없습니다.