Monday, September 16, 2024

unordered_multimap

Overview
The standard library provides unordered_multimap to store key value pairs in a hash table where keys are unsorted and can have duplicates.

Details
unordered_multimap is basically a unsorted hash table of  elements where each  element is a key, value pair. The keys can be duplicate, 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_multimap;

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_multimap can be graphically represented as below. It's basically a hash table. It holds values [{1,100}, {2,200}, {3,300}, {4,400}, {5,500}, {3,350}]. Notice key value 3 is repeated with different values.

New elements can be added or removed or searched in the unordered_multimap.  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_multimap ()Default Constructor.

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

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

Iterator
NameDescription
iterator begin()
iterator end()

Returns iterator to beginning and end of the unordered_multimap.

Example:
//[5,500] [4,400] [3,300] [3,350] [2,200] [1,100] 
unordered_multimap<int,int> v{{1,100},{2,200},{3,300},{4,400},{5,500},{3,350}};
//[5,500] [4,400] [3,300] [3,350] [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_multimap.

Example:
//[5,500] [4,400] [3,300] [3,350] [2,200] [1,100] 
unordered_multimap<int,int> v{{1,100},{2,200},{3,300},{4,400},{5,500},{3,350}};
//[5,500] [4,400] [3,300] [3,350] [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_multimap.

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

//prints 6
cout << v.size();
size_type max_size() Returns maximum  possible number of elements possible. A very large number.
bool empty()Test whether unordered_multimap 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] [3,350] [2,200] [1,100] 
unordered_multimap<int,int> v{{1,100},{2,200},{3,300},{4,400},{5,500},{3,350}};


//itr = v.begin()+4
auto itr = v.find(2);

//itr = v.begin()+2
itr = v.find(3);

//itr = v.end()
itr = v.find(6);
size_type count (const value_type& val)Returns number of elements matching val.

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

//knt=1
auto knt =v.count(2);

//knt=2
knt =v.count(3);

//knt=0
knt =v.count(6);
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,350] [3,300] [2,200] [1,100] 
unordered_multimap<int,int> v{{1,100},{2,200},{3,300},{4,400},{5,500},{3,350}};

//p: {v.begin()+2,v.begin()+4}
auto p = v.equal_range(3);

//p: {v.begin()+5,v.end()}
p = v.equal_range(1);


//p: {v.end(),v.end()}
p = v.equal_range(6);


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 an iterator to the inserted element.
  4. Insert elements with the contents of initializer_list.
    Example:

    pair<int,int> a[]{{1,100},{2,200},{3,300},{4,400},{5,500},{3,350}};
    unordered_multimap<int,int> v;

//(1) 
// v:[3,300] [2,200] 
v.insert(begin(a)+1,begin(a)+3);
    
//(2) 
// v:[3,300] [3,350] [2,200] 
//it=begin(v)+1
auto it = v.insert(v.begin(),{3,350});
    
//(3) 
// v:[1,100] [3,300] [3,350] [2,200] 
//it:begin(v)
it = v.insert({1,100});
    
//(4) 
// v:[4,400] [1,100] [3,300] [3,350] [2,200]
v.insert({4,400});
    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:

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

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

      Example:
      unordered_multimap<int,int> v{{1,100},{2,200}, {3,300}};
unordered_multimap<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 and resets size to 0.

      Example:
      unordered_multimap<int,int> v{{1,100},{2,200},{3,300},{4,400},{5,500},{3,350}};
      //v:{}
      v.clear();
      iterator emplace(Args ...arg)Constructs and inserts an element using arg. Returns an iterator to the inserted element.

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

      //v:[1,100] [2,200] [3,350] [3,300] [4,400] [5,500]  
      //itr: v.begin()+2      
auto itr = v.emplace(make_pair(3,350));
      

      //v:[6,600] [1,100] [2,200] [3,350] [3,300] [4,400] [5,500]
      //itr: v.begin()
      itr = v.emplace(make_pair(6,600));   
      iterator emplace_hint(iterator hintpos, Args ...arg))Constructs and attempts to insert an element at the hintpos using arg. It returns an iterator to the new 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_multimap<int,int> v({{1,100},{2,200},{3,300},{4,400},{5,500}});
      
//v:[1,100] [2,200] [3,350] [3,300] [4,400] [5,500] 
      //itr:v.begin()+2
auto itr = v.emplace_hint(v.begin(),make_pair(3,350));

//v:[6,600] [1,100] [2,200] [3,350] [3,300] [4,400] [5,500] 
      //itr:v.begin()
itr = v.emplace_hint(v.end(),make_pair(6,600));



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

      Example:
      unordered_multimap<int,int> v{{1,100},{2,200},{3,300},{4,400},{5,500},{3,350}};
      //prints 7
      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_multimap<int,int> v{{1,100},{2,200},{3,300},{4,400},{5,500},{3,350}};
      vector<int> v2;
for_each(v.begin(), v.end(), [&v2](auto kv){v2.push_back(kv.first);});
unique(v2.begin(),v2.end());
cout << "bucket\tbucket_size" << endl;
for ( auto i:v2)
    cout << v.bucket(i) << "\t" << v.bucket_size(v.bucket(i)) << endl;

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

      Example:
      unordered_multimap<int,int> v{{1,100},{2,200},{3,300},{4,400},{5,500},{3,350}};
      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
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_multimap<int,int> v{{1,100},{2,200},{3,300},{4,400},{5,500},{3,350}};
      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;

/*
size = 		6
bucket_count = 	7

load_factor = size() / bucket_count()

load_factor = 		0.857143
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_multimap<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_multimap<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_multimap<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)