我正在将一些非常旧的c代码移植到c中,并且我遇到了在数组中实现的链表.元素是一个简单的结构：
struct element
{
void *m_ptrData;
short m_nextEntry;
short m_prevEntry;
};
作为数组,如果您知道索引,则可以快速访问数据.链接列表方面允许元素移动,并从列表中“删除”.可以根据使用频率在列表中移动元素(MRU为LRU,LRU为向下).
我想找到一种比使用另一个数组更好的方法来实现它.我想使用STL,但我不确定哪种容器最好用.
有人有什么想法吗？
解决方法
由于这是一个链表,你应该使用
std::list ……
经验法则是,当您需要将元素插入列表中的随机位置或从列表中删除随机元素时,您希望使用链接列表.如果您主要需要在列表末尾添加/删除元素,那么您应该使用std :: vector.如果需要在列表的开头或末尾添加/删除元素,则应使用std :: deque.
请记住,我们在这里讨论概率.如果你需要在蓝色月亮中将一个元素插入到std :: vector的中间,那么这可能是正常的.但是如果你需要一直这样做,它会对性能产生重大影响,因为向量需要不断移动它的元素,并且可能也会重新分配它的内存.
另一方面,使用向量的优点是它的元素在内存中是连续的,如果你只是因为缓存而需要按顺序遍历它们,这会大大提高性能.