<<C++标准程序库>>中的STL简单学习笔记

0. 内容为个人学习笔记, 仅供参考, 如有错漏, 欢迎指正!

1. STL中的所有组件都是由模板构成的, 所以其元素可以是任意型别的. 组件有:

　　- 容器: 管理某类对象的集合. 不同的容器有各自的优缺点.

　　- 迭代器: 用来在一个对象集群(Collection of Objects) 的元素上进行遍历. 这个CoB可以是容器/容器的一部分. 每种容器都提供了自己的迭代器.

　　- 算法(Algorithm): 用来处理集群内的元素(比如: 查询,修改,排序等).

　　- 适配器(adapter)

　　- 仿函数(functors or function objects)

2. STL基本观念是将数据和操作分离, 数据交给容器进行管理, 操作(算法)可以定制算法, 使用迭代器来提供两者间统一的接口.

　　- STL 的概念有点儿和OOP的最初思想矛盾, 然而这个小框架提供了很好的容器/算法弹性.

　　- STL 是泛型编程的出色范例, 容器和算法对任意型别和类别而已已经一般化了.

　　- STL 提供了适配器和仿函数可以实现对算法的: 补充, 约束和定制, 从而满足不同的需求.

3. 容器

　　- 序列式容器(Sequence container): 可序集群.(3个) ---- vector/deque/list (为什么queue,stack 和 string不是呢?)

　　　　- 可以将string 和 array 也当作是一种序列式容器(why?)

　　　　- array 是C/C++语言核心所支持的一个型别(type), 而不是(class). 具有静态大小和动态大小. 但它也并不是STL容器. 因为没有类似size(),empty()等成员函数. 但是STL的设计又允许它调用STL算法. 当我们以static arrays作为初始化行时特别有用.

　　　　- 没有必要直接编写dynamic array了, 因为可以用vector实现.

　　- 关联式容器(Association container): 已序集群(4个). 排序和元素值,插入顺序无关. ---- set/multiset/map/multimap

　　　　- 自动会对元素进行排序. 默认情况下是使用 operator < 进行比较.

　　　　- 一般关联容器由二叉搜索树实现 , 各容器的主要差别在于元素的类型已经处理重复元素的方式.

　　　　- set: 按内部元素的值进行排序, 不允许重复.

　　　　- multiset: 和set相同, 但允许重复

　　　　- map: key/values , 键不允许重复.

　　　　- multimap: 和map一样, 但键允许重复.可以用来当做字典.

4. 容器适配器

　　- stack: FILO

　　- queue: FIFO

　　- priority_queue: 下一个出队的元素永远是具有最高优先级的元素 ( 默认比较是 operator < 所以数值越小,优先级越高? ).

5. 迭代器(基本操作)

　　- operator */++/==/!=/=

　　- 每种容器都必须提供自己的内部类, 事实上每种容器都将其适配器定义为内部类.

　　- 任何一种容器都有2种类别的迭代器

　　　　- container::iterator

　　　　- container::const_iterator

6. 关联式容器的一些应用

　　- typedef set<int> IntSet; / typedef set<int, greater<int> >IntSet; greater<> 是一个预先定义的仿函数.

　　- 所有的关联容器都有一个insert()方法, 但是没有序列式容器的push_back(),push_front()方法 , 因为你没有权力指定新元素的位置.

　　- map 允许使用 operator [] 来安插元素. 而multimap不允许使用下标操作符(因为key可以重复哦).

　　- 存取multimap或map的元素时, 必须用pair结构的first和second成员才能访问到具体key/value

 1 #include <iostream>
 2 #include <map>
 3 #include <string>
 4 using namespace std;
 5 int main(){
 6     typedef map<string,float> StringFloatMap;
 7     StringFloatMap coll;
 8     coll["VAT"] = 0.15;
 9     coll["pi"] = 3.14;
10     coll["This is a string"] = 3.4;
11     coll["NULL"] = 0;
12     StringFloatMap::iterator it = coll.begin(); // map 是不能手动排序,但是并不是没有序
13     for(;it!=coll.end();++it){ // 使用++it效率高于 it++
14         cout<<it->first<<" : "<<it->second<<endl;
15     }
16     return 0;
17 }

View Code

7. 迭代器分类(2种)

　　- 双向迭代器(Bidirectional iterator): list/set/multiset/map/multiset提供的属于此类.

　　- 随机存取迭代器(Random access iterator): vector/deque/string提供的属于此类. 随机访问迭代器可以支持 operator <

8. 算法

　　- 不是容器的成员函数, 而是搭配迭代器使用的全局函数.

　　- pos = min_element(coll.begin(),coll.end()) / pos = max_element(coll.begin(),coll.end())

　　- sort(coll.begin(),coll.end()[,comp]);

　　- pos = find(coll.begin(),coll.end(),value);

　　- reserve(pos,coll.end())

　　- 处理多个区间

　　　　- equal(coll1.begin(),coll1.end(), coll2.begin() ); //必须设定第一个区间的起点和终点, 至于其他区间, 只需设置起点即可, 终点通常由第一区间的元素数量推断出来.

　　　　- copy(coll1.begin(),coll1.end(),coll2.begin()); //处理多个区间时注意区间的大小, 否则可能会读写到其他地方造成错误,如果不是STL安全版本不会有异常.

　　　　- 可以使用resize()改变目标容器的大小, 适用于序列式容器.

9. 迭代器适配器(Iterator Adapters)

　　- 迭代器是接口, 任何类别(class)只要具备这个接口就可以实现迭代. C++标准库提供了几个预定义的特殊迭代器, 即迭代器适配器(以下3种).

　　- Insert Iterator: 可以使算法以插入而非覆写的方式运作. 插入的位置(最前/最后/特定位置), 根据3重不同的Insert Iterator而异.

　　　　- back_inserter: copy(coll1.begin(),coll1.end(),back_inserter(coll2));

　　　　　　- 只有在提供push_back()的容器中才能用. (vector/deque/list)

　　　　- front_inserter: copy(coll1.begin(),coll1.end(),front_inserter(coll3));

　　　　　　- 容器要满足有push_front(). (deque/list)

　　　　- inserter: copy(coll1.begin(),coll1.end(),inserter(coll2,coll2.begin()); //只有inserter可以在关联容器上工作(非关联容器上应该也可以吧). 上面两种不行.

　　　　　　- 所有的STL容器都提供有insert(), 对于关联式容器而言, 提供一个开始搜寻的位置.

　　- Stream Interator: 一种用来读写流的迭代器, 提供了必要的抽象性, 使得来自键盘的输入像是个集群.

　　　　- copy(istream_iterator<string> (cin), istream_iterator<string>(), back_inserter(coll));

　　　　　　- istream_iterator<string>(cin) : 会产生一个从标准输入流cin读取数据的stream Iterator,读取string类型, 每当算法处理下一个元素时, 就转化为:cin>>string

　　　　　　- ostream_iterator<string>(): 调用istream iterator的default构造函数, 产生一个代表"流结束符"的迭代器.

　　　　- unique_copy(coll.begin(),coll.end(),ostream_iterator<string>(cout," "));

　　　　　　- 第二个参数是可选的元素分隔符.

　　- Reverse Iterator: 提供逆向操作. 可以通过 rbegin()/rend()来产生逆向迭代器.

　　　　- copy(coll.rbegin(), coll.rend(), ostream_iterator<int>(cout," "));

　　　　- 可以将一般的迭代器转换为逆向迭代器, 反之亦然.

10. 更易型算法(manipulating algorithm)

　　- remove(): 移除元素, 但是容器的size(),返回的end() 没有改变, 因为是用容器后面的元素覆盖了删除的元素.

　　- remove()会返回删除元素后新的迭代器的位置, 而不改变原来容器迭代器的位置. list<int>::iterator end = remove(coll.begin(),coll.end(),value);

 1 #include <iostream>
 2 #include <map>
 3 #include <string>
 4 #include <iterator>
 5 #include <list>
 6 #include <algorithm>
 7 using namespace std;
 8 int main(){
 9     list<int> coll; //list提供双向迭代器, 是双向链表.
10     for(int i=1;i<=6;++i){
11         coll.push_front(i);
12         coll.push_back(i);
13     }
14     copy(coll.begin(),coll.end(), ostream_iterator<int>(cout," "));
15     cout<<endl;
16     list<int>::iterator end = remove(coll.begin(),coll.end(),3);
17     copy(coll.begin(),end,ostream_iterator<int>(cout," "));
18     cout<<endl;
19     cout<<distance(end,coll.end())<<endl;
20     coll.erase(end,coll.end());
21     copy(coll.begin(),coll.end(),ostream_iterator<int>(cout," "));
22     cout<<endl;
23     return 0;
24 }

View Code

　　- 辅助函数 distance(), 返回迭代器之间的距离, 可以用于随机存取迭代器(还可以使用算术运算)和双向迭代器.

　　- coll.erase(end,coll.end()); 删除区间内的所有元素.

　　- 更易型算法不适用于关联式容器. 关联式的所有迭代器均被声明为指向常量. 更易关联式容器中的元素会产生编译错误.

　　- 不能使用算法函数 remove() 来移除关联式容器的元素, 但是可以通过调用关联式容器的方法erase()移除元素,返回被删除元素个数.

11. 算法函数和成员函数

　　- 容器本身可能提供功能相似算法函数而性能更佳的成员函数, 成员函数更了解具体容器的具体需要, 因此应该优先考虑成员函数.

　　- 有的容器操作, 使用成员函数和算法函数都可以. 但是成员函数性能更高.

12. 自定义泛型函数

13. 函数作为算法的参数

　　- 算法函数: for_each(coll.begin(),coll.end(), print) ;// print 是一个函数

　　　　　　　　std::transform(coll1.begin(),coll1.end(),std::back_inserter(coll2),square); //square 是一个函数

　　　　　　　 pos = find_if(coll.begin(),coll.end(), isPrime);

　　- 判断式

　　　　- 判断式通常用来指定排序准则和搜索准则, 不允许改变参数的状态. 如 isPrime

　　　　- 如果元素本身不支持 operator < ,那么一般会使用二元判断式(2个参数).

14. 仿函数(function object: 函数对象)

　　- 定义: 可以这么理解, 任何东西只要能像函数一样调用 , 就说它是个函数, 因此一般的对象如果重载了operator (), 那么就能像函数一样调用, 成为一个函数对象.

　　- 例子:

 1 #include <iostream>
 2 #include <map>
 3 #include <string>
 4 #include <iterator>
 5 #include <list>
 6 #include <algorithm>
 7 #include <vector>
 8 using namespace std;
 9 class PrintInt{
10 public:
11     void operator()(int elem) const{
12         cout<<elem<<endl;
13     }
14 };
15 int main(){
16     vector<int> coll;
17     for(int i=1;i<=9;++i){
18         coll.push_back(i);
19     }
20     for_each(coll.begin(),coll.end(),PrintInt());
21     cout<<endl;
22     return 0;
23 }

View Code

　　- 函数对象的优点:

　　　　- 是智能型函数:

　　　　　　- 函数对象有自己的类型, 可以拥有其他成员函数和成员变量, 意味着函数对象可以拥有状态.

　　　　　　- 可以在执行期间初始化它们.

　　　　- 每个函数对象有自己的型别:

　　　　　　- 一般函数只有当signature不同时才算型别不同, 而函数对象即使签名相同, 也可以有不同的类型.

　　　　　　- 可以设计仿函数继承体系, 完成其他事情.

　　　　- 仿函数比一办函数快

　　　　　　- 对template而言 , 更多的细节在编译期就已确定, 所以运行更佳.

　　　　　　- 例子

 1 #include <iostream>
 2 #include <iterator>
 3 #include <list>
 4 #include <algorithm>
 5 using namespace std;
 6 //function object that adds the value with witch it is initialized.
 7 class AddValue{
 8 private:
 9     int theValue;  // the value to add
10 public:
11     AddValue(int v):theValue(v){}
12     void operator()(int& elem) const{
13         elem += theValue;
14     }
15 };
16 
17 int main(){
18     list<int> coll;
19     for(int i=1;i<=9;++i){
20         coll.push_back(i);
21     }
22     copy(coll.begin(),coll.end(),ostream_iterator<int>(cout," "));
23     cout<<endl;
24     for_each(coll.begin(),coll.end(),AddValue(10));
25     copy(coll.begin(),coll.end(),ostream_iterator<int>(cout," "));
26     cout<<endl;
27     for_each(coll.begin(),coll.end(),AddValue(*coll.begin()));
28     copy(coll.begin(),coll.end(),ostream_iterator<int>(cout," "));
29     cout<<endl;
30     return 0;
31 }

View Code

　　- STL中预定义的仿函数

　　　　- less<int>() //默认的排序准则

　　　　- negate<int>(); // 处理数值, 转换为相反值. transform(coll.begin(),coll.end(),coll.begin(), negate<int>()); // 求相反数并回写.

　　　　- multiplies<int>(); // 处理数值, 相乘 transform(coll.begin(),coll.end(),coll.begin(),coll.begin(),multiplies<int>()); // 3个集群相同, 求的是平方, 保存回去.

　　　　- mem_fun_ref(&Person::save) //调用它所作用的元素的某个成员函数,参数可以是Person的派生类. for_each(coll.begin(), coll.end(), mem_fun_ref(&Person::save));

　　　　- 仿函数和适配器结合使用, 更加灵活; 而且这样这些仿函数都是inline, 性能更佳.

 1 #include <iostream>
 2 #include <iterator>
 3 #include <set>
 4 #include <queue>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 int main(){
 9     // 可以在创建set的时候指定set内的排序规则.(?)
10     set<int,greater<int> > coll1;  // 为什么不是 greater<int>()呢, greater不是一个类吗? 
11     deque<int> coll2;
12     for(int i=1;i<=9;++i)
13         coll1.insert(i);
14     copy(coll1.begin(),coll1.end(),ostream_iterator<int>(cout," "));
15     cout<<endl;
16     //使用适配器 bind2nd() 将预先定义的仿函数和其他数值组合在一起.
17     // bind2nd会将10当成内部数值保存下来,当算法以实际集群元素为参数, 
18     //调用bind2nd时, bind2nd会把该元素当成第一参数, 10当成第二参数,调用bind2nd的第一参数(仿函数).
19     transform(coll1.begin(),coll1.end(),back_inserter(coll2),bind2nd(multiplies<int>(),10));//这里是multiplies<int>(),有括号呀?
20     copy(coll2.begin(),coll2.end(),ostream_iterator<int>(cout," "));
21     cout<<endl;
22     replace_if(coll2.begin(),coll2.end(),bind2nd(equal_to<int>(),70),42);
23     copy(coll2.begin(),coll2.end(),ostream_iterator<int>(cout," "));
24     cout<<endl;
25     coll2.erase(remove_if(coll2.begin(),coll2.end(), // range
26         bind2nd(less<int>(),50)), // 删除标准
27         coll2.end());
28     copy(coll2.begin(),coll2.end(),ostream_iterator<int>(cout," "));
29     cout<<endl;
30     return 0;
31 }

View Code