2012-05-16
Chapter04
1、容器分类
顺序容器：向量vector，列表list。双端队列deque→存储一个元素序列
容器适配器：队列queue，优先队列priority queue，栈stack→建立在三种顺序容器之上的接口
关联容器：集合set，映射map（包含多集，多映射）→建立了键与值的关联
在set中，键本身就是值
特殊容器：位集bitset
2、set按有序方式存储元素，插入、删除、查找都是O(logn)
底层用平衡二叉树实现→使用情况：如果希望插入删除和查找性能相当
set不允许有重复的元素 ∴可用multiset存储重复的元素
3、map存储了键/值对 元素按键排序，其他方面与set相同
map、set
应用举例：set集合会忽略重复的单词
set<string>s;
set<string>::iterator j;
string t;
while(cin>>t)
s.insert(t);
for(j=s.begin() ; j!=s.end() ; j++)
cout<<*j<<endl;
map集合可以进行key,value的映射（统计单词个数）
map<string,int>M;
map<string,int>:iterator j;
string t;
while(cin>>t)
M[t]++;
for(j=M.begin() ;j!=M.end(); j++)
cout<<j->first<<” ”<<j->second>>endl;
4、bieset：标志集合，每个标志用一位表示（无插入删除方法）
但可用O(1)进行查找
5、STL算法：用模板实现，在大多数不同容器类型都能使用
STL把数据（容器）与功能（算法）分离
但有些容器以类方法的形式提供某些算法（优先使用，效率更高）
例如vector v;
v.find() //类方法
find(…) //STL算法