[C++] Associative containers (set, map, multiset, multimap)

 

 

Associative Containers

• 데이터를 특정 기준에 따라 정렬된 상태로 유지하는 자료구조
  • 삽입되는 데이터가 항상 자동으로 정렬된 상태를 유지하며, 이를 통해 효율적인 검색, 삽입, 삭제 연산을 제공
• key - value 구조를 통해 요소에 빠른 접근은 가능하지만 삽입되는 요소의 위치를 지정할 수 없음
• Red-Black Tree를 기반으로 하고 데이터의 추가/삭제/접근의 시간복잡도가 O(log n)

 

std::set

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {3, 1, 4, 1, 5, 9};
    
    // 요소 삽입
    mySet.insert(2);

    // 요소 삭제
    mySet.erase(4);

    // 요소 검색
    if (mySet.find(3) != mySet.end()) {
        std::cout << "3 is in the set" << std::endl;
    }

    // 요소 출력
    for (const int& num : mySet) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

 

• 특징:
  • 중복된 요소를 허용하지 않는 정렬된 연관 컨테이너
  • 데이터 자체를 key로 사용
    • 저장하는 값이 key가 되고 오름차순으로 정렬
  • 요소는 자동으로 정렬
  • 요소의 삽입, 삭제, 검색이 평균적으로 O(log n)의 시간 복잡도를 가짐
• 사용 사례:
  • 중복되지 않는 요소들을 저장하고자 할 때
  • 정렬된 상태로 데이터가 유지되어야 할 때
  • 데이터의 존재 유무를 파악하는데 유용
• 멤버 함수
  • begin(): 첫 번째 요소에 대한 반복자를 반환
  • end(): 마지막 요소 다음에 대한 반복자를 반환
  • cbegin(): 첫 번째 요소에 대한 상수 반복자를 반환
  • cend(): 마지막 요소 다음에 대한 상수 반복자를 반환
  • rbegin(): 마지막 요소에 대한 역방향 반복자를 반환
  • rend(): 첫 번째 요소 이전에 대한 역방향 반복자를 반환
  • crbegin(): 마지막 요소에 대한 상수 역방향 반복자를 반환
  • crend(): 첫 번째 요소 이전에 대한 상수 역방향 반복자를 반환
  • empty(): set이 비어 있는지 확인
  • size(): set의 요소 개수를 반환
  • max_size(): set이 가질 수 있는 최대 요소 개수를 반환
  • clear(): set의 모든 요소를 제거
  • insert(const T& value): 요소를 삽입
  • insert(T&& value): 요소를 이동하여 삽입
  • insert(std::initializer_list<T> ilist): 초기화 리스트의 요소들을 삽입
  • erase(iterator pos): 지정된 위치의 요소를 제거
  • erase(const T& value): 주어진 값과 동일한 요소를 제거
  • swap(set& other): 다른 set과 요소를 교환
  • find(const T& value): 주어진 값과 동일한 요소를 찾습니다.
  • count(const T& value): 주어진 값과 동일한 요소의 개수를 반환합니다.
  • lower_bound(const T& value): 주어진 값보다 크거나 같은 첫 번째 요소의 반복자를 반환
  • upper_bound(const T& value): 주어진 값보다 큰 첫 번째 요소의 반복자를 반환
  • equal_range(const T& value): 주어진 값과 동일한 요소의 범위를 반환

 

std::map

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    // 요소 삽입
    myMap[4] = "four";

    // 요소 삭제
    myMap.erase(2);

    // 요소 검색
    if (myMap.find(3) != myMap.end()) {
        std::cout << "Key 3 has value: " << myMap[3] << std::endl;
    }

    // 요소 출력
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

 

 

• 특징:
  • 키-값 쌍을 저장하는 정렬된 연관 컨테이너
  • 각 키는 유일하며, 키를 기준으로 자동으로 정렬
  • 하나의 key에 하나의 value만 연결
  • 키의 삽입, 삭제, 검색이 평균적으로 O(log n)의 시간 복잡도를 가짐
• 사용 사례:
  • 키와 값의 쌍을 저장하고, 키를 기준으로 정렬된 상태를 유지하고자 할 때.
  • 빠른 키 기반 검색이 필요할 때.
• 멤버 함수
  • empty(): map이 비어 있는지 확인
  • size(): map의 요소 개수를 반환
  • max_size(): map이 가질 수 있는 최대 요소 개수를 반환
  • clear(): map의 모든 요소를 제거
  • insert(const value_type& value): 요소를 삽입
  • insert(value_type&& value): 요소를 이동하여 삽입
  • insert(std::initializer_list<value_type> ilist): 초기화 리스트의 요소들을 삽입
  • erase(iterator pos): 지정된 위치의 요소를 제거
  • erase(const key_type& key): 주어진 키와 동일한 요소를 제거
  • swap(map& other): 다른 map과 요소를 교환
  • find(const key_type& key): 주어진 키와 동일한 요소를 찾음
  • count(const key_type& key): 주어진 키와 동일한 요소의 개수를 반환
  • lower_bound(const key_type& key): 주어진 키보다 크거나 같은 첫 번째 요소의 반복자를 반환
  • upper_bound(const key_type& key): 주어진 키보다 큰 첫 번째 요소의 반복자를 반환
  • equal_range(const key_type& key): 주어진 키와 동일한 요소의 범위를 반환

 

std::set vs std::map

단순히 데이터를 정렬 상태로 유지하고 존재 유무만 알고 싶다면 std::set

(key, value) 데이터 쌍을 key를 기준으로 정렬하고 싶다면 std::map

 

std::multiset

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    // 요소 삽입
    myMap[4] = "four";

    // 요소 삭제
    myMap.erase(2);

    // 요소 검색
    if (myMap.find(3) != myMap.end()) {
        std::cout << "Key 3 has value: " << myMap[3] << std::endl;
    }

    // 요소 출력
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

 

 

• 특징:
  • 중복된 요소를 허용하는 정렬된 연관 컨테이너
  • 요소는 자동으로 정렬
  • 요소의 삽입, 삭제, 검색이 평균적으로 O(log n)의 시간 복잡도를 가짐
• 사용 사례:
  • 중복되는 요소를 저장해야 할 때
  • 정렬된 상태로 데이터가 유지되어야 할 때

 

std::multimap

#include <iostream>
#include <map>

int main() {
    std::multimap<int, std::string> myMultimap = {{1, "one"}, {2, "two"}, {3, "three"}};

    // 요소 삽입
    myMultimap.insert({2, "second two"});

    // 요소 삭제
    myMultimap.erase(2); // 키 2에 해당하는 모든 요소 삭제

    // 요소 검색
    auto range = myMultimap.equal_range(3);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << "Key 3 has value: " << it->second << std::endl;
    }

    // 요소 출력
    for (const auto& pair : myMultimap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

 

 

•  

 

• 특징:
  • 키-값 쌍을 저장하는 정렬된 연관 컨테이너로, 동일한 키를 가진 여러 값을 허용
  • 키를 기준으로 자동으로 정렬
  • 키의 삽입, 삭제, 검색이 평균적으로 O(log n)의 시간 복잡도를 가짐
• 사용 사례:
  • 동일한 키에 대해 여러 값을 저장해야 할 때
  • 정렬된 상태로 키-값 쌍을 유지하고자 할 때