Vector Vs List

Vectors and Lists are belong to sequence containers of C++ Standard Template Library. Primary difference between two comes from the internal data-structure used by both,

Vector
Internally vector uses a dynamic array (continues block of memory), which grows in forward direction.
This means random access and insertion/deletion in the end is faster. However if we insert/delete at the beginning or middle, operations will take more time as entire contents needs to be pushed/moved.

List
List is realized as (doubly) linked list.
So insertion/deletion any where is faster, which internally works as altering next of linked list nodes. By default list doesn't support random access, and hence search inside list is slower.

Simple shared_ptr implementation

auto_ptr does not allow sharing object, i.e. when auto_ptr is shared ownership transfers to rhs. This ensures that we have only one copy of pointer and pointer will be destroyed when scope is over. A simple auto_ptr implementation

However there are situations where we like to share our object pointer. For such need boost has shared_ptr implementation, my version of shared_ptr implementation is as follows



template <class T>
class MySharedPtr
{


public:
//constructor creates the dynamic interger to hold ref counting
explicit MySharedPtr(T* p = 0):m_ptr(p)
{
pRefCount = new int();
*pRefCount = 1;
}


~MySharedPtr()
{
//destroy only if ref count is 1 else null set member
if(1 == *pRefCount)
{
if(NULL != m_ptr)
delete m_ptr;
delete pRefCount;
}
else
{
m_ptr = NULL;
//decrement the counter when not deleteing object
--*pRefCount;
}

}


MySharedPtr(MySharedPtr<T> & rhs)
{
//during copy construction share the object pointer
// and ref counting pointer
this->m_ptr = rhs.m_ptr;
this->pRefCount = rhs.pRefCount;
//increment the counter as we have one more object now
++*pRefCount;
}


MySharedPtr<T>& operator = (MySharedPtr<T>& rhs)
{
if(this->m_ptr != rhs.m_ptr)
{
if(this->m_ptr != NULL)
{
//if rhs object counter is 1 then delete it otherwise
//decrement rhs counter
if(*this->pRefCount == 1)
{
delete m_ptr;
m_ptr = NULL;
delete pRefCount; 
pRefCount = NULL;
}
else
{
--*(this->pRefCount);
}
}
//assing rhs and increment counter
this->m_ptr = rhs.m_ptr;
this->pRefCount = rhs.pRefCount;
++*(rhs.pRefCount);
}
return *this;
}


private:
T* m_ptr;
//pointer to hold ref counter
int* pRefCount;
};

auto_ptr concept extended to work with pool of memory.

Based on the concept of Simple auto_ptr implementation, following example shows class reusing allocated heap memory with the aid of a pool.

Features of this implementation are

• consumers need not worry of destroying memory.
• Assignment and copy constructor transfer ownership like auto_ptr
• Destructor doesn't delete allocated memory, instead pushes memory to pool for reuse.
• static function ClearPool clears memory pool in end.

class MemMgr
{
public:
MemMgr(char* p)
{
if(NULL == memPool.size())
{
//allocate memory only if pool is not having entries
cout<<"Pool size is zero"<<endl;
pMemory = new char[MemSize];

}
else
{
//dont allocate, reuse from pool
cout<<"Pool size is "<<memPool.size()<<endl;
pMemory = memPool.front();
memset(pMemory,0,MemSize);
memPool.pop_front();
}


strncpy((char*)pMemory, p, strlen(p));
((char*)pMemory)[strlen(p)]=0;
}


MemMgr(MemMgr& rhs)
{
//in copy constructor make sure the ownership is transfered
this->pMemory = rhs.pMemory;
rhs.pMemory = NULL;
}


MemMgr& operator =(MemMgr& rhs)
{
if(this->pMemory != rhs.pMemory)
{
//if rhs is different, push lhs to pool
if(NULL != this->pMemory)
{
memPool.push_back(this->pMemory);
this->pMemory = 0;
}
}
//assign rhs memory to lhs
this->pMemory = rhs.pMemory;
//set rhs pointer to null
rhs.pMemory = NULL;
return *this;
}


~MemMgr()
{
if(NULL != this->pMemory)
{
//dont delete memory, push to pool
memPool.push_back(this->pMemory);
this->pMemory = 0;
}
}
void Print()
{
cout<<(char*)pMemory<<endl;
}


//static function to clear pool in end
static void ClearPool()
{
cout<<"Pool size is "<<memPool.size()<<endl;
if(NULL != memPool.size())
{
void* pMem = 0;
for(list<void*>::iterator iter = memPool.begin(); iter != memPool.end(); iter++)
{
delete [] *(iter);
}
}
}


private:
static const int MemSize = 100;
       //our memory pool implemented with stl::list
static list<void*> memPool;
void* pMemory;
};


//don't forget to initialize static member
list<void*> MemMgr::memPool;

Simple auto_ptr implementation

STL auto_ptr utilizes simple concepts realized with templates to achieve automatic memory management in C++.
One simple implementation of auto_ptr could be as follows


template <class T>
class MyAutoPtr
{
//typedef our template pointer and class, so that code looks cleaner
typedef T* _ele ;
typedef MyAutoPtr<T> _eleType;


public:
//make constructor explicit to avoid converting constructor
explicit MyAutoPtr(_ele ptr =0):element(ptr){}


//destructor - delete only if pointer is non zero
~MyAutoPtr()
{
if(element)
delete element;
}


//copy constructor
MyAutoPtr(_eleType &obj) 
:element(obj.release())
{}


//operator overloads
_ele operator -> ()
{
return element;
}
_ele operator * ()
{
return element;
}
//assignment operator
_eleType & operator = (_eleType & rhs)
{
//release the rhs so that ownership is moved to lhs
//reset pointer if needed
reset(rhs.release());
return *this;
}


private:
_ele element;


//inorder to transfer ownership of object, store a copy of object in temp.
//assign zero to pointer and return temp.
_ele release()
{
_ele temp = this->element;
this->element = 0;
return temp;
}


//during assignment delete our object and point to assinged object
void reset(_ele rhs)
{
if(this->element != rhs)
{
delete this->element;
this->element = rhs;
}
}
};