copy assignment operator unordered_map

• <cassert> (assert.h)
• <cctype> (ctype.h)
• <cerrno> (errno.h)
• C++11 <cfenv> (fenv.h)
• <cfloat> (float.h)
• C++11 <cinttypes> (inttypes.h)
• <ciso646> (iso646.h)
• <climits> (limits.h)
• <clocale> (locale.h)
• <cmath> (math.h)
• <csetjmp> (setjmp.h)
• <csignal> (signal.h)
• <cstdarg> (stdarg.h)
• C++11 <cstdbool> (stdbool.h)
• <cstddef> (stddef.h)
• C++11 <cstdint> (stdint.h)
• <cstdio> (stdio.h)
• <cstdlib> (stdlib.h)
• <cstring> (string.h)
• C++11 <ctgmath> (tgmath.h)
• <ctime> (time.h)
• C++11 <cuchar> (uchar.h)
• <cwchar> (wchar.h)
• <cwctype> (wctype.h)

Containers:

• C++11 <array>
• <deque>
• C++11 <forward_list>
• <list>
• <map>
• <queue>
• <set>
• <stack>
• C++11 <unordered_map>
• C++11 <unordered_set>
• <vector>

Input/Output:

• <fstream>
• <iomanip>
• <ios>
• <iosfwd>
• <iostream>
• <istream>
• <ostream>
• <sstream>
• <streambuf>

Multi-threading:

• C++11 <atomic>
• C++11 <condition_variable>
• C++11 <future>
• C++11 <mutex>
• C++11 <thread>
• <algorithm>
• <bitset>
• C++11 <chrono>
• C++11 <codecvt>
• <complex>
• <exception>
• <functional>
• C++11 <initializer_list>
• <iterator>
• <limits>
• <locale>
• <memory>
• <new>
• <numeric>
• C++11 <random>
• C++11 <ratio>
• C++11 <regex>
• <stdexcept>
• <string>
• C++11 <system_error>
• C++11 <tuple>
• C++11 <type_traits>
• C++11 <typeindex>
• <typeinfo>
• <utility>
• <valarray>
• <unordered_map>
• C++11 unordered_map
• C++11 unordered_multimap
• unordered_map
• C++11 unordered_map::~unordered_map
• C++11 unordered_map::unordered_map

member functions

• C++11 unordered_map::at
• C++11 unordered_map::begin
• C++11 unordered_map::bucket
• C++11 unordered_map::bucket_count
• C++11 unordered_map::bucket_size
• C++11 unordered_map::cbegin
• C++11 unordered_map::cend
• C++11 unordered_map::clear
• C++11 unordered_map::count
• C++11 unordered_map::emplace
• C++11 unordered_map::emplace_hint
• C++11 unordered_map::empty
• C++11 unordered_map::end
• C++11 unordered_map::equal_range
• C++11 unordered_map::erase
• C++11 unordered_map::find
• C++11 unordered_map::get_allocator
• C++11 unordered_map::hash_function
• C++11 unordered_map::insert
• C++11 unordered_map::key_eq
• C++11 unordered_map::load_factor
• C++11 unordered_map::max_bucket_count
• C++11 unordered_map::max_load_factor
• C++11 unordered_map::max_size
• C++11 unordered_map::operator[]
• C++11 unordered_map::operator=
• C++11 unordered_map::rehash
• C++11 unordered_map::reserve
• C++11 unordered_map::size
• C++11 unordered_map::swap

non-member overloads

• C++11 operators (unordered_map)
• C++11 swap (unordered_map)

std:: unordered_map ::operator=

Return value, iterator validity.

std::unordered_map:: operator=

Replaces the contents of the container.

1) Copy assignment operator. Replaces the contents with a copy of the contents of other .

2) Move assignment operator. Replaces the contents with those of other using move semantics (i.e. the data in other is moved from other into this container). other is in a valid but unspecified state afterwards.

[ edit ] Parameters

[ edit ] return value, [ edit ] complexity.

1) Linear in the size of the container.

2) Constant.

[ edit ] Example

The following code uses to assign one std:: unordered_map to another:

[ edit ] See also

<unordered_map>

Unordered_map, std:: unordered_map ::operator=, return value, iterator validity.

• Information
• <cassert> (assert.h)
• <cctype> (ctype.h)
• <cerrno> (errno.h)
• <cfenv> (fenv.h)
• <cfloat> (float.h)
• <cinttypes> (inttypes.h)
• <ciso646> (iso646.h)
• <climits> (limits.h)
• <clocale> (locale.h)
• <cmath> (math.h)
• <csetjmp> (setjmp.h)
• <csignal> (signal.h)
• <cstdarg> (stdarg.h)
• <cstdbool> (stdbool.h)
• <cstddef> (stddef.h)
• <cstdint> (stdint.h)
• <cstdio> (stdio.h)
• <cstdlib> (stdlib.h)
• <cstring> (string.h)
• <ctgmath> (tgmath.h)
• <ctime> (time.h)
• <cuchar> (uchar.h)
• <cwchar> (wchar.h)
• <cwctype> (wctype.h)

Containers:

• <array>
• <deque>
• <forward_list>
• <list>
• <map>
• <queue>
• <set>
• <stack>
• <unordered_set>
• <vector>

Input/Output:

• <fstream>
• <iomanip>
• <ios>
• <iosfwd>
• <iostream>
• <istream>
• <ostream>
• <sstream>
• <streambuf>

Multi-threading:

• <atomic>
• <condition_variable>
• <future>
• <mutex>
• <thread>
• <algorithm>
• <bitset>
• <chrono>
• <codecvt>
• <complex>
• <exception>
• <functional>
• <initializer_list>
• <iterator>
• <limits>
• <locale>
• <memory>
• <new>
• <numeric>
• <random>
• <ratio>
• <regex>
• <stdexcept>
• <string>
• <system_error>
• <tuple>
• <typeindex>
• <typeinfo>
• <type_traits>
• <utility>
• <valarray>
• unordered_multimap
• unordered_map::unordered_map
• unordered_map::~unordered_map

member functions:

• unordered_map::at
• unordered_map::begin
• unordered_map::bucket
• unordered_map::bucket_count
• unordered_map::bucket_size
• unordered_map::cbegin
• unordered_map::cend
• unordered_map::clear
• unordered_map::count
• unordered_map::emplace
• unordered_map::emplace_hint
• unordered_map::empty
• unordered_map::end
• unordered_map::equal_range
• unordered_map::erase
• unordered_map::find
• unordered_map::get_allocator
• unordered_map::hash_function
• unordered_map::insert
• unordered_map::key_eq
• unordered_map::load_factor
• unordered_map::max_bucket_count
• unordered_map::max_load_factor
• unordered_map::max_size
• unordered_map::operator=
• unordered_map::operator[]
• unordered_map::rehash
• unordered_map::reserve
• unordered_map::size
• unordered_map::swap

non-member overloads:

• operators (unordered_map)
• swap (unordered_map)

• Standard Template Library
• STL Priority Queue
• STL Interview Questions
• STL Cheatsheet
• C++ Templates
• C++ Functors
• C++ Iterators

unordered_map in C++ STL

• Different Ways to Initialize an unordered_map in C++

Commonly Used Methods

• unordered_map begin() in C++
• unordered_map end( ) function in C++ STL
• unordered_map size() in C++ STL
• unordered_map insert in C++ STL
• unordered_map at() in C++
• unordered_map find in C++ STL
• unordered_map empty in C++ STL

Other Member Methods

• unordered_map max_size in C++ STL
• unordered_map rehash in C++ STL
• bucket_count and bucket_size in unordered_map in C++
• unordered_map bucket() in C++ STL
• unordered_map load_factor in C++ STL
• Traversing a Map and unordered_map in C++ STL
• How to use unordered_map efficiently in C++
• map vs unordered_map in C++
• How to create an unordered_map of tuples in C++?
• How to create an unordered_map of user defined class in C++?

unordered_map is an associated container that stores elements formed by the combination of a key value and a mapped value. The key value is used to uniquely identify the element and the mapped value is the content associated with the key. Both key and value can be of any type predefined or user-defined. In simple terms, an unordered_map is like a data structure of dictionary type that stores elements in itself. It contains successive pairs (key, value), which allows fast retrieval of an individual element based on its unique key.

Internally unordered_map is implemented using Hash Table , the key provided to map is hashed into indices of a hash table which is why the performance of data structure depends on the hash function a lot but on average, the cost of search, insert, and delete from the hash table is O(1). 

Note: In the worst case, its time complexity can go from O(1) to O(n), especially for big prime numbers. In this situation, it is highly advisable to use a map instead to avoid getting a TLE(Time Limit Exceeded) error.

unordered_map syntax

Below is the C++ program to demonstrate an unordered map:

unordered_map Output

Explanation: The specific thing that this output justifies is that the value of the outcome of unordered_map is produced in a random key-to-value manner whereas the map displays value and key in an ordered manner.

unordered_map vs unordered_set

Note: For example, consider the problem of counting the frequencies of individual words. We can’t use unordered_set (or set) as we can’t store counts while we can use unordered_map.

unordered_map vs map

Methods on unordered_map .

A lot of functions are available that work on unordered_map. The most useful of them are:

• operator []
• size for capacity
• begin and end for the iterator.
• find and count for lookup.
• insert and erase for modification.

The below table shows the complete list of the methods of an unordered_map:

The C++11 library also provides functions to see internally used bucket count, bucket size, and also used hash function and various hash policies but they are less useful in real applications. We can iterate over all elements of unordered_map using Iterator. 

Find frequencies of individual words

Given a string of words, the task is to find the frequencies of the individual words:

Input: str = “geeks for geeks geeks quiz practice qa for”; Output: Frequencies of individual words are              (practice, 1)              (for, 2)             (qa, 1)             (quiz, 1)             (geeks, 3)

Below is the C++ program to implement the above approach: 

Recent Articles on unordered_map

Please Login to comment...

Similar reads.

• cpp-containers-library
• CPP-Library
• cpp-unordered_map
• cpp-unordered_map-functions

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

std::unordered_map:: operator=

Replaces the contents of the container.

[ edit ] Parameters

[ edit ] return value, [ edit ] complexity, [ edit ] example.

The following code uses to assign one std:: unordered_map to another:

[ edit ] See also

• conditionally noexcept

std::unordered_map<Key,T,Hash,KeyEqual,Allocator>:: operator=

Replaces the contents of the container.

Return value

After container move assignment (overload (2) ), unless elementwise move assignment is forced by incompatible allocators, references, pointers, and iterators (other than the end iterator) to other remain valid, but refer to elements that are now in * this . The current standard makes this guarantee via the blanket statement in §23.2.1[container.requirements.general]/12, and a more direct guarantee is under consideration via LWG 2321 .

The following code uses operator= to assign one std:: unordered_map to another:

cppreference.com

Std::map<key,t,compare,allocator>:: operator=.

Replaces the contents of the container.

[ edit ] Parameters

[ edit ] return value, [ edit ] complexity, [ edit ] exceptions, [ edit ] notes.

After container move assignment (overload (2) ), unless element-wise move assignment is forced by incompatible allocators, references, pointers, and iterators (other than the end iterator) to other remain valid, but refer to elements that are now in * this . The current standard makes this guarantee via the blanket statement in [container.reqmts]/67 , and a more direct guarantee is under consideration via LWG issue 2321 .

[ edit ] Example

The following code uses operator = to assign one std::map to another:

[ edit ] See also

• conditionally noexcept
• Recent changes
• Offline version
• What links here
• Related changes
• Upload file
• Special pages
• Printable version
• Permanent link
• Page information
• In other languages
• This page was last modified on 29 November 2021, at 19:46.
• This page has been accessed 85,985 times.
• Privacy policy
• About cppreference.com
• Disclaimers

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications

daaangdennis/CSCE221_UnorderedMapPA5

Folders and files, repository files navigation, unordered map.

Have you ever wanted to associate two things together? For instance, you have an array of the names of your friends and an array of their birthdays in order to remember which birthday belongs to which friend. These two arrays are associated because each friend has one corresponding birthday. While many data structures including trees can be used to associate keys and values, hash tables are a popular choice since they support efficent O(1) insertion, deletion, and search. They accomplish this by transforming each key into a unique index through the use of a hash function. This index can be used to find the object in an array. Ideally, each index would correspond to a single key-value pair. This is called perfect hashing. In practice, it is very difficult to find a hash function which accomplishes perfect hashing. Most hashing datastructures permit collisions and resolve them through various methods.

In this assignment, you will be parodying std::unordered_map with UnorderedMap . Unordered map is an associative container that stores key-value pairs and can search them by unique keys. Search, insertion, and removal of elements have average constant-time complexity. Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. Keys with the same hash code appear in the same bucket. This allows fast access to individual elements, since once the hash is computed, it refers to the exact bucket the element is placed into. Each bucket has an assoicated list where all colliding key-value pairs are stored. This allows the map to achieve high load factors without a drastic reduction in performance. (This effect is commonly associated with closed-addressing.) std::unordered_map resizes automatically when the load factor exceedes a user-designated maximum load factor. It accomplishes this by increasing the number of buckets and rehashing the keys. To simplify the assignment, your map will have a fixed size.

Table of Contents

Getting Started

Implement Unordered Map

• Implement the following functions

Implement the Unordered Map's Iterator

Implement the unordered map's local iterator, implement two hashing algorithms, further reading, application of unordered maps, getting started.

Download this code by running the following command in the directory of your choice:

Open the code in your editor of choice. For instance, if you use VS Code:

Note: On OSX you may need to enable the code command in VS Code with Cmd + Shift + P and typing "shell command." You can select the option to install the command, and then the above command will work.

Fundamentally, the UnorderedMap is a lot like a List<std::pair<Key, Value>> (see your past Programming Assignment ). One problem with List was that accessing a particular element was very slow because we had to start at the beginning and walk our way through until we found the element. UnorderedMap solves this problem by maintaining _buckets which is an array of size _bucket_count containing pointers to HashNode s. These nodes are like Linked List nodes.

How does marking certain nodes grant an advantage to the UnorderedMap ? Well, these nodes are marked because they mark the start of a new hash code within the map. A hash code is the result of running _hash() (the Hash function) on a key . We often want to map the hash codes to an index within the _buckets array to determine which bucket the key should be hashed to. This is done via the provided _range_hash helper function. The performance is best when each bucket is very small. The average number of nodes in the buckets of the UnorderedMap is called the load_factor . Typically, the number of buckets changes to ensure that the load_factor does not exceed the max_load_factor (by default 1.0 ). You do not need to increase the number of buckets in this manner.

In Computer Science literature, UnorderedMap is often referred to as a Hash Table by Chaining because multiple elements can fall into the same bucket, where they form a chain. This is typically represented as an array of independent Linked Lists. In C++, the suggested architecture is a single, long List with certain nodes "remembered" in the _buckets array. This is not required for the programming assignment. If it is easier for you, you can create separate Lists .

You are to implement the below UnorderedMap functions.

Implement the following functions:

Description: Returns the index of the bucket for hash code code . You should consider utilizing the provided _range_hash(size_type hash_code, size_type bucket_count) function. You can call this _bucket function from within the size_type _bucket(const Key &key) function, once you have a hash code for its key .

Time Complexity: O(1) – Constant Time

Used In: _bucket , _find , insert

Description: Returns the index of the bucket for key key . Elements (if any) with keys equivalent to key are always found in this bucket. You can call this function from within the size_type _bucket(const value_type &val) function passing in the key value in val as the parameter.

Used In: erase , bucket

Description: Returns the index of the bucket for value_type val . Elements (if any) with keys equivalent to the key value in val are always found in this bucket.

Used In: operator++ , insert

Description: Starts with the nodes in bucket bucket and iterates forward until the key matches key , returning the node where the keys match. If no such match occurs, returns nullptr .

Time Complexity: Average case: O(1) , Worst case: O( size() )

Used In: _find , insert

Description: Calls _find(size_type code, size_type bucket, const Key & key) with the code from the _hash and the bucket from the _bucket functions called on key and code respectively.

Used In: find , erase

Description: Inserts a new node with pair value at index bucket in the array of _buckets as the new bucket head. This is not necessarily the global head, but is the first node in the bucket. If the global _head is empty or the bucket index of _head is greater than value 's bucket index ( head should be in the first populated bucket), the inserted node also becomes the new _head . The pair value should be moved into the node.

Used In: insert

Description: Moves the contents from map src into map dst . This is meant to be used in the move constructor and move assignment operator functions.

Used In: move constructor , move assignment operator

Description: Constructs empty container. You must ensure that the _bucket_count is prime by calling the next_greater_prime function which will return the prime that is at least as large as bucket_count . If you do not have a prime _bucket_count , very bad things can happen to the efficiency of the UnorderedMap .

Test Names: constructor

Link: https://en.cppreference.com/w/cpp/container/unordered_map/unordered_map

Description: Destructs the UnorderedMap . The destructors of the elements are called and the used storage is deallocated. Note, that if the elements are pointers, the pointed-to objects are not destroyed.

Time Complexity: O( size() ) – Linear Time

Test Names: used frequently

Link: https://en.cppreference.com/w/cpp/container/unordered_map/~unordered_map

Description: Constructs the container with the copy of the contents of other, copies the load factor, the predicate, and the hash function as well.

Test Names: constructor_copy

Description: Constructs the container with the contents of other using move semantics.

Test Names: constructor_move

Description: Replaces the contents with a copy of the contents of other.

Time Complexity: O( size() + other.size() )

Test Names: operator_copy

Link: https://en.cppreference.com/w/cpp/container/unordered_map/operator=

Description: Replaces the contents with those of other using move semantics (i.e. the data in other is moved from other into this container). other is in a valid but unspecified state afterwards.

Test Names: operator_move

Description: Erases all elements from the container. After this call, size() returns zero.

Invalidates any references, pointers, or iterators referring to contained elements. May also invalidate past-the-end iterators.

Time Complexity: O( size() ) – Linear Time Test Names: clear_and_empty

Link: https://en.cppreference.com/w/cpp/container/unordered_map/clear

Description: Returns the number of elements in the container.

Link: https://en.cppreference.com/w/cpp/container/unordered_map/size

Description: Checks if the container has no elements.

Test Names: clear_and_empty

Link: https://en.cppreference.com/w/cpp/container/unordered_map/empty

Description: Returns the number of buckets in the container.

Link: https://en.cppreference.com/w/cpp/container/unordered_map/bucket_count

Description: Returns a const_iterator to the first element of the UnorderedMap .

If the UnorderedMap is empty, the returned iterator will be equal to end() .

Test Names: iterator

Link: https://en.cppreference.com/w/cpp/container/unordered_map/begin

Description: Returns a const_iterator to the element following the last element of the UnorderedMap .

This element acts as a placeholder; attempting to access it results in undefined behavior.

Link: https://en.cppreference.com/w/cpp/container/unordered_map/end

Description: Returns an iterator to the first element of the UnorderedMap .

Description: Returns an iterator to the element following the last element of the UnorderedMap .

Description: Returns a local iterator to the first element of the bucket with index n .

Test Names: local_iterator

Link: https://en.cppreference.com/w/cpp/container/unordered_map/begin2

Description: Returns a local iterator to the element following the last element of the bucket with index n . This element acts as a placeholder, attempting to access it results in undefined behavior.

Link: https://en.cppreference.com/w/cpp/container/unordered_map/end2

Description: Returns the number of elements in the bucket with index n .

Time Complexity: O(elements in n ) – Linear Time

Test Names: bucket_size

Link: https://en.cppreference.com/w/cpp/container/unordered_map/bucket_size

Description: Returns the average number of elements per bucket, that is, size() divided by bucket_count() .

Test Names: load_factor

Link: https://en.cppreference.com/w/cpp/container/unordered_map/load_factor

Description: Returns the index of the bucket for key key . Elements (if any) with keys equivalent to key are always found in this bucket. The returned value is valid only for instances of the container for which bucket_count() returns the same value.

The behavior is undefined if bucket_count() is zero.

Test Names: bucket

Link: https://en.cppreference.com/w/cpp/container/unordered_map/bucket

Description: Inserts value using move semantics. Returns a pair consisting of an iterator to the inserted element (or to the element that prevented the insertion) and a bool denoting whether the insertion took place ( true if insertion happened, false if it did not).

Test Names: insert_and_move

Link: https://en.cppreference.com/w/cpp/container/unordered_map/insert

Description: Inserts value using copy semantics. Returns a pair consisting of an iterator to the inserted element (or to the element that prevented the insertion) and a bool denoting whether the insertion took place ( true if insertion happened, false if it did not).

Test Names: insert_and_local_iterator , insert_and_global_iterator

Description: Finds an element with key equivalent to key . If no such element is found, past-the-end (see end() ) iterator is returned.

Test Names:

Link: https://en.cppreference.com/w/cpp/container/unordered_map/find

Description: Inserts a value_type object constructed in-place if the key does not exist. Returns a reference to the mapped value of the new element if no element with key key existed. Otherwise, returns a reference to the mapped value of the existing element whose key is equivalent to key .

Test Names: access_operator

Link: https://en.cppreference.com/w/cpp/container/unordered_map/operator_at

Description: Removes the element at pos . The iterator pos must be valid and dereferenceable. Thus the end() iterator (which is valid, but is not dereferenceable) cannot be used as a value for pos . Returns an iterator following the last removed element.

Test Names: erase_iterator

Link: https://en.cppreference.com/w/cpp/container/unordered_map/erase

Description: Removes the element (if one exists) with the key equivalent to key . Returns the number of elements removed ( 0 or 1 ).

Test Names: erase

Provided Helper

Description: Prints everything in map to os (default: std::cout ). This is useful for debugging purposes.

Time Complexity: Linear in the size of the container, i.e., the number of elements.

This is an iterator to all of the nodes within the UnorderedMap . It should jump from one bucket to the next as it iterates along the UnorderedMap . It should visit every node within the bucket before moving to the next bucket.

Description: Creates an iterator to the key-value pair belonging to the HashNode pointed to by ptr .

Description: Creates a basic_iterator by default, where the pointer beloning to the iterator is nullptr .

Description: Return a reference to the key-value pair beloning to the _node owned by this iterator.

Description: Return a pointer to the key-value pair beloning to the _node owned by this iterator.

Description: Change the _node to be the next _node in the UnorderedMap , even if that node is in a different bucket. Return a reference to the iterator after the change.

Description: Change the _node to be the next _node in the UnorderedMap , even if that node is in a different bucket, but return a copy of the iterator from before the change.

Test Names: iterator , insert_and_global_iterator

Description: Test whether two basic_iterator s refer to the same HashNode .

Description: Test whether two basic_iterator s refer to different HashNode s.

Test Names: insert_and_global_iterator , iterator

This is an iterator to the nodes within a single bucket of the UnorderedMap .

Description: Creates a local_iterator to the key-value pair belonging to the HashNode pointed to by ptr limited to the bucket bucket within map .

Description: Creates a local_iterator by default, where the pointer beloning to the local iterator is nullptr .

Test Names: local_iterator , insert_and_local_iterator

Description: Change the _node to be the next _node in the UnorderedMap . If that node is in a different bucket, change _node to be nullptr . Return a reference to the iterator after the change.

Description: Change the _node to be the next _node in the UnorderedMap . If that node is in a different bucket, change _node to be nullptr . Return a copy of the local_iterator from before the change.

Description: Test whether two local_iterator s refer to the same HashNode .

Description: Test whether two local_iterator s refer to different HashNode s.

For this assignment, you are also tasked with designing 2 significant hashing algorithms, which could be used in a hash table. Each of the functions also provides some psuedocode.

polynomial_rolling_hash size_t operator() (std::string const & str) const;

Description: Returns the hash code resulting from hashing str using a polynomial rolling hash algorithm. To pass our test cases, you will need to have b be 19 and m be 3298534883309ul .

Time Complexity: O( str.size() ) – Linear Time

Test Names: polynomial_hash

Link: https://en.wikipedia.org/wiki/Rolling_hash

Pseudocode:

fnv1a_hash size_t operator() (std::string const & str) const;

Description: Returns the hash code resulting from hashing str using the fnv1a algorithm. To pass our test cases, you will need to have the prime be 0x00000100000001B3 and the basis be 0xCBF29CE484222325 .

Test Names: fnv1a_hash

Link: https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function

In cpp, the XOR (exclusive or) operator is ^ . You can use it similarly to a mathematical operator such as + . For example

• Hashing Data Structure - GeeksforGeeks
• Hashing (Separate Chaining) - GeeksforGeeks
• Hash table - Wikipedia
• Hash Table - Tutorialspoint
• Your textbook Chapter 5 Section 3 (page 196)

Unordered maps are perhaps the most commonly used data structure. You will encounter them all of the time in Software Engineering and should be familiar with using them. The specifics of implementation of Hash Tables (Unordered maps) will likely never appear again after this project.

In light of the difficulty of the project, you need only implement an UnorderedMap . If you want to see an application, the main.cpp creates an UnorderedMap called map with at least 30 buckets and gathers statistics about the map after inserting many random values.

First consult this guide: tests/README.md

To run the tests, you need to rename main.cpp or you need to rename the int main function within that file.

Execute the following commands from the leyk-csce221-assignment-unordered-map folder to accomplish what you need:

Build all of the tests

Run the test called <test-name> . Replace <test-name> with the name of any .cpp file in the ./tests/tests folder.

Run every test in the ./tests/tests folder.

Debugging tests – For a detailed view, see ./tests/README.md .

Alex recommends you use cgdb which has the same commands as gdb but a better user interface. You can install it with sudo apt install cgdb on WSL or brew install cgdb on MacOS (provided you have brew )

The first command builds the tests, the next enters the folder where the tests were build. The third invokes gdb ( use lldb if on Mac OSX ) which is used to debug the program by examining Segmentation Faults and running code line-by-line. Finally, the last command takes you back to the top-level directory.

Incremental Testing:

To ensure the correctness of an insert, the bucket iterator has to be fully implemented so the test cases can compare the insertion location against the correct location. Completing insert , bucket_iterator , and the required helpers is fairly involved. We suggest the following order:

• constructor : complete bucket_count , constructor , and size .
• insert_and_global_iterator : complete begin , end , insert , iterator::operator++(int) , iterator::operator->() , and iterator::operator!= . (You may wish to complete the _insert_into_bucket , _bucket , and _find helpers for insert .)
• insert_and_local_iterator : complete bucket_size , begin(bucket) , end(bucket) , local_iterator::operator++(int) , local_iterator::operator!= , and local_iterator::operator->() .

After passing these tests, you should be able to selectively complete the remaining methods.

main.cpp is a test bench which compares four hash functions and their effect on the spatial distribution of values over the buckets. You can test the performance of your map on the following string hash functions:

• Zero Hash: A hash function which always maps to zero.
• First Character Hash: A hash function which returns the first element in the string.
• Polynomial Rolling Hash: A variant of the polynomial hash which appears in the lecture notes. (Roughly based on a linear congruential generator.)
• FNV1a: GCC uses a variant of FVN-1A.

This function will be applied to unique keys consisting of randomly generated animals:

The program will calculate the load-factor, load-variance, and plot the proportion of data in each bucket. A well-designed hash function should distribute the sample data uniformly over the buckets.

Submit the following file and no other files to Gradescope:

• UnorderedMap.h
• hash_functions.h
• hash_functions.cpp
• Makefile 1.6%