C++ - unordered_map, unordered_set, array

정렬안된 맵(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