C++ - unordered_map, unordered_set, array

mohadang·2022년 10월 12일
cpp
0

C++

목록 보기
26/48
post-thumbnail

정렬안된 맵(unordered map)

  • std::unordered_map;
    • 말 그대로 Map, 정렬을 하지 않기 때문에 추가할 때 마다 O(1)
  • std::map
std::map<std::string, int> scores;
scores["Nana"] = 60;
scores["Mocha"] = 70;
scores["Coco"] = 100;

for(auto it = scores.begin(); it != scores.end(); ++it)
{
  std::cout << it->first << ":" << it->second << std::endl;
}
// Coco:100
// Mocha:70
// Nana:60

  • 다른 언어들은 기본적으로 정렬안된 map을 사용하고 정렬된 것을 원할 때만 특별한 옵션을 취하는데 C++은 그러하지 않음

  • 이진 트리 삽입시 마다 O(log n)

  • 그래서, 요소 삽입/제거가 비번할 경우 성능이 저하됨.

  • std::unordered_map

std::unordered_map<std::string, int> scores;
scores["Nana"] = 60;
scores["Mocha"] = 70;
scores["Coco"] = 100;

for(auto it = scores.begin(); it != scores.end(); ++it)
{
  std::cout << it->first << ":" << it->second << std::endl;
}

// Coco:100
// Nana:60
// Mocha:70
  • 키와 값의 쌍들을 저장(std::map 과 같음)
  • 키는 중복 불가(std::map 과 같음)
  • 자동으로 정렬되지 않는 컨테이너
    • 요소는 해쉬 함수가 생성하는 색인(index) 기반의 버킷(bucket)들로 구성됨
    • 해쉬맵(hashmap)이라고도 함
    • 접근, 삽입이 O(1)
  • C#의 Dictionary와 같음
  • 요소 삽입하기
    • scores["Coco"] = 100;
      • "Coco" <- 키
      • "Coco" => [해쉬 함수] => 5(Index) 는 가능
      • 5(Index) => [해쉬 함수] => "Coco" 는 불가능
      • 해쉬 충돌 가능
        • "Coco" => 5
        • "Nana" => 5
  • 버킷 => [0][1][2][3][4][5]
  • 버킷 내용 보여주기
#include <unordered_map>

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

  scores["Nana"] = 60;
  scores["Mocha"] = 70;
  scores["Coco"] = 100;
  scores["Ari"] = 40;
  scores["Chris"] = 90;

  for(size_t i = 0; i < scores.bucket_count(); ++i)
  {
    std::cout << "Bucket #" << i << ":";

    for(auto it = scores.begin(i); it != scores.end(i); ++it)
    {
      std::cout << " " << it->first << ":" << it->second;
    }

    std::cout << std::endl;
  }
}

// Bucket #0:
// Bucket #1: Ari:40, Coco:100, Nana:60 <-- 충돌이 나더라도 3번 순회하면 끝.
// Bucket #2:
// Bucket #3:
// Bucket #4: Chris:90
// Bucket #5: Mocha:70
// Bucket #6:
// Bucket #7:

  • Bucket 갯수가 소수면 충돌하는 횟수가 적어짐, 수학적인 증명하는 시도 있음.

  • std::map, std::unordered_map

    • std::map

      • 자동으로 정렬되는 컨테이너

      • 키-값 쌍들을 저장

      • 이진 탐색 트리

      • 탐색 시간 : O(logn)

      • 삽입과 제거가 빈번하면 느림

    • std::unordered_map

      • 자동으로 정렬되지 않는 컨테이너
      • 키-값을 쌍들 저장
      • 해쉬 테이블
      • 탐색 시간:
        O(1), 해쉬 충돌이 없을 경우
        O(N), 최악의 경우
      • 버킷 때문에 메모리 사용량 증가.

정렬안된 셋(unordered set)

  • Map 하고 똑같음
  • std::unordered_set;
  • "unordered set에는 reserve 함수가 있음"
#include <set>

int main()
{
  std::set<std::string> names;

  names.insert("Victor");
  names.insert("Lulu");
  names.insert("Mocha");

  for(auto it = names.begin(); it != namese.end(); ++it)
  {
    std::cout << *it << std::endl;
  }

  return 0;
}

// Lulu
// Mocha
// Victor
  • std::map와 같은 문제
  • 자동 정렬되는 컨테이너
  • 그래서, 요소 삽입/제거가 빈번할 경우 느릴 수 있음.
  • std::unordered_set
#include <unordered_set>

int main()
{
  std::unordered_set<std::string> names;

  names.insert("Victor");
  names.insert("Lulu");
  names.insert("Mocha");

  for(auto it = names.begin(); it != namese.end(); ++it)
  {
    std::cout << *it << std::endl;
  }

  return 0;
}

// Victor
// Mocha
// Lulu
  • "성능 비교"(좀더 제대로 된 성능 비교, 릴리즈 모드로 실행 할 것)
void SpeedTestExample()
{
  // RUN THIS EXAMPLE IN RELEASE CONFIG

  // initialize test
  set<int> orderedSet;
  unordered_set<int> unorderedSet;

  const int NUMBER_TO_INSERT_LATER = 1023;
  const int MAX_NUMBER_IN_SET = 100000;

  unorderedSet.reserve(MAX_NUMBER_IN_SET);// unordered set에는 reserve 함수가 있음

  static_assert(MAX_NUMBER_IN_SET > NUMBER_TO_INSERT_LATER, "MAX_NUMBER_IN_SET should be greater than NUMBER_TO_INSERT");

  for (int i = 0; i < MAX_NUMBER_IN_SET; i++)
  {
    if (i == NUMBER_TO_INSERT_LATER)
    {
      continue;
    }

    orderedSet.insert(i);
    unorderedSet.insert(i);
  }

  auto start = chrono::high_resolution_clock::now();

  orderedSet.insert(NUMBER_TO_INSERT_LATER);

  auto end = chrono::high_resolution_clock::now();

  auto elapsedNanoSeconds = end - start;

  cout << "Inserting into orderedSet: " << elapsedNanoSeconds.count() << " ns" << endl;// 1498 nano second

  start = chrono::high_resolution_clock::now();

  unorderedSet.insert(NUMBER_TO_INSERT_LATER);

  end = chrono::high_resolution_clock::now();

  elapsedNanoSeconds = end - start;

  cout << "Inserting into unorderedSet: " << elapsedNanoSeconds.count() << " ns" << endl;// 899 nano second

  // Uncomment this when you run it with Release configuration
  // system("pause");
}

어레이(array)

  • std::array;

  • 요소 수를 기억하지 않음

  • 단순히 C 스타일 배열을 추상화한 것

  • std::array

#include <array>
std::array<int, 3> numbers;// 요소 3개 잡는 순간 3개 할당.

numbers[0] = 1;

// => 3 : 그냥 배열 size, 요소 수를 추적하지 않겠다는 의미이다.
std::cout << numbers.size() << std::endl;
// => 3 : 그냥 배열 size
std::cout << numbers.max_size() << std::endl;

  • 결국 외부에서 3개라는 범위 체크를 해 주어야 한다.

    • 말 그대로 배열을 추상화 한 것 뿐이다. 따라서 배열을 할당하고 그 크기를 외부에서 관리해서 열거 하거나 사용해야 한다.

  • "요소 수를 기억하지 않음"

    • 그래서 이게 필요한 이유에 대해 100% 확신은 못 하겠음.

  • 아마도 std::algorithm을 쓸 수 있어서?

  • 어쩌면 반복자를 쓸 수 있어서?

    • "허나 더 나은 방법이 있음". => "범위 기반 반복자"

  • 범위 기반 반복자

    • C#의 foreach

    • 일반적인 for 반복문

      • for(int i = 0; i < 3; i++)
      • for(auto it = scoreMap.begin(); it != scoreMap.end(); ++it)

    • C++의 foreach

      • 배열
      int scores[3] = {10, 20, 30};
for(int score : scores) <- 배열인데 돈다.
{
  값이니까 복사
  std::cout << score << endl;
}
      • 컨테이너
      std::map<std::string, int> scoreMap;

scoreMap["Lulu"] = 10;
scoreMap["Coco"] = 50;
scoreMap["Mocha"] = 100;

for(auto& score : scoreMap)
{
  std::cout << score.first << ":" << score.second << std::endl;
}

    • for 반복문을 더 간단하게 쓸 수 있음

    • 이전의 for 반복보다 가독성이 더 높음

    • STL 컨테이너와 C 스타일 배열 모두에서 작동함

    • auto 키워드를 범위 기반 for 반복에 쓸 수 있음

    • 컨테이너/배열을 역순회할 수 없음.

    • for_each는 어떨까?

      • C++ 03
      • 컨테이너의 각 요소마다 함수를 실행하는 알고리듬
      • 범위 기반 for 만큼 가독성이 높지 않음
      std::map<std::string, int> scoreMap;

  scoreMap["Lulu"] = 10;
  scoreMap["Coco"] = 50;
  scoreMap["Mocha"] = 100;

  auto printElement = [](std::unordered_map<std::string, int>::value_type& item)
  {
    std::cout << item.first << ": " << item.second << std::endl;
  }

  for_each(scoreMap.begin(), scoreMap.end(), printElement);

  • 좀 이상함

    • 다른 언어들은 알고리듬 말고 언어 문법으로 지원

  • 그러니, 범위 기반 for를 사용하는것을 지향해야 한다.

값, 참조

  • By value
//["Lulu", 10], ["Chris", 50], ["Monica", 100]

std::map<std::string, int> scoreMap;
scoreMap["Lulu"] = 10;
scoreMap["Chris"] = 50;
scoreMap["Monica"] = 100;

for (auto score : scoreMap)
{
  score.second -= 10;
}

for (const auto& score : scoreMap)
{
  std::cout << score.first << ":" << score.second << std::endl;
}
// Chris : 50
// Lulu : 10
// Monica : 100
  • By reference
for(auto& score : scoreMap)
{
  score.second -= 10;
}

for (const auto& score : scoreMap)
{
  std::cout << score.first << ":" << score.second << std::endl;
}

// Chris : 40
// Lulu : 0
// Monica : 90
profile
mohadang
mohadang
이전 포스트

C++ - 헤더에서 초기화

다음 포스트

C++ - Smart Pointer

0개의 댓글