: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

> 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.

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........

This article has been dead for over six months. Start a new discussion instead.