CMapStringToPtr

Expand Post »

:mrgreen:
Hi to all, I have a challange in my work, we have a project that uses a variable of type "CMapStringToPtr", this object is use to store some data, now we want to change the type to more efective type, the problem is that we need to know if a value was change and put it in the first place of the list, I was thinking using "Linked List", if I value was changed, dleted the current value and put it in head of the list.
I was wandering is linked list the best solution?
Do you have any suggestion of Data Structures, we can use?
we have are saving something like this:
key, value

key value key value key value
1 1------>2 4------>4 6

Now for example key "2" its value is change to 1, now the list should be like:
key value key value key value
2 1------>1 1------>4 6
In the head of the list should be the last object(key) that was changed
Thanks

dev.cplusplus

Reputation Points: 10

Solved Threads: 0

Junior Poster in Training

Offline

61 posts
since Jun 2006

Permalink

Aug 9th, 2006

Re: CMapStringToPtr

> I was wandering is linked list the best solution?
There isn't a "best" solution as such, there are many tradeoffs to be considered. Some of which are not so obvious.

Well the search/replace is going to be expensive on larger lists, but that has to be weighed against the extra complexity of something like std::map.

Are you only interested in the head of the list, or in the whole of the list?

How many times do you process the list compared to modifying the list?
Like do you scan it 100 times and change it once?

As it stands, I might go with a std::map to permit easy lookup and changing of values, and also maintain a std::list through the map to indicate the change order.

Salem

Team Colleague

Reputation Points: 5862

Solved Threads: 950

Posting Sage

Offline

7,164 posts
since Dec 2005

Permalink

Aug 10th, 2006

Re: CMapStringToPtr

The problem you've described might consists of pair of key value... using pair< T1,T2> template is agood choice .....then.

I totally agree with salem, every Data Structure has some advantages and tradsoff, its depends upon your need and how it fits the scenario...

in LIFO(Last in First Out) link list the complexity of insert is O(1);
search is O(n) and it provides the forward iterator;.......

in most situation with pair of values we often need to change the "value" part of pair with key like v["key"]="value";
this is often required what is called Random Access iterator like array indexing mechanism.....

I suggest you to develop your Own std::map like structure and modify it that best suited your needs........

Laiq Ahmed

Reputation Points: 113

Solved Threads: 20

Junior Poster

Offline

147 posts
since Jun 2006

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C Forum Timeline: Sorting CList

Next Thread in C Forum Timeline: wat is flag??pls...can someone explain it to me!!

DaniWeb Message

Cancel Changes

User Name
Password