std::set: 유일한 요소의 정렬된 집합

std::set은 중복을 허용하지 않는 키(Key)들의 집합을 관리하는 컨테이너입니다. 내부적으로 주로 레드-블랙 트리(Red-Black Tree) 구조로 구현되어 있어, 삽입, 삭제, 탐색 작업 시 O(log N)의 시간 복잡도를 보장합니다. 만약 중복된 값을 허용해야 한다면 std::multiset을 대신 사용하면 됩니다.

주요 제어 메서드

• insert(val): 새로운 원소를 추가합니다. std::pair<iterator, bool>을 반환하며, 이미 존재하는 원소인 경우 bool 값은 false가 됩니다.
• erase(val): 해당 값을 가진 요소를 모두 제거합니다.
• erase(iterator): 특정 위치의 요소를 제거합니다.
• clear(): 모든 요소를 삭제하여 컨테이너를 비웁니다.

데이터 탐색 및 정보 확인

연관 컨테이너는 효율적인 탐색을 위해 다음과 같은 멤버 함수를 제공합니다.

• find(val): 값이 존재하면 해당 위치의 반복자를, 없으면 end()를 반환합니다.
• count(val): 특정 값의 존재 여부를 0 또는 1로 반환합니다. (multiset의 경우 개수 반환)
• lower_bound(val): val보다 크거나 같은 첫 번째 원소의 위치를 반환합니다.
• upper_bound(val): val보다 큰 첫 번째 원소의 위치를 반환합니다.

주의사항: std::lower_bound와 같은 알고리즘 헤더의 함수를 set에 사용하면 O(N)의 시간이 걸릴 수 있으므로, 반드시 컨테이너의 멤버 함수인 set::lower_bound를 사용해야 O(log N)의 효율을 얻을 수 있습니다.

코드 예시: 그리디 알고리즘에서의 활용

#include <iostream>
#include <set>

void findAndProcess(std::set<int>& resourcePool, int threshold) {
    // threshold 이상의 값을 가진 요소 중 가장 작은 것을 탐색
    auto targetPos = resourcePool.lower_bound(threshold);

    if (targetPos != resourcePool.end()) {
        std::cout << "조건을 만족하는 요소 발견: " << *targetPos << std::endl;
        resourcePool.erase(targetPos); // 사용 후 제거
    } else {
        std::cout << "조건에 맞는 요소가 없습니다." << std::endl;
    }
}

std::map: 키-값 쌍의 연관 배열

std::map은 고유한 키(Key)와 그에 대응하는 값(Value)을 한 쌍으로 저장하는 컨테이너입니다. 배열처럼 인덱스를 통해 값에 접근할 수 있지만, 정수뿐만 아니라 사용자 정의 타입이나 문자열 등을 키로 사용할 수 있다는 장점이 있습니다.

삽입과 접근 시의 특징

operator[]를 사용하여 데이터에 쉽게 접근할 수 있습니다. 하지만 주의할 점은, 존재하지 않는 키에 대해 대괄호 연산자를 사용하면 기본값이 삽입된다는 것입니다. 단순 확인 용도라면 find() 메서드를 권장합니다.

#include <map>
#include <string>

void manageScores() {
    std::map<std::string, int> scoreBoard;

    // 데이터 삽입
    scoreBoard["Alice"] = 95;
    scoreBoard.insert({"Bob", 88});

    // 안전한 탐색
    std::string name = "Charlie";
    if (scoreBoard.find(name) != scoreBoard.end()) {
        int score = scoreBoard[name];
    }
}

컨테이너 순회 방식

반복자(Iterator)를 사용하여 모든 요소를 정렬된 순서대로 순회할 수 있습니다. C++11 이후부터는 범위 기반 for 문을 통해 더욱 간결하게 작성이 가능합니다.

std::set<int> numbers = {10, 30, 20};
for (const auto& num : numbers) {
    std::cout << num << " "; // 10 20 30 순으로 출력
}

std::map<std::string, int> items = {{"Apple", 5}, {"Banana", 3}};
for (const auto& [name, count] : items) { // C++17 구조화된 바인딩
    std::cout << name << ": " << count << std::endl;
}

정렬 기준 커스텀 설정

기본적으로 오름차순 정렬이 수행되지만, 펑터(Functor)를 정의하여 정렬 방식을 변경할 수 있습니다. 예를 들어, 내림차순으로 정렬되는 set은 다음과 같이 선언합니다.

struct DescendingOrder {
    bool operator()(const int& a, const int& b) const {
        return a > b;
    }
};

std::set<int, DescendingOrder> descSet;