Friday 18 October 2013

std::unordered_map example

Unordered map is a structure that allows you to save data in an easy to access format.

For example, let assume that we would like to create a telephone catalogue. If we use an std::vector then looping though all the contact to find a number is time expensive. Instead we can use an std::unordered_map and have a much quicker search of data.

So this is an example code using the unordered_map:

#include 
#include 


int main(void)
{
   // initialise the map which takes as input a string and an integer
   std::unordered_map < std::string,unsigned int > mymap;

   // create and insert a new contact
   std::pair < std::string, unsigned int > pair("Maria",300);
   mymap.insert(pair);

   // search for a contract
   std::string input = "Maria";

   std::unordered_map < std::string,unsigned int > ::const_iterator got = mymap.find(input);
   if(got == mymap.end())
   {
       std::cout << "Contact does not exist\n";
   }
   else
   {
       std::cout << got -> first << "'s number is " << got->second <<"\n";
   }

  return 0;
}


So if you run the above example, this is what you get:

Maria's number is 300


Please note that unsigned int is not a prober type to save telephone numbers, because telephone numbers if are treated as numbers then you can easily end up with an overflow.
In this example I just wanted to show that unordered map allows you to save two different types of variables. A better approach will have been to have two string instead of string and an unsigned int.

Wednesday 9 October 2013

Merge Sort without Recursion.

MathJax TeX Test Page
Well, I needed a sorting algorithm in C++, so I decided to write my own. Merge sort is quick, O(nlogn), and stable. Recursion is also slow so I decided to write it without recursion:


  // array to be sorted
  int array[] = {12,4,10,2,3,2,8,7,-1,-4,14,8,9,2,11};
  unsigned int len = 15;
  // allocate memory for temporarly saved values
  std::vector tempValues;
  tempValues.resize(len);
  // start sorting 2 elements each time, then merge them with the two next to them etc
  for(int step=2; step/2 < len; step*=2)
  {
     for(unsigned int i=0; i < len; i+=step)
     {
        int endOfT2 = i+step;
        if(i+ step/2 >= len)
        {
           continue;
        }
        else if (i+step >= len)
        {
           endOfT2 = len;
        }
        // both sets have step/2 items.
        // t1 points to the first set of values
        int t1 = i;
        // t2 points to the second set of values
        int t2 = i+step/2;
        // here we save all the values that have been overridden from the first set
        unsigned int tempIndex=0;
        while(t1 < i+step/2 && t2 < endOfT2)
        {
           if(array[t1]>array[t2])
           {
              tempValues[tempIndex]=array[t1];
              t1++;
           }
           else
           {
              tempValues[tempIndex]=array[t2];
              t2++;
           }
           tempIndex++;
        }
        while(t1 < i+step/2)
        {
           tempValues[tempIndex]=array[t1];
           t1++;
           tempIndex++;
        }
        // write values back to the array
        for(unsigned int t=0; t < tempIndex; ++t)
        {
            array[i+t]=tempValues[t];
        }
     }
  }

  // print the sorted array
  for(unsigned int i=0; i < len; ++i)
  {
      std::cout << " " << array[i];
  }
  std::cout << "\n";