member functions are given by compiler in c++

Following member functions are given by compiler if we are not defined in the class..

1) default constructor
2) default destructor
3) copy constructor
4) assignment operator
5) address operator

Things to be taken care of in defination of assignment operator

• Deep copy/shallow copy
• Guard against self assignment in the assignment operator.
• Strong exception safety in the assignment operator. (acquire new resources before deleting old)
• Call base class's assignment operator if needed.

Final Class in C++

A class in Java is said to be final class if it can't be inherited by any other class. In C++, language has no built in feature to implement this. This has to be implemented by the developer.

• By making the destructor private 
• In this case, the object can only be created in heap by some static function defined in the class. Similarly a function must be implemented for destruction of object.

• If we create object on stack, stack unwinding needs the destructor to be accessible. Hence compiler won't allow this.

• Let's look at the following code.

#include <iostream>

using namespace std;

class F
{
public:
        static F* Create()
        {
                return new F();
        }

        static void Destroy(F* ob)
        {
                delete ob;
        }

        void show()
        {
                cout<<"In F Show()"<<endl;
        }

private:
        ~F() {}
};


int main()
{
        F *f_ob ;
        f_ob = F::Create();
        f_ob->show();
        F::Destroy(f_ob);

        return 0;
}

 
• Here no class can inherit F as the destructor is private. During child class object destruction, parent class destructor can't be called. Because parent class destructor is private.

• By friend class
• In this case, the object can be created on stack. 
• Here we will need a dummy class whose destructor is private. The Final class must be a friend of this class and the Final class will inherit from dummy class.
• We can create the object of Final class. As Final class is the friend of dummy class, it will have access to it's destructor. 
• But if any class(Child) inherits Final Class, then it won't compile because destructor of temp is not accessible inside Child class.
• Let's look at the following code

#include <iostream>

using namespace std;

class Final;

class Dummy
{
private:
        ~Dummy() {}
        friend class Final;
};

class Final : public Dummy
{
public:
        Final() {}
        ~Final() {}
        void show()
        {
                cout<<"Show"<<endl;
        }
};


int main()
{
        Final ob;
        ob.show();
        return 0;
}

Implementation of Binary Search Tree

/* 


/* 
 * File:   main.cpp
 * Author: asit
 *
 * Created on 24 September, 2011, 2:14 PM
 */

#include <cstdlib>
#include <iostream>
#include <iterator>
#include <stack>
#include <vector>
#include <utility>

using namespace std;

/*
 * 
 */

struct node
{
    int id;
    string name;
    node *left;
    node *right;
    node():id(0),name(""),left(NULL), right(NULL) {}
    node(int id, string name):id(id), name(name), left(NULL), right(NULL) {}
};

typedef pair<int,string> emp_det;

class BinarySearchTree
{
    node *root;
    
public:
    BinarySearchTree():root(NULL) {}
    
    void addNode(int dt, string nm) 
    {
        node *temp = NULL;
        
        if(root==NULL)
        {
            temp = new node;
            temp->id = dt;
            temp->name = nm;
            root = temp;
        }
        else
        {
            temp = root;
            while(true)
            {
                if(temp->id >= dt) 
                {
                    if(temp->left == NULL)
                    {
                        temp->left = new node(dt,nm);
                        break;
                    }
                    else
                        temp = temp->left;
                }
                else
                {
                    if(temp->id < dt)
                    {
                        if(temp->right == NULL)
                        {
                            temp->right = new node(dt, nm);
                            break;
                        }
                        else
                            temp = temp->right;
                    }
                }
            }
        }
    }
    
    
    void sort(vector<emp_det> &list)
    {
        node *temp = NULL;
        
        stack<node*> st;
        
        temp = root;
        
        while(true)
        {
            if(temp != NULL)
            {
                st.push(temp);
                temp = temp->left;
            }
            else
            {
                if(st.empty())
                    break;
                temp = st.top();
                st.pop();
                list.push_back(emp_det(temp->id, temp->name));
                temp = temp->right;
            }
        }
    }
    
};

int main(int argc, char** argv) 
{
    emp_det arr[] = { emp_det(4, "A"), 
                      emp_det(23,"B"),
                      emp_det(10,"C"),
                      emp_det(65,"D"),
                      emp_det(43,"E"),
                      emp_det(89,"F"),
                      emp_det(77,"G"),
                      emp_det(98,"H"),
                      emp_det(76,"I"),
                      emp_det(56,"J") };

    
    BinarySearchTree bst;
    
    for(int i=0; i<10; i++)
        bst.addNode(arr[i].first, arr[i].second);
    
    vector<emp_det> list;
    
    bst.sort(list);
    
    vector<emp_det> ::iterator it;
    
    for(it = list.begin(); it != list.end(); it++)
        cout<<(*it).first<<"  "<<(*it).second<<endl;
    
    cout<<endl;

    return 0;
}

Array vs linked list

A few reasons why Array is better

• In array, we the provision of random access. But in linked list, the nodes can only be sequentially accessed. 
• Better locality - Whenever the OS brings data into memory, it loads a whole page. Hence less page fault occurs. With linked list, different parts of the linked list are stored at different parts of memory. Hence branch Prediction doesn't work as well with linked list. This causes the pipeline to be flushed more often which result in poor performance.
• In linked list, the extra storage needed for references, which often makes them impractical for lists of small data items such as characters or boolean values. It can also be slow, and with a naïve allocator, wasteful, to allocate memory separately for each new element.

A few reasons why Linked List is better

• It's easier to store data of different sizes in a linked list. An array assumes every element is exactly the same size.
• It's easier for a linked list to grow organically. An array's size needs to be known ahead of time, or re-created when it needs to grow.
• Shuffling a linked list is just a matter of changing what points to what. Shuffling an array is more complicated and/or takes more memory.
• As long as your iterations all happen in a "foreach" context, you don't lose any performance in iteration.

new instead of malloc

While searching I found a very naive, but useful thing about new/malloc.

Why should we use new instead of malloc ?

1. New and Delete makes sure that constructors and sestructors are called but not the case with malloc and free functions of C. 
2. Pointer conversion safety: malloc() returns a void* which isn't safe. new returns a pointer of the right type. 
3. new is a Operator: new is an operator that can be overloaded for better memory management by a class, while malloc() is not an operaotor. 
4. new operator computes the size of object automatically whereas malloc cannot.
5. It is possible to initialize the object while allocating memory with new. 
6. Its possible to construct an object over an already allocated memory using another version of 'new' operator known as 'placement new' operator. While with malloc() it is not possible.

Nth last element in Linked List (C++)

The following code shows how to get nth last element in a linked list. It uses a queue to hold the temporary elements.

Algorithm:-
1>Make a queue of length N
2>Traverse the linked list from root
3>While traversing, en-queue first N elements
4>After this for en-queuing every element, de-queue another element.
5>When we reach the end of linked list, the last de-queued element will be the Nth last element.

/* 
 * File:   main.cpp
 * Author: Asit
 *
 * Created on 16 September, 2011, 12:25 AM
 */

#include <cstdlib>
#include <iostream>
#include <queue>

using namespace std;

struct node
{
    int data;
    node *next;
};

class LinkedList
{
    node *root;
public:
    LinkedList():root(NULL){}
    void add(int x)
    {
        node *temp = NULL;
                
        if(root==NULL)
        {
            root = new node;
            root->data = x;
            root->next = NULL;
        }
        else
        {
            temp = root;
            while(temp->next != NULL)
            {
                temp = temp->next;
            }
            
            temp->next = new node;
            temp = temp->next;
            temp->data = x;
            temp->next = NULL;
        }
    }
    
    void show()
    {
        node *temp = root;
        
        while(temp != NULL)
        {
            cout<<temp->data<<"  ";
            temp = temp->next;
        }
        cout<<endl;
    }
    
    int nthLast(int n)
    {
        queue<node*> t_queue;
        int i=1, t_data = -1;
        node *temp = root;
        
        while(temp != NULL)
        {
            t_queue.push(temp);
            if(i>=n)
            {
                t_data = (t_queue.front())->data; 
                t_queue.pop();
            }
            i++;
            temp = temp->next;
        }
        
        i--;
        if(i<n)
            cout<<"Linked list contains less than "<<n<<" elements"<<endl;
        
        return t_data;
    }
};

int main(int argc, char** argv) 
{
    LinkedList list;
    
    for(int i=0; i<20; i++)
        list.add(i*7+90);
    
    cout<<"Created linked list is .. "<<endl;
    list.show();
    
    cout<<"3rd last element : ";
    
    cout<<list.nthLast(3)<<endl;
    
    return 0;
}

Output:-

Created linked list is .. 
90  97  104  111  118  125  132  139  146  153  160  167  174  181  188  195  202  209  216  223  
3rd last element : 209

CountDown Latch to measure sorting time (java)

The following code uses CountDown Latch to measure the performance of sorting example. The sorting method sorts n array of random numbers in separate threads.

import java.util.*;
import java.util.concurrent.*;

public class SortRace {

 /**
  * @param args
         * @developer lipun4u
  */
 public static void main(String[] args) throws Exception{
  // TODO Auto-generated method stub
  int max = 10000;
  int array[] = new int[max];
  Random randomGenerator = new Random();
  
  for(int i=0; i<max; i++)
   array[i] = randomGenerator.nextInt(max*10);
  
  List<String> sortList = Collections.synchronizedList(new ArrayList<String>());
  CountDownLatch startLatch = new CountDownLatch(1);
  CountDownLatch prepareLatch = new CountDownLatch(3);
  CountDownLatch endLatch = new CountDownLatch(3);
  
  new SortThread("BubbleSort", startLatch, prepareLatch, endLatch, array, sortList).start();
  new SortThread("InsertionSort", startLatch, prepareLatch, endLatch, array, sortList).start();
  new SortThread("SelectionSort", startLatch, prepareLatch, endLatch, array, sortList).start();
  
  startLatch.countDown();
  endLatch.await();
  
  System.out.println("Fisrt Position : " + sortList.get(0));
  System.out.println("Second Position : " + sortList.get(1));
  System.out.println("Third Position : " + sortList.get(2));

 }

}

class SortThread extends Thread {
 
 private String sortName;
 private CountDownLatch startLatch, prepareLatch, endLatch;
 private int[] pArray;
 private int[] array;
 
 List<String> list;
 
 public SortThread(String sortName, 
   CountDownLatch startLatch,
   CountDownLatch prepareLatch,
   CountDownLatch endLatch,
   int[] pArray,
   List<String> list) {
  this.sortName = sortName;
  this.startLatch = startLatch;
  this.prepareLatch = prepareLatch;
  this.endLatch = endLatch;
  this.list = list;
  this.pArray = pArray;
  System.out.println(sortName + " Started..");
 }
 
 public void run() {
  try {
   startLatch.await();
   prepareArray();
   prepareLatch.countDown();
   prepareLatch.await();
   if(sortName == "BubbleSort") {
    bubble_sort(array);
   }
   else if(sortName == "InsertionSort") {
    insertion_sort(array);
   }
   else if(sortName == "SelectionSort") {
    selection_sort(array);
   }
   list.add(sortName);
   endLatch.countDown();
  }
  catch(Exception e) {
   e.printStackTrace();
  }
 }
 
 public void prepareArray() {
  array = new int[pArray.length];
  System.arraycopy(array,0, pArray, 0, pArray.length);
 }
 
 public void insertion_sort(int array[]) {
  for(int i=1; i<array.length; i++) {
   int j=i;
   int b = array[i];
   while((j>0) && (array[j-1]>b)) {
    array[j] = array[j-1];
    j--;
   }
   array[j] = b;
  }
   
 }
 
 public void bubble_sort(int array[]) {
  for(int i=0; i<array.length; i++) {
   for(int j=1; j<(array.length-i); j++) {
    if(array[j-1]>array[j]) {
     int t = array[j-1];
     array[j-1]=array[j];
     array[j]=t;
    }
   }
  }
 }
 
 public void selection_sort(int array[]) {
  for(int i=0; i<array.length; i++) {
   for(int j=i+1; j<array.length;j++) {
    if(array[i]>array[j]) {
     int t = array[i];
     array[i]=array[j];
     array[j]=t;
    }
   }
  }
 }
}

auto_ptr

Look at the following code.

<br /> <br /> T *ptr = new T();<br /> /*-----<br /> do some stuffs<br /> -------*/<br /> delete ptr;<br />

The above code will work perfectly if the "do some stuffs" section doesn't throw any unhandled exception. If some exception is thrown, then the object will be created in the heap and won't be deleted till the program termination.

Hence, object creation in heap is always dangerous than object creation in stack. We can avoid the above situation by using auto_ptr templatised class in STL.

Automatic Pointer(auto_ptr) class is a limited garbage collection facility which takes responsibility of object destruction when the auto_ptr goes out of scope.

Auto_ptr takes the responsibility of the destruction of the object. Hence if same auto_ptr points to another object, the previous object is destroyed properly.

Example :-

#include <iostream>
#include <memory>

using namespace std;

class T
{
	static int i;
	int id;
public:
	T():id(i++)
	{	
		cout<<"T constructor :: "<<id<<endl;
	}
	~T()
	{	
		cout<<"T destructor :: "<<id<<endl;
	}
	void show()
	{
		cout<<"id :: "<<id<<endl;
	}
};

int T::i = 1;

int main()
{
	auto_ptr<T> pt(new T());
	pt->show();
	pt.reset(new T());
	pt->show();
	
	return 0;
}

Output :-

T constructor :: 1
id :: 1
T constructor :: 2
T destructor :: 1
id :: 2
T destructor :: 2

If the responsibility is transferred from 1st pointer to the second pointer(by assignment operator), then 1st pointer is set to NULL. Hence, no two auto pointer points to the same object.

Example :-

#include <iostream>
#include <memory>

using namespace std;

class T
{
        static int i;
        int id;
public:
        T():id(i++)
        {
                cout<<"T constructor :: "<<id<<endl;
        }
        ~T()
        {
                cout<<"T destructor :: "<<id<<endl;
        }
        void show()
        {
                cout<<"id :: "<<id<<endl;
        }
};

int T::i = 1;

int main()
{
        auto_ptr<T> p1(new T());
        p1->show();
        auto_ptr<T> p2;
        p2 = p1;
        p2->show();
        return 0;
}

Output :-

T constructor :: 1
id :: 1
id :: 1
T destructor :: 1

Certain Links that might prove useful
http://www.gotw.ca/publications/using_auto_ptr_effectively.htm
http://www.alwynberkeley.com/autoptr.html
http://www.cprogramming.com/tutorial/auto_ptr.html