?
Solved

Some useful thoughts are needed

Posted on 2003-03-02
8
Medium Priority
?
307 Views
Last Modified: 2010-05-18
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?
0
Comment
Question by:n_fortynine
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 4
8 Comments
 
LVL 40

Expert Comment

by:Kyle Abrahams
ID: 8055104
Depends on what kind of hashing you're using.

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.


0
 
LVL 4

Author Comment

by:n_fortynine
ID: 8055157
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> >?
0
 
LVL 40

Accepted Solution

by:
Kyle Abrahams earned 80 total points
ID: 8055174
ah, pretty much, storage space:

if you have

array[0] = list;

Then you actually have 2 copies of it.  One in array, one where the list is actually stored.  By making it pointers, you only save the locations of the lists and can get to it by going to that location, instead of making the array hold it itself.
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 4

Author Comment

by:n_fortynine
ID: 8055258
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
0
 
LVL 40

Expert Comment

by:Kyle Abrahams
ID: 8058743
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?

0
 
LVL 4

Author Comment

by:n_fortynine
ID: 8059656
Alrite thanks. I'll not get too hooked up on this. It ain't my problem in the first place =)
0
 
LVL 40

Expert Comment

by:Kyle Abrahams
ID: 8061779
do you understand what I'm saying though?
0
 
LVL 4

Author Comment

by:n_fortynine
ID: 8062174
yeah i think i understand it. just that i never thought the system would "back up" the list that way. =)
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
Suggested Courses
Course of the Month12 days, 15 hours left to enroll

777 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question