华师一附中OI组

标题: C++:标准模板库(STL) [打印本页]

---

作者: admin    时间: 2018-8-11 09:19
标题: C++:标准模板库(STL)
介绍
STL(standard template library)标准模板库,是一种高效的C++程序库。
STL分为三类：container(容器),iterator(迭代器)和algorithm(算法)。


容器(container)
容器是用来管理某一类对象的集合,包括序列式容器和关联式容器。
    序列式容器：vector,list,deque
    关联式容器：map,set




遵循规则：

1.所有容器中存放的都是值而非引用。因此容器中的每个元素必须能够被拷贝，如想存放的不是副本，容器元素只能是指针。

2.容器中所有元素都是有次序(order)的，可以进行一次或多次遍历每个元素。

迭代器(iterators)
迭代器用于遍历对象集合的元素，这些集合可能是容器也可能是容器子集。

所有容器都提供获得迭代器的函数。

begin()      返回一个迭代器，指向第一个元素
end()        返回一个迭代器，指向最后一个元素


算法(algorithm)
算法作用于容器，包括对容器内容进行初始化，排序，搜索和转换等操作。

STL算法分为四类：

1.非可变序列算法：不直接修改容器中内容。

2.可变序列算法：可以直接修改容器的内容。

3.排序算法：包含对序列的排序，合并，搜索和对有序序列的操作等算法那。

4.数值算法：对容器内容计算。

---

作者: admin    时间: 2018-8-11 09:33
容器概述:
 可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构。
 容器分为三大类：
1) 顺序容器
vector：后部插入/删除，直接访问
deque：前/后部插入/删除，直接访问
list：双向链表，任意位置插入/删除
2)关联容器
set：快速查找，无重复元素
multiset ：快速查找，可有重复元素
map：一对一映射，无重复元素，基于关键字查找
multimap ：一对一映射，可有重复元素，基于关键字查找前2者合称为第一类容器
3)容器适配器
stack： LIFO
queue： FIFO
priority_queue：优先级高的元素先出容器概述
 对象被插入容器中时，被插入的是对象的一个复制品。
 许多算法，比如排序，查找，要求对容器中的元素进行比较，所以，放入容器的对象所属的类，还应该实现== 和 <运算符。

---

作者: admin    时间: 2018-8-11 09:41
1. 概论
 C++ 语言的核心优势之一就是便于软件的重用
 C++中有两个方面体现重用：
    1. 面向对象的思想：继承和多态，标准类库

    2. 泛型程序设计(generic programming)的思想：模板机制，以及标准模板库机制，以及标准模板库STL泛型程序设计

 泛型程序设计，简单地说就是使用模板的程序设计法。
 将一些常用的数据结构（比如链表，数组，二叉树）和算法（比如排序，查找）写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对象，则都不必重新实现数据结构，重新编写算法。
 标准模板库 (Standard Template Library)就是一些常用数据结构和算法的模板的集合。主要由 Alex Stepanov开发，于1998年被添加进C++标准
 有了STL，不必再从头写大多的标准数据结构和算法，并且可获得非常高的性能。



模板引子:

1.假如设计一个求两参数最大值的函数， 在实践中我们可能需要定义四个函数：
int max ( int a , int b ) { return ( a > b ) ? a , b ; }
long max ( long a , long b ) { return ( a > b ) ? a , b ;}
double max ( double a , double b ) { return ( a >b)? a , b ; }
char max ( char a , char b ) { return ( a > b ) ? a , b ;}
2.这些函数几乎相同， 唯一的区别就是形参类型不同
3.需要事先知道有哪些类型会使用这些函数， 对于未知类型这些函数不起作用



模板的概念:
1. 所谓模板是一种使用无类型参数来产生一系列函数或类的机制。
2. 若一个程序的功能是对某种特定的数据类型进行处理， 则可以将所处理的数据类型说明为参数， 以便在其他数据类型的情况下使用， 这就是模板的由来。
3. 模板是以一种完全通用的方法来设计函数或类而不必预先说明将被使用的每个对象的类型。
4. 通过模板可以产生类或函数的集合，使它们操作不同的数据类型，从而避免需要为每一种数据类型产生一个单独的类或函数。



模板分类:
 函数模板(function template): 是独立于类型的函数; 可产生函数的特定版本
 类模板(class template): 跟类相关的模板，如vector: 可产生类对特定类型的版本，如vector<int>

求最大值模板函数实现:
1.求两个数最大值， 使用模板
template < class T >
T max(T a , T b){
return ( a > b ) ? a , b;
}
2.template < 模板形参表>
<返回值类型> <函数名>（ 模板函数形参表）
{
//函数定义体
}

模板工作方式:
 函数模板只是说明，不能直接执行，需要实例化为模板函数后才能执行
 在说明了一个函数模板后，当编译系统发现有一个对应的函数调用时，将根据实参中的类型来确认是否匹配函数模板中对应的形参，然后生成一个重载函数。该重载函数的定义体与函数模板的函数定义体相同，它称之为模板函数
编写一个对具有n个元素的数组a[ ]求最小值的程序，要求将求最小值的函数设计成函数模板。
#include <iostream>
template <class T>
T min(T a[],int n)
{
int i;
T minv=a[0];
for( i = 1;i < n ; i++){
if(minv>a[i])
minv=a[i];
}
return minv;
}

void main()
{
ina a[]={1,3,0,2,7,6,4,5,2};
double b[]={1.2,-3.4,6.8,9,8};
cout<<”a数组的最小值为： ”
<<min(a,9)<< endl;
cout<<”b数组的最小值为： ”
<<min(b,4)<<endl;
}

此程序的运行结果为：
a数组的最小值为： 0
b数组的最小值为： -3.4



模板优缺点:
 函数模板方法克服了C语言解决上述问题时用大量不同函数名表示相似功能的坏习惯
 克服了宏定义不能进行参数类型检查的弊端
 克服了C++函数重载用相同函数名字重写几个
函数的繁琐
 缺点，调试比较困难
 一般先写一个特殊版本的函数
 运行正确后，改成模板函数

2. STL中的几个基本概念
 容器：可容纳各种数据类型的数据结构。
 迭代器：可依次存取容器中元素的东西
 算法：用来操作容器中的元素的函数模板。例如，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象。
 函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。
 比如，数组int array[100]就是个容器，而int * 类型的指针变量就可以作为迭代器，可以为这个容器编写一个排序的算法



容器概述:
 可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构。
 容器分为三大类：
1) 顺序容器
vector：后部插入/删除，直接访问
deque：前/后部插入/删除，直接访问
list：双向链表，任意位置插入/删除
2)关联容器
set：快速查找，无重复元素
multiset ：快速查找，可有重复元素
map：一对一映射，无重复元素，基于关键字查找
multimap ：一对一映射，可有重复元素，基于关键字查找前2者合称为第一类容器
3)容器适配器
stack： LIFO
queue： FIFO
priority_queue：优先级高的元素先出容器概述
 对象被插入容器中时，被插入的是对象的一个复制品。
 许多算法，比如排序，查找，要求对容器中的元素进行比较，所以，放入容器的对象所属的类，还应该实现== 和 <运算符。



顺序容器简介:
1) vector 头文件 <vector>
实际上就是个动态数组。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。
2) deque 头文件 <deque>
也是个动态数组，随机存取任何元素都能在常数时间完成(但性能次于vector)。在两端增删元素具有较佳的性能。
3) list 头文件 <list>
双向链表，在任何位置增删元素都能在常数时间完成。不支持随机存取。
上述三种容器称为顺序容器，是因为元素的插入位置同元素的值无关。



关联容器简介:
 关联式容器内的元素是排序的，插入任何元素，都按相应的排序准则来确定其位置。关联式容器的特点是在查找时具有非常好的性能。
1) set/multiset: 头文件<set>
set 即集合。 set中不允许相同元素，multiset中允许存在相同的元素。
2) map/multimap: 头文件<map>
map与set的不同在于map中存放的是成对的key/value。并根据key对元素进行排序，可快速地根据key来检索元素map同multimap的不同在于是否允许多个元素有相同的
key值。
上述4种容器通常以平衡二叉树方式实现，插入和检索的时间都是O(logN)



容器适配器简介:
1) stack :头文件 <stack>
栈。是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入序列的项。即按照后进先出的原则
2) queue :头文件 <queue>
队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。按照先进先出的原则。
3） priority_queue :头文件<queue>
优先级队列。最高优先级元素总是第一个出列容器的共有成员函数
1) 所有标准库容器共有的成员函数：
 相当于按词典顺序比较两个容器大小的运算符：=, < , <= , > , >=, == , !=
 empty : 判断容器中是否有元素
 max_size: 容器中最多能装多少元素
 size: 容器中元素个数
 swap: 交换两个容器的内容

比较两个容器的例子：
#include <vector>
#include <iostream>
int main()
{
std::vector<int> v1;
std::vector<int> v2;
v1.push_back (5);
v1.push_back (1);
v2.push_back (1);
v2.push_back (2);
v2.push_back (3);
std::cout << (v1 < v2);
return 0;
}

输出： 0
•若两容器长度相同、所有元素相等，则两个容器就相等，否则为不等。
•若两容器长度不同，但较短容器中所有元素都等于较长容器中对应的元素，则较短容器小于另一个容器
•若两个容器均不是对方的子序列，则取决于所比较的第一个不等的元素容器的成员函数
2) 只在第一类容器中的函数：
begin 返回指向容器中第一个元素的迭代器
end 返回指向容器中最后一个元素后面的位置的迭代器
rbegin 返回指向容器中最后一个元素的迭代器
rend 返回指向容器中第一个元素前面的位置的迭代器（反向迭代器）
erase 从容器中删除一个或几个元素
clear 从容器中删除所有元素

迭代器:
 用于指向第一类容器中的元素。有const和非const两种。
 通过迭代器可以读取它指向的元素，通过非const迭代器还能修改其指向的元素。迭代器用法和指针类似。
 定义一个容器类的迭代器的方法可以是：
容器类名::iterator 变量名;
或：
容器类名::const_iterator变量名;
 访问一个迭代器指向的元素：
* 迭代器变量名
 迭代器上可以执行 ++ 操作,以指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面，则迭代器变成past-the-end值。
 使用一个past-the-end值的迭代器来访问对象是非法的，就好像使用NULL或未初始化的指针一样。
例如：
#include <vector>
#include <iostream>
using namespace std;
int main() {
vector<int> v; //一个存放int元素的向量，一开始里面没有元素
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
vector<int>::const_iterator i; //常量迭代器
for( i = v.begin();i != v.end();i ++ )
cout << * i << ",";
cout << endl;
vector<int>::reverse_iterator r; //反向迭代器
for( r = v.rbegin();r != v.rend();r++ )
cout << * r << ",";
cout << endl;
vector<int>::iterator j; //非常量迭代器
for( j = v.begin();j != v.end();j ++ )
* j = 100;
for( i = v.begin();i != v.end();i++ )
cout << * i << ",";
}
输出结果：
1,2,3,4,
4,3,2,1,
100,100,100,100,

 不同容器上支持的迭代器功能强弱有所不同。
 容器的迭代器的功能强弱，决定了该容器是否支持STL中的某种算法。
 例1：只有第一类容器能用迭代器遍历。
 例2：排序算法需要通过随机迭代器来访问容器中的元素，那么有的容器就不支持排序算法。
STL 中的迭代器
 STL 中的迭代器按功能由弱到强分为5种：
1. 输入： Input iterators提供对数据的只读访问。
1. 输出： Output iterators提供对数据的只写访问
2. 正向： Forward iterators提供读写操作，并能一次一个地向前推进迭代器。
3. 双向： Bidirectional iterators提供读写操作，并能一次一个地向前和向后移动。
4. 随机访问： Random access iterators提供读写操作，并能在数据中随机移动。
 编号大的迭代器拥有编号小的迭代器的所有功能，能当作编号小的迭代器使用。不同迭代器所能进行的操作(功能）
 所有迭代器： ++p, p ++
 输入迭代器： * p, p = p1, p == p1 , p!= p1
 输出迭代器： * p, p = p1
 正向迭代器： 上面全部
 双向迭代器： 上面全部， --p, p --,
 随机访问迭代器： 上面全部，以及：
 p+= i, p -= i,
 p + i： 返回指向p 后面的第i个元素的迭代器
 p - i： 返回指向p 前面的第i个元素的迭代器
 p[i]: p 后面的第i个元素的引用
 p < p1, p <= p1, p > p1, p>= p1
容器所支持的迭代器类别
容器        迭代器类别
vector        随机
deque        随机
list        双向
set/multiset        双向
map/multimap        双向
stack        不支持迭代器
queue        不支持迭代器
priority_queue        不支持迭代器


例如， vector的迭代器是随机迭代器，所以遍历vector 可以有以下
几种做法：
vector<int> v(100);
vector<int>::value_type i; //等效于写 int i;(P687)
for(i = 0;i < v.size() ; i ++)
cout << v[i];
vector<int>::const_iterator ii;
for( ii = v.begin(); ii != v.end ();ii ++ )
cout << * ii;
//间隔一个输出：
ii = v.begin();
while( ii < v.end()) {
cout << * ii;
ii = ii + 2;
}


而 list 的迭代器是双向迭代器，所以以下代码可以：
list<int> v;
list<int>::const_iterator ii;
for( ii = v.begin(); ii ！＝v.end ();ii ++ )
cout << * ii;
以下代码则不行：
for( ii = v.begin(); ii <v.end ();ii ++ )
cout << * ii;
//双向迭代器不支持 <
for(int i = 0;i < v.size() ; i ++)
cout << v[i];//双向迭代器不支持 []



算法简介：

 STL中提供能在各种容器中通用的算法，比如插入，删除，查找，排序等。大约有70种标准算法。
 算法就是一个个函数模板。
 算法通过迭代器来操纵容器中的元素。许多算法需要两个参数，一个是起始元素的迭代器，一个是终止元素的后面一个元素的迭代器。比如，排序和查找
 有的算法返回一个迭代器。比如 find() 算法，在容器中查找一个元素，并返回一个指向该元素的迭代器。
 算法可以处理容器，也可以处理C语言的数组



算法分类:

 变化序列算法
 copy ,remove,fill,replace,random_shuffle,swap, …..
 会改变容器
 非变化序列算法：
 adjacent-find, equal, mismatch,find ,count, search,count_if, for_each, search_n
 以上函数模板都在<algorithm>中定义
 此外还有其他算法，比如<numeric>中的算法



算法示例： find()
template<class InIt, class T>
InIt find(InIt first, InIt last, const T& val);
 first 和last 这两个参数都是容器的迭代器，它们给出了容器中的查找区间起点和终点。
 这个区间是个左闭右开的区间，即区间的起点是位于查找范围之中的，而终点不是
 val参数是要查找的元素的值
 函数返回值是一个迭代器。如果找到，则该迭代器指向被找到的元素。如果找不到，则该迭代器指向查找区间终点。
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
main() {
int array[10] = {10,20,30,40};
vector<int> v;
v.push_back(1);        v.push_back(2);
v.push_back(3);        v.push_back(4);

vector<int>::iterator p;
p = find(v.begin(),v.end(),3);
if( p != v.end())
cout << * p << endl;
p = find(v.begin(),v.end(),9);
if( p == v.end())
cout << "not found " << endl;
p = find(v.begin()+1,v.end()-2,1);
if( p != v.end())
cout << * p << endl;
int * pp = find( array,array+4,20);
cout << * pp << endl;
}


输出：
3
not found
3
20



顺序容器：
 除前述共同操作外，顺序容器还有以下共同操作：
 front() :返回容器中第一个元素的引用
 back() : 返回容器中最后一个元素的引用
 push_back(): 在容器末尾增加新元素
 pop_back(): 删除容器末尾的元素
 比如，查 list::front的help,得到的定义是：
 reference front();
 const_reference front() const;
 list有两个front函数

 reference和const_reference 是typedef的类型
 对于 list<double> ,
 list<double>::reference实际上就是 double &
 list<double>::const_reference实际上就是 const double &
 对于 list<int> ,
 list<int>::refrence实际上就是 int &
 list<int>::const_refreence实际上就是 const int & vector
 支持随机访问迭代器，所有STL算法都能对vector操作。
 随机访问时间为常数。在尾部添加速度很快，在中间插入慢。实际上就是动态数组。
例1：
int main()
{ int i;
int a[5] = {1,2,3,4,5 }; vector<int> v(5);
cout << v.end() - v.begin() << endl;
for( i = 0;i < v.size();i ++ ) v[i] = i;
v.at(4) = 100;//v.at(n)和v[n]是一样的，只不过前者会检查是否越界
for( i = 0;i < v.size();i ++ )
cout << v[i] << "," ;
cout << endl; // v2的size为5， v2被初始化为a的5个值
vector<int> v2(a,a+5); //后一个指针要指向将被拷贝的末元素的下一位置
v2.insert( v2.begin() + 2, 13 ); //在begin()+2位置插入 13
for( i = 0;i < v2.size();i ++ )
cout << v2[i] << "," ;
return 0;
}


输出：
5
0,1,2,3,100,
1,2,13,3,4,5,
例2：

int main()
{ const int SIZE = 5;
int a[SIZE] = {1,2,3,4,5 };
vector<int> v (a,a+5);
try
{
{ const int SIZE = 5;
int a[SIZE] = {1,2,3,4,5 };
vector<int> v (a,a+5);
try
{
v.at(100) = 7;
}
catch( out_of_range e) //异常处理
{
cout << e.what() << endl;
}
cout << v.front() << “,” << v.back() << endl;
v.erase(v.begin());
ostream_iterator<int> output(cout ,“*");
copy (v.begin(),v.end(),output);
v.erase( v.begin(),v.end()); //等效于 v.clear();
if( v.empty ())
cout << "empty" << endl;
v.insert (v.begin(),a,a+SIZE);
copy (v.begin(),v.end(),output);
}


// 输出：
invalid vector<T> subscript
1,5
2*3*4*5*empty
1*2*3*4*5*



算法解释：
 ostream_iterator<int> output(cout ,“*");
 定义了一个 ostream_iterator对象，可以通过cout输出以* 分隔的一个个整数
 copy (v.begin(),v.end(),output);
 导致v的内容在cout上输出
 copy 函数模板(算法）：
template<class InIt, class OutIt>
OutIt copy(InIt first, InIt last, OutIt x);
 本函数对每个在区间[0, last - first)中的N执行一次*(x+N) = *( first + N) ，返回x + N
 对于copy (v.begin(),v.end(),output);
 first 和last 的类型是 vector<int>::const_iterator
 output 的类型是ostream_iterator<int>



关于 ostream_iterator, istream_iterator的例子:

int main() {
istream_iterator<int> inputInt(cin);
int n1,n2;
n1 = * inputInt; //读入 n1
inputInt ++;
n2 = * inputInt; //读入 n2
cout << n1 << "," << n2 << endl;
ostream_iterator<int>> outputInt(cout);
* outputInt = n1 + n2; cout << endl;
int a[5] = { 1,2,3,4,5};
copy(a,a+5,outputInt); //输出整个数组
return 0;
}


程序运行后输入 78 90敲回车，则输出结果为：
78,90
168
12345



list 容器
 在任何位置插入删除都是常数时间，不支持随机存取。除了具有所有顺序容器都有的成员函数以外，还支持8个成员函数：
 push_front: 在前面插入
 pop_front: 删除前面的元素
 sort: 排序( list不支持STL 的算法sort)
 remove: 删除和指定值相等的所有元素
 unique: 删除所有和前一个元素相同的元素
 merge: 合并两个链表，并清空被合并的那个
 reverse: 颠倒链表
 splice: 在指定位置前面插入另一链表中的一个或多个元素,并在另一链表中删除被插入的元素



deque 容器:
 所有适用于vector的操作都适用于deque
 deque还有push_front（将元素插入到前面）和
pop_front(删除最前面的元素）操作

关联容器:
 set, multiset, map, multimap
 内部元素有序排列，新元素插入的位置取决于它的值，查找速度快
 map关联数组：元素通过键来存储和读取
 set大小可变的集合，支持通过键实现的快速读取
 multimap支持同一个键多次出现的map类型
 multiset支持同一个键多次出现的set类型
 与顺序容器的本质区别
 关联容器是通过键(key)存储和读取元素的
 而顺序容器则通过元素在容器中的位置顺序存储和访问元素。

关联容器:
 除了各容器都有的函数外，还支持以下成员函数：设m表容器，k表键值
 m.find(k) ：如果容器中存在键为k的元素，则返回指向该元素的迭代器。如果不存在，则返回end()值。
 m.lower_bound(k)：返回一个迭代器，指向键不小于k的第一个元素
 m.upper_bound(k)：返回一个迭代器，指向键大于k的第一个元素
 m.count(k) ：返回m中k的出现次数
 插入元素用 insert

set:
template<class Key, class Pred = less<Key>,class A =allocator<Key> >
class set { … }
插入set中已有的元素时，插入不成功。

pair模板:
 pair模板类用来绑定两个对象为一个新的对象，该类型在<utility>头文件中定义。
 pair模板类支持如下操作：
 pair<T1, T2> p1：创建一个空的pair对象，它的两个元素分别是T1和T2类型，采用值初始化
 pair<T1, T2> p1(v1, v2)：创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2
 make_pair(v1, v2)：以v1和v2值创建一个新的pair对象，其元素类型分别是v1和v2的类型
 p1 < p2字典次序：如果p1.first<p2.first或者!(p2.first <p1.first)&& p1.second<p2.second，则返回true
 p1 == p2：如果两个pair对象的first和second成员依次相等，则这两个对象相等。
 p.first：返回p中名为first的（公有）数据成员
 p.second：返回p中名为second的（公有）数据成员
#include <set>
#include <iostream>
using namespace std;
int main()
{
typedef set<double,less<double> > double_set;
const int SIZE = 5;
double a[SIZE] = {2.1,4.2,9.5,2.1,3.7 };
double_set doubleSet(a,a+SIZE);
ostream_iterator<double> output(cout," ");
cout << "1) ";
copy(doubleSet.begin(),doubleSet.end(),output);
cout << endl;
pair<double_set::const_iterator, bool> p;
p = doubleSet.insert(9.5);
if( p.second )
cout << "2) " << * (p.first) << " inserted" << endl;
else
cout << "2) " << * (p.first) << " not inserted" << endl;
return 0; //insert函数返回值是一个pair对象，其first实被插入元素的迭代器， second代
表是否成功插入了
}


输出：
1) 2.1 3.7 4.2 9.5
2) 9.5 not inserted
54



multimap:
template<class Key, class T, class Pred = less<Key>, class A =allocator<T> >
class multimap {
….
typedef pair<const Key, T> value_type;
…….
}; //Key 代表关键字
 multimap中的元素由<关键字,值>组成，每个元素是一个pair对象。multimap 中允许多个元素的关键字相同。元素按照关键字升序排列，缺省情况下用less<Key> 定
义关键字的“小于”关系

map:
template<class Key, class T, class Pred = less<Key>,
class A = allocator<T> >
class map {
….
typedef pair<const Key, T> value_type;
…….
};
 map 中的元素关键字各不相同。元素按照关键字升序排列，缺省情况下用less 定义“小于”

map:
 可以用pairs[key]访形式问map中的元素。
 pairs 为map容器名，key为关键字的值。
 该表达式返回的是对关键值为key的元素的值的引用。
 如果没有关键字为key的元素，则会往pairs里插入一个关键字为key的元素，并返回其值的引用
 如：

map<int,double> pairs;

则 pairs[50] = 5; 会修改pairs中关键字为50的元素，使其值变成5
#include <iostream>
#include <map>
using namespace std;
ostream & operator <<( ostream & o,const pair< int,double> & p)
{
o << "(" << p.first << "," << p.second << ")";
return o;
}
int main() {
typedef map<int,double,less<int> > mmid;
mmid pairs;
cout << "1) " << pairs.count(15) << endl;
pairs.insert(mmid::value_type(15,2.7));
pairs.insert(make_pair(15,99.3));//make_pair生成pair对象
cout << "2) " << pairs.count(15) << endl;
pairs.insert(mmid::value_type(20,9.3));
mmid::iterator i;
cout << "3) ";
for( i = pairs.begin(); i != pairs.end();i ++ )
cout << * i << ",";
cout << endl;
cout << "4) ";
int n = pairs[40];//如果没有关键字为40的元素，则插入一个
for( i = pairs.begin(); i != pairs.end();i ++ )
cout << * i << ",";
cout << endl;
cout << "5) ";
pairs[15] = 6.28; //把关键字为15的元素值改成6.28
for( i = pairs.begin(); i != pairs.end();i ++ )
cout << * i << ",";
return 0;
}


输出：
1) 0
2) 1
3) (15,2.7),(20,9.3),
4) (15,2.7),(20,9.3),(40,0),
5) (15,6.28),(20,9.3),(40,0),

思考题:
 如何用程序用来统计一篇英文文章中单词出现的频率（为简单起见，假定依次从键盘输入该文章）
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<string, int> wordCount;
string word;
while (cin >> word)
++wordCount[word];
for (map<string, int>::iterator it = wordCount.begin(); it !=
wordCount.end(); ++it)
cout<<"Word: "<<(*it).first<<" \tCount: "<<(*it).second<<endl;
return 0;
}


容器适配器:stack:
 可用 vector, list, deque来实现
 缺省情况下，用deque实现
 用 vector和deque实现，比用list实现性能好


template<class T, class Cont = deque<T> >

class stack {
…..
};
 stack 是后进先出的数据结构，只能插入、删除、访问栈顶的元素

容器适配器:stack
 stack 上可以进行以下操作：
 push: 插入元素
 pop: 弹出元素
 top: 返回栈顶元素的引用

容器适配器: queue
 和stack基本类似，可以用 list和deque实现，缺省情况下用deque实现
template<class T, class Cont = deque<T> >
class queue {
……
};
 同样也有push,pop,top函数
 但是push发生在队尾，pop,top发生在队头，先进先出

容器适配器: priority_queue
 和 queue类似，可以用vector和deque实现，缺省情况下用vector实现。
 priority_queue 通常用堆排序技术实现，保证最大的元素总是在最前面。即执行pop操作时，删除的是最大的元素，执行top操作时，返回的是最大元素的引用。默认的元素比较器是less<T>
#include <queue>
#include <iostream>
using namespace std;
int main() {
priority_queue<double> priorities;
priorities.push(3.2);
priorities.push(9.8);
priorities.push(5.4);
while( !priorities.empty() ) {
cout << priorities.top() << " "; priorities.pop();
}
return 0;
}


//输出结果： 9.8 5.4 3.2

排序和查找算法:
 Sort
template<class RanIt>
void sort(RanIt first, RanIt last);
 find
template<class InIt, class T>
InIt find(InIt first, InIt last, const T& val);
 binary_search 折半查找，要求容器已经有序
template<class FwdIt, class T>
bool binary_search(FwdIt first, FwdIt last, const T& val);


int main() {
const int SIZE = 10;
int a1[] = { 2,8,1,50,3,100,8,9,10,2 };
vector<int> v(a1,a1+SIZE);
ostream_iterator<int> output(cout," ");
vector<int>::iterator location;
location = find(v.begin(),v.end(),10);
if( location != v.end())
{
cout << endl << "1) " << location - v.begin();
}
sort(v.begin(),v.end());
if( binary_search(v.begin(),v.end(),9))
cout << endl << "3) " << "9 found";
else
cout << endl << " 3) " << " 9 not found";
return 0;
}


输出： (无sort语句)
1) 8
2) 3
3) 9 not found
输出： (有sort语句)
1) 8
2) 3
3) 9 found
69
sort
 sort 实际上是快速排序，时间复杂度O(n*log(n));
 平均性能最优。但是最坏的情况下，性能可能非常差。如果要保证“最坏情况下”的性能，那么可以使用stable_sort
 stable_sort
 stable_sort 实际上是归并排序（ 将两个已经排序的序列合并成一个序列），特点是能保持相等元素之间的先后次序
 在有足够存储空间的情况下，复杂度为n * log(n)，否则复杂度为n * log(n) * log(n)
 stable_sort 用法和 sort相同
 排序算法要求随机存取迭代器的支持，所以list不能使用排序算法，要使用list::sort

sort:
 partial_sort : 部分排序，直到 前 n 个元素就位即可
 nth_element : 排序，直到第 n个元素就位，并保证比第n个元素小的元素都在第n 个元素之前即可
 partition: 改变元素次序，使符合某准则的元素放在前面
 …


小结

 C++模板
 函数模板
 STL库
 各种容器
 迭代器
 算法

---

作者: admin    时间: 2018-8-11 09:50
1.1 什么是STL？
STL（Standard Template Library），即标准模板库，是一个具有工业强度的，高效的C++程序库。它被容纳于C++标准程序库（C++ Standard Library）中，是ANSI/ISO C++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。
STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念，但这种分离确实使得STL变得非常通用。例如，由于STL的sort()函数是完全通用的，你可以用它来操作几乎任何数据集合，包括链表，容器和数组；
STL另一个重要特性是它不是面向对象的。为了具有足够通用性，STL主要依赖于模板而不是封装，继承和虚函数（多态性）——OOP的三个要素。你在STL中找不到任何明显的类继承关系。这好像是一种倒退，但这正好是使得STL的组件具有广泛通用性的底层特征。另外，由于STL是基于模板，内联函数的使用使得生成的代码短小高效；
从逻辑层次来看，在STL中体现了泛型化程序设计的思想，引入了诸多新的名词，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。与OOP（object-oriented programming）中的多态（polymorphism）一样，泛型也是一种软件的复用技术；从实现层次看，整个STL是以一种类型参数化的方式实现的，这种方式基于一个在早先C++标准中没有出现的语言特性--模板（template）。
1.2 STL内容介绍
STL中六大组件：
1）容器（Container），是一种数据结构，如list，vector，和deques ，以模板类的方法提供。为了访问容器中的数据，可以使用由容器类输出的迭代器；
2）迭代器（Iterator），提供了访问容器中对象的方法。例如，可以使用一对迭代器指定list或vector中的一定范围的对象。迭代器就如同一个指针。事实上，C++的指针也是一种迭代器。但是，迭代器也可以是那些定义了operator*()以及其他类似于指针的操作符地方法的类对象；
3）算法（Algorithm），是用来操作容器中的数据的模板函数。例如，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象，函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用；
4）仿函数（Function object）
5）迭代适配器（Adaptor）
6）空间配制器（allocator）
下面我将依次介绍STL的这三个主要组件。
1.2.1 容器
STL中的容器有队列容器和关联容器，容器适配器（congtainer adapters：stack,queue，priority queue），位集（bit_set），串包(string_package)等等。
　　（1）序列式容器（Sequence containers），每个元素都有固定位置－－取决于插入时机和地点，和元素值无关，vector、deque、list；
Vectors：将元素置于一个动态数组中加以管理，可以随机存取元素（用索引直接存取），数组尾部添加或移除元素非常快速。但是在中部或头部安插元素比较费时；
Deques：是“double-ended queue”的缩写，可以随机存取元素（用索引直接存取），数组头部和尾部添加或移除元素都非常快速。但是在中部或头部安插元素比较费时；
Lists：双向链表，不提供随机存取（按顺序走到需存取的元素，O(n)），在任何位置上执行插入或删除动作都非常迅速，内部只需调整一下指针；
（2）关联式容器（Associated containers），元素位置取决于特定的排序准则，和插入顺序无关，set、multiset、map、multimap；
Sets/Multisets：内部的元素依据其值自动排序，Set内的相同数值的元素只能出现一次，Multisets内可包含多个数值相同的元素，内部由二叉树实现，便于查找；
Maps/Multimaps：Map的元素是成对的键值/实值，内部的元素依据其值自动排序，Map内的相同数值的元素只能出现一次，Multimaps内可包含多个数值相同的元素，内部由二叉树实现，便于查找；
容器类自动申请和释放内存，无需new和delete操作。vector基于模板实现，需包含头文件vector。


//1.定义和初始化
    vector<int> vec1;    //默认初始化，vec1为空
    vector<int> vec2(vec1);  //使用vec1初始化vec2
    vector<int> vec3(vec1.begin(),vec1.end());//使用vec1初始化vec2
    vector<int> vec4(10);    //10个值为的元素
    vector<int> vec5(10,4);  //10个值为的元素
//2.常用操作方法
    vec1.push_back(100);            //添加元素
    int size = vec1.size();         //元素个数
    bool isEmpty = vec1.empty();    //判断是否为空
    cout<<vec1[0]<<endl;        //取得第一个元素
    vec1.insert(vec1.end(),5,3);    //从vec1.back位置插入个值为的元素
    vec1.pop_back();              //删除末尾元素
    vec1.erase(vec1.begin(),vec1.end());//删除之间的元素，其他元素前移
    cout<<(vec1==vec2)?true:false;  //判断是否相等==、！=、>=、<=...
    vector<int>::iterator iter = vec1.begin();    //获取迭代器首地址
    vec1.clear();                 //清空元素
//3.遍历
    //下标法
    int length = vec1.size();
    for(int i=0;i<length;i++)
    {
       cout<<vec1;
    }
    cout<<endl<<endl;
    //迭代器法
    vector<int>::const_iterator iterator = vec1.begin();
    for(;iterator != vec1.end();iterator++)
    {
       cout<<*iterator;
    }
1.2.2.STL迭代器
Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。

迭代器的作用：能够让迭代器与算法不干扰的相互发展，最后又能无间隙的粘合起来，重载了*，＋＋，＝＝，！＝，＝运算符。用以操作复杂的数据结构，容器提供迭代器，算法使用迭代器；常见的一些迭代器类型：iterator、const_iterator、reverse_iterator和const_reverse_iterator,实例如下：


#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> v;
    v.push_back(3);  //数组尾部插入3
    v.push_back(2);
    v.push_back(1);
    v.push_back(0);
    cout << " 下标 " << v[3] << endl;
    cout << " 迭代器 " << endl;
    for(vector<int>::iterator i = v.begin();i!= v.end();++i)
    {
        cout << *i << " ";
    }
    cout << endl;
    //在第一个元素之前插入111  insert begin+n是在第n个元素之前插入
    v.insert(v.begin(),111);
    //在最后一个元素之后插入222 insert end + n 是在n个元素之后插入
    v.insert(v.end(),222);
    for(vector<int>::iterator i = v.begin();i!= v.end();++i)
    {
        cout << *i << " ";
    }
    cout << endl;

    vector<int> arr(10);
    for(int i = 0; i < 10; i++)
    {
        arr = i;
    }
    for(vector<int>::iterator i = arr.begin();i!= arr.end();++i)
    {
        cout << *i << " ";
    }
    cout << endl;
    //删除 同insert
    arr.erase(arr.begin());
    for(vector<int>::iterator i = arr.begin();i!= arr.end();++i)
     {
        cout << *i << " " ;
     }
    cout << endl ;
    arr.erase(arr.begin(),arr.begin()+5);
    for(vector<int>::iterator i = arr.begin();i!= arr.end();++i)
    {
        cout << *i << " " ;
    }
    cout << endl ;
    return 0 ;
}
运行结果：

实例2：数组转置 (<algorithm> reverse)
     reverse(v.begin(),v.end())
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    vector<int> v;
    for(int i = 0; i < 10; ++i)
    {
        v.push_back(i);
    }
    for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
    reverse(v.begin(),v.end());
    for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
    return 0;
}
运行结果：

1.2.3、算法
函数库对数据类型的选择对其可重用性起着至关重要的作用。举例来说，一个求方根的函数，在使用浮点数作为其参数类型的情况下的可重用性肯定比使用整型作为它的参数类性要高。而C++通过模板的机制允许推迟对某些类型的选择，直到真正想使用模板或者说对模板进行特化的时候，STL就利用了这一点提供了相当多的有用算法。它是在一个有效的框架中完成这些算法的——你可以将所有的类型划分为少数的几类，然后就可以在模版的参数中使用一种类型替换掉同一种类中的其他类型。
STL提供了大约100个实现算法的模版函数，比如算法for_each将为指定序列中的每一个元素调用指定的函数，stable_sort以你所指定的规则对序列进行稳定性排序等等。只要我们熟悉了STL之后，许多代码可以被大大的化简，只需要通过调用一两个算法模板，就可以完成所需要的功能并大大地提升效率。
算法部分主要由头文件<algorithm>，<numeric>和<functional>组成。
<algorithm>是所有STL头文件中最大的一个（尽管它很好理解），它是由一大堆模版函数组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。
<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。
<functional>中则定义了一些模板类，用以声明函数对象。
STL中算法大致分为四类：
1）非可变序列算法：指不直接修改其所操作的容器内容的算法。
2）可变序列算法：指可以修改它们所操作的容器内容的算法。
3）排序算法：对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
4）数值算法：对容器内容进行数值计算。
以下对所有算法进行细致分类并标明功能：
<一>查找算法(13个)：判断容器中是否包含某个值
adjacent_find: 在iterator对标识元素范围内，查找一对相邻重复元素，找到则返回指向这对元素的第一个元素的ForwardIterator。否则返回last。重载版本使用输入的二元操作符代替相等的判断。
binary_search: 在有序序列中查找value，找到返回true。重载的版本实用指定的比较函数对象或函数指针来判断相等。
count: 利用等于操作符，把标志范围内的元素与输入值比较，返回相等元素个数。
count_if: 利用输入的操作符，对标志范围内的元素进行操作，返回结果为true的个数。
equal_range: 功能类似equal，返回一对iterator，第一个表示lower_bound，第二个表示upper_bound。
find: 利用底层元素的等于操作符，对指定范围内的元素与输入值进行比较。当匹配时，结束搜索，返回该元素的一个InputIterator。
find_end: 在指定范围内查找"由输入的另外一对iterator标志的第二个序列"的最后一次出现。找到则返回最后一对的第一个ForwardIterator，否则返回输入的"另外一对"的第一个ForwardIterator。重载版本使用用户输入的操作符代替等于操作。
find_first_of: 在指定范围内查找"由输入的另外一对iterator标志的第二个序列"中任意一个元素的第一次出现。重载版本中使用了用户自定义操作符。
find_if: 使用输入的函数代替等于操作符执行find。
lower_bound: 返回一个ForwardIterator，指向在有序序列范围内的可以插入指定值而不破坏容器顺序的第一个位置。重载函数使用自定义比较操作。
upper_bound: 返回一个ForwardIterator，指向在有序序列范围内插入value而不破坏容器顺序的最后一个位置，该位置标志一个大于value的值。重载函数使用自定义比较操作。
search: 给出两个范围，返回一个ForwardIterator，查找成功指向第一个范围内第一次出现子序列(第二个范围)的位置，查找失败指向last1。重载版本使用自定义的比较操作。
search_n: 在指定范围内查找val出现n次的子序列。重载版本使用自定义的比较操作。
<二>排序和通用算法(14个)：提供元素排序策略
inplace_merge: 合并两个有序序列，结果序列覆盖两端范围。重载版本使用输入的操作进行排序。
merge: 合并两个有序序列，存放到另一个序列。重载版本使用自定义的比较。
nth_element: 将范围内的序列重新排序，使所有小于第n个元素的元素都出现在它前面，而大于它的都出现在后面。重载版本使用自定义的比较操作。
partial_sort: 对序列做部分排序，被排序元素个数正好可以被放到范围内。重载版本使用自定义的比较操作。
partial_sort_copy: 与partial_sort类似，不过将经过排序的序列复制到另一个容器。
partition: 对指定范围内元素重新排序，使用输入的函数，把结果为true的元素放在结果为false的元素之前。
random_shuffle: 对指定范围内的元素随机调整次序。重载版本输入一个随机数产生操作。
reverse: 将指定范围内元素重新反序排序。
reverse_copy: 与reverse类似，不过将结果写入另一个容器。
rotate: 将指定范围内元素移到容器末尾，由middle指向的元素成为容器第一个元素。
rotate_copy: 与rotate类似，不过将结果写入另一个容器。
sort: 以升序重新排列指定范围内的元素。重载版本使用自定义的比较操作。
stable_sort: 与sort类似，不过保留相等元素之间的顺序关系。
stable_partition: 与partition类似，不过不保证保留容器中的相对顺序。
<三>删除和替换算法(15个)
copy: 复制序列
copy_backward: 与copy相同，不过元素是以相反顺序被拷贝。
iter_swap: 交换两个ForwardIterator的值。
remove: 删除指定范围内所有等于指定元素的元素。注意，该函数不是真正删除函数。内置函数不适合使用remove和remove_if函数。
remove_copy: 将所有不匹配元素复制到一个制定容器，返回OutputIterator指向被拷贝的末元素的下一个位置。
remove_if: 删除指定范围内输入操作结果为true的所有元素。
remove_copy_if: 将所有不匹配元素拷贝到一个指定容器。
replace: 将指定范围内所有等于vold的元素都用vnew代替。
replace_copy: 与replace类似，不过将结果写入另一个容器。
replace_if: 将指定范围内所有操作结果为true的元素用新值代替。
replace_copy_if: 与replace_if，不过将结果写入另一个容器。
swap: 交换存储在两个对象中的值。
swap_range: 将指定范围内的元素与另一个序列元素值进行交换。
unique: 清除序列中重复元素，和remove类似，它也不能真正删除元素。重载版本使用自定义比较操作。
unique_copy: 与unique类似，不过把结果输出到另一个容器。
<四>排列组合算法(2个)：提供计算给定集合按一定顺序的所有可能排列组合
next_permutation: 取出当前范围内的排列，并重新排序为下一个排列。重载版本使用自定义的比较操作。
prev_permutation: 取出指定范围内的序列并将它重新排序为上一个序列。如果不存在上一个序列则返回false。重载版本使用自定义的比较操作。
<五>算术算法(4个)
accumulate: iterator对标识的序列段元素之和，加到一个由val指定的初始值上。重载版本不再做加法，而是传进来的二元操作符被应用到元素上。
partial_sum: 创建一个新序列，其中每个元素值代表指定范围内该位置前所有元素之和。重载版本使用自定义操作代替加法。
inner_product: 对两个序列做内积(对应元素相乘，再求和)并将内积加到一个输入的初始值上。重载版本使用用户定义的操作。
adjacent_difference: 创建一个新序列，新序列中每个新值代表当前元素与上一个元素的差。重载版本用指定二元操作计算相邻元素的差。
<六>生成和异变算法(6个)
fill: 将输入值赋给标志范围内的所有元素。
fill_n: 将输入值赋给first到first+n范围内的所有元素。
for_each: 用指定函数依次对指定范围内所有元素进行迭代访问，返回所指定的函数类型。该函数不得修改序列中的元素。
generate: 连续调用输入的函数来填充指定的范围。
generate_n: 与generate函数类似，填充从指定iterator开始的n个元素。
transform: 将输入的操作作用与指定范围内的每个元素，并产生一个新的序列。重载版本将操作作用在一对元素上，另外一个元素来自输入的另外一个序列。结果输出到指定容器。
<七>关系算法(8个)
equal: 如果两个序列在标志范围内元素都相等，返回true。重载版本使用输入的操作符代替默认的等于操作符。
includes: 判断第一个指定范围内的所有元素是否都被第二个范围包含，使用底层元素的<操作符，成功返回true。重载版本使用用户输入的函数。
lexicographical_compare: 比较两个序列。重载版本使用用户自定义比较操作。
max: 返回两个元素中较大一个。重载版本使用自定义比较操作。
max_element: 返回一个ForwardIterator，指出序列中最大的元素。重载版本使用自定义比较操作。
min: 返回两个元素中较小一个。重载版本使用自定义比较操作。
min_element: 返回一个ForwardIterator，指出序列中最小的元素。重载版本使用自定义比较操作。
mismatch: 并行比较两个序列，指出第一个不匹配的位置，返回一对iterator，标志第一个不匹配元素位置。如果都匹配，返回每个容器的last。重载版本使用自定义的比较操作。
<八>集合算法(4个)
set_union: 构造一个有序序列，包含两个序列中所有的不重复元素。重载版本使用自定义的比较操作。
set_intersection: 构造一个有序序列，其中元素在两个序列中都存在。重载版本使用自定义的比较操作。
set_difference: 构造一个有序序列，该序列仅保留第一个序列中存在的而第二个中不存在的元素。重载版本使用自定义的比较操作。
set_symmetric_difference: 构造一个有序序列，该序列取两个序列的对称差集(并集-交集)。
<九>堆算法(4个)
make_heap: 把指定范围内的元素生成一个堆。重载版本使用自定义比较操作。
pop_heap: 并不真正把最大元素从堆中弹出，而是重新排序堆。它把first和last-1交换，然后重新生成一个堆。可使用容器的back来访问被"弹出"的元素或者使用pop_back进行真正的删除。重载版本使用自定义的比较操作。
push_heap: 假设first到last-1是一个有效堆，要被加入到堆的元素存放在位置last-1，重新生成堆。在指向该函数前，必须先把元素插入容器后。重载版本使用指定的比较操作。
sort_heap: 对指定范围内的序列重新排序，它假设该序列是个有序堆。重载版本使用自定义比较操作。
...
参考：
http://www.cnblogs.com/giszhang/archive/2010/02/02/1661844.html
http://blog.csdn.net/conanswp/article/details/23297441
http://www.cnblogs.com/biyeymyhj ... /07/22/2603525.html
http://blog.chinaunix.net/uid-24219701-id-2181266.html

---

作者: admin    时间: 2018-8-11 10:00
我们先来区分一下count, find, binary_search, lower_bound, upper_bound, equal_range.

count是简单地查找所有满足条件的元素。
find找到满足条件的元素，并返回它在哪里。
binary_search是返回元素在不在。
lower_bound是返回满足条件的第一个元素的位置。
upper_bound是返回满足条件的元素后的第一个元素的位置。
equal_range返回lower_bound和upper_bound。
需要注意的是，count和find都是使用相等性测试，而binary_search, lower_bound, upper_bound, equal_range都使用等价性测试！
这意味着在使用lower_bound时必须确保手工编的等价性测试代码和算法中使用的比较函数是相同的。

#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<int> v_i{1, 2, 3, 4, 2, 3, 4, 5, 1, 4};
    sort(v_i.begin(), v_i.end(), [](int i, int j) -> bool {
        return i < j;
    });
    copy(v_i.begin(), v_i.end(), ostream_iterator<int> (cout, " "));
    cout << endl;
    vector<int>::iterator iter = lower_bound(v_i.begin(), v_i.end(), 3, [](int i, int j = 3) -> bool {
        return i != j;
    });
    if (iter != v_i.end() && *iter == 3) { //  判断是否存在
        cout << *iter << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
使用equal_range也可以知道有多少个与之相等的值。通过区间的distance可以判读个数。

简单的总结就是：

这里写图片描述

需要注意的是：对于set和map而言，find并不是第一个满足条件的对象位置，而是其中的任意一个对象。

---

作者: admin    时间: 2018-8-11 10:11
对vector/string执行insert/erase操作后迭代器的情况说明
      在本文中，用字符c表示顺序容器vector和string。
      1.insert()操作
      常见用法：
      c.insert(p,t);     //在迭代器p指向的元素之前创建一个值为t的元素。返回指向新添加的元素的迭代器
      c.insert(p,n,t);  //在迭代器p指向的元素之前插入n个值为t的元素。返回指向新添加的第一个元素的迭代器，                                             //若n为0，则返回p
      c.insert(p,b,e); //将迭代器b和e指定的范围内的元素插入到迭代器p指向的元素之前。b和e不能指向c中的元素。                                     //返回指向新添加的第一个元素的迭代器；若范围为空，则返回p
      c.insert(p,i1);   //i1是一个花括号包围的元素值列表。将这些给定值插入到迭代器p指向的元素之前。返回指向新添加                               //的第一个元素的迭代器；若列表为空，则返回p
      注意：向一个vector、string或deque插入元素会使所有指向容器的迭代器、引用和指针失效！！！
      2.erase()操作
      常见用法：
      c.erase(p);       //删除迭代器p所指定的元素，返回一个指向被删元素之后元素的迭代器，若p指向尾元素，则返                                   //回尾后(off-the-end)迭代器。若p是尾后迭代器，则函数行为未定义
      c.erase(b,e);    //删除迭代器b和e所指定范围内的元素。返回一个指向最后一个被删元素之后的元素的迭代器，若                               //e本身就是尾后迭代器，则函数也返回尾后迭代器   

      c.clear();          //删除c中的所有元素，返回void

      注意：删除deque中除首尾位置之外的任何元素都会使所有的迭代器、引用和指针失效。指向vector或string中删除点之后位置的迭代器、引用和指针都会失效。

      3.容器操作可能使迭代器失效
      3.1向容器中添加元素
      对于vector和string，若存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。若存储空间未重新分配，指向插入位置之前的元素的迭代器、指针和引用仍有效，但指向插入位置之后元素的迭代器、指针和引用将会失效。
      3.2向容器中删除元素
      对于vector和string，指向被删元素之前元素的迭代器、引用和指针仍然有效。注意：当我们删除元素时，尾后迭代器总是失效的。
      4.编写改变容器的循环程序例子
      添加/删除vector，string或deque元素的循环程序必须考虑迭代器、引用和指针可能失效的问题。程序必须保证每个循环中都更新迭代器、引用和指针。如果循环中调用的是insert或erase，那么更新迭代器很容易。这些操作都返回迭代器。
      例1：编写改变容器的循环程序
vector<int> vi = {0,1,2,3,4,5,6,7,8,9};
auto iter = vi.begin();
while(iter!=vi.end()){
       if(*iter%2){
           iter=vi.insert(iter,*iter);//复制当前元素
           iter +=2;//向前移动迭代器，跳过当前元素以及插入到它之前的元素
       }else
           iter=vi.erase(iter);//删除偶元素
           //不应该向前移动迭代器，iter指向我们删除的元素之后的元素  
}
参考书籍：《C++ Primer》(第5版)

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2