Comprehensive Guide to Hash Tables in C++ STL: Unordered Set, Multiset, Unordered Map, and Multimap

Explore the implementation of hash tables in C++ STL using unordered_set, multiset, unordered_map, and multimap. Learn how to insert, search, and erase elements, along with practical examples like word puzzles and removing duplicates from vectors. Dive into recursive functions and efficiently manage data structures. See code snippets, demos, and step-by-step instructions for a deep understanding.

• C++
• Hash Tables
• Unordered Set
• Unordered Map
• STL

mariate Follow

Uploaded on Oct 07, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Recitation Outline Hash tables in C++ STL unordered_set (multiset) unordered_map (multimap) Examples Word puzzle using hash tables Remove duplicate elements from a vector Recursive example Print out numbers

2. unordered_set #include <unordered_set> using namespace std; std::pair<iterator, bool> insert(const value_type& val); Insert an element val into hash table iterator find(const key_type& k); Search key k void erase(const_iterator position); size_type erase(const key_type& k); Delete an element begin() end() iterators

3. unordered_map #include <unordered_map> Using namespace std; std::pair<iterator, bool> insert(const value_type& obj); Insert an element typedef std::pair<const Key, T> value_type; void erase(const_iterator position); size_type erase(const key_type& k); Delete an element (with a given iterator or key) iterator find(const key_type& k); Search an element (with given key) begin(), end() Iterators mapped_type& operator[](const key_type& k); Return value if key k exists in map Otherwise an element with key k and default value will be inserted

4. Word Puzzle using hash table In this version we store word dictionary in an unordered_set See examples/r7/word_puzzle_ht.cpp, word_puzzle_ht.h, rotation.cpp Review the code A demo of running the program

5. Remove Duplicate Elements Remove duplicate elements from a vector Examples/r7/remove_duplicate1.cpp This version uses a hash table to record unique elements To compile: make remove_duplicate1.x

6. Recursive Function Convert the following function into recursive one void printnumber(size_t k) { for (size_t I = 0; I <= k; ++i) { cout << I << ; } } See Examples/r7/printnumber_nonrecursive.cpp And printnumber_recursive.cpp To compile: make printnumber_recursive.x