0.x 1.vector和list的区别

dddd数据结构课本

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

1.list逻辑顺序与物理顺序不同；vector逻辑顺序与物理顺序相同。
静态链表：物理空间连续内存块，但是其逻辑顺序并不是严格按照物理顺序存储的，所以也是链式存储，也有人称之为索引存储。
散列表：散列存储。

2.list获得的是双向迭代器，vector获取的是随机访问迭代器。

3.vector可以直接使用标准库算法sort，而list不能使用。
因为sort算法要求可以获得随机访问迭代器。list定义了自己版本的sort函数，可以实现更高效的排序，不需要直接交换元素，直接改变链表的连接来间接“交换”元素。
另外，list还定义了自己的merge、unique等算法，同样因为通用版本会使用很多交换操作，比如unique，而链表可以通过改变连接情况来实现交换。不需要直接交换。
实际上，只使用双向迭代器就可以完成几乎所有排序算法了！只不过标准库的排序算法要求更高，所以需要随机访问迭代器。

4.各种操作的效率不同：比如vector在push_back时的效率很高，但是在容器中间位置添加元素效率非常低；list在任意位置都能实现高效的插入。删除元素的时候情况也类似。

5.二分搜索算法不能用于list，可以用于vector。