C++ STL Associative Containers (연관 컨테이너)

Seongcheol Jeon·2024년 11월 18일

C++ STL Associative Containers C++ map C++ multimap C++ multiset c++ set

CPP

목록 보기

24/47

연관 컨테이너

연관 컨테이너는 데이터를 저장하고 검색할 때에 사용한다. 특정 키(key)를 사용하여 데이터를 효율적으로 검색할 수 있다.

연관 컨테이너의 내부 구조는 트리나 해시 테이블과 같은 최적화된 데이터 구조를 사용하므로 검색 작업의 시간 복잡도가 일반적으로 O(log n) 또는 O(1)에 가깝다. 😆

이러한 구조 덕에 대량의 데이터에서도 빠르게 검색할 수 있으며, 실시간 또는 반응형 시스템에서 매우 유용하다. C++ 표준 템플릿 라이브러리에서 제공하는 주요 연관 컨테이너는 다음과 같다.

컨테이너	헤더	정렬	특징
set	<set>	O	중복된 값 허용하지 않음
multiset	<set>	O	중복된 값 허용
map	<map>	O	키와 값이 서로 쌍으로 구성
multimap	<map>	O	중복된 키 허용

Set Container

set (std::set)

연관 컨테이너 중 가장 기본인 std::set을 살펴보자. set은 고유한 값을 정렬된 순서로 저장한다. set 컨테이너는 다음처럼 선언한다.

std::set<데이터_형식> 객체_이름;

set 컨테이너가 제공하는 주요 함수들을 살펴보자. 먼저 set에 데이터를 넣을 때는 insert 함수를 사용하며 제거할 때는 erase나 clear 함수를 사용한다. erase 함수는 set에서 특정 값을, clear 함수는 모든 값을 제거한다.

그리고 find 함수는 set에서 특정 값을 검색할 때 사용한다. 만약 해당 값이 없으면 set::end를 반환한다. count 함수는 set에서 특정 값의 개수를 반환하는데, set은 중복된 값을 허용하지 않으므로 반환값은 0이나 1이다. 반면 size 함수는 전체 값의 개수를 반환한다.

begin() 함수는 set에서 첫 번째 데이터가 있는 곳을 가리키는 반복자를 반환하고, end() 함수는 마지막 데이터가 있는 곳의 다음을 가리키는 반복자(유효한 값이 아님)를 반환한다.

set 컨테이너가 제공하는 함수를 사용하는 예를 살펴보자.

#include <iostream>
#include <set>

using std::cout;
using std::endl;


int main()
{
    std::set<int> mySet;

    // 값 삽입
    mySet.insert(5);
    mySet.insert(9);
    mySet.insert(3);

    // 값 5가 셋에 있는지 확인
    if (mySet.find(5) != mySet.end()) {
        cout << "5는 set에 존재합니다." << endl;
    }

    // set을 순회하며 값 출력
    for (auto it = mySet.begin(); it != mySet.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;

    // set의 크기 출력
    int size = mySet.size();
    cout << "set의 크기: " << size << endl;

    return 0;
}

실행 결과

5는 set에 존재합니다.
3 5 9
set의 크기: 3

set은 연관 컨테이너에 속하지만 내부적으로는 이진 탐색 트리를 사용하여 원소를 저장하고 정렬된 순서를 유지하는 정렬 컨테이너(sorted container)이기도 하다. 따라서 set에 원소를 삽입하면 자동으로 정렬되어 저장된다.

이때 정렬은 오름차순이 기본이지만, 사용자 정의 형식(클래스나 구조체)의 원소를 저장할 때는 해당 형식에 오버로딩된 비교 연산자(operator <)에 따라 정렬 순서가 결정된다.

이처럼 set 컨테이너는 데이터를 항상 정렬된 상태로 유지하므로 검색을 효율적으로 수행할 수 있다. 이진 탐색 트리의 특성 덕분에 삽입, 삭제, 검색 작업의 시간 복잡도가 O(log n)에 가깝다.

multiset (std::multiset)

std::multiset도 std::set처럼 정렬된 set 자료구조를 구현하는 연관 컨테이너이지만, 중복된 값을 포함한다는 차이가 있다. 즉, multiset 컨테이너에는 중복된 값을 저장할 수 있다.

다음 코드는 중복된 값을 허용하지 않는 set에 중복된 값을 삽입하는 예이다.

#include <iostream>
#include <set>

using std::cout;
using std::endl;


int main()
{
    std::set<int> mySet;

    mySet.insert(5);
    mySet.insert(3);
    mySet.insert(5); // 중복된 값. 저장되지 않음.

    cout << "set size: " << mySet.size() << endl;

    return 0;
}

실행 결과

set size: 2

multiset 컨테이너를 선언하는 방법은 다음과 같다.

std::multiset<데이터_형식> 객체_이름;

multiset 컨테이너가 제공하는 함수는 set 컨테이너와 같다. 다만 erase 함수로 데이터를 제거할 때 중복된 값이 있다면 해당 값을 모두 제거한다는 정도의 차이만 있을 뿐이다.

위의 set 컨테이너 예제를 multiset 컨테이너로 바꿔서 해보자.

#include <iostream>
#include <set>

using std::cout;
using std::endl;


int main()
{
    std::multiset<int> myMultiset;

    myMultiset.insert(5);
    myMultiset.insert(3);
    myMultiset.insert(5); // 중복된 값도 저장됨.

    // 특정 값의 개수 출력
    int count = myMultiset.count(5);
    cout << "저장되어 있는 5의 개수: " << count << endl;

    // 멀티 셋을 순회하며 값 출력
    for (auto it = myMultiset.begin(); it != myMultiset.end(); it++) {
        cout << *it << " ";
    }

    return 0;
}

실행 결과

저장되어 있는 5의 개수: 2
3 5 5

Map Container

map (std::map)

std::map은 키-값(key-value) 쌍을 저장하는 연관 컨테이너이다. 각 키는 고유해야 하며 키를 기준으로 정렬된 순서로 저장된다.

맵 컨테이너는 특정 키에 연관된 값을 검색하고, 값을 추가, 제거, 수정하는 등의 작업에 주로 사용되며 키-값 쌍을 관리하고자 할 때 유용하다.

std::map<std::키_형식, 값_형식> 객체_이름;

예를 들어 학생의 이름과 그에 해당하는 점수로 구성된 키-값 쌍을 맵 컨테이너로 만든다고 가정해보자. 이름은 문장열이므로 string 형식으로, 값은 정수이므로 int 형식으로 선언할 수 있다.

std::map<std::string, int> scores;

맵에 키-값 쌍을 삽입할 때는 insert 함수를 이용한다. 이때 기와 값을 묶어 std::pair 객체로 만들어 주는 std::make_pair 함수를 사용할 수 있다.
make_pair 함수는 템플릿 매개변수를 이용하므로 키-값 쌍으로 묶을 원소의 데이터 형식을 따로 지정하지 않아도 된다.

예를 들어 다음 코드는 std::make_pair 함수로 Foo라는 이름과 99라는 점수를 키-값 쌍으로 만든 후, insert 함수를 사용해 scores 맵에 삽입하는 예이다.

scores.insert(std::make_pair("Foo", 99));

특정 키를 기준으로 원소를 검색할 때는 find 함수를 이용한다. find 함수는 맵에서 특정 키에 해당하는 반복자를 반환한다. 이 반복자로 키에 해당하는 값을 찾을 수 있다.

다음 코드는 이름에 해당하는 점수를 찾아서 출력하는 예이다.

auto it = scores.find("Foo");
if(it != scores.end()){
	std::cout << "Foo의 점수 검색 결과: " << it->second << std::endl;
}
else {
	std::cout << "Foo의 점수는 존재하지 않음." << std::endl;
}

맵에서 특젇ㅇ 키에 해당하는 키-값 쌍을 삭제할 때는 erase 함수를 사용한다. 예를 들어 키-값 쌍으로 구성된 scores 맵에서 erase 함수에 키에 해당하는 이름만 넣어주면 점수까지 삭제된다.

scores.erase("Foo");

map 컨테이너를 선언하고 원소를 삽입, 검색, 삭제하는 방법을 알아보았다. 이를 이용해 학생별 점수를 관리하는 전체 소스를 살펴보자.

#include <iostream>
#include <string>
#include <map>

using std::cout;
using std::endl;


int main()
{
    std::map<std::string, int> scores;

    // key-value pairs
    scores.insert(std::make_pair("John", 99));
    scores.insert(std::make_pair("Doe", 85));
    scores.insert(std::make_pair("Tom", 90));

    // 맵 크기 출력
    cout << "Map size: " << scores.size() << endl;

    // 특정 키에 해당하는 값 검색
    auto it = scores.find("John");
    if (it != scores.end()) {
        cout << "John's score: " << it->second << endl;
    }
    else {
        cout << "John not found" << endl;
    }

    // 특정 키에 해당하는 키-값 제거
    scores.erase("Tom");

    // 맵 크기 출력
    cout << "Tom 정보 제거 후, Map size: " << scores.size() << endl;

    // 맵을 순회하며 키-값 출력
    cout << "--- Map iteration ---" << endl;
    for (const auto& pair : scores) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

실행 결과

Map size: 3
John's score: 99
Tom 정보 제거 후, Map size: 2
--- Map iteration ---
Doe: 85
John: 99

multi map (std::multimap)

std::multimap도 std::map처럼 키-값 쌍으로 구성된 맵을 구현하는 연관 컨테이너지만, 중복된 값을 허용한다는 차이가 있다. 즉, 멀티 맵은 같은 키로 여러 값을 저장할 수 있다. 멀티 맵의 특징은 다음과 같다.

중복된 키 저장
- 멀티 맵은 중복된 키를 허용한다. 같은 키를 가진 여러 개의 값을 저장할 수 있다.
자동 정렬
- 멀티 맵은 내부적으로 키를 기준으로 정렬된다. 기본은 오름차순이지만, 정렬 기준을 정의할 수도 있다.
이진 탐색 트리
- 멀티 맵은 이진 탐색 트리 자료 구조를 기반으로 구현되어 검색, 삽입, 삭제 등의 작업을 효율적으로 수행한다.

이런 특징 덕분에 멀티 맵은 같은 키로 여러 값을 관리해야 하는 다중 매핑이나 정렬된 키-값 쌍을 유지해야 할 때 활용할 수 있다.

멀티 맵을 선언하고 원소를 삽입하는 방법은 맵과 같다. 다만 중복된 키를 허용한다는 차이가 있다. 따라서 멀티 맵에서는 equal_range 함수로 특징 키를 가진 원소의 범위를 구할 수 있다.
이때 범위는 (first, last) 형태의 반복자 쌍으로 표현되며, first는 첫 번째 원소를 가리키는 반복자이고, last는 범위에서 끝을 가리키는 반복자이다.

auto range = scores.equal_range("Foo");

멀티 맵을 사용해 학생 별 점수를 관리하는 예제를 살펴보자.

#include <iostream>
#include <string>
#include <map>

using std::cout;
using std::endl;


int main()
{
    std::multimap<std::string, int> scores;

    // 멀티 맵에 key-value pairs
    scores.insert(std::make_pair("John", 99));
    scores.insert(std::make_pair("Doe", 85));
    scores.insert(std::make_pair("Tom", 90));
    scores.insert(std::make_pair("John", 100)); // 중복 키 허용

    // 맵 크기 출력
    cout << "multimap size: " << scores.size() << endl;

    // 특정 키에 해당하는 원소의 개수 구하기
    size_t count = scores.count("John");
    cout << "저장되어 있는 John 점수의 개수: " << count << endl;

    // 특정 키를 가진 원소의 범위 구하기
    auto range = scores.equal_range("John");

    if (range.first != scores.end()) {
        cout << "John의 모든 점수: ";
        for (auto it = range.first; it != range.second; it++) {
            cout << it->second << " ";
        }
        cout << endl;
    }
    else {
        cout << "John의 점수가 없습니다." << endl;
    }
    cout << endl;

    // 특정 키에 해당하는 모든 원소 제거
    scores.erase("John"); // John 정보 제거

    // 멀티 맵의 크기 출력
    cout << "John 정보 제거 후, multimap size: " << scores.size() << endl;

    // 멀티 맵을 순회하며 모든 키와 값 출력
    cout << "---multimap 순회---" << endl;
    for (const auto& pair : scores) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

실행 결과

multimap size: 4
저장되어 있는 John 점수의 개수: 2
John의 모든 점수: 99 100

John 정보 제거 후, multimap size: 2
---multimap 순회---
Doe: 85
Tom: 90

set와 map의 차이점

std::set은 고유한 원소들을 정렬된 상태로 유지해야 할 때 사용한다.
std::map은 키-값 쌍을 저장하고 고유한 키를 기준으로 정렬된 상태를 유지한다. 따라서 특정 키에 대응하는 값을 관리해야 할 때 사용한다.

Seongcheol Jeon

이전 포스트

C++ STL Sequence Containers (순차 컨테이너)

다음 포스트

C++ STL Associative Containers (연관 컨테이너)

CPP

연관 컨테이너

Set Container

set (std::set)

multiset (std::multiset)

Map Container

map (std::map)

multi map (std::multimap)

set와 map의 차이점

C++ STL Sequence Containers (순차 컨테이너)

C++ Container Adapter (Stack, Queue)

0개의 댓글