Thoughts on how to implement?

Question

I am porting some very old c-code into c++ and I've run across a linked list implemented within 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 the data, if you know the index. The linked list aspect lets the elements be moved around, and "deleted" from the list. Elements can be moved in the list, based on 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'd like to use STL, but I'm not certain which container is best to use.

Any one 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 elements into random positions in the list, or delete random elements from the list. If you mainly need to add/delete elements to/from the end of the list, then you should use std::vector. If you need to add/delete elements to/from either beginning or the 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 into the middle of an std::vector once in a blue moon, that will probably be ok. But if you need to do this all the time, it will have a major impact on performance, because the vector will need to constantly move its elements, and probably reallocate its memory too.

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

Answer 2

Since the data in this list is pointers, why bother with a linked list at all? For small PODs, std::vector is usually the best first bet, and due to the better locality of its data playing nicely with processor caches it often out-performs a linked list even where, in theory, a linked list should be better. I'd pick std::vector until some profiling would show that there is a performance problem and std::list performs better.

Answer 3

See here:

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

There's a flow chart to help you choose the right container at the bottom.