목차

• set 구조
• map 구조
• Binary Search Tree
• Iterator
• set 문법

Set / Map 구조

• Binary Search Tree 형태
• Red-Black Tree

Space O(n)
Search O(log n)
Insert O(log n)
Delete O(log n)

• averager, worst case 모두

Iterator

• 노드 지워지지 않는 한, iterator는 유효
• 양방향 iterator
• erase 되면 iterator 무효화됨 erase()는 다음 iterator 반환

 // 조건에 따라 여러 개의 요소 삭제 (예: 짝수 키 삭제)
    for (auto it = m.begin(); it != m.end(); ) {
        if (it->first % 2 == 0) {
            // 요소 삭제 후, 삭제된 요소 다음을 가리키는 이터레이터 반환
            it = m.erase(it);
        } else {
            ++it; // 삭제하지 않는 경우 다음 요소로 이동
        }
    }

set 문법

O(1)

• s.begin(), s. end()
• s.empty()
• s.clear()
• s.size()
• s.erase() - iterator 이용

O(log n)

• s.count()
• s.find
• s.lower_bound, s.upper_bound()
• s.insert() - key를 이용해서
• s.erase() - key를 이용

iterator 이용한 여러개 적용

• s.insert(first, last) -- O(clogn)
• s.erase(first, last) -- O(n)

Predefined Function & Compare Function

less<T>
greater<T>
//
struct AbsComp {
bool operator()(const int &l, const int &r) const {
if(abs(l) != abs(r)) return abs(l) < abs(r)
return l < r;
}
};

// Custom Data type의 경우 직젖 operator overloading 해줘야함
struct Data {
int a, b, c;
bool operator<(const Data& r) const {
return a < r.a;
}
};

Map 문법

O(1)

• m.begin(), m.end()
• m[T k]
• m.empty
• m.size()
• m.erase() - iterator로 삭제

O(log n)

• m[T k] = v
• m.count()
• m.find()
• m.lower_bound(), m.,upper_bound()
• m.insert({T A, T B})
• m.erase(T k) - key로 삭제

O(n)

• m.clear()

iterator

• m.erase(first, last) -- O(c)
• insert(first, last) -- O(c logn)

Multi Set / Map

• equal_range(x)

pair<iterator, iterator> ret = m.equal_range;
m.find() // 최초 원소
m.erase(x) // 모두 제거
m.erase(m.find(x)) // 최초 하나 제거