关于如何实施的想法？

Question

我正在将一些非常旧的c代码移植到c ++中,并且我遇到了在数组中实现的链表.元素是一个简单的结构:

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

作为数组,如果您知道索引,则可以快速访问数据.链接列表方面允许元素移动,并从列表中"删除".可以根据使用频率在列表中移动元素(MRU为LRU,LRU为向下).

我想找到一种比使用另一个数组更好的方法来实现它.我想使用STL,但我不确定哪种容器最好用.

有人有什么想法吗？

Answer 1

由于这是一个链表,你应该使用std :: list ...

经验法则是,当您需要将元素插入列表中的随机位置或从列表中删除随机元素时,您希望使用链接列表.如果您主要需要在列表末尾添加/删除元素,那么您应该使用std::vector.如果您需要在列表的开头或结尾添加/删除元素,那么您应该使用std::deque.

请记住,我们在这里讨论概率.如果你需要std::vector在蓝色月亮的中间插入一个元素,那可能就行了.但是如果你需要一直这样做,它会对性能产生重大影响,因为向量需要不断移动它的元素,并且可能也会重新分配它的内存.

另一方面,使用向量的优点是它的元素在内存中是连续的,如果你只是因为缓存而需要按顺序遍历它们,这会大大提高性能.