标准模板库的内容

• 标准模板类：复数、序偶
• 迭代器
• 标准容器：向量、表、栈、堆、队列、集合、映射等
• 标准算法：查找、排序等

标准模板库型式的使用方法

• <>：模板名称<数据对象基型式> 数据对象名称；
• 示例一：Complex<double> a(1.0, 2.0);
• 示例二：pair<string,string> name("Zhang", "san");
• 示例三：vector<int> v(8);

复数 类模板

一般说明

• 头文件："complex"
• 模板名：complex<>
• 基型式：float、double、long double
• 首选double，float精度太低，long double已废弃

实部与虚部

• 成员函数real与imag()

复数操作

• 复数的全部操作均可以按照数学格式进行
• cout、cin均已重载：格式为(real, imag)

序偶 模板类

一般说明

• 头文件："utility"
• 模板类：pair<>
• 用于表示总是成对出现的两个对象
• 示例一：pair<int, double> a(1, 1.0);
• 示例二：pair<string, string> name("Zhang", "San");

使用规则

• 公开的数据成员：first、second
• 示例：cout << name.fisrt << "," << name.second;
• 序偶比较：先比较first大小，相同时比较second大小
• make_pair：构造序偶的辅助函数
• 示例：pair<int, double> a; a = make_pair(1, 1.0);

向量模板类

向量的目的

• 替代数组，可以像数组一样使用向量

向量的使用

• 格式定义：vector<int> v(8);// 包含8个整数元素
• operator[]：已重载，使用格式v[i]访问第i个元素
• 向量可以整体赋值
• size()：返回向量中元素数目
• capacity()：返回向量当前可存储的最多元素数目
• clear()：删除向量所有元素，但不释放向量本身
• resize(int newsize)：重新设置向量容量

补充：随机数接口

头文件声明

// Random.h
void Randomize();
int GenerateRandomNumber(int low, int high);
double GenerateRandomReal(double low, double high);

实现随机数库

#include <iostream>
#include <cstdlib>  // 这里包含srand()
#include <ctime>#include "Random.h"
using namespace std;
void Randomize()
{srand((int)time(NULL));
}int GenerateRandomNumber( int low, int high)
{double _d;if( low > high){cout　<< "GenerateRandomNumber: Make sure low <= high.\n";exit(1);}_d = (double)rand() / (RAND_MAX + 1.0);return (low + (int)(_d * (high - low + 1)));
}double GenerateRandomReal( double low, double high)
{double _d;if(low > high){cout　<< "GenerateRandomReal: Make sure low <= high.\n";exit(2);}_d = (double)rand() / (double)RAND_MAX;return (low + _d * (high - low));
}

测试

#include <iostream>
#include "Random.h"
using namespace std;int main(){int i;Randomize();for( i = 0; i < 8; ++i){int t =  GenerateRandomNumber(10,99);cout << t << ";";}cout << endl;for(i = 0; i < 8; ++i){double d = GenerateRandomReal(10.0, 99.0);cout << d << ";";}cout << endl;return 0;
}// 测试结果如下：
12;90;43;51;89;42;85;58;
98.9864;77.336;16.3992;74.9621;42.1728;89.8765;77.1567;11.4559;

迭代器

注意：没有必要搞清楚迭代器究竟是啥？不同容器的迭代器实现形式可能不同，即便是同一种容器的迭代器，也可能有多种实现迭代器的方式。只需要明白它有像指针一样的特性，使用很方便即可。

迭代器的性质

• 通过迭代器访问容器中的数据对象
• 类似指针、数组索引的功能：通过指针加减与数组下标算法获取下一数据对象
• 迭代器可以是指针，但并不必须是指针，也不必总是使用数据对象的地址

迭代器的典型使用方法

• 声明迭代器变量
• 使用引领操作符访问迭代器指向的当前目标对象
• 使用递增操作符获取下一对象的访问权
• 若迭代器新值超出容器的元素范围，类似指针变成NULL，目标对象不可引用

迭代器的分类

• 输出迭代器：提供对象的只读访问
• 输出迭代器：提供对象的只写访问
• 前向迭代器：提供对象的正向（递增）读写访问
• 双向迭代器：提供对象的正向与反向（递增递减）读写访问
• 随机访问迭代器：提供对象的随机读写访问

指针作为迭代器

调用标准模板库的find()函数查找数组元素

#include <iostream>
#include <algorithm>
using namespace std;
const int size = 16;
int main()
{int a[size];for(int i = 0; i < size; ++i)a[i] = i;int key = 7;int * ip = find(a, a + size, key);if(ip == a + size) // 不要使用NULL做指针测试，直接使用过尾值cout << key << " not found." << endl;elsecout << key << " found." << endl;return 0;
}

使用迭代器操作向量

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{int key = 7;vector<int> iv(10);for(int i = 0; i < 10; i++)iv[i] = i;// 下面一句就是在定义迭代器对象vector<int>::iterator it, head = iv.begin(), tail = iv.end();it = find( head, tail ,key );if(it != tail)cout << "Vector contains the value" << key << endl;elsecout << "Vector does NOT contain the value" << key << endl;return 0;
};

常迭代器

• 若不想通过迭代器修改目标对象值，定义迭代器常量

示例

• const vector<int>::iterator it;
• 非法操作：*it = 10;// 不能修改常迭代器指向的对象

流迭代器

使用迭代器访问流

• 将输入输出流作为容器

使用方式：定义流迭代器对象

• 示例一：ostream_iterator<int> oit(cout, " "); // 将 oit 迭代器和 cout 绑定在一块，输出的两元素之间用空格" "隔开
• 示例二（从cin获取数据）：istream_iterator<int> iit(cin);
• 示例三（使用空指针创建流结束迭代器）：istream_iterator<int> iit;
• 凡是可以出现迭代器参数的标准算法都可以使用

示例：输出流迭代器

#include <iostream>
#include <iterator>
#include <algorithm>
#include "random.h"
using namespace std;
const int size = 8;
const int lower_bound = 10;
const int upper_bound = 99;void Display( vector<int> & v, const char * s)
{cout << endl << s << endl;vector<int>::iterator head = v.begin(), tail = v.end();// 输出流迭代器实际是是指向输出流容器，所以数据向输出流里面一拷贝，这个数据就是到屏幕上// 拷贝一个，输出一个，中间是用逗号分开的ostream_iterator<int> oit(cout, ";"); // oit是迭代器名称，可以随便起copy(head, tail, oit);cout << endl;
}int main()
{vector<int> a(size);for(int i = 0; i < size; ++i)a[i] = GenerateRandomNumber(10, 99);Display(a, "Array generated:");vector<int>::iterator head = a.begin(), tail = a.end();sort(head, tail);  // 只要该容器支持迭代器，sort都可以进行排序，缺省排序是从小到大Display(a, "Array sorted:");reverse(head, tail);Display(a, "Array reversed:");return 0;
}

示例：输入流迭代器

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{vector<int> v(4);vector<int>::iterator it = v.begin();cout << "Enter 4 ints separated by spaces & a char:\n";// head 就是迭代器，和cin绑定；tail空迭代器，表示输入流的结尾istream_iterator<int> head(cin), tail; copy(head, tail, it);cin.clear();cout << "vector = ";for(it = v.begin(); it != v.end(); ++it)cout << *it << " ";cout << endl;return 0;
}

表

模板库中的表实际上是双向列表

表的使用

• 定义包含Point对象的容器：list<Point> pts(8);
• 插入：pts.insert(pts.begin(), Point(1, 2));
• 表头插入：pts.push_front(Point(1, 2));
• 插入：pts.insert(pts.end(), Point(1, 2));
• 表尾插入：pts.push_back(Point(1, 2));
• 定义包含Point 指针的容器：list<Point*> ppts(8);
• 插入：ppts.insert(ppts.begin(), new Point(1, 2));
• 插入：ppts.insert(ppts.end(), new Point(1, 2));
• 删除：delete ppts.front(); ppts.remove( ppts.front());
• 判断是否为空：if(pts.empty()) cout << "Empty!";

表与迭代器

• 迭代器可以和表协同工作，方式与向量相同

  list<int> a(8);
  list<int>::iterator it;
  for( it = a.begin(); it != a.end(); ++it)*it = GenerateRandomNumber(10, 99);
  

  表排序

  • 直接使用表的成员函数：a.sort();// 默认升序
  • 降序排序之一：升序排序后调用成员函数reverse()
  • 降序排序之二：传入函子greater_equal<int>()
a.sort(greater_equal<int>());
  • 对于自定义对象，需要重载operator <以进行比较

标准算法

• 查找算法
• 排序算法
• 删除和替换算法
• 排列组合算法
• 算术算法
• 关系算法
• 集合算法
• 生成和变异算法
• 堆算法

共提供了84个抽象算法

标准函子

算术函子

• plus<T> 加
  minus<T> 减
  multiplies<T> 乘
  divides<t> 除
  modulus<T> 取模
  negate<T> 取负
  

关系函子

• equal_to<T> 等于
  not_equal_to<T> 不等于
  greater<T> 大于
  great_equal<T> 大于等于
  less<T> 小于
  less_equal<T> 小于等于
  

逻辑函子

• logical_and<T> 逻辑与
  logical_or<t> 逻辑或
  logical_not<T> 逻辑非