如何让链表节点的内存块连续

Question

MFC的CArray模板类是不是就是连续的内存块,或者CString类,它们的实现原理,
链表如果大了定位每次都要搜索,如何让链表的内存块也是连续的,可以是头指针加偏移量就能够定位.

Answer 1

搜的：
vector是C++标准模板库中的部分内容，中文偶尔译作“容器”，但并不准确。它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。vector之所以被认为是一个容器，是因为它能够像容器一样存放各种类型的对象，简单地说，vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。 
简单的使用方法如下:   
  vector<int>   test;//建立一个vector
  test.pushback(1);//把1和2压入vector   这样test[0]就是1,test[1]就是2
  test.pushback(2); 
新手，共同学习

Answer 2

vector动态生成的节点 内存地址是连续的吗?

Answer 3

如果知道链表大小，可以new出那块内存，这样就可以用数组了。
如果不知道大小，还要内存连续，你认为系统应该怎么做呢？应该给你分配多少内存？分小了越界了怎么办？分多了浪费资源怎么办？
考虑事情不要想当然！

Answer 4

链表就是处理不连续的,你还要连续,那就直接用vector了

Answer 5

唯一的方法就是自己写Memory Pool，不过链表很麻烦，你可以开始保证内存是连续的，取下一个结点怎么办？就得乾坤大挪移。链表比数组的优势就是添加删除容易，你搬来搬去还不如用数组了，挪起来还快，一个MoveMemory就行了。

Answer 6

同意akirya(坏[其实偶不是什么所谓的坏人]) ，链表和vector各有优缺点，你如果想连续和直接+偏移，那就用vector,

Answer 7

>>feimingbiao() 
CArray和CString好像就是用的memmove来使内存连续的,但是如果链表大了,就算是移动怎能确定后面的内存是没有被占用的,然后使用memmove?

Answer 8

首先谈到memmove,严格来讲已经不是链表了，属于vector类了。通常Vector或者Array之类的实现都是开始有个起始长度，通常称为capacity,比如8个元素。当元素个数超过8的时候，就需要grow了，就是再开一块更大的内存把大家都搬到新家里面去。Grow的选择有很多，比如比较常见的加倍算法。通常不断x2，直到一个预先设定的Threshhold值后恒定加长（这样避免涨得太快消耗内存）。