[STL] Map Container

Seonghun Kim·2022년 7월 26일
1

C++!

목록 보기
9/10
post-thumbnail

📌 map container

  • associative container
    • key와 value로 구성된 pair 객체를 원소로하는 컨테이너
    • key는 중복이 허용되지 않지만, value는 중복을 허용
    • 특정 기준에 따라 원소들을 자동으로 정렬
    • 위치가 계속 변경되므로 원소에 직접 접근이 불가능
  • 균형 이진트리 (balanced binary tree) 형태
    • 원소 추가, 제거, 탐색 등의 연산 시간복잡도: O(log n)

✔ map 사용

#include <map>
using namespace std;
  • <map> header
  • std::map

✔ map 생성

map<[key type], [value type], [compare]> [name]

[compare] default : less<[key type]>

  • map에 저장될 key와 value의 타입을 명시
  • 우선순위 기준이 없는 경우, key를 기준으로 오름차순 정렬
// 문자형 key, 정수형 value를 원소로하는 map m1을 생성
map<char, int> m1;

// 정수형 key를 내림차순으로 저장하는 map m2를 생성
map<int, string, greater<int>> m2;

// 초기화 값이 있는 map m3를 생성
map<string, int> m3 = {
    {"apple", 1000},
    {"banana", 2000},
    {"orange", 3000}
};
  • 사용 용도에 알맞게 key와 value의 타입을 정의
  • 생성과 동시에 pair 형태로 하드코딩 가능

✔ map 멤버 함수

1) capacity & element access

functiondescription
m.size()map m의 크기 반환
m.empty()비어있으면 true, 그렇지 않으면 false 반환
m[key]key에 해당하는 value 반환. 없는 경우 {key, 0}를 생성하고 0을 반환
m.at(key)key에 해당하는 value 반환. 없는 경우 error 발생

2) iterators

functiondescription
m.begin()첫번째 원소를 가리키는 iterator
m.end()마지막 원소의 다음을 가리키는 iterator
m.rbegin()마지막 원소를 가리키는 iterator
m.rend()첫번째 원소의 이전을 가리키는 iterator
map<string, int> fruit_price = {
    {"apple", 1000},
    {"banana", 2000},
    {"grape", 3000}
};

cout << "map size: " << fruit_price.size() << endl;     // 3
cout << "apple: " << fruit_price["apple"] << endl;      // 1000
cout << "orange: " << fruit_price["orange"] << endl;    // 0 (not defined)
cout << "map size: " << fruit_price.size() << endl;     // 4
cout << endl;

map<string, int>::iterator iter;
for (iter = fruit_price.begin(); iter != fruit_price.end(); iter++)
{
    cout << iter->first << " ";
    cout << iter->second << endl;
}
  • output:
map size: 3
apple: 1000
orange: 0
map size: 4

apple 1000
banana 2000
grape 3000
orange 0

3) modifiers (수정)

functiondescription
m[key] = valuepair(key, value)를 map m에 삽입
m.insert(pair)pair를 map m에 삽입
m.erase(key)key에 해당하는 pair를 map m에서 제거
m.clear()모든 원소(pair) 제거

4) operations (연산)

functiondescription
m.find(key)key에 해당하는 pair의 iterator를 반환. 없는 경우 m.end() 반환
m.count(key)key에 해당하는 pair의 개수 반환
map<string, int> fruit_price;

fruit_price.insert(pair<string, int>("apple", 1000));       // (apple, 1000)
fruit_price.insert(pair<string, int>("grape", 2000));       // (apple, 1000) (grape, 2000)
fruit_price.insert(pair<string, int>("banana", 3000));      // (apple, 1000) (banana, 3000) (grape, 2000)

fruit_price.erase("banana");            // (apple, 1000) (grape, 2000)
fruit_price.erase("apple");             // (grape, 2000)

fruit_price["melon"] = 7000;            // (grape, 2000) (melon, 7000)
fruit_price["grape"] = 5000;            // (grape, 5000) (melon, 7000) -> modify
fruit_price["berry"] = 3000;            // (berry, 3000) (grape, 5000) (melon, 7000)

string fruits[5] = { "apple", "banana", "berry", "grape", "melon" };
for (string fruit : fruits)
{
    if (fruit_price.find(fruit) != fruit_price.end()) 
        cout << fruit << " is in map ";
    else 
        cout << fruit << " is not in map ";
    
    cout << "(" << fruit_price.count(fruit) << " element)\n";
}
  • output :
apple is not in map (0 element)
banana is not in map (0 element)
berry is in map (1 element)
grape is in map (1 element)
melon is in map (1 element)

✔ map 예제

문자열을 구성하는 알파벳 정보

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

using namespace std;

int main()
{
    string str = "this is map container.";
    map<char, int> alpha_cnt;

    for (char alpha : str)
    {
        if (isalpha(alpha))
        {
            // map에 alpha key의 value를 증가
            alpha_cnt[alpha]++;
        }
    }

    for (pair<char, int> p : alpha_cnt)
    {
        cout << "문자열에서 ";
        cout << p.first << "의 개수는 ";
        cout << p.second << "개 입니다.\n";
    }

    return 0;
}
  • output :
문자열에서 a의 개수는 2개 입니다.
문자열에서 c의 개수는 1개 입니다.
문자열에서 e의 개수는 1개 입니다.
문자열에서 h의 개수는 1개 입니다.
문자열에서 i의 개수는 3개 입니다.
문자열에서 m의 개수는 1개 입니다.
문자열에서 n의 개수는 2개 입니다.
문자열에서 o의 개수는 1개 입니다.
문자열에서 p의 개수는 1개 입니다.
문자열에서 r의 개수는 1개 입니다.
문자열에서 s의 개수는 2개 입니다.
문자열에서 t의 개수는 2개 입니다.


📌 Multimap

  • key값의 중복을 허용
  • 이외에는 map의 특성과 동일

✔ multimap 사용

#include <map>
using namespace std;
  • <map> header
  • std::multimap

✔ multimap 생성

multimap<[key type], [value type], [compare]> [name]

[compare] default : less<[key type]>

  • multimap에 저장될 타입을 명시
  • 우선순위 기준이 없는 경우, key를 기준으로 오름차순으로 정렬
// 문자형 key, 정수형 value를 원소로하는 multimap mm1을 생성
multimap<char, int> mm1;

// 정수형 key를 내림차순으로 저장하는 multimap mm2를 생성
multimap<int, string, greater<int>> mm2;

// 초기화 값이 있는 multimap mm3를 생성
multimap<string, int> mm3 = {
    {"apple", 1000},
    {"apple", 2000},
    {"orange", 3000},
    {"orange", 2500}
};
  • 사용 용도에 알맞게 key와 value의 타입을 정의
  • 생성과 동시에 pair 형태로 하드코딩 가능하며, 중복을 허용

✔ multimap 멤버 함수

1) capacity

functiondescription
mm.size()multimap mm 의 크기 반환
mm.empty()비어있으면 true, 그렇지 않으면 false 반환

2) iterators

functiondescription
mm.begin()첫번째 원소를 가리키는 iterator
mm.end()마지막 원소의 다음을 가리키는 iterator
mm.rbegin()마지막 원소를 가리키는 iterator
mm.rend()첫번째 원소의 이전을 가리키는 iterator

3) modifiers (수정)

functiondescription
mm.insert(pair)pair를 multimap mm에 삽입
mm.erase(key)key에 해당하는 pair들을 multimap mm에서 모두 제거
mm.clear()모든 원소(pair) 제거

4) operations (연산)

functiondescription
mm.find(key)key에 해당하는 pair의 iterator를 반환. 없는 경우 mm.end() 반환
mm.count(key)key에 해당하는 pair의 개수 반환
multimap<string, int> person_age = { 
	{ "John", 20 }, { "Mary", 40 }, { "Emma", 30 }, { "John", 23 }, { "Mike", 32 } };

multimap<string, int>::iterator iter;

cout << "Initialize: \n";
for (iter = person_age.begin(); iter != person_age.end(); iter++)
	cout << iter->first << "(" << iter->second << ") ";
cout << "\n\n";

// person_age["Emma"] = 34;  // error
person_age.insert(pair<string, int>("Emma", 34));
person_age.insert(pair<string, int>("John", 39));
person_age.insert(pair<string, int>("Alice", 20));

cout << "insert(Emma, John, Alice): \n";
for (iter = person_age.begin(); iter != person_age.end(); iter++)
	cout << iter->first << "(" << iter->second << ") ";
cout << "\n\n";

person_age.erase("John");
person_age.erase("Sophia");  // discard
person_age.erase("Mary");

cout << "erase(John, Mary): \n";
for (iter = person_age.begin(); iter != person_age.end(); iter++)
	cout << iter->first << "(" << iter->second << ") ";
cout << "\n\n";

vector<string> names = { "John", "Mary", "Emma", "Mike", "Alice", "Sophia" };
for (string name : names)
	if (person_age.find(name) != person_age.end())
		cout << "There are " << person_age.count(name) << " people(s) named " << name << '\n';
  • output :
Initialize:
Emma(30) John(20) John(23) Mary(40) Mike(32)

insert(Emma, John, Alice):
Alice(20) Emma(30) Emma(34) John(20) John(23) John(39) Mary(40) Mike(32)

erase(John, Mary):
Alice(20) Emma(30) Emma(34) Mike(32)

There are 2 people(s) named Emma
There are 1 people(s) named Mike
There are 1 people(s) named Alice

0개의 댓글