Sunday, September 15, 2024

unordered_map

Overview
The standard library provides unordered_map to store key value pairs in a lookup table where keys are unique and unsorted .

Details
unordered_map is basically a unsorted hash table of  elements where each  element is a key, value pair. The keys are unique, that can be used to search and retrieve elements fast. elements are stored in buckets using the hash() function provided as the template parameter. 
A bucket is a slot in the container's internal hash table to which elements are assigned based on the hash value of the key. The equal_to() template parameter represents the compare function to check equality of two keys.

Syntax
The syntax is as below. Template parameter Key represents the datatype to store, Hash represents hash function object to generate, Pred represents comparison function object  to compare two Key data types and Alloc represents the allocator used for storage.
template <class Key, class Value, class Hash = hash<Key>, class Pred = equal_to<Key>, class Alloc = allocator<Key>> 
class unorered_map;

Members
 It defines following types
NameDescription
key_typeThe first template parameter (Key)
mapped_typeThe second template parameter (Value)
value_typepair<Key,Value>
hasherThe second template parameter (Hash)
key_equalThe third template parameter (Pred)
allocator_typeThe third template parameter (Alloc)
referencevalue_type&
const_referenceconst value_type&
pointerallocator_traits<allocator_type>::pointer
const_pointerallocator_traits<allocator_type>::const_pointer
iteratorforward iterator to value_type convertible to const_iterator
const_iteratorforward iterator to const value_type
local_iteratorSame as iterator. This iterator can be used to iterate through a single bucket but not across buckets.
const_local_iteratorSame as const_iterator. This iterator can be used to iterate through a single bucket but not across buckets.
difference_typea signed integral type
size_typean unsigned integral type

Operation
unordered_map can be graphically represented as below. It's basically a hash table. It holds values [{1,100},{2,200}, {3,300},{4,400}].


New elements can be added or removed or searched in the unordered_map.  A hashtable is internally used for storage. 
As shown above, a hashtable basically comprises of multiple  buckets where the elements are stored. The hash function determines to which bucket the element will go. A bucket can contain multiple elements in such case, equal_to function is used to determine correct element.
The hashtable can be created with a user defined value. Otherwise a default value is used. Similarly custom hash and equal_to functions can be supplied. Otherwise default hash and equal_to function objects are used for hashing and equality checks.
The load_factor influences the probability of collision in the hash table (i.e., the probability of two elements being located in the same bucket). load_factor is calculated as 
load_factor = size / bucket_count.
The container automatically increases the number of buckets to keep the load factor below  max_load_factor, causing a rehash each time an expansion is needed. This will invalidate iterators.
reserve can be used allocate more buckets.

Complexity
The cost of Insertion or removal or search is O(1).

Functionality

Constructors
In following constructors use default values. Custom number of buckets, custom hash, custom compare operations, custom allocators can be supplied  by passing them as an additional arguments. 

NameDescription
unordered_map ()Default Constructor.

Example:
//v:
unordered_map<int,int> v;
unordered_map (InputIterator first, InputIterator last)Constructs a set and copies the elements in the range.

Example:
pair<int,int> a[]{{1,100},{2,200}, {3,300},{4,400},{5,500}};
//[5,500] [4,400] [3,300] [2,200] [1,100] 
unordered_map<int,int> v(begin(a),end(a));
unordered_map (const unordered_map & x)copy constructor.
unordered_map (unordered_map && x)move constructor.
unordered_map (initializer_list<value_type> il)initializer_list constructor.

Example:
//[5,500] [4,400] [3,300] [2,200] [1,100] 
unordered_map<int,int> v{{1,100},{2,200}, {3,300},{4,400},{5,500}};

Iterator
NameDescription
iterator begin()
iterator end()

Returns iterator to beginning and end of the unordered_map.

Example:
//[5,500] [4,400] [3,300] [2,200] [1,100] 
unordered_map<int,int> v{{1,100},{2,200}, {3,300},{4,400},{5,500}};
//prints [5,500] [4,400] [3,300] [2,200] [1,100] 
for (auto itr=v.begin(); itr!=v.end(); ++itr)
    cout << *itr << ' ';
const_iterator cbegin()
const_iterator cend()		Returns const_iterator to beginning and end of the unordered_map.

Example:
//[5,500] [4,400] [3,300] [2,200] [1,100] 
unordered_map<int,int> v{{1,100},{2,200}, {3,300},{4,400},{5,500}};
//prints [5,500] [4,400] [3,300] [2,200] [1,100] 
for (auto itr=v.cbegin(); itr!=v.cend(); ++itr)
    cout << *itr << ' ';

Capacity
NameDescription
size_type size() Returns the number of elements in the unordered_map.

Example:
//[5,500] [4,400] [3,300] [2,200] [1,100] 
unordered_map<int,int> v{{1,100},{2,200}, {3,300},{4,400},{5,500}};
//prints 5
cout << v.size();
size_type max_size() Returns maximum  possible number of elements possible. A very large number.
bool empty()Test whether unordered_map is empty. 

Element Access
NameDescription
iterator find(const value_type& val)Returns iterator to the first element or end if not found.

Example:
//[5,500] [4,400] [3,300] [2,200] [1,100] 
unordered_map<int,int> v{{1,100},{2,200}, {3,300},{4,400},{5,500}};
//itr = v.begin()+3
auto itr = v.find(002);
//itr = v.end()
itr = v.find(006);
size_type count (const value_type& val)Returns number of elements matching val.

Example:
//[5,500] [4,400] [3,300] [2,200] [1,100] 
unordered_map<int,int> v{{1,100},{2,200}, {3,300},{4,400},{5,500}};
//knt=1
auto knt =v.count(002);
//knt=0
knt =v.count(006);
  1. iterator lower_bound(const value_type& val)
  2. iterator upper_bound(const value_type& val)
  1. Returns iterator to the first element matching val or end
  2. Returns iterator next to the last  element matching val or end. Note that end will be returned if matching element is the last in the set.
Example:
//[5,500] [4,400] [3,300] [2,200] [1,100] 
unordered_map<int,int> v{{1,100},{2,200}, {3,300},{4,400},{5,500}};
//itr = v.begin()+3
auto itr = v.lower_bound(002);
//itr = v.begin()+4
itr = v.upper_bound(002);
//itr = v.begin()
itr = v.lower_bound(005);
//itr = v.begin()+1
itr = v.upper_bound(005);
//itr = v.end()
itr = v.lower_bound(006);
//itr = v.end()
itr = v.upper_bound(006);
pair<iterator,iterator>  equal_range(
                const value_type& val)		Returns a pair object containing lower_bound and upper_bound iterators matching value val.

Example:
//[5,500] [4,400] [3,300] [2,200] [1,100] 
unordered_map<int,int> v{{1,100},{2,200}, {3,300},{4,400},{5,500}};
//p: {v.begin()+3,v.begin()+4}
auto p = v.equal_range(002);
//p: {v.begin()+0,v.begin()+1}
p = v.equal_range(005);//p: {v.end(),v.end()}

p = v.equal_range(006);

Modifiers
NameDescription
  1. void insert(InputIterator first, InputIterator last)
  2. iterator insert(const_iterator hintpos, const value_type& val)
  3. pair<iterator,bool>  insert(const value_type& val)
  4. void insert(initializer_list<value_type> il)

  1. Inserts the  elements in the range.
  2. Inserts an element initialized with val. hintpos, is used to scout for location.  Returns an iterator to the inserted element or existing element.
  3. Insert an element initialized with with val.  Returns a pair object containing iterator to the inserted element or existing element and bool with value true if a new value is inserted otherwise false.
  4. Insert elements with the contents of initializer_list.
    Example:
    pair<int,int> a[]{{1,100},{2,200}, {3,300},{4,400},{5,500}};
    unordered_map<int,int> v;

//(1) 
// v:[3,300] [2,200] [1,100] 
v.insert(begin(a),begin(a)+3);
    
//(2) 
// v:[4,400] [3,300] [2,200] [1,100] 
//it=begin(v)
auto it = v.insert(v.end(),{004,400});
    
//(3) 
// v:[5,500] [4,400] [3,300] [2,200] [1,100] 
//p=<begin(v),true>
auto p = v.insert({005,500});
    
//(4) 
// v:[6,600] [5,500] [4,400] [3,300] [2,200] [1,100] 
v.insert({006,600});
    1. iterator erase(const_iterator pos)
    2. iterator erase(const_iterator first, const_iterator last)
    3. size_type erase( const value_type& val)


    1. Erases element at pos. Returns an iterator that points to the element that was  located after the last erased element.
    2. Erases elements in the range. Returns an iterator that points to the element that was  located after the last erased element.
    3. Erases the elements of value val. Returns number of elements erased.
      Example:
      //[5,500] [4,400] [3,300] [2,200] [1,100] 
unordered_map<int,int> v{{1,100},{2,200}, {3,300},{4,400},{5,500}};

      //(1)
// v:[4,400] [3,300] [2,200] [1,100] 
      //it = begin(v)
auto it = v.erase(cbegin(v));
    
//(2)
// v:[4,400] [3,300]
//it = begin(v)+2
it = v.erase(begin(v)+2,cend(v));
    
//(3)
// v:[4,400]
//knt=1
auto knt = v.erase(003);
      void swap(unordered_set& v)Swap content with v. Note T has to be same.

      Example:
      unordered_map<int,int> v{{1,100},{2,200}, {3,300}};
      unordered_map<int,int> v2{{4,400},{5,500}};
      //v2:[3,300] [2,200] [1,100] 
      //v:[5,500] [4,400] 
      v2.swap(v);
      void clear()Clears the contents.

      Example:
      unordered_map<int,int> v{{1,100},{2,200},{3,300},{4,400},{5,500}};
      //v:{}
      v.clear();
      pair<iterator,bool> emplace(Args ...arg)Constructs and inserts an element using arg. Returns a pair object containing an iterator to the inserted element and true if succeeded or an iterator to the existing element and false on failure.

      Example:
      unordered_map<int,int> v{{1,100},{2,200},{3,300},{4,400},{5,500}};
      //v:[5,500] [4,400] [3,300] [2,200] [1,100] 
      //p: {v.begin()+3,false}      
auto p = v.emplace(make_pair(002,200));
      //v:[6,600] [5,500] [4,400] [3,300] [2,200] [1,100]
      //p: {v.begin(),true}
      p = v.emplace(make_pair(006,600));
      iterator emplace_hint(iterator hintpos, Args ...arg))Constructs and attempts to insert an element at the hintpos using arg. If returns an iterator to the new element or existing element. Note that the hintpos is used as starting point to scout to add new element. It  will go round robin if the scout is exhausted.

      Example:
      unordered_map<int,int> v({{1,100},{2,200},{3,300},{4,400},{5,500}});
      //v:[5,500] [4,400] [3,300] [2,200] [1,100] 
      //itr:v.begin()+3
auto itr = v.emplace_hint(v.begin(),make_pair(002,200));
//v:[6,600] [5,500] [4,400] [3,300] [2,200] [1,100] 
      //itr:v.begin()
itr = v.emplace_hint(v.end(),make_pair(006,600));

      Buckets
      NameDescription
      size_type bucket_count() Returns the number of buckets in the unordered_set.

      Example:
      unordered_map<int,int> v{{1,100},{2,200},{3,300},{4,400},{5,500}};
      //prints 13
      cout << v.bucket_count();
      size_type max_bucket_count() Returns maximum  possible number of buckets possible. A very large number.
      size_type  bucket_size(size_type  n)Returns number of elements in the current bucket.

      Example:
      unordered_map<int,int> v{{1,100},{2,200},{3,300},{4,400},{5,500}};
      cout << "bucket\tbucket_size" << endl;
for ( auto i:v)
    cout << v.bucket(i.first) << "\t" << v.bucket_size(v.bucket(i.first)) << endl;

/*
bucket	bucket_size
5	1
4	1
3	1
2	1
1	1
*/
      size_type  bucket(const key_type key)Returns the bucket number where the key is located.

      Example:
      unordered_map<int,int> v{{1,100},{2,200},{3,300},{4,400},{5,500}};
      cout <<       "key\tbucket" << endl;
for ( auto itr=v.begin(); itr !=  v.end(); ++itr)
    cout << setw(3) << setfill('0') <<  right <<  itr->first 
              << '\t' << dec << v.bucket(itr->first) << endl;
      /*
key	bucket
005	5
004	4
003	3
002	2
001	1
*/

      Hash Policy
      NameDescription
      size_type load_factor() 
      Returns the current load factor. It needs to stay under  or equal to max_load_factor().

      Example:
      unordered_map<int,int> v{{1,100},{2,200},{3,300},{4,400},{5,500}};
      cout << "size = \t\t" << v.size() << endl;
cout << "bucket_count = \t" << v.bucket_count() << endl << endl;
cout << "load_factor = size() / bucket_count()" << endl << endl;
cout << "load_factor = \t\t" << v.load_factor() << endl;
cout << "max_load_factor = \t" << v.max_load_factor() << endl;

/*
output:
size =          5
bucket_count = 	13

load_factor = size() / bucket_count()

load_factor = 		0.384615
max_load_factor = 	1
*/
      1. float max_load_factor() 
      2. void max_load_factor(float z)
      1. Returns current maximum  load factor 
      2. Sets current maximum  load factor 
      Example:
          float amlf[]{1.0f,0.5f};
    for (auto clf :amlf)
    {
        unordered_map<char,int> v;
        v.max_load_factor (clf);
        for (auto c='a'; c <= 'z'; ++c)
            v.emplace(make_pair(c,c));
  
        cout << "max_load_factor: " << v.max_load_factor() << endl;
        cout << "size: " << v.size() << endl;
        cout << "bucket_count: " << v.bucket_count() << endl;
        cout << "load_factor: " << v.load_factor() << endl;
        cout << endl;
          }
/*
max_load_factor: 1
size: 26
bucket_count: 29
load_factor: 0.896552

max_load_factor: 0.5
size: 26
bucket_count: 97
load_factor: 0.268041
*/
      void reserve(size_type  n)
      Sets the number of buckets in the container to hold at least  n elements.

      Example:
      unordered_map<int,int> v;
cout <<   "bucket_count before rehash: "  << v.bucket_count() << endl;
v.reserve(10);
cout <<   "bucket_count after rehash: "  << v.bucket_count() << endl;

/*
output:
bucket_count before reserve: 1
      bucket_count after reserve: 11
      */

      void rehash(size_type  n)Sets the number of buckets in the container to n or more.

      Example:
      unordered_map<int,int> v;
cout <<   "bucket_count before rehash: "  << v.bucket_count() << endl;
v.rehash(10);
cout <<   "bucket_count after rehash: "  << v.bucket_count() << endl;

/*
output:
bucket_count before rehash: 1
bucket_count after rehash: 11
*/

      at
      Labels:

      No comments:

      Post a Comment

      Subscribe to: Post Comments (Atom)