Containers
_______________________________________________________________________
Container: A Container class is one which contains other objects. There are three types of container classes avialable in C++.
Sequence Containers: vector, list, dqueue
Container Adapters: queue, stack, priority_queue
Associative Containers: set, map, multiset, multimap
Container: Containers help organize data in memory. The below program shows how a container class and an iterator can be implemented using c++. The below program simulates some of the vector functions although memory management is done using linked list instead of dynamic array.
Vectors are good at:
· Accessing individual elements by their position index (constant time).
· Iterating over the elements in any order (linear time).
· Add and remove elements from its end (constant amortized time).
Example: Usage of Vector
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
int main()
{
vector<int> v;
v.push_back(5);
v.push_back(3);
v.push_back(6);
v.push_back(9);
v.push_back(4);
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
cout<<*it<<" ";
}
cout<<endl;
}
Design your own vector:
#include<iostream>
using namespace std;
template<typename T>
class MyContainer
{
private:
int size;
struct Node
{
T data;
Node *link;
Node(T d):data(d),link(NULL){}
} *head, *last;
public:
MyContainer():size(0),head(0){}
MyContainer(int s):size(s),head(0)
{
for (int i=0;i<s;++i)
this->push_back(0);
}
virtual ~MyContainer()
{
while(head)
this->pop_back();
}
class MyIterator
{
private:
Node *node;
public:
MyIterator():node(0){} // initializion of member
MyIterator(Node* n):node(n){} // initializion of member
MyIterator& operator++ ()
{
node = node->link;
return *this;
}
T operator * ()
{
return node->data;
}
bool operator !=(const MyIterator& mi)
{
if (!mi.node) //no node available
return false;
//cout<<mi.node->data<<endl;
return (this->node != mi.node->link)?true:false;
}
};
void push_back(T);
T pop_back();
MyIterator begin()
{
return MyIterator(head);
}
MyIterator end()
{
return MyIterator(last);
}
};template<typename T>
T MyContainer<T>::pop_back()
{
if (!head)
{
cout<<"Empty Container!!!"<<endl;
return 0;
}
T d;
Node *temp = head;
if (head == last) //only one node exists
{
d = head->data;
delete temp;
head = NULL;
last=NULL;
}
else //more than one node exists
{
while(temp->link->link)
{
temp=temp->link;
}
//temp now contains the last but one node
//d=last->data;
d=temp->link->data;
last = temp;
last->link=NULL;
delete temp->link;
}
--size;
return d;
}
template <typename T>
void MyContainer<T>::push_back(T d)
{
if (head==0)
{
head = new Node(d);
last = head;
// ++size;
}
else
{
Node *temp = head;
while(temp->link) //go to the last node
{
temp=temp->link;
}
temp->link=new Node(d);
last = temp->link;
}
++size;
}
int main()
{
MyContainer<int> v(3);
v.push_back(10);
v.push_back(110);
v.push_back(12);
v.push_back(10);
v.push_back(15);
v.push_back(100);
cout<<v.pop_back()<<endl;
cout<<v.pop_back()<<endl;
for (MyContainer<int>::MyIterator it=v.begin(); it!= v.end(); ++it)
{
cout<<*it<<" ";
}
return 0;
}
_______________________________________________________________________
|
Copyright © Open Sky Technology |
Corporate Office: #4, RR Complex, 2nd Floor, Munnekolala, Marathahalli, Bangalore – 560037. (Landmark: near Munnekolala Bus Stop)