请教一个STL的问题

yxdeath

小弟最近刚刚开始看STL，看到vector,deque的迭代器是可随机存取的，而且中间插入或者删除一个元素，再这个元素后面的所有元素的指针，迭代器都要变（没有超过容器容量）。list,set,map,multiset,multimap这些类型都是不可随机存取的，其中删除，添加一个元素任何其它元素指针和迭代器都不变，我想问的是这2种类型的指针区别是什么，为什么前面的指针在添加删除元素时候会变化，后面的不会变

lenovo

那是因为在内存中vector,deque的元素的地址是相邻的，
像数组一样，而list,set,map,multiset,multimap的元素的
地址是不相邻的，像链表。

yxdeath

其实我认为deque不是像一个数组，而是像2个数组，版主果然厉害，标准程序库的作者都没说得那么详细，嘻嘻

oustar

C++标准对STL的特性有详细的规定；STL的作者必须保证符合这些特性。

对于具体的实现细节可以有所不同。

whyglinux

>;>; 那是因为在内存中vector,deque的元素的地址是相邻的，像数组一样

对于vector确实如此，无论是在逻辑上还是在物理上元素都是相邻的。但是对于deque，由于它的结构是由一个一个的内存块组成，在内存块内的元素其地址是相邻的，但是在块与块之间一般是有“空隙”的，因此说“deque的元素的地址是相邻的”这一说法欠妥。对于deque，相邻其实只是一种逻辑上的相邻，从内存存储形式来看，deque类似于list、set、map等容器类。

对于楼主提出的问题，正确的原因似乎应该是：vector、deque内元素的（逻辑）顺序与元素在内存中的（物理）存储地址相对应，而list、set、map等容器内元素的顺序与其在内存中的位置无关，元素之间只是一种逻辑上的联系。

step_by_step

楼上的好像有误吧，对于vector<bool>;,你去看看是不是连续的？

albcamus

[quote]原帖由 "step_by_step"]楼上的好像有误吧，对于vector<bool>;,你去看看是不是连续的？[/quote 发表：


难道不连续吗？那为什么能提供速度很快的下标操作呢？

whyglinux

>;>; 楼上的好像有误吧，对于vector<bool>;,你去看看是不是连续的？

我什么时候说过vector的元素是不连续的？稍微认真一点，相信你就不会这么说了。

step_by_step

原帖由 "whyglinux" 发表：
>;>; 楼上的好像有误吧，对于vector<bool>;,你去看看是不是连续的？

我什么时候说过vector的元素是不连续的？稍微认真一点，相信你就不会这么说了。

我的意思是说不是所有的vector都是连续的

不信你看如下文章

http://www.gotw.ca/publications/mill09.htm

step_by_step

对于楼主的问题，侯捷的《stl源码解析》讲的很清楚。有空翻翻，就会明白了。