STL:标准模版库

Forums: 

img: 

STL:标准模版库

STL,Standard Template Library,是 C++ 标准库的一部分,主要包括容器类、算法、函数对象、迭代器等的一些东西,是泛型编程的典范。C 的标准库内容过于有限,内置的数组类型并不是很好用,关键是 C 需要程序猿自己管理内存,这是一件灰常麻烦的事;所以如果可以的话就使用 C++ 的标准库,特别是 STL 部分。

容器类

所谓容器,就是说可以向其中添加东西的东西,比如 vector、list、map 等;在其他语言中和容器相似的概念可能是集合类、数据结构等。容器类分为两大类:序列容器和非序列容器。序列容器就是说其中的东西是一个序列 e1 e2 e3 ... ek...。非序列容器则包括 set 和 map 两类,set 就是集合了,没有顺序一说;map 则是 key-value 对,也没有顺序一说。

序列容器按其内部存储结构的不同又认为两类,一是数组形式的 vector ,另外一个是链表形式的 list。vector 是内置数组的替代品,实际上 C++ 推荐使用 vector 而不是内置数组。序列容器都属于线性结构,根据具体的应用场景又抽象出来两种常见的结构——栈和队列,对应两种适配器容器 stack 和 deque;之说它们是适配器容器,是因为它们可以在 vector 或是 list 基础上通过添加限制改造出来。

下面是一个 vector 的例子,当然完全可以使用 int[] 替换,这里主要就是体验一下 vector :(请使用 c++11 编译器:$ g++ -std=c++11 hello.cpp)

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     vector<int> iv = {1, 3, 4, 2, 8, 7, 5, 6, 10, 9};
  8.        
  9.     for(int i=0; i<iv.size(); ++i){
  10.         cout << iv[i] << " ";
  11.     }
  12.     cout << endl;
  13.        
  14.     return 0;
  15. }

非序列容器 setmap 默认都是不存储重复元素的,如果有这个需要,可以使用 multisetmultimap。这里的 set 和 map 组织的结构都是 tree,实际上还有一种结构叫 hash 结构,它们对应的是 unordered_map/unordered_multimapunordered_set/unordered_multiset (名字有点古怪,貌似是历史原因,因为 hash_map 这样的名字被有些实现占用了;其次使用 unordered 说明这种结构实际上是“无序的”)。

下面是一个 map 的例子:

  1. #include <iostream>
  2. #include <map>
  3. using namespace std;
  4.  
  5.  
  6. int main()
  7. {
  8.     map<string, int> user_age;
  9.    
  10.     user_age.insert(make_pair("zhangsan", 12));
  11.     user_age["li si"] = 20;
  12.    
  13.     cout << user_age["zhangsan"] << " " << user_age["li si"] << endl;
  14.    
  15.     return 0;
  16. }

广义滴说,内置数组和 string 也算是容器,因为它们也是一种数据结构:内置数组是一系列同类型的元素的有序集合;string 则是一系列 char 元素的有序集合。这里把它们加进来是因为在 c++ 中的确也将它们视为一种“容器”,而所有的容器都提供相似的抽象和操作(虽说不是绝对的)。

算法

典型的算法,恐怕要数排序 sort 了。STL 中算法是一系列抽象的操作,独立于具体的容器,也就是说 sort 算法可以排序 vector,可以排序 list,可以排序 map 等。然而这要肿么实现呢?通过迭代器这个中间组件。

体验一下如何排序数组和 vector :

  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     int ia[10] = {3, 4, 8, 7, 1, 10, 2, 5, 6, 9};
  9.     vector<int> iv = {1, 3, 4, 2, 8, 7, 5, 6, 10, 9};
  10.    
  11.     sort(ia, ia+10);
  12.     sort(iv.begin(), iv.end());
  13.    
  14.     for(int i=0; i<10; ++i){
  15.         cout << ia[i] << " ";
  16.     }
  17.     cout << '\n';
  18.     for(int i=0; i<iv.size(); ++i){
  19.         cout << iv[i] << " ";
  20.     }
  21.     cout << endl;
  22.        
  23.     return 0;
  24. }

迭代器

迭代器是容器类和算法之间的纽带,比如上面的 sort 排序 vector,并不是将 iv 当参数传给 sort,而是传递的 iv.begin() 和 iv.end(),分别指代 iv 的开始位置和结束位置。迭代器可以认为是指针的泛化,大体就是一个位置的概念。任何一个容器的每个元素都应该有其一个“位置”,可以按照某个顺序遍历一遍。iv.begin() 是其首元素的位置,iv.end() 是最后一个元素的下一个位置,所以可以认为 iv 就是位置 [iv.begin(), iv.end()) 这个左开右闭区间对应的一个序列;区间中的每一个元素就是一个迭代器的值 it,*it 指代元素,++it 指代下一个元素位置,--it 指代前一个元素位置。

下面是使用迭代器遍历 vector :

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     vector<int> iv = {1, 3, 4, 2, 8, 7, 5, 6, 10, 9};
  8.  
  9.     for(auto it=iv.begin(); it != iv.end(); ++it){
  10.         cout << *it << " ";
  11.     }
  12.     cout << endl;
  13.        
  14.     return 0;
  15. }

函数对象

排序 sort 算法中,默认是递增排序,但是有时候 me 们需要定制排序规则,这个时候可能需要一个 compare 函数。而在 C++ 中函数调用 () 是一个运算符,也就是 operator() 可以重载,那么可以像一个函数调用的就未必真的是一个函数,也可以是一个对象,只要重载了 operator() 运算符就可以。C++ 11 中还引入了匿名函数一说,下面给一个例子,权当体验一下:

  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     vector<int> iv = {1, 3, 4, 2, 8, 7, 5, 6, 10, 9};
  9.  
  10.     sort(iv.begin(), iv.end(), [](int a, int b){return b<a;});
  11.    
  12.     for(auto it=iv.begin(); it != iv.end(); ++it){
  13.         cout << *it << " ";
  14.     }
  15.     cout << endl;
  16.        
  17.     return 0;
  18. }