Hello everyone,


I am going to design a Cache in C/C++ (memory cache). I have two different approaches to design/implement it, any comments will be appreciated.

Design 1, using a map (hashtable) to store key --> object pointer relationship (simple and straight forward);

Design 2, store real object or object pointer in a stack/linked list/queue/array as an internal storage data structure, then using a map (hashtable) as an external interface to mapping key --> index in the stack/linked list/queue/array; (in this design, when accessing an object, we need two times mapping, first mapping key to index in the stack/linked list/queue/array, then using the index to access the real object)

I am wondering any advantages or disadvantages of the two designs. Any better design approach suggestion will be appreciated.


thanks in advance,
George

I really don't recommend 2nd method, because it like nightmare for me to learn during I study abstract data type paper at university. However it give you full control on all objects in memory, but you need to pay with much more programming afford.
I don't think at current year we need to go for it.
Ks

The main difference I see is in destruction control. The first allows destruction in-scope (or dynamically), however something external would have to notify the table when something is deleted. The second forces its own allocation, making the cache responsible for destruction. The first might require modified destructors or containers which deregister the objects, but the second would require an external function to remove an object when it's no longer needed. Is this a dynamic or fixed cache, i.e. will the program start and end with the same number of objects?
ta0kira

Thank you kstan!


Could you give more information about what in your mind is the advantages of the 2nd design, when compared with the 1st design?


regards,
George

Thank you ta0kira!


It is a fixed sized cache for some customer structure. You talked something about the destruction differences of the two designs. Any comments about the advantages of each design?


regards,
George

this is an example, and only 1 of the applied method
1. Imagine you have a groups of object which have same field, maybe a student in a school.
2. Consider student have 2 hand, left hand grep previous student hand, right hand grep next person hand.
3. then hand consider as pointer or cursur.
4. If many student in a school grep their hand together, then we can have a long linked student (consider as link list)
5. If you ask the 50th student left hand grep 2nd student right hand, 3rd student left hand grep last studentleft hand, then you will see the entire structure change.
6. pointer is more suitable if compare with the array, because it is dynamic size and you can extent it with 2 handed student, 3 handed student, 4 handed student (just imagine and don't go to find this kind of student)
7. queue is same but the first student left hand grep the last student right hand
8. stack is similar but using fifo mechanism

Now you know the ideal, it good for manipulate data, but normally we manage the data with database because easier and much more function. However, if you want to have a method to handle large amount of data in lighting speed, then go for it because it keep all data into memory.

So, in linked list you can simply instruct student to change their hand position, during programming maybe you just tell function where is the 1st student.

Finally, this is only my opinion and maybe it not 100% correct.

If you just store a table of pointers to objects, something else will have to be responsible for them, which means they'll be deleted when the responsible scope ends. If they are created by the cache itself (or if you pass 'new' objects and make the cache responsible) then they outlast all scopes until the cache destructs. If your cache is fixed size with all the same elements (no polymorphism), I'd recommend just a fixed array. If they will require polymorphism at all or any dynamic sizing or arangement, I'd recommend a linked list where the user would register 'new' objects, making the cache ultimately responsible for their deletion. When the cache destructs it deletes any objects it currently contains.
ta0kira

PS Probably with an additional hash table, as you suggested.