STL

STL

STL（Standard Template Library，标准模板库)，它是由惠普实验室开发的一系列标准化的组件，目前是C++的一部分。

‚STL的代码从广义上讲分为三类：container（容器）、iterator（迭代器）和algorithm（算法），容器和算法通过迭代器可以进行无缝地连接。

ƒstring,wstring也是STL的一部分

使用STL的好处

STL是C++的一部分，因此不用额外安装什麽，它被内建在你的编译器之内。

STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念，但是这种分离确实使得STL变得非常通用。例如，STL的sort()函数可以用来操作vector,list等容器。

STL具有高可重用性，高性能，高移植性，跨平台的优点:

高可重用性：STL中几乎所有的代码都采用了模板类和模版函数的方式实现，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。关于模板的介绍，在第二讲会讲解。

高性能：如map可以高效地从十万条记录里面查找出指定的记录，因为map是采用红黑树的变体实现的。(红黑树是平横二叉树的一种)

高移植性：如在项目A上用STL编写的模块，可以直接移植到项目B上。

跨平台：如用windows的Visual Studio编写的代码可以在Mac OS的XCode上直接编译。

程序员可以不用思考STL具体的实现过程，只要能够熟练使用STL就OK了。这样他们就可以把精力放在程序开发的别的方面。

string讲解纲要

string是什么

string是STL的字符串类型，通常用来表示字符串。而在使用string之前，字符串通常是用char*表示的。

string与char*的比较

string不用考虑内存释放和越界。

string管理char*所分配的内存。每一次string的复制，取值都由string类负责维护，不用担心复制越界和取值越界等。

string支持运算。（这个等下会详细讲）

 如： string a; string b; a += b;

‚string提供了一系列的字符串操作函数（这个等下会详讲）

        查找find， 拷贝copy，删除erase

         替换replace，插入insert，等等

string使用之前的准备

#include

using namespace std;

string的构造函数

默认构造函数：

string(); //构造一个空的字符串string s1。

拷贝构造函数：

string(const string &str);//构造一个与str一样的string。如string s1(s2)。

带参数的构造函数

string(const char *s); //用字符串s初始化

string(int n,char c); //用n个字符c初始化

string的存取字符操作

string类的字符操作：

const char &operator[] (int n) const;

const char &at(int n) const;

char &operator[] (int n);

char &at(int n);

char c = strA[3];

char d = strA.at(5);

以上两句对应前两个方法

strA[3] = ‘X’;

strA.at(5) = ‘Y’;

以上两句对应后两个方法

operator[]和at()均返回当前字符串中第n个字符，但二者是有区别的。

主要区别在于at()在越界时会抛出异常，[]在刚好越界时会返回(char)0，再继续越界时，编译器直接出错。

如果你的程序希望可以通过try,catch捕获异常，建议采用at()。

从string取得const char*的操作

string类的字符操作：

const char *c_str() const; //返回一个以’\0’结尾的字符串

把string拷贝到char*指向的空间的操作

int copy(char *s, int n, int pos=0) const;

把当前串中以pos开始的n个字符拷贝到以s为起始位置的字符数组中，返回实际拷贝的数目。注意要保证s所指向的空间足够大以容纳当前字符串，不然会越界。

string的长度

int length() const; //返回当前字符串的长度。长度不包括字符串结尾的’\0’。

bool empty() const; //当前字符串是否为空

string的赋值

string &operator=(const string &s);//把字符串s赋给当前的字符串

string &assign(const char *s); //把字符串s赋给当前的字符串

string &assign(const char *s, int n); //把字符串s的前n个字符赋给当前的字符串

string &assign(const string &s); //把字符串s赋给当前字符串

string &assign(int n,char c); //用n个字符c赋给当前字符串

string &assign(const string &s,int start, int n); //把字符串s中从start开始的n个字符赋给当前字符串

string的连接

string &operator+=(const string &s); //把字符串s连接到当前字符串结尾

string &operator+=(const char *s);//把字符串s连接到当前字符串结尾

string &append(const char *s); //把字符串s连接到当前字符串结尾

string &append(const char *s,int n); //把字符串s的前n个字符连接到当前字符串结尾

string &append(const string &s); //同operator+=()

string &append(const string &s,int pos, int n);//把字符串s中从pos开始的n个字符连接到当前字符串结尾

string &append(int n, char c); //在当前字符串结尾添加n个字符c

string的比较

int compare(const string &s) const; //与字符串s比较

int compare(const char *s) const; //与字符串s比较

compare函数在>时返回 1，<时返回 -1，==时返回 0。比较区分大小写，比较时参考字典顺序，排越前面的越小。大写的A比小写的a小。

string的子串

string substr(int pos=0, int n=npos) const; //返回由pos开始的n个字符组成的子字符串

string的查找

int find(char c,int pos=0) const; //从pos开始查找字符c在当前字符串的位置

int find(const char *s, int pos=0) const; //从pos开始查找字符串s在当前字符串的位置

int find(const string &s, int pos=0) const; //从pos开始查找字符串s在当前字符串中的位置

find函数如果查找不到，就返回-1

int rfind(char c, int pos=npos) const; //从pos开始从后向前查找字符c在当前字符串中的位置

int rfind(const char *s, int pos=npos) const;

int rfind(const string &s, int pos=npos) const;

//rfind是反向查找的意思，如果查找不到， 返回-1

string的插入

string &insert(int pos, const char *s);

string &insert(int pos, const string &s);

//前两个函数在pos位置插入字符串s

string &insert(int pos, int n, char c); //在pos位置 插入n个字符c

string的删除

string &erase(int pos=0, int n=npos); //删除pos开始的n个字符，返回修改后的字符串

string的替换

string &replace(int pos, int n, const char *s);//删除从pos开始的n个字符，然后在pos处插入串s

string &replace(int pos, int n, const string &s); //删除从pos开始的n个字符，然后在pos处插入串s

void swap(string &s2); //交换当前字符串与s2的值

string与wstring的区别

string是对char*的管理，一个字符只占一个字节大小。一个汉字占两个字节，ASCII编码。

wstring是对wchar_t*的管理，一个字符占两个字节大小，一个汉字占两个字节，Unicode编码。

wstring的使用方法跟string类似，区别主要在于函数参数char与函数参数wchar_t

string与wstring的转换

第一种方法

调用Windows的API函数：WideCharToMultiByte()函数和MultiByteToWideChar()函数。

第二种方法

使用ATL的CA2W类与CW2A类。或使用A2W宏与W2A宏。

第三种方法，跨平台的方法，使用CRT库的mbstowcs()函数和wcstombs()函数，需设定locale。

以下是第三种方法的实现例子。

#include

#include <locale.h>

using namespace std;

//wstring转成string

string ws2s(const wstring &ws)

{

string curLocale = setlocale(LC_ALL,NULL); //curLocale=“C”;

setlocale(LC_ALL,“chs”);

const wchar_t * _Source=ws.c_str();

size_t _Dsize=2*ws.size()+1;

char * _Dest = new char[_Dsize];

memset(_Dest,0,_Dsize);

wcstombs(_Dest,_Source,_Dsize);

string result = _Dest;

delete[] _Dest;

setlocale(LC_ALL,curLocale.c_str());

return result;

}

//string转成wstring

wstring s2ws(const string &s)

{

string curLocale = setlocale(LC_ALL,NULL); //curLocale = “C”

setlocale(LC_ALL, “chs”);

const char *_Source = s.c_str();

size_t _Dsize = s.size()+1;

wchar_t *_Dest = new wchar_t[_Dsize];

wmemset(_Dest,0,_Dsize);

mbstowcs(_Dest,_Source,_Dsize);

wstring result = _Dest;

delete[] _Dest;

setlocale(LC_ALL, curLocale.c_str());

return result;

}

编码统一化，编写单一源代码

如果我们想建立两个版本的程序，一个处理ASCII字符串，另一个处理Unicode字符串，最好的解决办法是编写出既能按ASCII编译又能按Unicode编译的单一源代码。把以下代码加入到程序中，只要修改一个宏就能满足我们的要求。

#ifdef _UNICODE

typedef wstring tstring;

typedef wchar_t tchar;

#define _T(x) L ## x

#else

typedef string tstring;

typedef char tchar;

#define _T(x) x

#endif

回顾

这一讲，主要讲解如下要点：

一、什么是STL，使用STL的好处

STL的代码从广义上讲分为三类：container（容器）、iterator（迭代器）和algorithm（算法），容器和算法通过迭代器可以进行无缝连接。

string,wstring也是STL的一部分。

STL具有高可重用性，高性能，高移植性，跨平台的优点。

二、STL的string类型的使用方法

string是什么,string与char*的比较,string使用之前的准备,string的构造函数，取字符操作，取const char*的操作，拷贝，长度，赋值，连接，比较，子串，查找，插入，删除，替换，与wstring的区别与转换，编码统一化。

讲解要点

这一讲，主要讲解如下要点：

一、模板的简介，函数模板与类模板的用法；

二、容器的简介，容器的分类，各个容器的数据结构；

三、容器vector的具体用法（包括迭代器的具体用法）

模板的简介

模板是实现代码重用机制的一种工具，实质就是实现类型参数化，即把类型定义为参数。

C++提供两种模板：函数模板，类模板。

函数模板就是建立一个通用的函数，其函数返回类型和形参类型不具体指定，而是用虚拟的类型来代表。

凡是函数体相同的函数都可以用函数模板来代替，不必定义多个函数，只需在模板中定义一次即可。

在调用函数时系统会根据实参的类型来取代模板中的虚拟类型，从而实现了不同函数的功能。

类模板的简介

和函数模板一样，类模板就是建立一个通用类，其数据成员的类型、成员函数的返回类型和参数类形都可以不具体指定，而用虚拟的类型来代表。

当使用类模板建立对象时，系统会根据实参的类型取代类模板中的虚拟类型，从而实现不同类的功能。

可以定义多种类型的形参。

template<typename T1, typename T2>

class CTest

{…};

对象实例化时：

CTest testA<int, float>;

CTest testB<double, string>

容器的简介

容器是用来存放、管理一组元素的数据集合。

容器的数据结构示意图：

容器的分类

容器有序列式容器（Sequence containers）和关联式容器（Associated containers）

序列式容器：每个元素的位置取决于元素被插入的时机,被插入时设置的位置，和元素值本身无关。

序列式容器有vector、deque、list，queue, stack

关联式容器：元素位置取决于特定的排序准则，和插入顺序无关。

关联式容器有set、multiset、map、multimap

vector与迭代器的讲解纲要

vector的简介

vector是将元素置于一个动态数组中加以管理的容器。

vector可以随机存取元素（支持索引值直接存取， 用[]操作符或at()方法，这个等下会详讲）。

vector尾部添加或移除元素非常快速。但是在中部或头部插入元素或移除元素比较费时

vector使用之前的准备

#include

using namespace std;

vector对象的默认构造

vector采用模板类实现，vector对象的默认构造形式：vector vecT; 如：

vector vecInt; //一个存放int的vector容器。

vector vecFloat; //一个存放float的vector容器。

vector vecString; //一个存放string的vector容器。

… //尖括号内还可以设置指针类型或自定义类型。

Class CA{};

vector<CA*> vecpCA; //用于存放CA对象的指针的vector容器。

vector vecCA; //用于存放CA对象的vector容器。由于容器元素的存放是按值复制的方式进行的，所以此时CA必须提供CA的拷贝构造函数，以保证CA对象间拷贝正常。

vector末尾的添加移除操作

vector.push_back(elem); //在容器尾部加入一个元素。

vector.pop_back(); //移除容器中最后一个元素

例如： vector vecInt;

          vecInt.push_back(1); vecInt.push_back(3);

     vecInt.push_back(5);vecInt.push_back(7);

           vecInt.push_back(9);

此时容器vecInt就包含了按顺序的1,3,5,7,9元素。

如果在此基础上再运行语句vecInt.pop_back();

vecInt.pop_back();此时容器vecInt就包含了按顺序的1,3,5元素。

vector的数据存取

vec.at(idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range异常。

vec[idx]; //返回索引idx所指的数据，越界时，运行直接报错。

例如：假设vecInt是用vector 声明的，且已包含按顺序的1,3,5,7,9值;此时vecInt.at(2)==vecInt[2]==5。若运行代码vecInt.at(2)=8,或者运行vecInt[2]=8，则vecInt就包含按顺序的1,3,8,7,9值。

vector.front(); //返回第一个数据。

vector.back(); //返回最后一个数据。

vector vecInt; //假设包含{1,3,5,7,9}

int iF = vector.front(); //iF==1

int iB = vector.back(); //iB==9

vector.front() = 11; //vecInt包含{11,3,5,7,9}

vector.back() = 19; //vecInt包含{11,3,5,7,19}

迭代器的简介

迭代器是一个“可遍历STL容器内全部或部分元素”的对象。

迭代器指出容器中的一个特定位置。

迭代器就如同一个指针。

迭代器提供对一个容器中的对象的访问方法，并且可以定义了容器中对象的范围。

这里大概介绍一下迭代器的类别。

输入迭代器：也有叫法称之为“只读迭代器”，它从容器中读取元素，只能一次读入一个元素向前移动，只支持一遍算法，同一个输入迭代器不能两遍遍历一个序列。

输出迭代器：也有叫法称之为“只写迭代器”，它往容器中写入元素，只能一次写入一个元素向前移动，只支持一遍算法，同一个输出迭代器不能两遍遍历一个序列。

正向迭代器：组合输入迭代器和输出迭代器的功能，还可以多次解析一个迭代器指定的位置，可以对一个值进行多次读/写。

双向迭代器：组合正向迭代器的功能，还可以通过–操作符向后移动位置。

随机访问迭代器：组合双向迭代器的功能，还可以向前向后跳过任意个位置，可以直接访问容器中任何位置的元素。

目前本系列教程所用到的容器，都支持双向迭代器或随机访问迭代器，下面将会详细介绍这两个类别的迭代器。

双向迭代器与随机访问迭代器

双向迭代器支持的操作：

it++, ++it, it–, --it，*it， itA = itB，

itA == itB，itA != itB

      其中list,set,multiset,map,multimap支持双向迭代器。

随机访问迭代器支持的操作：

在双向迭代器的操作基础上添加

it+=i， it-=i， it+i(或it=it+i)，it[i],

itA<itB, itA<=itB, itA>itB, itA>=itB 的功能。

      其中vector，deque支持随机访问迭代器。

vector与迭代器的配合使用

vec.begin(); //返回容器中第一个元素的迭代器。

vec.end(); //返回容器中最后一个元素之后的迭代器。

例如：vecInt是用vector声明的容器，假设已经包含了按顺序的1,3,5,7,9元素。

vector::iterator it; //声明容器vector的迭代器。

运行 it=vecInt.begin(); //此时*it==1。

运行++it; // 或者it++; 此时*it==3，前++的效率比后++的效率高，前++返回引用，后++返回值。

运行it += 2; //此时*it==7。

运行it = it +1; //此时*it=9。

运行++it; //此时it==vecInt.end(); 此时不能再执行*it;

以下是用迭代器遍历容器的例子。

假设vecInt是用vector声明的容器，里面包含按顺序的1,3,5,7,9元素。

for(vector::iterator it=vecInt.begin(); it!=vecInt.end(); ++it)

{

  int iItem = *it;

  cout << iItem;    //或直接使用  cout << *it;

}

这样子便打印出1 3 5 7 9

vec.rbegin(); //返回容器中倒数第一个元素的迭代器。

vec.rend(); //返回容器中倒数最后一个元素之后的迭代器。

例如： vecInt是vector声明的容器，已包含按顺序的1,3,5,7,9元素。现要求逆序打印这些元素。

迭代器还有其它两种声明方法：

如：

vector::const_iterator

vector::const_reverse_iterator

这两种分别是

vector::iterator

vector::reverse_iterator

的只读形式，使用这两种迭代器时，不会修改到容器中的值。

备注：不过容器中的insert和erase方法仅接受这四种类型中的iterator，其它三种不支持。《Effective STL》建议我们尽量使用iterator取代const_iterator、reverse_iterator和const_reverse_iterator。

vector对象的带参数构造

vector(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。注意该区间是左闭右开的区间。

vector(n,elem); //构造函数将n个elem拷贝给本身。

vector(const vector &vec); //拷贝构造函数。

vector的赋值

vector.assign(beg,end); //将[beg, end)区间中的数据拷贝赋值给本身。注意该区间是左闭右开的区间。

vector.assign(n,elem); //将n个elem拷贝赋值给本身。

vector& operator=(const vector &vec); //重载等号操作符

vector.swap(vec); // 将vec与本身的元素互换。

vector的大小

vector.size(); //返回容器中元素的个数

vector.empty(); //判断容器是否为空

vector.resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

vector.resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

例如 vecInt是vector 声明的容器，现已包含1,2,3元素。

执行vecInt.resize(5); //此时里面包含1,2,3,0,0元素。

再执行vecInt.resize(8,3); //此时里面包含1,2,3,0,0,3,3,3元素。

再执行vecInt.resize(2); //此时里面包含1,2元素。

vector的插入

vector.insert(pos,elem); //在迭代器pos位置插入一个elem元素的拷贝，返回新数据的位置。

vector.insert(pos,n,elem); //在pos位置插入n个elem数据，无返回值。

vector.insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据，无返回值。

vector的删除

vector.clear(); //移除容器的所有数据

vec.erase(beg,end); //删除[beg,end)区间的数据，返回下一个数据的位置。

vec.erase(pos); //删除pos位置的数据，返回下一个数据的位置。

例如： vecInt是用vector声明的容器，现已包含按顺序的1,3,5,6,9元素。

vector::iterator itBegin=vecInt.begin()+1;

vector::iterator itEnd=vecInt.begin()+3;

vecInt.erase(itBegin,itEnd);

//此时容器vecInt包含按顺序的1,6,9三个元素。

例如 vecInt是用vector声明的容器，现已包含按顺序的1,3,2,3,3,3,4,3,5,3元素。现要求删除容器中所有等于3的元素。

for(vector::iterator it=vecInt.being(); it!=vecInt.end(); ) //小括号里不需写 ++it

{

if(*it == 3)

{

    it  =  vecInt.erase(it);       //以迭代器为参数，删除元素3，并把数据删除后的下一个元素位置返回给迭代器。

     //此时，不执行  ++it；  

}

else

{

   ++it;

}

}

回顾

这一讲，主要讲解如下要点：

一、模板的简介，函数模板与类模板的用法

类型参数化

二、容器的简介，容器的分类，各个容器的数据结构

vector,deque,list,set,multiset,map,multimap

三、容器vector的具体用法（包括迭代器的具体用法）。

vertor简介，vector使用之前的准备，vector对象的默认构造，vector末尾的添加移除操作，vector的数据存取，迭代器的简介，双向迭代器与随机访问迭代器

vector与迭代器的配合使用，vector对象的带参数构造，vector的赋值，vector的大小，vector的插入，vector的删除。

这一讲，主要讲解如下要点：

一、容器deque的使用方法;

二、容器queue,stack的使用方法;

三、容器list的使用方法。

deque的讲解纲要

deque的简介

deque是“double-ended queue”的缩写，和vector一样都是STL的容器，deque是双端的，而vector是单端的。

deque在接口上和vector非常相似，在许多操作的地方可以直接替换。

deque可以随机存取元素（支持索引值直接存取， 用[]操作符或at()方法，这个等下会详讲）。

deque头部和尾部添加或移除元素都非常快速。但是在中部安插元素或移除元素比较费时。

deque使用之前的准备

#include

using namespace std;

deque对象的默认构造

deque采用模板类实现，deque对象的默认构造形式：deque deqT; 如：

deque deqInt; //一个存放int的deque容器。

deque deq Float; //一个存放float的deque容器。

deque deq String; //一个存放string的deque容器。

…

//尖括号内还可以设置指针类型或自定义类型。

deque末尾的添加移除操作

deque.push_back(elem); //在容器尾部添加一个数据

deque.push_front(elem); //在容器头部插入一个数据

deque.pop_back(); //删除容器最后一个数据

deque.pop_front(); //删除容器第一个数据

deque的数据存取

deque.at(idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range。

deque[idx]; //返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。

deque.front(); //返回第一个数据。

deque.back(); //返回最后一个数据。

deque与迭代器

deque.begin(); //返回容器中第一个元素的迭代器。

deque.end(); //返回容器中最后一个元素之后的迭代器。

deque.rbegin(); //返回容器中倒数第一个元素的迭代器。

deque.rend(); //返回容器中倒数最后一个元素之后的迭代器。

deque对象的带参数构造

deque(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。注意该区间是左闭右开的区间。

deque(n,elem); //构造函数将n个elem拷贝给本身。

deque(const deque &deq); //拷贝构造函数。

deque的赋值

deque.assign(beg,end); //将[beg, end)区间中的数据拷贝赋值给本身。注意该区间是左闭右开的区间。

deque.assign(n,elem); //将n个elem拷贝赋值给本身。

deque& operator=(const deque &deq); //重载等号操作符

deque.swap(deq); // 将vec与本身的元素互换。

deque的大小

deque.size(); //返回容器中元素的个数

deque.empty(); //判断容器是否为空

deque.resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

deque.resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

例如 deqInt是deque 声明的容器，现已包含1,2,3元素。

执行deqInt.resize(5); //此时里面包含1,2,3,0,0元素。

再执行deqInt.resize(8,3); //此时里面包含1,2,3,0,0,3,3,3元素。

再执行deqInt.resize(2); //此时里面包含1,2元素。

deque的插入

deque.insert(pos,elem); //在pos位置插入一个elem元素的拷贝，返回新数据的位置。

deque.insert(pos,n,elem); //在pos位置插入n个elem数据，无返回值。

deque.insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据，无返回值。

deque的删除

deque.clear(); //移除容器的所有数据

deque.erase(beg,end); //删除[beg,end)区间的数据，返回下一个数据的位置。

deque.erase(pos); //删除pos位置的数据，返回下一个数据的位置。

queue，stack的讲解纲要

queue的简介

queue是队列容器，是一种“先进先出”的容器。

queue是简单地装饰deque容器而成为另外的一种容器。

queue使用之前的准备

#include

using namespace std;

queue对象的默认构造

queue采用模板类实现，queue对象的默认构造形式：queue queT; 如：

queue queInt; //一个存放int的queue容器。

queue queFloat; //一个存放float的queue容器。

queue queString; //一个存放string的queue容器。

//尖括号内还可以设置指针类型或自定义类型。

queue的push与pop操作

queue.push(elem); //往队尾添加元素

queue.pop(); //从队头移除第一个元素

例如：queue queInt;

queInt.push(1);queInt.push(3);…

queInt.push(5);queInt.push(7);

queInt.push(9);queInt.pop();

queInt.pop();

此时queInt存放的元素是5,7,9

queue对象的拷贝构造与赋值

queue(const queue &que); //拷贝构造函数

queue& operator=(const queue &que); //重载等号操作符

如：

queue queIntA, queIntC;…

queue queIntB(queIntA);

queue queIntD;

queIntD = queIntC;

queue的数据存取

queue.back(); //返回最后一个元素

queue.front(); //返回第一个元素

queue的大小

queue.empty(); //判断队列是否为空

queue.size(); //返回队列的大小

stack的简介

stack是堆栈容器，是一种“先进后出”的容器。

stack是简单地装饰deque容器而成为另外的一种容器。

stack使用之前的准备

#include

using namespace std;

stack对象的默认构造

stack采用模板类实现， stack对象的默认构造形式： stack stkT; 如：

stack stkInt; //一个存放int的stack容器。

stack stkFloat; //一个存放float的stack容器。

stack stkString; //一个存放string的stack容器。

//尖括号内还可以设置指针类型或自定义类型。

stack的push与pop操作

stack.push(elem); //往栈头添加元素

stack.pop(); //从栈头移除第一个元素

例如：stack stkInt;

stkInt.push(1);stkInt.push(3);stkInt.pop();

stkInt.push(5);stkInt.push(7);

stkInt.push(9);stkInt.pop();

stkInt.pop();

此时stkInt存放的元素是1,5

stack对象的拷贝构造与赋值

stack(const stack &stk); //拷贝构造函数

stack& operator=(const stack &stk); //重载等号操作符

如：

stack stkIntA, stkIntC; …

stack stkIntB(stkIntA);

stack stkIntD;

stkIntD = stkIntC;

stack的数据存取

stack.top(); //返回最后一个压入栈元素

stack的大小

stack.empty(); //判断堆栈是否为空

stack.size(); //返回堆栈的大

list的讲解纲要

list的简介

list是一个双向链表容器，可高效地进行插入删除元素。

list不可以随机存取元素，所以不支持at.(pos)函数与[]操作符。

list使用之前的准备

#include

using namespace std;

list对象的默认构造

list采用模板类实现，list对象的默认构造形式：list lstT; 如：

list lstInt; //定义一个存放int的list容器。

list lstFloat; //定义一个存放float的list容器。

list lstString; //定义一个存放string的list容器。

…

//尖括号内还可以设置指针类型或自定义类型。

list头尾的添加移除操作

list.push_back(elem); //在容器尾部加入一个元素

list.pop_back(); //删除容器中最后一个元素

list.push_front(elem); //在容器开头插入一个元素

list.pop_front(); //从容器开头移除第一个元素

list的数据存取

list.front(); //返回第一个元素。

list.back(); //返回最后一个元素。

list与迭代器

list.begin(); //返回容器中第一个元素的迭代器。

list.end(); //返回容器中最后一个元素之后的迭代器。

list.rbegin(); //返回容器中倒数第一个元素的迭代器。

list.rend(); //返回容器中倒数最后一个元素的后面的迭代器。

list对象的带参数构造

list(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。注意该区间是左闭右开的区间。

list(n,elem); //构造函数将n个elem拷贝给本身。

list(const list &lst); //拷贝构造函数。

list的赋值

list.assign(beg,end); //将[beg, end)区间中的数据拷贝赋值给本身。注意该区间是左闭右开的区间。

list.assign(n,elem); //将n个elem拷贝赋值给本身。

list& operator=(const list &lst); //重载等号操作符

list.swap(lst); // 将lst与本身的元素互换。

list的大小

list.size(); //返回容器中元素的个数

list.empty(); //判断容器是否为空

list.resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

list.resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

list的插入

list.insert(pos,elem); //在pos位置插入一个elem元素的拷贝，返回新数据的位置。

list.insert(pos,n,elem); //在pos位置插入n个elem数据，无返回值。

list.insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据，无返回值。

list的删除

list.clear(); //移除容器的所有数据

list.erase(beg,end); //删除[beg,end)区间的数据，返回下一个数据的位置。

list.erase(pos); //删除pos位置的数据，返回下一个数据的位置。

lst.remove(elem); //删除容器中所有与elem值匹配的元素。

list的反序排列

lst.reverse(); //反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素。

回顾

一、容器deque的使用方法

适合 在头尾添加移除元素。使用方法与vector类似。

二、容器queue,stack的使用方法

适合队列，堆栈的操作方式。

三、容器list的使用方法

适合在任意位置快速插入移除元素。

这一讲，主要讲解如下要点：

一、容器set/multiset的使用方法；

二、functor的使用方法；

三、pair的使用方法。

讲解纲要

set/multiset的简介

set是一个集合容器，其中所包含的元素是唯一的，集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入，所以不能指定插入位置。

set采用红黑树变体的数据结构实现，红黑树属于平衡二叉树。在插入操作和删除操作上比vector快。

set不可以直接存取元素。（不可以使用at.(pos)与[]操作符）。

multiset与set的区别：set支持唯一键值，每个元素值只能出现一次；而multiset中同一值可以出现多次。

不可以直接修改set或multiset容器中的元素值，因为该类容器是自动排序的。如果希望修改一个元素值，必须先删除原有的元素，再插入新的元素。

set/multiset使用之前的准备

#include

using namespace std;

set/multiset对象的默认构造

set采用模板类实现，set/multiset对象的默认构造形式：set setT; multiset multisetT; 如：

set setInt; //一个存放int的set容器。

set setFloat; //一个存放float的set容器。

set setString; //一个存放string的set容器。

multiset mulsetInt; //一个存放int的multi set容器。

multi set multisetFloat; //一个存放float的multi set容器。

multi set multisetString; //一个存放string的multi set容器。

…

//尖括号内可以还设置各种指针类型或自定义类型。

set的插入与迭代器

set.insert(elem); //在容器中插入元素。

set.begin(); //返回容器中第一个数据的迭代器。

set.end(); //返回容器中最后一个数据之后的迭代器。

set.rbegin(); //返回容器中倒数第一个元素的迭代器。

set.rend(); //返回容器中倒数最后一个元素的后面的迭代器。

例如： set setInt;

setInt.insert(3); setInt.insert(1);setInt.insert(5);setInt.insert(2);

for(set::iterator it=setInt.begin(); it!=setInt.end(); ++it)

{

  int iItem = *it;

  cout << iItem;    //或直接使用cout << *it

}

//这样子便顺序输出 1 2 3 5。

疑问: 能不能在插入数值时，采用降序排列，而不是升序排列呢。

set<int,less > setIntA; //该容器是按升序方式排列元素。

set<int,greater> setIntB; //该容器是按降序方式排列元素。

set 相当于 set<int,less>。

less与greater中的int可以改成其它类型，该类型主要要跟set容纳的数据类型一致。

疑问1：less<>与greater<>是什么？

疑问2：如果set<>不包含int类型，而是包含自定义类型，set容器如何排序？

要解决如上两个问题，需要了解容器的函数对象，也叫伪函数，英文名叫functor。

下面将讲解什么是functor，functor的用法。

函数对象functor的简介

尽管函数指针被广泛用于实现函数回调，但C++还提供了一个重要的实现回调函数的方法，那就是函数对象。

functor，翻译成函数对象，伪函数，算符，是重载了“()”操作符的普通类对象。从语法上讲，它与普通函数行为类似。

greater<>与less<>就是函数对象。

下面举出greater的简易实现原理。

struct greater

{

bool operator() (const int& iLeft, const int& iRight)

{

   return (iLeft>iRight);          //如果是实现less<int>的话，这边                                                                                             //是写return (iLeft<iRight);

}

}

容器就是调用函数对象的operator()方法去比较两个值的大小。

题目：学生包含学号，姓名属性，现要求任意插入几个学生对象到set容器中，使得容器中的学生按学号的升序排序。

//学生类

class CStudent

{

public:

CStudent(int iID, string strName)

{

m_iID = iID;

m_strName = strName;

}

 int m_iID;	//学号

 string m_strName; //姓名

}

//为保持主题鲜明，本类不写拷贝构造函数，但大家仍要有考虑拷贝构造函数的习惯。

//函数对象

struct StuFunctor

{

bool operator() (const CStudent &stu1, const CStudent &stu2)

{

return (stu1.m_iID<stu2.m_iID);

}

}

//main函数

void main()

{

set<CStudent, StuFunctor> setStu;

setStu.insert(CStudent(3,“小张”));

setStu.insert(CStudent(1,“小李”));

setStu.insert(CStudent(5,“小王”));

setStu.insert(CStudent(2,“小刘”));

//此时容器setStu包含了四个学生对象，分别是按姓名顺序的“小李”，“小刘”，“小张”，“小王”

}

函数对象functor的用法

set(const set &st); //拷贝构造函数

set& operator=(const set &st); //重载等号操作符

set.swap(st); //交换两个集合容器

如：

set setIntA, setIntC;

…

set setIntB(setIntA);

set setIntD;

setIntD = setIntC;

set对象的拷贝构造与赋值

set(const set &st); //拷贝构造函数

set& operator=(const set &st); //重载等号操作符

set.swap(st); //交换两个集合容器

如：

set setIntA, setIntC;

…

set setIntB(setIntA);

set setIntD;

setIntD = setIntC;

set的大小

set.size(); //返回容器中元素的数目

set.empty();//判断容器是否为空

set的删除

set.clear(); //清除所有元素

set.erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。

set.erase(beg,end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。

set.erase(elem); //删除容器中值为elem的元素。

set的查找

set.find(elem); //查找elem元素，返回指向elem元素的迭代器。

set.count(elem); //返回容器中值为elem的元素个数。对set来说，要么是0，要么是1。对multiset来说，值可能大于1。

set.lower_bound(elem); //返回第一个>=elem元素的迭代器。

set.upper_bound(elem); // 返回第一个>elem元素的迭代器。

set.equal_range(elem); //返回容器中与elem相等的上下限的两个迭代器。上限是闭区间，下限是开区间，如[beg,end)。

以上函数返回两个迭代器，而这两个迭代器被封装在pair中。

以下讲解pair的含义与使用方法。

pair的简介

pair译为对组，可以将两个值视为一个单元。

pair<T1,T2>存放的两个值的类型，可以不一样，如T1为int，T2为float。T1,T2也可以是自定义类型。

pair.first是pair里面的第一个值，是T1类型。

pair.second是pair里面的第二个值，是T2类型。

pair的使用

例如 set setInt;

… //往setInt容器插入元素1,3,5,7,9

pair< set::iterator , set::iterator > pairIt = setInt.equal_range(5);

set::iterator itBeg = pairIt.first;

set::iterator itEnd = pairIt.second;

//此时 *itBeg==5 而 *itEnd == 7

回顾

一、容器set/multiset的使用方法；

红黑树的变体，查找效率高，插入不能指定位置，插入时自动排序。

二、functor的使用方法；

类似于函数的功能，可用来自定义一些规则，如元素比较规则。

三、pair的使用方法。

对组，一个整体的单元，存放两个类型(T1,T2，T1可与T2一样)的两个元素。

容器map/multimap的使用方法

map/multimap的简介

map是标准的关联式容器，一个map是一个键值对序列，即(key,value)对。它提供基于key的快速检索能力。

map中key值是唯一的。集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入，所以不能指定插入位置。

map的具体实现采用红黑树变体的平衡二叉树的数据结构。在插入操作和删除操作上比vector快。

map可以直接存取key所对应的value，支持[]操作符，如map[key]=value。

multimap与map的区别：map支持唯一键值，每个键只能出现一次；而multimap中相同键可以出现多次。multimap不支持[]操作符。

map/multimap使用之前的准备

#include

using namespace std;

map/multimap对象的默认构造

map/multimap采用模板类实现，对象的默认构造形式：

map<T1,T2> mapTT;

multimap<T1,T2> multimapTT;

如：map<int, char> mapA;

map<string,float> mapB;

//其中T1,T2还可以用各种指针类型或自定义类型

map的插入与迭代器

map.insert(…); //往容器插入元素，返回pair<iterator,bool>

在map中插入元素的三种方式：

假设 map<int, string> mapStu;

一、通过pair的方式插入对象

mapStu.insert( pair<int,string>(3,“小张”) );

二、通过value_type的方式插入对象

mapStu.insert( map<int,string>::value_type(1,“小李”) );

三、通过数组的方式插入值

mapStu[3] = “小刘";

mapStu[5] = “小王"；

…

第三种方法非常直观，但存在一个性能的问题。插入3时，先在mapStu中查找主键为3的项，若没发现，则将一个键为3，值为初始化值的对组插入到mapStu中，然后再将值修改成“小刘”。若发现已存在3这个键，则修改这个键对应的value。

string strName = mapStu[2]; //取操作或插入操作

只有当mapStu存在2这个键时才是正确的取操作，否则会自动插入一个实例，键为2，值为初始化值。

前两种方法，采用的是insert()方法，该方法返回值为pair<iterator,bool>

pair< map<int,string>::iterator , bool > pairResult = mapStu.insert( pair<int,string>(3,“小张”) );

如果插入成功，(pairResult.first)->first3, (pairResult.first)->second"小张" pairResult.second==true。

map<T1,T2,less > mapA; //该容器是按键的升序方式排列元素。未指定函数对象，默认采用less函数对象。

map<T1,T2,greater> mapB; //该容器是按键的降序方式排列元素。

less与greater 可以替换成其它的函数对象functor。

可编写自定义函数对象以进行自定义类型的比较，使用方法与set构造时所用的函数对象一样。

map.begin(); //返回容器中第一个数据的迭代器。

map.end(); //返回容器中最后一个数据之后的迭代器。

map.rbegin(); //返回容器中倒数第一个元素的迭代器。

map.rend(); //返回容器中倒数最后一个元素的后面的迭代器。

map对象的拷贝构造与赋值

map(const map &mp); //拷贝构造函数

map& operator=(const map &mp); //重载等号操作符

map.swap(mp); //交换两个集合容器

如：

map<T1,T2> mapIntA, mapIntC;

…

map<T1,T2> mapIntB(mapIntA);

map<T1,T2> mapIntD;

mapIntD = mapIntC;

map的大小

map.size(); //返回容器中元素的数目

map.empty();//判断容器是否为空

map的删除

map.clear(); //删除所有元素

map.erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。

map.erase(beg,end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。

map.erase(keyElem); //删除容器中key为keyElem的对组。

map的查找

map.find(key); 查找键key是否存在，若存在，返回该键的元素的迭代器；若不存在，返回map.end();

map.count(keyElem); //返回容器中key为keyElem的对组个数。对map来说，要么是0，要么是1。对multimap来说，值可能大于1。

map<int,string>::iterator it=mapStu.find(3);

if(it == mapStu.end())

{

//没找到

}

else

{

//找到了

    pair<int, string> pairStu = *it;

int iID = pairStu.first; //或 int iID = it->first;

    string strName = pairStu.second;	//或   string strName = it->second;

}

map.lower_bound(keyElem); //返回第一个key>=keyElem元素的迭代器。

map.upper_bound(keyElem); // 返回第一个key>keyElem元素的迭代器。

例如： mapStu是用map<int,string>声明的容器，已包含{1,“小李”}{3,“小张”}{5,“小王”}{7,“小赵”}{9,“小陈”}元素。map<int,string>::iterator it;

it = mapStu.lower_bound(5); //it->first5 it->second"小王"

it = mapStu.upper_bound(5); //it->first7 it->second"小赵"

it = mapStu.lower_bound(6); //it->first7 it->second"小赵"

it = mapStu.upper_bound(6); //it->first7 it->second"小赵"

map.equal_range(keyElem); //返回容器中key与keyElem相等的上下限的两个迭代器。上限是闭区间，下限是开区间，如[beg,end)。

以上函数返回两个迭代器，而这两个迭代器被封装在pair中。

例如 map<int,string> mapStu;

… //往mapStu容器插入元素{1,“小李”}{3,“小张”}{5,“小王”}{7,“小赵”}{9,“小陈”}

pair< map<int,string>::iterator , map<int,string>::iterator > pairIt = mapStu.equal_range(5);

map<int, string>::iterator itBeg = pairIt.first;

map<int, string>::iterator itEnd = pairIt.second;

//此时 itBeg->first==5 , itEnd->first == 7,

itBeg->second==“小王”, itEnd->second==“小赵”

Multimap例子

struct userdevice{

string m_devicename;

long m_deviceid;

int m_devicePopedom;

};

typedef multimap<string,userdevice> USERTABLE;

typedef USERTABLE::const_iterator CIT;

typedef pair<CIT, CIT> Range;

本 讲 要 点

一、容器的共通能力；

二、各个容器的使用时机；

三、常用算法（Algorithm）的用法介绍。

容器的共通能力

所有容器提供的都是值（value）语意，而非引用（reference）语意。容器执行插入元素的操作时，内部实施拷贝动作。所以STL容器内存储的元素必须能够被拷贝（必须提供拷贝构造函数）。

除了queue与stack外，每个容器都提供可返回迭代器的函数，运用返回的迭代器就可以访问元素。

通常STL不会丢出异常。要求使用者确保传入正确的参数。

每个容器都提供了一个默认构造函数跟一个默认拷贝构造函数。

如已有容器vecIntA。

vector vecIntB(vecIntA); //调用拷贝构造函数，复制vecIntA到vecIntB中。

与大小相关的操作方法(c代表容器)：

c.size(); //返回容器中元素的个数

c.empty(); //判断容器是否为空

比较操作(c1,c2代表容器)：

c1 == c2 判断c1是否等于c2

c1 != c2 判断c1是否不等于c2

c1 = c2 把c2的所有元素指派给c1

各个容器的使用时机

Vector的使用场景：比如软件历史操作记录的存储，我们经常要查看历史记录，比如上一次的记录，上上次的记录，但却不会去删除记录，因为记录是事实的描述。

deque的使用场景：比如排队购票系统，对排队者的存储可以采用deque，支持头端的快速移除，尾端的快速添加。如果采用vector，则头端移除时，会移动大量的数据，速度慢。

vector与deque的比较：

一：vector.at()比deque.at()效率高，比如vector.at(0)是固定的，deque的开始位置却是不固定的。

二：如果有大量释放操作的话，vector花的时间更少，这跟二者的内部实现有关。

三：deque支持头部的快速插入与快速移除，这是deque的优点。

list的使用场景：比如公交车乘客的存储，随时可能有乘客下车，支持频繁的不确实位置元素的移除插入。

set的使用场景：比如对手机游戏的个人得分记录的存储，存储要求从高分到低分的顺序排列。

map的使用场景：比如按ID号存储十万个用户，想要快速要通过ID查找对应的用户。二叉树的查找效率，这时就体现出来了。如果是vector容器，最坏的情况下可能要遍历完整个容器才能找到该用户。

算法（Algorithm）的简介

算法部分主要由头文件，和组成。

是所有STL头文件中最大的一个，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、反转、排序、合并等等。

体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。

中则定义了一些模板类，用以声明函数对象。

STL提供了大量实现算法的模版函数，只要我们熟悉了STL之后，许多代码可以被大大的化简，只需要通过调用一两个算法模板，就可以完成所需要的功能，从而大大地提升效率。

算法（Algorithm）使用之前的准备

#include

#include

#include

using namespace std;

算法（Algorithm）的讲解大纲

常用的查找算法：

adjacent_find()（ adjacent 是邻近的意思）,binary_search(),count(),

count_if(),equal_range(),find(),find_if()。

常用的排序算法：

merge(),sort(),random_shuffle()（shuffle是洗牌的意思） ,reverse()。

常用的拷贝和替换算法：

copy(), replace(),

replace_if(),swap()

常用的算术和生成算法：

accumulate()（ accumulate 是求和的意思）,fill(),。

常用的集合算法：

set_union(),set_intersection(),

set_difference()。

常用的遍历算法：

for_each(), transform()（ transform 是变换的意思）

常用的查找算法

adjacent_find(): 在iterator对标识元素范围内，查找一对相邻重复元素，找到则返回指向这对元素的第一个元素的迭代器。否则返回past-the-end。

例如：vecInt是用vector声明的容器，现已包含1,2,2,4,5元素。

vector::iterator it=adjacent_find(vecInt.begin(),vecInt.end());

此时 *it == 2

binary_search: 在有序序列中查找value,找到则返回true。注意：在无序序列中，不可使用。

例如： setInt是用set声明的容器，现已包含1，3，5，7，9元素。

bool bFind = binary_search(setInt.begin(),setInt.end(),5);

此时 bFind == true

count: 利用等于操作符，把标志范围内的元素与输入值比较，返回相等的个数。

count_if: 利用输入的函数，对标志范围内的元素进行比较操作，返回结果为true的个数。

例如：vecInt是用vector声明的容器，已包含1,3,5,7,9元素，现要求求出大于等于3的元素个数

//先定义比较函数

bool GreaterThree(int iNum)

{

if(iNum>=3)

{

return true;

}

else

{

return false;

}

}

int iCount = count_if(vecIntA.begin(), vecIntA.end(), GreaterThree);

//此时iCount == 4

equal_range: 返回一对iterator，第一个表示lower_bound,第二个表示upper_bound。

find: 利用底层元素的等于操作符，对指定范围内的元素与输入值进行比较。当匹配时，结束搜索，返回该元素的迭代器。

例如： vecInt是用vector声明的容器，已包含1,3,5,7,9

vector::iterator it = find(vecInt.begin(),vecInt.end(),5);

此时 *it == 5

find_if: 使用输入的函数代替等于操作符执行find。返回被找到的元素的迭代器。

例如：vecInt是用vector声明的容器，已包含1,3,5,3,9元素。现要找出第一个大于等于3的元素的迭代器。

vector::iterator it = find_if(vecInt.begin(),vecInt.end(),GreaterThree);

此时 *it==3, *(it+1)==5, *(it+2)==3, *(it+3)==9

常用的排序算法

以下是排序和通用算法：提供元素排序策略

merge: 合并两个有序序列，存放到另一个序列。

例如：vecIntA,vecIntB,vecIntC是用vector声明的容器，vecIntA已包含1,3,5,7,9元素，vecIntB已包含2,4,6,8元素

vecIntC.resize(9); //扩大容量

merge(vecIntA.begin(),vecIntA.end(),vecIntB.begin(),vecIntB.end(),vecIntC.begin());

此时vecIntC就存放了按顺序的1,2,3,4,5,6,7,8,9九个元素

sort: 以默认升序的方式重新排列指定范围内的元素。若要改排序规则，可以输入比较函数。

例如: vecInt是用vector声明的容器，已包含2,1,4,3,6,5元素

sort(vecInt.begin(),vecInt.end()); 此时，vecInt包含了1,2,3,4,5,6元素。

如果vector,T是自定义类型，则要提供T类型的比较函数。

random_shuffle: 对指定范围内的元素随机调整次序。

reverse: 对指定范围内元素重新反序排序。

常用的拷贝和替换算法

copy: 复制序列

例如：vecIntA,vecIntB是用vector声明的对象，vecIntA已包含1,3,5,7,9元素。

vecIntB.resize(5);

copy(vecIntA.begin(),vecIntA.end(),vecIntB.begin());

此时vecIntB也包含了1,3,5,7,9元素

replace(beg,end,oldValue,newValue):将指定范围内的所有等于oldValue的元素替换成newValue。

replace_if : 将指定范围内所有操作结果为true的元素用新值替换。

用法举例：replace_if(vecIntA.begin(),vecIntA.end(),GreaterThree,newVal)

其中 vecIntA是用vector声明的容器

GreaterThree 函数的原型是 bool GreaterThree(int iNum)

swap: 交换两个容器的元素

常用的算术与生成算法

accumulate: 对指定范围内的元素求和，然后结果再加上一个由val指定的初始值。

fill: 将输入值赋给标志范围内的所有元素。

算法（Algorithm）的使用方法

set_union: 构造一个有序序列，包含两个有序序列的并集。

set_intersection: 构造一个有序序列，包含两个有序序列的交集。

set_difference: 构造一个有序序列，该序列保留第一个有序序列中存在而第二个有序序列中不存在的元素。

常用的遍历算法

for_each: 用指定函数依次对指定范围内所有元素进行迭代访问。该函数不得修改序列中的元素。

transform: 与for_each类似，遍历所有元素，但可对容器的元素进行修改

回顾

一、容器的共通能力；

二、各个容器的使用时机；

三、常用算法（Algorithm）的用法介绍

查找，排序，拷贝，替换，算术，生成，关系，集合，遍历。