unordered_map — hash, tenglik va rezerv

~20 daq · C++ · Standart kutubxona vositalari

Muammodan boshlaylik

Kalitli qidiruvda tartib kerak emas. Hash asosidagi tuzilma bilan uning o‘rtacha va yomon holatlarini farqlaymiz.

Tushunib olamiz

Unordered_map odatda o‘rtacha tez qidiradi, lekin eng yomon holat chiziqli bo‘lishi mumkin. Iteratsiya tartibi kafolatlanmaydi. Reserve kutilgan elementlar uchun qayta hashni kamaytiradi, lekin reference/iterator qoidalarini bekor qilmaydi. Teng kalitlar bir xil hashga ega bo‘lishi kerak.

Misolni bajaramiz

C++17 ishlating. Mustaqil misolni main.cppga yozing: g++ -std=c++17 -Wall -Wextra -pedantic main.cpp -o dastur, keyin ./dastur (Windows PowerShell’da .\dastur.exe). MSVC’da /std:c++17 /EHsc /utf-8 flaglarini ishlating. Build/test/thread darslaridagi maxsus flaglarni alohida qo‘shing.

#include <iostream>
#include <string>
#include <unordered_map>


int main() {
  std::unordered_map<std::string, int> sonlar;
  sonlar.reserve(16);
  for (const auto& s : {"java", "go", "java"}) { ++sonlar[s]; }
  std::cout << sonlar.at("java") << '\n';
}

Natija va izoh

2 chiqadi. Tartib talab qilinmagani uchun unordered_map tanlandi; natijani tartibli ko‘rsatish kerak bo‘lsa alohida saralang.

[!WARNING] Rehash iteratorlarni yaroqsiz qilishi mumkin. Custom hash ishlatganda tenglik bilan uyg‘unligini tekshiring.

Mustaqil mashq

Chastotalarni kalit nomi bo‘yicha saralab ko‘rsating.

Avval kodni mustaqil o‘zgartiring. Oddiy holatdan tashqari bo‘sh qiymat, noto‘g‘ri kirish yoki resurs mavjud bo‘lmagan vaziyatni ham sinang. Natijani taxmin qilib, haqiqiy natija bilan solishtiring.

Yechim va tekshirish yo‘li

Juftlarni vectorga nusxalang va nom bo‘yicha sort qiling. Hash konteynerning tasodifiy ko‘rinayotgan tartibiga tayanmang.

Xulosa

Unordered_map odatda o‘rtacha tez qidiradi, lekin eng yomon holat chiziqli bo‘lishi mumkin.

Bu usulni avvalgi katalog loyihasiga alohida bosqich sifatida qo‘shing: ishlayotgan qismini saqlab, yangi talab uchun kichik tekshiruv yozing. Xato holatidagi xulqni ham hujjatlashtiring; muvaffaqiyatli namunaning o‘zi yetarli emas.

Keyingi dars: deque va queue — navbatlar.

Rasmiy manba: Microsoft C++ hujjatlari, CMake qo‘llanmasi, Clang AddressSanitizer