unordered_set functions in C++ Part -II

unordered_set

File unordered_set.h

Unordered sets are containers that store unique elements in no particular order, and which allow for fast retrieval of individual elements based on their value.

Keys are immutable, therefore, the elements in an unordered_set cannot be modified.

Internally, the elements in the unordered_set are not sorted in any particular order but organized into buckets depending on their hash values to allow for fast access to individual elements directly by their values (with a constant average time complexity on average).

Some of the functions of unordered_set

find(): It tries to locate an element in an unordered_set.

get_allocator(): It returns the allocator object used by the unordered_set.

hash_function(): It returns the hash functor object with which the unordered_set was constructed.

insert(): It attempts to insert an element or elements into the unordered_set.

key_seq(): It returns the key comparison object with which the unordered_set was constructed.

load_factor(): It returns the average number of elements per bucket.

max_bucket_count(): It returns the maximum number of buckets of the unordered_set.

max_load_factor(): It returns (or set the max load factor value) a value to which the unordered_set load factor is less.

max_size(): It returns the maximum size of the unordered_set.

rehash(): It may rehash the unordered_set.

reserve(): It prepares the unordered_set for a specified number of elements.

size(): It returns the size of the unordered_set.

swap():  It swaps data with another unordered_set.

unordered_set swap() in C++

swap(): This function is available in the File: unordered_set.h. This function is a build-in function in STL of C++. This function swaps data with another unordered_set.

Syntax:

void std::unordered_set<int>::swap(std::unordered_set<int> &__x)

This function takes one argument of type unordered_set as its parameter. This function swaps data with another unordered_set.

Parameters: One parameter is required for this method.

__x – An unordered_set of the same element and allocator types.

This exchanges the elements between two sets in constant time.

File: unordered_set.h

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_set<int> st1 = {9, 4, 5};

    unordered_set<int> st2 = {10, 25, 124, 67};

    cout << "unordered_set 1 size before swap :" << 
             st1.size() << "\n";
    cout << "unordered_set 2 size before swap :" << 
             st2.size() << "\n";

    st1.swap(st2);

    cout << "\n";

    cout << "unordered_set 1 size after swap :" << 
             st1.size() << "\n";
    cout << "unordered_set 2 size after swap :" << 
             st2.size() << "\n";
    return 0;
}

Output:

unordered_set 1 size before swap :3
unordered_set 2 size before swap :4

unordered_set 1 size after swap :4
unordered_set 2 size after swap :3

unordered_set size() in C++

size(): This function is available in the File: unordered_set.h. This function is a build-in function in STL of C++. This function returns the number of elements in the unordered_set.

Syntax:

std::size_t std::unordered_set<int>::size() const

This function returns the size of the unordered_set.

Parameters: NA

File: unordered_set.h

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_set<int> st = {1, 2, 3, 4, 5};

    cout << st.size() << "\n";
    return 0;
}

Output:

5

unordered_set reserve() in C++

reserve(): This function is available in the File: unordered_set.h. This function is a build-in function in STL of C++. This function reserve the number of elements in unordered_set.

Syntax:

void std::unordered_set<int>::reserve(std::size_t __n)

This function takes one argument of type size_t as its parameter. This function prepare the unordered_set for a specified number of elements.

Parameters: One parameter is required for this method.

__n – Number of elements required.

Same as rehash(ceil(n / max_load_factor())).

File: unordered_set.h

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_set<int> st = {1, 2, 3, 4};
    int n = 56;

    cout << "Before reserve bucket count is " << 
              st.bucket_count() << "\n";
    st.reserve(n);

    cout << "After reserve bucket count is " << 
              st.bucket_count() << "\n";
    return 0;
}

Output:

Before reserve bucket count is 5
After reserve bucket count is 59 

unordered_set rehash() in C++

rehash(): This function is available in the File: unordered_set.h. This function is a build-in function in STL of C++. This function rehashes the unordered_set.

Syntax:

void std::unordered_set<int>::rehash(std::size_t __n)

This function takes one argument of type size_t as its parameter. This function may rehash the unordered_set.

Parameters: One parameter is required for this method.

__n – The new number of buckets.

Rehash will occur only if the new number of buckets respects the unordered_set maximum load factor.

File: unordered_set.h

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_set<int> st = {1, 2, 3, 4, 5};

    int n = 56;

    cout << "Before rehash bucket count is " << 
              st.bucket_count() << "\n";
    st.rehash(n);

    cout << "After rehash bucket count is " << 
              st.bucket_count() << "\n";
    return 0;
}

Output:

Before rehash bucket count is 7
After rehash bucket count is 59 

unordered_set max_size() in C++

max_size(): This function is available in the File: unordered_set.h. This function is a build-in function in STL of C++. This function returns the maximum size of the unordered_set.

Syntax:

std::size_t std::unordered_set<int>::max_size() const

This functions returns the maximum size of the unordered_set.

Parameters: NA

File: unordered_set.h

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_set<int> st = {1, 2, 3, 4, 5};

    cout << st.max_size() << "\n";
    return 0;
}

Output:

1152921504606846975

unordered_set max_load_factor() in C++

max_load_factor(): This function is available in the File: unordered_set.h. This function is a build-in function in STL of C++. This function returns (or set the max load factor value) a value to which the unordered_set load factor is less.

Approach 1: When the function does not take any argument.

Syntax:

float std::unordered_set<int>::max_load_factor() const

This functions returns a positive number that the unordered_set tries to keep the load factor less than or equal to.

File: unordered_set.h

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_set<int> st = {1, 2, 3, 4, 10, 23, 45};

    cout << st.max_load_factor() << "\n";
    return 0;
}

Output:

1

Approach 2: When the function takes one argument.

Syntax:

void std::unordered_set<int>::max_load_factor(float __z)

This function takes one argument of type float as its parameter. This functions change the unordered_set maximum load factor to the new value.

Parameters: One parameter is required for this function.

 __z – The new maximum load factor.

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_set<int> st = {1, 2, 3, 4, 10, 23, 45};
    float z = 0.45;
    st.max_load_factor(z);

    cout << "New load factor: " << st.max_load_factor() << "\n";
    return 0;
}

Output:

New load factor: 0.45

unordered_set max_bucket_count() in C++

max_bucket_count(): This function is available in the File: unordered_set.h. This function is a build-in function in STL of C++. This function returns the maximum number of buckets in the unordered_set.

Syntax:

std::size_t std::unordered_set<int>::max_bucket_count() const

This function returns the maximum number of buckets of the unordered_set.

Parameters: NA

File: unordered_set.h

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_set<int> st = {1, 2, 3, 4, 5, 67, 89};

    cout << st.max_bucket_count() << "\n";
    return 0;
}

Output:

1152921504606846975

unordered_set load_factor() in C++

load_factor(): This function is available in the File: unordered_set.h. This function is a build-in function in STL of C++ which returns the average number of elements per bucket.

Syntax:

float std::unordered_set<int>::load_factor() const

This function returns the average number of elements per bucket.

Parameters: NA

File: unordered_set.h

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_set<int> st = {1, 2, 3, 4, 5, 6, 89, 12};

    cout << st.load_factor() << "\n";
    return 0;
}

Output:

0.727273

unordered_set key_seq() in C++

key_seq(): This function is available in the File: unordered_set.h. This function is a build-in function in STL of C++.

Syntax:

std::equal_to<int> std::unordered_set<int>::key_eq() const

This functions returns the key comparison object with which the unordered_set was constructed.

File: unordered_set.h 

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_set<string> st;

    bool res = st.key_eq()("hello", "hello");
    if (res==1)
        cout << "equal\n";
    else
        cout << "not equal\n";

    return 0;
}

Output:

equal

unordered_set insert() in C++

insert(): This function is available in the File: unordered_set.h. This function is a build-in function is STL of C++.

Approach 1: When the single value into the unordered_set.

Syntax:

std::pair<std::__detail::_Node_iterator<int, true, false>, bool> std::unordered_set<int>::insert(const int &__x) 

This function takes one argument of type as similar to the type of unordered_set as its parameter. This function attempts to insert an element into the unordered_set.

Parameters: One parameter is required for this function.

__x – Element to be inserted.

Returns:  A pair, of which the first element is an iterator that points to the possibly inserted element, and the second is a bool that is true if the element was actually inserted. This function attempts to insert an element into the unordered_set.

Note: Insertion requires amortized constant time.

File: unordered_set.h

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_set<int> st = {3, 4, 5};

    vector<int> arr = {28, 35, 4, 54, 11};
    int value = 12;
    st.insert(value);
    cout << "Set elements are: ";
    for (auto it = st.begin(); it != st.end(); it++)
        cout << *it << " ";
    return 0;
}

Output:

Set elements are: 12 5 4 3 

Approach 2: When inserting the range elements into the unordered_set.

Syntax:

void std::unordered_set<int>::insert<std::vector<int>::iterator> (std::vector<int>::iterator __first, std::vector<int>::iterator __last) 

This function takes two arguments of type iterator. This function is a  template function that attempts to insert a range of elements.

Parameters:  Two parameters are required for this function.

__first – Iterator pointing to the start of the range to be inserted.

__last – Iterator pointing to the end of the range.

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_set<int> st = {3, 4, 5};

    vector<int> arr = {28, 35, 4, 54, 11};
    st.insert(arr.begin(), arr.end());
    cout << "Set elements are: ";
    for (auto it = st.begin(); it != st.end(); it++)
        cout << *it << " ";
    return 0;
}

Output:

Set elements are: 11 54 35 28 3 4 5

Approach 3: When inserting the initializer list into the unordered_set.

Syntax:

void std::unordered_set<int>::insert(std::initializer_list<int> __l)

This function takes one argument of type initializer_list as its parameter. This functions attempts to insert a list of elements into the unordered_set.

Parameters:  One parameter is required for this function.

__l – A std::initializer_list<value_type> of elements to be inserted.

Note: Complexity similar to that of the range constructor.

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_set<int> st = {3, 4, 5};

    vector<int> arr = {28, 35, 4, 54, 11};
    st.insert({234, 345});
    cout << "Set elements are: ";
    for (auto it = st.begin(); it != st.end(); it++)
        cout << *it << " ";
    return 0;
}

Output:

Set elements are: 234 3 345 4 5

Complexities:

Single element insertions

Average case: constant.

Worst case: linear in container size.

Multiple elements insertion

Average case: linear in the number of elements inserted.

Worst case: N*(size+1): number of elements inserted times the container size plus one.

unordered_set hash_function() in C++

hash_function(): This function is available in the File: unordered_set.h. This function is a build-in function in STL of C++.

Syntax:

std::hash<int> std::unordered_set<int>::hash_function() const

This function returns the hash functor object with which the unordered_set was constructed.

Parameters: NA

File: unordered_set.h

Returns: Returns the hash function object used by the unordered_set container.

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_set<string> st = {"Hello", "C++", "Program", 
                                 "World", "Code"};

    unordered_set<string>::hasher hash = st.hash_function();

    cout << hash("Hello") << "\n";

    cout << hash("C++") << "\n";

    return 0;
}

Output:

2275118702903107253
15518724754199266856

unordered_set get_allocator() in C++

get_allocator(): This function is available in the File: unordered_set.h. This function is a build-in function in STL of C++.

Syntax:

std::allocator<int> std::unordered_set<int>::get_allocator() const

This functions returns the allocator object used by the unordered_set.

Parameters: NA

File: unordered_set.h

Returns : The member function returns the stored allocator object.

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_set<int> st = {4, 6, 8, 12, 2, 5};

    unordered_set<int>::allocator_type type = st.get_allocator();

    int x = 4;
    cout << "Address is " << type.address(x) << "\n";

    cout << "Maximum size is " << type.max_size() << "\n";

    return 0;
}

Output:

Address is 0x61fda8
Maximum size is 4611686018427387903

unordered_set find() in C++

find(): This function is available in the File: unordered_set.h. This function is a build-in function in STL of C++.

Syntax:

std::unordered_set<int>::iterator std::unordered_set<int>::find(const int &__x)

This function takes one argument as its parameter. This function tries to locate an element in an unordered_set.

Parameters: One parameter is required for this method.

__x – Element to be located.

Returns: Iterator pointing to sought-after element, or end() if not found. This function takes a key and tries to locate the element with which the key matches.

File: unordered_set.h

Approach 1: When an element with the given key is present in the unordered_set.

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_set<int> st = {9, 5, 4, 3, 2, 10};

    int x = 4;
    unordered_set<int>::iterator it = st.find(x);

    if (it == st.end())
        cout << "Element is not found\n";
    else
        cout << "Element is found\n";

    return 0;
}

Output:

Element is found

Approach 2: When an element with the given key is not present in the unordered_set.

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_set<int> st = {9, 5, 4, 3, 2, 10};

    int x = 40;
    unordered_set<int>::iterator it = st.find(x);

    if (it == st.end())
        cout << "Element is not found\n";
    else
        cout << "Element is found\n";

    return 0;
}

Output:

Element is not found