C++ 11 Hash Table, Hash Map, Dictionaries, Set, Iterators

In this post we are going to look at general use of hash map, set, iterators, dictionaries in C++ 11. I wont do much explaining, if you want to know more I encourage you to dive deeper on the topic. You can think of this post as a laundry list of things you can keep around that might come handy at times.

To practice C++ code online cpp.sh or geeksforgeeks online IDE.

Hash Table Collision Resolution with Separate Chaining Src: https://en.wikipedia.org/wiki/Hash_table

Following is a simple hash table in C++

#include <iostream>
#include <map>
int main(){
  std::map<std::string, int> mymap;
  mymap["a"] = 1;
  mymap["b"] = 2;
  mymap["c"] = 4;
  mymap["a"] += 5;
  std::cout<<"key='a' --> mymap[key]="<<mymap["a"]<<"\n";
  for (auto i : mymap){
    std::cout<<"key:"<<i.first<<", val:"<<i.second<<"\n";
  }
  return 0;
}

std::set — Set data structure in C++

Functions associated with Set:
1. begin() — Returns an iterator to the first element in the set
2. end() — returns theoretical element that follows last element in the set
3. size() — Returns the number of elements in the set
4. max_size() — Returns the maximum number of elements that the set can hold
4. empty() — Returns whether the set is empty
5. pair <iterator, bool> insert(const g) — Adds a new element ‘g’ to the set
6. iterator insert (iterator position, const g) — Adds a new element ‘g’ at the position pointed by iterator
5. erase(iterator position) — Removes the element at the position pointed by the iterator
erase(const g)- Removes the value ‘g’ from the set
clear() — Removes all the elements from the set
6. key_comp() / value_comp() — Returns the object that determines how the elements in the set are ordered (‘<‘ by default)
7. find(const g) — Returns an iterator to the element ‘g’ in the set if found, else returns the iterator to end
8. count(const g) — Returns 1 or 0 based on the element ‘g’ is present in the set or not.
9. lower_bound(const g) — Returns an iterator to the first element that is equivalent to ‘g’ or definitely will not go before the element ‘g’ in the set
10. upper_bound(const g) — Returns an iterator to the first element that is equivalent to ‘g’ or definitely will go after the element ‘g’ in the set

Example of a set —

#include <iostream>
#include <set>
#include <iterator>
int main(){
 // empty set container
 std::set <int, std::greater <int> > mymap;
 // inserting elements in random order
 mymap.insert(40);
 mymap.insert(30);
 mymap.insert(60);
 mymap.insert(20);
 mymap.insert(50);
 mymap.insert(50); // only one 50 will be added to the set
 mymap.insert(10);
 // printing set mymap
 std::set <int, std::greater <int> > :: iterator i;
 std::cout << "The set mymap is : ";
 for (i = mymap.begin(); i != mymap.end(); ++i){
  std::cout << '\t' << *i;
 }std::cout << "\n";
 // assigning the elements from mymap to mymap2
 std::set <int> mymap2(mymap.begin(), mymap.end());
 // print all elements of the set mymap2
 std::cout << "\nThe set mymap2 after assign from mymap is : ";
 for (i = mymap2.begin(); i != mymap2.end(); ++i){
  std::cout << '\t' << *i;
 }std::cout << "\n";
 // remove all elements up to 30 in mymap2
 std::cout << "\nmymap2 after removal of elements less than 30 : ";
 mymap2.erase(mymap2.begin(), mymap2.find(30));
 for (i = mymap2.begin(); i != mymap2.end(); ++i){
  std::cout << '\t' << *i;
 }
// remove element with value 50 in mymap2
 int num;
 num = mymap2.erase (50);
 std::cout << "\nmymap2.erase(50) : ";
 std::cout << num << " removed \t" ;
 for (i = mymap2.begin(); i != mymap2.end(); ++i){
  std::cout << '\t' << *i;
 }std::cout << "\n";
 
 return 0;
}

The output looks like this —

The set mymap is : 	60	50	40	30	20	10

The set mymap2 after assign from mymap is : 	10	20	30	40	50	60

mymap2 after removal of elements less than 30 : 	30	40	50	60
mymap2.erase(50) : 1 removed 		30	40	60

std::map

#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
int main(){
  std::map<std::string, int> mymap;
  mymap["a"] = 1;
  mymap["b"] = 2;
  mymap["c"] = 4;
  mymap["z"] = 0;
  
  std::cout<<"mymap[key]="<<mymap["c"]<<"\n";
  
  
  
  for (auto i : mymap){
    std::cout<<"key:"<<i.first<<" val:"<<i.second<<"\n";
      
  }
  
  typedef std::function<bool(std::pair<std::string, int>, 
             std::pair<std::string, int>)> Comparator;
  Comparator comparator = [](std::pair<std::string, int> x ,
                            std::pair<std::string, int> y){
      return x.second < y.second;
  };
  std::set<std::pair<std::string, int>, Comparator> sortedmap(
     mymap.begin(), mymap.end(), comparator);
  std::cout<<"\nafter sorting:\n";
  for (std::pair<std::string, int> element : sortedmap)
    std::cout << element.first << "=" << element.second << "\n";
  std::cout<<"\nafter sorting, use auto traverse:\n";
  for (auto kv : sortedmap)
  std::cout << kv.first << "=" << kv.second << "\n";
  
  std::cout<<"\ncheck count(key) mymap['a']="<<mymap.count("a")<<"\n";
  std::cout<<"check count(key) mymap['no']="<<mymap.count("no")<<"\n";
  return 0;
}

Output —

mymap[key]=4
key:a val:1
key:b val:2
key:c val:4
key:z val:0

after sorting:
z=0
a=1
b=2
c=4

after sorting, use auto traverse:
z=0
a=1
b=2
c=4

check count(key) mymap['a']=1
check count(key) mymap['no']=0

Checking whether an item exists in the list or not —

mymap.count(key) // -->returns 0 or 1; 1 if the key is found
mymap.find( key ) != my_map.end()

Iterators (auto i : mymap) and tips

std::cout<<"Printing with iterator:";
for (auto& x : myset){
      std::cout<<" "<<x;
}std::cout<<"\n";

Tips on iteration:

1. For observing the elements, use the following syntax:

for (const auto& elem : container)    // capture by const reference

1-a. If the objects are cheap to copy (like ints, doubles, etc.), it's possible to use a slightly simplified form:

for (auto elem : container)    // capture by value

2. For modifying the elements in place, use:

for (auto& elem : container)    // capture by (non-const) reference

• If the container uses “proxy iterators” (like std::vector<bool>), use:

for (auto&& elem : container)    // capture by &&

Of course, if there is a need to make a local copy of the element inside the loop body, capturing by value (for (auto elem : container)) is a good choice.

By Mr.C64