1.C++ STL 之所以得到广泛的赞誉，也被很多人使用，不只是提供了像 vector,
string, list 等方便的容器，更重要的是 STL 封装了许多复杂的数据结构算法和大
量常用数据结构操作。vector 封装数组，list 封装了链
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
，map 和 set 封装了二叉
树等
2.标准关联容器 set, multiset, map, multimap内部采用的就是一种非常高效的平衡
检索二叉树：红黑树，也成为 RB 树(Red-Black Tree)。RB 树的统计性能要好于
一般的平衡二叉树
3.STL map 和 set 的使用虽不复杂，但也有一些不易理解的地方，如：
map: type pair
，很多不同的 const Key 对应的 T对象的一个
集合，所有的记录集中只要 const Key 不一样就可以，T无关！
set: type const Key. 只存单一的对 const Key，没有 map 的 T 对像！可以
看成 map 的一个特例
（1）为何 map 和 set 的插入删除效率比用其他序列容器高？，树
答：因为对于关联容器来说，不需要做内存拷贝和内存移动。说对了，确实如此。
map 和 set 容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，
指向父节点和子节点
·
（2）为何每次 insert 之后，以前保存的 iterator 不会失效？
答：iterator 这里就相当于指向节点的指针，内存没有变，指向内存的指针怎么
会失效呢(当然被删除的那个元素本身已经失效了)。相对于 vector 来说，每一次
删除和插入，指针都有可能失效，调用 push_back 在尾部插入也是如此。因为为
了保证内部数据的连续存放，iterator 指向的那块内存在删除和插入过程中可能
已经被其他内存覆盖或者内存已经被释放了。即使时 push_back 的时候，容器内
部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的
更大的内存，复制已有的数据元素到新的内存，最后把需要插入的元素放到最后，
那么以前的内存指针自然就不可用了。特别时在和 find 等算法在一起使用的时
候，牢记这个原则：不要使用过期的 iterator。
（3）为何 map 和 set 不能像 vector 一样有个 reserve 函数来预分配数据？
答：我以前也这么问，究其原理来说时，引起它的原因在于在 map 和 set 内部存
储的已经不是元素本身了，而是包含元素的节点。也就是说map内部使用的 Alloc
并不是 map声明的时候从参数中传入的 Alloc。例如：
4.4.4.4.set,set,set,set, multisetmultisetmultisetmultiset
set 和 multiset 会根据特定的排序准则自动将元素排序，set 中元素不允许重复，
multiset 可以重复。
因为是排序的，所以 set 中的元素不能被修改，只能删除后再添加。
向 set 中添加的元素类型必须重载<操作符用来排序。排序满足以下准则：
1、非对称，若 A
因为是排序的，所以 map 中元素的 key 不能被修改，只能删除后再添加。key 对
应的 value 可以修改。
向 map 中添加的元素的 key 类型必须重载<操作符用来排序。排序与 set 规则一
致。
6.6.6.6. ListListListList的功能方法
实际上有两种 List: 一种是基本的 ArrayList,其优点在于随机访问元素，另一
种是更强大的 LinkedList,它并不是为快速随机访问
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
的，而是具有一套更通用
的方法。
List : 次序是 List 最重要的特点：它保证维护元素特定的顺序。List 为
Collection 添加了许多方法，使得能够向 List 中间插入与移除元素 (这只推荐
LinkedList 使用。)一个 List 可以生成 ListIterator,使用它可以从两个方向遍历 List,
也可以从 List 中间插入和移除元素。
ArrayList : 由数组实现的 List。允许对元素进行快速随机访问，但是向 List
中间插入与移除元素的速度很慢。ListIterator只应该用来由后向前遍历 ArrayList,
而不是用来插入和移除元素。因为那比 LinkedList 开销要大很多。
LinkedList : 对顺序访问进行了优化，向 List 中间插入与删除的开销并不大。
随机访问则相对较慢。(使用ArrayList代替。)还具有下列方法：addFirst(), addLast(),
getFirst(), getLast(), removeFirst() 和 removeLast(), 这些方法 (没有在任何接口
或基类中定义过)使得 LinkedList 可以当作堆栈、队列和双向队列使用
7.7.7.7..1.1.1.1 hash_maphash_maphash_maphash_map和 mapmapmapmap的区别在哪里？
构造函数。hash_map 需要 hash 函数，等于函数；map 只需要比较函数(小于函数).
存储结构。hash_map 采用 hash 表存储，map 一般采用红黑树(RB Tree)实现。因
此其 memory 数据结构是不一样的。
7777.2.2.2.2 什么时候需要用 hash_maphash_maphash_maphash_map，什么时候需要用 map?map?map?map?
总体来说，hash_map 查找速度会比 map 快，而且查找速度基本和数据数据量大
小，属于常数级别;而 map 的查找速度是 log(n)级别。并不一定常数就比 log(n)
小，hash 还有 hash 函数的耗时，明白了吧，如果你考虑效率，特别是在元素达
到一定数量级时，考虑考虑 hash_map。但若你对内存使用特别严格，希望程序
尽可能少消耗内存，那么一定要小心，hash_map 可能会让你陷入尴尬，特别是
当你的 hash_map 对象特别多时，你就更无法控制了，而且 hash_map 的构造速度
较慢。
现在知道如何选择了吗？权衡三个因素: 查找速度, 数据量, 内存使用。
8.8.8.8.一些使用上的建议：
Level 1 - 仅仅作为 Map 使用：采用静态数组
Level 2 - 保存定长数据，使用时也是全部遍历：采用动态数组（长度一开始就固
定的话静态数组也行）
Level 3 - 保存不定长数组，需要动态增加的能力，侧重于寻找数据的速度：采用
vector
Level 3 - 保存不定长数组，需要动态增加的能力，侧重于增加删除数据的速度：
采用 list
Level 4 - 对数据有复杂操作，即需要前后增删数据的能力，又要良好的数据访问
速度：采用 deque
Level 5 - 对数据中间的增删操作比较多：采用 list，建议在排序的基础上，批量
进行增删可以对运行效率提供最大的保证
Level 6 - 上述中找不到适合的：组合 STL 容器或者自己建立特殊的数据结构来
实现
9.
(1).vector - 会自动增长的数组
vector vec(10) //一个有 10 个 int 元素的容器
vector vec(10, 0.5)//一个有 10 个 float 元素的容器，并且他们得值都是 0.5
vector::iterator iter;
for(iter = vec.begin(); iter != vec.end(); iter++)
{
//. . . . . . .
}
vector 由于数组的增长只能向前，所以也只提供了后端插入和后端删除，
也就是 push_back 和 pop_back。当然在前端和中间要操作数据也是可以的，
用 insert 和 erase，但是前端和中间对数据进行操作必然会引起数据块的移动，
这对性能影响是非常大的。
最大的优势就是随机访问的能力。
vector::iterator 相关的方法有：
begin()：用来获得一个指向 vector 第一个元素的指针
end()：用来获得一个指向 vector 最后一个元素之后的那个位置的指针，注意不是
指向最后一个元素。
erase(vector::iterator)：用来删除作为参数所传入的那个 iterator 所指向的那
个元素。
(2).list - 擅长插入删除的链表
list Milkshakes; list Scores;
push_back, pop_back push_front. pop_front
list 是一个双向链表的实现。
为了提供双向遍历的能力，list 要比一般的数据单元多出两个指向前后的指针
一个使用 iterator 来删除元素的例子
list stringList;
list::iterator iter;
advance(iter, 5); //将 iterator 指向 stringList 的第五个元素
stringList.erase(iterator);//删除
那么删除操作进行以后，传入 erase()方法的 iterator 指向哪里了呢？它指向了删
除操作前所指向的那个元素的后一个元素。
(3).deque - 拥有 vector 和 list 两者优点的双端队列
(4)．这三个
模板
个人简介word模板免费下载关于员工迟到处罚通告模板康奈尔office模板下载康奈尔 笔记本 模板 下载软件方案模板免费下载
的
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
比较和一般使用准则
这三个模板都属于序列类模板，可以看到他们有一些通用方法
size():得到容器大小
begin():得到指向容器内第一个元素的指针（这个指针的类型依容器的不同而不
同）
end():得到指向容器内最后一个元素之后一个位置的指针
erase():删除传入指针指向的那个元素
clear():清除所有的元素
＝＝运算符：判断两个容器是否相等
＝运算符：用来给容器赋值
上面的三个模板有各自的特点
vector 模板的数据在内存中连续的排列，所以随机存取元素（即通过 []运算符存
取）的速度最快，这一点和数组是一致的。同样由于它的连续排列，所以它在除
尾部以外的位置删除或添加元素的速度很慢，在使用 vector 时，要避免这种操作。
list 模板的数据是链式存储，所以不能随机存取元素。它的优势在于任意位置添
加 删除元素的速度。
deque 模板是通过链接若干片连续的数据实现的，所以均衡了以上两个容器的特
点
浙公网安备 33021202002483