n_fortynine
asked on
Some useful thoughts are needed
Yesterday I came across one of my friend's assignments for a CS2 class. Basically he has to create a template Array of (template) Lists and use that as a (template) HashTable. The Lists are dynamic. HashTable uses multi-inheritance.
There are a few points in the teacher's design I do not really think are necessary. THIS IS NOT MY HOMEWORK, SO DON'T PROVIDE CODES, I'll only need reasonable thoughts on this. Here's the basic layouts (pseudo):
List<T> {...};
Array<T> {
protected:
T* dat_arr;
public:
Array(int);
...
};
HashTable<T> : public Array< List<T>* >, public List<T> {
protected:
int HashTableSiz;
public:
HashTable(int);
...
};
I keep on thinking what on Earth that he wanted when he let HashTable have a HashTableSiz, where logically that should have been in Array. And to create an Array < List<T> > is Ok (makes sense), but why an Array of pointers to Lists, since the Lists are first and foremost dynamic?
There are a few points in the teacher's design I do not really think are necessary. THIS IS NOT MY HOMEWORK, SO DON'T PROVIDE CODES, I'll only need reasonable thoughts on this. Here's the basic layouts (pseudo):
List<T> {...};
Array<T> {
protected:
T* dat_arr;
public:
Array(int);
...
};
HashTable<T> : public Array< List<T>* >, public List<T> {
protected:
int HashTableSiz;
public:
HashTable(int);
...
};
I keep on thinking what on Earth that he wanted when he let HashTable have a HashTableSiz, where logically that should have been in Array. And to create an Array < List<T> > is Ok (makes sense), but why an Array of pointers to Lists, since the Lists are first and foremost dynamic?
ASKER
Thanx ged325, but the hashing is not what I asked for. I was thinking what advantage (if any) Array< List<T>* > has over Array < List<T> >?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
ged325, are you saying that by not having <List<T>* I'd have 2 copies of the lists? Would you be able to elaborate more on that, or perhaps provide some useful links? Thanx
if you have the list actually stored in the array it would look something like
array[x] list
0 10 20 30 40 50 60
1 11 21 31 41 51
2 12 22 32 42 52
.
.
.
now, when you say array[0] = list0; //where list 0 is 10 20 30 40 50 60
you have:
The list0, the list itself which is stored at one address
and
array[0], which is a copy of list0 inputed into that row.
2 copies of the array.
Besides that, if you were to grow list 0, if the next memory cell wasn't free, it would have to move all of the array to a spot in free memory. (The array must be in contiguous memory.)
By storing the address of the list, (IE, pointing to it)
it has some advantages:
1) The lists have do not have to be in contiguous order, they can be sorted all throughout memory. (IE: you can have the first node at 0200, and the next one at 6004, it doesn't matter because you point to that location through next) As long as there's a free cell, you can grow much easier.
2) There's only one copy of the list in memory
That's all I can think of off the top of my head. Any more questions?
array[x] list
0 10 20 30 40 50 60
1 11 21 31 41 51
2 12 22 32 42 52
.
.
.
now, when you say array[0] = list0; //where list 0 is 10 20 30 40 50 60
you have:
The list0, the list itself which is stored at one address
and
array[0], which is a copy of list0 inputed into that row.
2 copies of the array.
Besides that, if you were to grow list 0, if the next memory cell wasn't free, it would have to move all of the array to a spot in free memory. (The array must be in contiguous memory.)
By storing the address of the list, (IE, pointing to it)
it has some advantages:
1) The lists have do not have to be in contiguous order, they can be sorted all throughout memory. (IE: you can have the first node at 0200, and the next one at 6004, it doesn't matter because you point to that location through next) As long as there's a free cell, you can grow much easier.
2) There's only one copy of the list in memory
That's all I can think of off the top of my head. Any more questions?
ASKER
Alrite thanks. I'll not get too hooked up on this. It ain't my problem in the first place =)
do you understand what I'm saying though?
ASKER
yeah i think i understand it. just that i never thought the system would "back up" the list that way. =)
If you use open hashing then it's possible to have
(using a mod 10 function)
0 -> 10 -> 20 -> 30
1
2 -> 32 -> 562 -> 692
3
4
5 -> 15 -> 95
6
7
8
9
where the list would be 10 15 20 30 32 95 562 692.
It's developed using the % 10 function, then the node is added on to the last one. (hence why it's dynamic, when you get a new number add it on to the last.) Obviously this isn't the best way as you can have 0's table with 30 elements to search and 9 with nothing in it. But it is one of the easiest one's to implement.