Thoughts on how to implement?

Question

I am porting some very old c-code in C ++, and I came across a linked list implemented in an array. The element is a simple structure:

struct element { void *m_ptrData; short m_nextEntry; short m_prevEntry; }; 

As an array, there is quick access to data if you know the index. An aspect of a linked list allows you to move items and “remove” them from the list. Items can be moved in the list by frequency of use (up for MRU and down for LRU).

I like to find a better way to implement this than using another array. I would like to use STL, but I'm not sure which container is best to use.

Anyone have any thoughts?

Answer 1

Since this is a linked list, you should probably use std :: list ...

The rule of thumb is that you want to use a linked list when you need to insert items at arbitrary positions in the list or remove random items from the list. If you basically need to add / remove items to / from the end of the list, you should use std::vector . If you need to add / remove items to / from the beginning or end of the list, then you should use std::deque .

Keep in mind we are talking about probabilities here. If you need to insert an element in the middle of std::vector once in the blue moon, this will probably be fine. But if you need to do this all the time, it will have a big impact on performance, because the vector will need to constantly move its elements and possibly redistribute its memory.

On the other hand, the advantage of using a vector is that its elements are contiguous in memory, which greatly improves performance if you just need to execute them in order due to caching.

Answer 2

Since the data in this list are pointers, why bind the list at all? For small PODs, std::vector usually the best first bet, and because of the better localization of its data, which play well with processor caches, it often leaves the linked list, even if the theoretically linked list should be better. I would choose std::vector until some profiling shows that there is a performance issue, and std::list works better.

Answer 3

See here:

http://linuxsoftware.co.nz/cppcontainers.html

There is a block diagram here that will help you choose the right container below.