What is an Arraylist?
The secret lying behind an Arraylist is simply an array!
Since we don’t have real arrays in C++ (let’s call spade a spade! Unbounded
Arrays are not Arrays!) We should watch some stuff in our C++ Codes. Like when
we want to have an array of a specified object, there is this possibility that
our code reaches out of filled indexes of our array. Like:
class Library{
private:
Book myBooks[20];
public:
Book getBook(int index){return
myBooks[index];}
void insertBook(Book a,int
index){myBooks[index] = a;}
}
void main(){
Library myLib();
myLib.insertBook(new Book(),0);
myLib.getBook(1); // NO WAY!
}
Well this is pretty dangerous. Especially when you don’t
have any counters for your array bound.
But there are plenty ways that we can solve this problems
like Linked Lists, Stacks, Queues and the simple one, Arraylists.
An Arraylist is an
array that can be expanded when reached to a certain index.
How to implement an Arraylist it in C++
The power of pointers and templates! Here is one of the
possible implementations of Arraylist:
template <class Type>
class TCollection{
private:
Type *pTs;
int lastIndex;
int maxIndex;
public:
TCollection(){
lastIndex =
0;
pTs = new Type[5];
maxIndex = 4;
}
void AddT(Type myT){
if(lastIndex<maxIndex) {
pTs[lastIndex]
= myT;
lastIndex++;
}else{
maxIndex
= lastIndex*2;
Type
*temp = new Type[maxIndex];
for(int i = 0; i <
lastIndex; i++){
temp[i]
= pTs[i];
}
temp[lastIndex]
= myT;
lastIndex++;
pTs =
temp;
delete temp;
temp =
NULL;
}
}
int getCount(){
return lastIndex;
}
Type* operator[](int
index){
if (index < lastIndex){
return &pTs[index];
} else{
return NULL;
}
}
};
The role of template
Consider we weren’t using C++ template feature in above
code. Then, every time we wanted an Arraylist, we had to write a new one that
could accept our desired type. Like, if we wanted an Arraylist of int s, we had
to change the pointer type to int or if we wanted an Arraylist of Books.
Using C++ Template, now we are not worried about what we
push into Arraylist. We can use this part of code, on any class we write.
class Student{
private:
string Name;
string Family;
int ID;
string Address;
public:
Student(string
sName, string sFamily, int sID, string
sAddress){
Name =
sName; Family = sFamily; ID = sID; Address = sAddress;
}
string GetName(){return Name;}
void SetName(string myName){Name = myName;}
string
GetFamily(){return Family;}
void SetFamily(string myFamily){Family = myFamily;}
string
GetAddress(){return Address;}
void SetAddress(string myAddress){Address =
myAddress;}
int GetID(){return
ID;}
void SetID(int
myID){ID = myID;}
};
class University{
private:
string Name;
string Address;
TCollection<Student>
uStudent;
public:
University(string
uName, string uAddress){
Name =
uName; Address = uAddress;
}
string GetName(){return Name;}
void SetName(string myName){Name = myName;}
string
GetAddress(){return Address;}
void SetAddress(string myAddress){Address =
myAddress;}
Student*
Get_Student(int index){return
uStudent[index];}
void Add_Student(Student myStudent){uStudent.AddT(myStudent);}
};
What’s next?
Arraylist is a simple solution to Collection Classes problem
but not the best one. In .Net Framework and many other programming platforms
(J2EE and…), we have Linked Lists as a powerful collection.
Especial collections like Stack (LIFO) and Queue (FIFO) are
used for certain goals like the Calculator Problem etc.
Implementing these collections may be a little harder than
an Arraylist but, they are widely used in today’s programming problems.
By: Reza BabaAhmadi and Milad Karbasizadeh
University of science and culture of Tehran
Spring 2008(1387)