C++ - map, set

mohadang·2022년 10월 9일
0

C++

목록 보기
15/48
post-thumbnail

Map

  • Key를 이용해 데이터를 가져옴
  • key와 값의 쌍들을 저장
  • Key는 중볼될 수 없음
  • C++ 맵은 자동 정렬되는 컨테이너 ... ??? <-- unordered map 존재함.
  • 이진 탐색 트리(binary search tree) 기반
    • 오름 차순
    • O(logN)
  • map은 Hash map이 아님 정렬되는 map임
    • 기대했던 Hash 자료 구조가 아님(C# 의 Dictionary 처럼...)
  • EX)
#include <map>

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

  --> 추가 방법 1
  simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 100));
  simpleScoreMap.insert(std::pair<std::string, int>("Coco", 50));

  --> 추가 방법 2
  simpleScoreMap["Mocha"] = 0;   <-- 대입 하는 문법만으로도 추가 가능.


  int data = simpleScoreMap["Coco"]; <-- 이렇게 읽기만 하더라도 추가

  std::cout << "Current Size : " << simpleScoreMap.size() << std::endl;
}

map 요소 삽입

  • 두 데이터를 한 단위로 저장하는 구조
std::pair<std::string, int> student1("Coco", 10);
//pair.first;
//pairs.second;
simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 100));
  • insert()
    • 새요소를 map에 삽입한다.
    • 반복자와 bool 값을 한 쌍으로 반환
      • 반복자는 요소를 가리키고
      • bool 값은 삽입 결과를 알려줌
      • Web 방식 예외 처리
    • 키를 중복으로 삽입할 수 없음
simpleScoreMap.insert(std::pari<std::string, int>("Mocha", 100));
// <iterator, tru> 를 반환한다.

simpleScoreMap.insert(std::pari<std::string, int>("Mocha", 0));// 중복 삽입
// <iterator, false>를 반환한다.
// 삽입 실패

operator[]

  • key에 대응하는 값을 참조로 반환한다.
  • 'map에 키가 없으면 새 요소를 삽입'
    • 이것땜에 실수 하는 경우 있음
  • map에 키가 이미 있으면 그 값을 덮어씀
std::map<std::string, int> simpleScoreMap;
simpleScoreMap["Coco"] = 10;// 새 요소를 삽입한다.
simpleScoreMap["Coco"] = 50;// "Coco"의 값을 덮어 쓴다.
// 값이 중복 되어 있는지 확인할 수 없다,,, find 함수로 찾아야 함.

return simpleScoreMap["Coco"];
// "만약 Coco가 없으면 기본값을 삽입해서 반환해 주기에 실수 할 수 있다."

자동 정렬

simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 100));
simpleScoreMap.insert(std::pair<std::string, int>("Coco", 50));

for(std::map<std::string, int>::iterator it = simpleScoreMap.begin(); it != simpleScoreMap.end(); ++it)
{
  std::cout << "(" << it->first <<", " << it->second << ")" << std::endl;
}

// "map은 vector처럼 순서가 없으니 key에 따라 정렬이 된다."

// OUTPUT>>
//   "Coco", 50
// "Mocha", 100

요소 찾기

#include <map>

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

  simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 100));

  // 찾음
  std::map<std::string, int>::iterator it = simpleScoreMap.find("Mocha");

  if(it != simpleScoreMap.end())
  {
    it->second = 80;
  }
}
  • "iterator로 컨테이너에 공통된 인터페이스를 구현할 수 있다"

find()

  • map안에서 key를 찾으면 그에 대응하는 값을 참조로 반환한다.
  • 못 찾으면 end()를 반환
    std::map<std::string, int>::iterator it = simpleScoreMap.find("Mocha");

swap(), clear()

  • void swap(map& other);
    • 두 map의 키와 값을 서로 맞바꾼다.
  • void clear();
    • map을 비운다.
std::map<std::string, int> scoreMap;// ["Mocha", 10], ["Coco", 40]
std::map<std::string, int> anotherScoreMap;// ["Nana", 100]
scoreMap.swap( anotherScoreMap)
// scoreMap : ["Nana", 100]
// anotherScoreMap : ["Mocha", 10], ["Coco", 40]
anotherScoreMap.clear()

erase()

  • map의 요소들을 제거한다.

    • void erase(iterator position);
    • size_type erase(const key_type& key);
    • void erase(iterator first, iterator last);
  • 삭제 방법 1

std::map<std::string, int>::iterator foundIt = simpleScoreMap.find("Coco");
simpleScoreMap.erase(foundIt);
  • 삭제 방법 2
simpleScoreMap.erase("Coco");
// 좀더 편하고 일반적인 방식

EX) 개체를 키로 사용하기

class StudentInfo
{
public:
private:
  std::string mName;
  std::string mStudentID
}

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

  scores.insert(std::pair<StudentInfo, int>(StudentInfo("Poppy", "a556"), 30));
  scores.insert(std::pair<StudentInfo, int>(StudentInfo("Lulu", "a112"), 70));

  std::cout << scores[StudentInfo("Poppy", "a556")] << std::endl;
}
  • 위의 코드가 잘 동작 할 까??

    • NO, Error 발생
    • StudentInfo 가 비교 연산자가 없어서... 왜 비교 연산자가 필요할까??
      • map은 Hash map이 아님 정렬되는 map임
      • "Map은 항상 정렬이 된다. 그래서 Key값 끼리 비교가 가능 해야 한다".
  • StudentInfo 클래스의 '<' 연산자 오버로딩을 해주면 된다.

bool StudentInfo::operator<(const StudentInfo& other) const
{
  if(mName == other.mName)
  {
    return mStudentID < other.mStudentID;
  }

  return mName < other.mName;
}
  • 요소들을 정렬하는 또 다른 방법
    • map을 만들 때 비교함수(comparer)를 넣을 수도 있음
    struct StudentInfoComparer
    {
      bool operator()(const StudentInfo& left, const StudentInfo& right) const
      {
        return (left.getName() < right.getName());
      }
    }
    std::map<StudentInfo, int, StudentInfoComparer> Scores;
    // operator< 를 구현하는게 더 좋지만 이 방법을 사용 못하는 경우도 있다. 
    // 만약 StudentInfo가 남이 만든 Code이거나 수정 할 수 없을 때는 이 방법이 유용할 수 있다.

장점

  • list, vector 보다 탐색 속도가 빠름

단점

  • 자동으로 정렬됨.
  • 해쉬맵이 아님, 따라서 O(1)이 아님. O(logN)
  • C++11에서 해결책이 있음.

Set

  • "Set은 map 과 거의 같다"

    • "map에서 값을 뺀것과 같다."
  • 역시 정렬되는 컨테이너

  • "중복되지 않는 키를 요소로 저장함"

  • 역시 이진 탐색 트리 기반

    • 오름 차순
  • 장점과 단점도 map과 같음

#include <set>
int main()
{
  std::set<int> scores;
  scores.insert(10);
  scores.insert(20);

  for(std::set<int>::iterator it = scores.begin(); it != scores.end(); ++it)
  {
    std::cout << *it << std::endl;
  }
  return 0;
}
profile
mohadang

0개의 댓글