526互联

STL学习笔记

发布时间 2023-09-06 09:58:25作者: BryceAi

迭代器

迭代器(iterator)是一种抽象的设计概念，现实程序语言中并没有直接对应于这个概念的实物。在<>一书中提供了23中设计模式的完整描述，其中iterator模式定义如下：提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。

迭代器案例

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;


//普通指针也是一种迭代器
void f01()
{
 int a[5] = { 0,1,2,3,6 }; //第一种遍历方式
 int *p = a;
 for (int i = 0; i < 5; i++)
 {
  //cout << a[i] << endl;
  cout << *(p++) << endl;
 }
}

void f02()  //f02和f03是第二种遍历方式
{
 vector<int>v;//声明了一个vector容器

 //向容器内添加数据
 v.push_back(0);
 v.push_back(1);
 v.push_back(2);
 v.push_back(3);

 //通过迭代器可以遍历容器
 //每个容器都有自己专有的迭代器
 vector<int>::iterator ibegin = v.begin();   //begin在第一个元素
 vector<int>::iterator iend = v.end();  //end在最后一个元素的后面一位

 while (ibegin != iend)  //遍历
 {
  cout << *ibegin << endl;
  ibegin++;
 }
 //缺点：麻烦，简单的见f03()
}

void f03()
{
 vector<int>v;//声明了一个vector容器

 //向容器内添加数据
 v.push_back(0);
 v.push_back(1);
 v.push_back(2);
 v.push_back(3);

 for (vector<int>::iterator i = v.begin(); i != v.end(); i++)
 {
  cout << *i << endl;
 }
 

}


void myPr(int n)
{
 cout << n << endl;
}

void f04()//第四种遍历方式，用算法库,需要 #include<algorithm> 和 回调函数void myPr(int n)
{
 vector<int>v;//声明了一个vector容器

//向容器内添加数据
 v.push_back(0);
 v.push_back(1);
 v.push_back(2);
 v.push_back(3);

 for_each(v.begin(), v.end(), myPr);
 //实现方法见定义
 //for (; _UFirst != _ULast; ++_UFirst)
 //{
 // _Func(*_UFirst);
 //}

}


//自定义数据类型
class pe
{
public:
 pe(string na, int age)
 {
  this->Name = na;
  this->Age = age;
 }
 string Name;
 int Age;

};

void f05()
{
 vector<pe>v;

 pe p1("AAA", 10);
 pe p2("BBB", 20);
 pe p3("CCC", 30);
 pe p4("DDD", 40);

 v.push_back(p1);
 v.push_back(p2);
 v.push_back(p3);
 v.push_back(p4);

 for (vector<pe>::iterator i = v.begin(); i != v.end(); i++)
 {
  cout << (*i).Name << "  " << (*i).Age << endl;
 }
}

void f06()
{
 vector<pe*>v;

 pe p1("AAA", 10);
 pe p2("BBB", 20);
 pe p3("CCC", 30);
 pe p4("DDD", 40);

 v.push_back(&p1);
 v.push_back(&p2);
 v.push_back(&p3);
 v.push_back(&p4);

 for (vector<pe*>::iterator i = v.begin(); i != v.end(); i++)
 {
  cout << (**i).Name << "  " << (**i).Age << endl;
 }
}


//容器可以嵌套容器
void f07()
{
 vector<vector<int>>v;//容器嵌套容器，类似于二维数组
 
 vector<int>v1;
 vector<int>v2;
 vector<int>v3;
 vector<int>v4;

 for (int i = 0; i < 10; i += 2)
 {
  v1.push_back(i + 5);
  v2.push_back(i + 15);
  v3.push_back(i + 105);
  v4.push_back(i + 315);
 }

 v.push_back(v1);
 v.push_back(v2);
 v.push_back(v3);
 v.push_back(v4);

 for (vector<vector<int>>::iterator it = v.begin(); it != v.end(); it++)
 {
  for (vector<int>::iterator vit = (*it).begin(); vit != (*it).end(); vit++)
  {
   cout << *vit << "  ";
  }
  cout << endl;
 }

}



int main()
{
 f07();


 return 0;
}

案例中包括：

  • 简单的遍历算法
  • 容器迭代器举例
    • 默认数据类型迭代器
    • 自定义数据类型迭代器
  • Cpp Algorithm 库遍历算法
  • 容器嵌套迭代器的使用

algorithm常用算法

这部分教程里没有，是自己加的。
c++之中的algorithm库包含了所有vector、list、set、map数据结构能想到的一些函数，例如查找，替换，排序，计数等常用的功能的。

max()，min()，abs()

max(x,y)和min(x,y)参数必须是两个，如果想比较x,y,z的最大值，可写为max(x,max(y,z))。
abs(x) 返回x的绝对值。x必须为整数，浮点型的绝对值要用math头文件下的fabs。

swap()

swap(x,y)交换x，y的数值

reverse()

reverse(it,it2) 可以将数组指针在[it,it2)之间的元素或容器的迭代器在[it,it2)范围内的元素进行反转

#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
    int a[10]={10,11,12,13,14,15};
    reverse(a,a+4);
    for(int i=0;i<6;i++){
        printf("%d ",a[i]);
    }
    return 0;
}
输出：13 12 11 10 14 15
#include<stdio.h>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    string str="abcdefghi";
    reverse(str.begin()+2,str.begin()+6);
    for(int i=0;i<str.length();i++){
        printf("%c",str[i]);
    }
    return 0;
}
输出：abfedcghi

next_permutation()

next_permutation() 给出一个序列在全排列中的下一个序列。

#include<stdio.h>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    int a[10]={1,2,3};
    do{
        printf("%d %d %d\n",a[0],a[1],a[2]);
    }while(next_permutation(a,a+3));  //循环停止的条件是什么
    return 0;
}
输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

fill()

fill() 可以把数组或容器中的某一段区间赋为某个相同的值。和memset不同，这里的赋值可以使数组类型对应范围中的任意值。

#include<stdio.h>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    int a[10]={1,2,3,4,5};
    fill(a,a+5,233);
    for(int i=0;i<5;i++){
        printf("%d ",a[i]);
    }
    return 0;
}
输出：233 233 233 233 233  每一个都是233了

sort()

Sort函数有三个参数：（第三个参数可不写）
（1）第一个是要排序的数组的起始地址。
（2）第二个是结束的地址（最后一位要排序的地址）
（3）第三个参数是排序的方法，可以是从大到小也可是从小到大，还可以不写第三个参数，此时默认的排序方法是从小到大排序。
默认为递增排序，若要递减排序，需要增加比较函数

bool cmp(int a,int b){
  return a>b;
}
sort(a,a+n,cmp);

struct node{
  int x,y;
}a[10];
bool cmp(node a,node b){
  return a.x>b.x; 
}
//
bool cmp(int x,int y){
  if(a.x!=b.x) return a.x>b.x;
  else return a.y<b.y;
}

对于递增和递减，标准库里已经有现成的了，就在functional里，include进来就行了。functional提供了一堆基于模板的比较函数对象。它们是（看名字就知道意思了）：equal_to、not_equal_to、greater、greater_equal、less、less_equal。普通的问题，greater和less就足够了，直接拿过来用：

升序：sort(begin,end,less<data-type>());
降序：sort(begin,end,greater<data-type>()).  

#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
	int a[20]={2,4,1,23,5,76,0,43,24,65},i;
	for(i=0;i<20;i++)
        cout<<a[i]<<" ";
    cout<<endl;
	sort(a,a+20,greater<int>());
	for(i=0;i<20;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    sort(a,a+20,less<int>());
    for(i=0;i<20;i++)
        cout<<a[i]<<" ";
    cout<<endl;
	return 0;
}
输出：
2 4 1 23 5 76 0 43 24 65 0 0 0 0 0 0 0 0 0 0
76 65 43 24 23 5 4 2 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 2 4 5 23 24 43 65 76

容器排序，在STL标砖容器中，只有vector/string/deque可以sort

#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(int a,int b){
    return a>b;
}
int main()
{
    vector<int> vi;
    vi.push_back(3);
    vi.push_back(1);
    vi.push_back(2);
    sort(vi.begin(),vi.end(),cmp);
    for(int i=0;i<3;i++){
        printf("%d ",vi[i]);
    }
    return 0;
}
输出：3 2 1

lower_bound()和upper_bound()

ower_bound 和 upper_bound()需要用在一个有序数组或容器中。
lower_bound(first,last,val) 用来寻找数组或容器的[first,last)范围内第一个值大于等于val元素的位置，如果是数组，返回该位置的指针；如果是容器，返回该位置的迭代器。

upper_bound(first,last,val) 用来寻找在数组或容器的[first,last)范围内第一个值大于val元素的位置，如果是数组，返回该位置的指针；如果是容器，返回该位置的迭代器。

#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int a[10]={1,2,2,3,3,3,5,5,5,5};
    printf("%d,%d\n",lower_bound(a,a+10,3)-a,upper_bound(a,a+10,3)-a);
    return 0;
}
**注意其中的  -a**
输出：3,6

String容器

C风格字符串(以空字符结尾的字符数组)太过复杂难于掌握，不适合大程序的开发，所以C++标准库定义了一种string类，定义在头文件<string>。
String和c风格字符串对比：

  • Char是一个指针，String是一个类
    string封装了char    ，管理这个字符串，是一个char*型的容器。
  • String封装了很多实用的成员方法
    查找find，拷贝copy，删除delete 替换replace，插入insert
  • 不用考虑内存释放和越界
    string管理char*所分配的内存。每一次string的复制，取值都由string类负责维护，不用担心复制越界和取值越界等。

String常用操作代码接口

string 构造函数

string();//创建一个空的字符串 例如: string str;      
string(const string& str);//使用一个string对象初始化另一个string对象
string(const char* s);//使用字符串s初始化
string(int n, char c);//使用n个字符c初始化

string大小函数

size()	//返回字符串中有效字符长度
length()	//返回字符串中有效字符长度
capacity()	//返回空间的总长度，字符长度size超过capacity会自动扩容
empty()	//检测字符串是否为空串，是返回true，不是返回false
clear()	//清空有效字符串，空间不释放，内容没改变，只是size变为0
reserve(size_t n=0)	//为字符串预留空间，就是提前开辟一段你想要大小的空间，如果不用reserve，编译器会自己开辟一段空间。
resize(size_t n,char c)
//将有效字符串个数改成n个,n小于size，缩小size到n。n大于size，增大size到n，多出来的空间用字符c填充，不给c，用'\0'填充
  • length和size底层实现是一样的，引入size的原因是为了与其它容器保持一致，一般情况下用size
  • clear()函数只是将对象的size置0，不改变底层空间大小
  • resize(size_t n,char c),当n小于对象size时，直接改变对象的size到n。当n大于对象size时，直接增大对象size到n，多出来的空间用给的字符c填充，没给字符c默认用\0填充。

string基本赋值操作

string& operator=(const char* s);//char*类型字符串 赋值给当前的字符串
string& operator=(const string &s);//把字符串s赋给当前的字符串
string& operator=(char c);//字符赋值给当前的字符串
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存取字符操作

char& operator[](int n);//通过[]方式取字符
char& at(int n);//通过at方法获取字符

string拼接操作

string& operator+=(const string& str);//重载+=操作符
string& operator+=(const char* str);//重载+=操作符
string& operator+=(const char c);//重载+=操作符
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 find(const string& str, int pos = 0) const; //查找str第一次出现位置,从pos开始查找
int find(const char* s, int pos = 0) const;  //查找s第一次出现位置,从pos开始查找
int find(const char* s, int pos, int n) const;  //从pos位置查找s的前n个字符第一次位置
int find(const char c, int pos = 0) const;  //查找字符c第一次出现位置
int rfind(const string& str, int pos = npos) const;//查找str最后一次位置,从pos开始查找
int rfind(const char* s, int pos = npos) const;//查找s最后一次出现位置,从pos开始查找
int rfind(const char* s, int pos, int n) const;//从pos查找s的前n个字符最后一次位置
int rfind(const char c, int pos = 0) const; //查找字符c最后一次出现位置
string& replace(int pos, int n, const string& str); //替换从pos开始n个字符为字符串str
string& replace(int pos, int n, const char* s); //替换从pos开始的n个字符为字符串s
  • rfind表示从右开始找；
  • 注意函数有两个参数，一个是目标字符，一个是开始查找的位置。
  • 需要一个int类型变量去接这个返回值，不然可能会出现乱码。
  • 替换中，是替换pos开始的n个字符为字符串str。仔细理解这句话。

string比较操作

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

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

string子串（截取字符串）

这是一个常用的功能

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

案例：截取网址里的字段

比如：www.abc.a.asdfgghhj.com.cn

string s1 = "www.abc.a.asdfgghhj.com.cn",t;
vector<string>v;
int start = 0;
int pos = 0;
while ((pos = s1.find('.', start))!=-1)
{
 
 v.push_back(s1.substr(start, pos - start));
 start=(pos+1);
}
v.push_back(s1.substr(start, pos - start));

for (vector<string>::iterator i = v.begin(); i != v.end(); i++)
{
 cout << *i << endl;
}

string插入和删除操作

string& insert(int pos, const char* s); //插入字符串
string& insert(int pos, const string& str); //插入字符串
string& insert(int pos, int n, char c);//在指定位置插入n个字符c
string& erase(int pos, int n = npos);//删除从Pos开始的n个字符

string和c-style字符串转换

//string 转 char*
string str = "itcast";
const char* cstr = str.c_str(); //或者强转
//char* 转 string 
char* s = "itcast";
string str(s);
  • const char*可以隐式类型转换为string，反之不可以

String相关注意事项

s.at()和s[]的区别

如果[]访问越界，会直接出错
at越界 会抛出一个异常out_of_range
比如

//头：#include<stdexcept>
try
{
 s.at(100);
}
catch (out_of_range &e)
{
 cout << e.what() << endl;
}

代码中out_of_range也可以更换为exception

下标运算符返回字符的引用在重新分配内存时的错误

为了修改string字符串的内容，下标操作符[]和at都会返回字符的引用。但当字符串的内存被重新分配之后，可能发生错误.
比如：

string s = "abcdefg";
 char& a = s[2];
 char& b = s[3];

 a = '1';
 b = '2';

 cout << s << endl;
 cout << (int*)s.c_str() << endl;

 s = "pppppppppppppppppppppppp";

 //a = '1';
 //b = '2';

 cout << s << endl;
 cout << (int*)s.c_str() << endl;

案例：字母大小写转换

验证码不区分大小写时，就是全部转换为大写或者小写，然后验证。

string s1 = "abCDEfg";

 for (int i = 0; i < s1.size(); i++)
 {
  //小写转大写
  //s1[i] = toupper(s1[i]);
  s1[i] = tolower(s1[i]);//大写转小写
 }
 cout << s1 << endl;

vector容器

vector基础功能

front()//首元素
back()//末尾元素

v.rend()//首元素的前面一位的指针
v.end()//末尾元素后面一位的指针
v.begin()//首元素的指针
v.rbegin()//末尾元素的指针

insert()//中间插入
push_back()//放入数据
pop_back()//弹出数据

vector数据结构

Vector所采用的数据结构非常简单，线性连续空间，它以两个迭代器_Myfirst和_Mylast分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器_Myend指向整块连续内存空间的尾端。
为了降低空间配置时的速度成本，vector实际配置的大小可能比客户端需求大一些，以备将来可能的扩充，这边是容量的概念。换句话说，一个vector的容量永远大于或等于其大小，一旦容量等于大小，便是满载，下次再有新增元素，整个vector容器就得另觅居所。
注意：
所谓动态增加大小，并不是在原空间之后续接新空间(因为无法保证原空间之后尚有可配置的空间)，而是一块更大的内存空间，然后将原数据拷贝新空间，并释放原空间。因此，对vector的任何操作，一旦引起空间的重新配置，指向原vector的所有迭代器就都失效了。这是程序员容易犯的一个错误，务必小心。

测试vector扩展内存

vector<int> v;
for (int i = 0; i < 10; i++) {
 v.push_back(i);
 cout << v.capacity() << endl;  // v.capacity()容器的容量
}

vector常用操作代码接口

vector构造函数

vector<T> v; //采用模板实现类实现，默认构造函数
vector(v.begin(), v.end());//将v[begin(), end())区间中的元素拷贝给本身。
vector(n, elem);//构造函数将n个elem拷贝给本身。
vector(const vector &vec);//拷贝构造函数。

//例子 使用第二个构造函数 我们可以...
int arr[] = {2,3,4,1,9};
vector<int> v1(arr, arr + sizeof(arr) / sizeof(int));

vector常用赋值操作

assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
vector& operator=(const vector  &vec);//重载等号操作符
swap(vec);// 将vec与本身的元素互换。

vector大小操作

size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(int num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
resize(int num, elem);//重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长>度的元素被删除。
capacity();//容器的容量
reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。

vector数据存取操作

at(int idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range异常。
operator[];//返回索引idx所指的数据，越界时，运行直接报错
front();//返回容器中第一个数据元素
back();//返回容器中最后一个数据元素

vector插入和删除操作

insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele.
push_back(ele); //尾部插入元素ele
pop_back();//删除最后一个元素
erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素
erase(const_iterator pos);//删除迭代器指向的元素
clear();//删除容器中所有元素

案例：巧用swap收缩内存

vector<int> v;
for (int i = 0; i < 100000; i++) {
 v.push_back(i);
}

cout << "capacity:" << v.capacity() << endl;
cout << "size:" << v.size() << endl;

//此时 通过resize改变容器大小
v.resize(10);

cout << "capacity:" << v.capacity() << endl;
cout << "size:" << v.size() << endl;

//容量没有改变
vector<int>(v).swap(v);

cout << "capacity:" << v.capacity() << endl;
cout << "size:" << v.size() << endl;

核心代码vector<int>(v).swap(v);
vector<int>(v)是vector(const vector &vec) 交换的本质是指针的交换。
交换前，匿名对象（假设为x）x被拷贝构造与v相同。然后利用swap函数交换了x和v的指针。

案例：reserve预留空间，查看数据迁移次数

vector<int>v;

int num = 0;
int *p = NULL;

//v.reserve(100000); //预留空间

for (int i = 0; i < 100000; i++)
{
 v.push_back(i);
 if (p != &v[0])
 {
  p = &v[0];
  num++;
 }
}
cout << num << endl;

案例：逆序遍历

需要使用反向迭代器：reverse_iterator

vector<int>v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);

for (vector<int>::reverse_iterator i = v.rbegin(); i != v.rend(); i++)
{
 cout << *i << endl;
}

案例：如何判断迭代器是否是随机访问迭代器

下面的代码vector<int>::iterator i = v.begin();可以通过就说明可以随机访问。

vector<int>v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);

vector<int>::iterator i = v.begin();
i = i + 1;

deque容器

Vector容器是单向开口的连续内存空间，deque则是一种双向开口的连续线性空间。所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，当然，vector容器也可以在头尾两端插入元素，但是在其头部操作效率奇差，无法被接受。

Deque容器和vector容器最大的差异，
一在于deque允许使用常数项时间对头端进行元素的插入和删除操作。
二在于deque没有容量的概念，因为它是动态的以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，换句话说，像vector那样，”旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在deque身上是不会发生的。
也因此，deque没有必须要提供所谓的空间保留(reserve)功能.

虽然deque容器也提供了Random Access Iterator,但是它的迭代器并不是普通的指针，其复杂度和vector不是一个量级，这当然影响各个运算的层面。因此，除非有必要，我们应该尽可能的使用vector，而不是deque。对deque进行的排序操作，为了最高效率，可将deque先完整的复制到一个vector中，对vector容器进行排序，再复制回deque.

deque常用操作代码接口

deque构造函数

deque<T> deqT;//默认构造形式
deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身。
deque(n, elem);//构造函数将n个elem拷贝给本身。
deque(const deque &deq);//拷贝构造函数。

deque赋值操作

assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
deque& operator=(const deque &deq); //重载等号操作符 
swap(deq);// 将deq与本身的元素互换

deque大小操作

deque.size();//返回容器中元素的个数
deque.empty();//判断容器是否为空
deque.resize(num);//重新指定容器的长度为num,若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置,如果容器变短，则末尾超出容器长度的元素被删除。

deque双端插入和删除操作

push_back(elem);//在容器尾部添加一个数据
push_front(elem);//在容器头部插入一个数据
pop_back();//删除容器最后一个数据
pop_front();//删除容器第一个数据

deque数据存取

at(idx);//返回索引idx所指的数据，如果idx越界，抛出out_of_range。
operator[];//返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。
front();//返回第一个数据。
back();//返回最后一个数据

deque插入操作

insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。

deque删除操作

clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。

相关使用技巧

多种类型的迭代器（反转、只读)

反转迭代器前面已经提到

for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
	{
		//*it = 100; //报错，因为使用了只读迭代器。
		cout << *it << endl;
	}

stack容器

stack常用操作代码接口

stack构造函数

stack<T> stkT;//stack采用模板类实现， stack对象的默认构造形式： 
stack(const stack &stk);//拷贝构造函数

stack赋值操作

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

stack数据存取操作

push(elem);//向栈顶添加元素
pop();//从栈顶移除第一个元素
top();//返回栈顶元素

stack大小操作

empty();//判断堆栈是否为空
size();//返回堆栈的大小

queue容器

queue常用操作代码接口

queue构造函数

queue<T> queT;//queue采用模板类实现，queue对象的默认构造形式：
queue(const queue &que);//拷贝构造函数

queue存取、插入和删除操作

push(elem);//往队尾添加元素
pop();//从队头移除第一个元素
back();//返回最后一个元素
front();//返回第一个元素

queue赋值操作

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

queue大小操作

empty();//判断队列是否为空
size();//返回队列的大小

list容器

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
相较于vector的连续线性空间，list就显得负责许多，它的好处是每次插入或者删除一个元素，就是配置或者释放一个元素的空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素的移除，list永远是常数时间。
List和vector是两个最常被使用的容器。
List容器是一个双向链表。

  • 采用动态存储分配，不会造成内存浪费和溢出
  • 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
  • 链表灵活，但是空间和时间额外耗费较大

List迭代器

List容器不能像vector一样以普通指针作为迭代器，因为其节点不能保证在同一块连续的内存空间上。List迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取操作。所谓”list正确的递增，递减、取值、成员取用”是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取的是节点的成员。
由于list是一个双向链表，迭代器必须能够具备前移、后移的能力，所以list容器提供的是Bidirectional Iterators.
List有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效。这在vector是不成立的，因为vector的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效，甚至List元素的删除，也只有被删除的那个元素的迭代器失效，其他迭代器不受任何影响。

list容器的数据结构

ist容器不仅是一个双向链表，而且还是一个循环的双向链表。

List常用功能代码接口

list构造函数

list<T> lstT;//list采用采用模板类实现,对象的默认构造形式：
list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身。
list(n,elem);//构造函数将n个elem拷贝给本身。
list(const list &lst);//拷贝构造函数。

list数据元素插入和删除操作

push_back(elem);//在容器尾部加入一个元素
pop_back();//删除容器中最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_front();//从容器开头移除第一个元素
insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。
remove(elem);//删除容器中所有与elem值匹配的元素。

list大小操作

size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(num);//重新指定容器的长度为num，
若容器变长，则以默认值填充新位置。
如果容器变短，则末尾超出容器长度的元素被删除。
resize(num, elem);//重新指定容器的长度为num，
若容器变长，则以elem值填充新位置。
如果容器变短，则末尾超出容器长度的元素被删除。

list赋值操作

assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
list& operator=(const list &lst);//重载等号操作符
swap(lst);//将lst与本身的元素互换。

list数据的存取

front();//返回第一个元素。
back();//返回最后一个元素。

list反转和排序

注意：所有系统提供的标准算法，使用的容器提供的迭代器必须支持随机访问。不支持算计访问的迭代器的容器，内部会对应提供相应的算法的接口。

reverse();//反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素。
sort(); //list排序，默认小到大。大到小需要函数做参，如下：

默认小到大。大到小需要函数做参，如下：

bool cmp(int a,int b)
{
  return a>b;
}

自定义数据类型排序，必须制定排序类型；如下

class pe
{
public:
	pe(string na,int age):Nam(na),Ag(age){}
	string Nam;
	int Ag;
};

bool cmppe(pe&a, pe&b)
{
	return a.Ag < b.Ag;
}


void f02()
{
	list<pe>l;
	
	pe p1("AA", 10);
	pe p2("BB", 12);
	pe p3("CC", 1310);
	pe p4("DD", 1);
	pe p5("EE", 120);

	l.push_back(p1);
	l.push_back(p2);
	l.push_back(p3);
	l.push_back(p4);
	l.push_back(p5);

	for (list<pe>::iterator it = l.begin(); it != l.end(); it++)
	{
		cout << (*it).Nam << "  " << (*it).Ag << endl;
	}

	l.sort(cmppe);

	for (list<pe>::iterator it = l.begin(); it != l.end(); it++)
	{
		cout << (*it).Nam << "  " << (*it).Ag << endl;
	}
}

set和multiset容器

#include <set>set和multiset头文件一样
关联型容器，插入数据自动排序

Set的特性是。所有元素都会根据元素的键值自动被排序。Set的元素不像map那样可以同时拥有实值和键值，set的元素即是键值又是实值。Set不允许两个元素有相同的键值。
我们可以通过set的迭代器改变set元素的值吗？不行，因为set元素值就是其键值，关系到set元素的排序规则。如果任意改变set元素值，会严重破坏set组织。换句话说，set的iterator是一种const_iterator.
set拥有和list某些相同的性质，当对容器中的元素进行插入操作或者删除操作的时候，操作之前所有的迭代器，在操作完成之后依然有效，被删除的那个元素的迭代器必然是一个例外。
multiset特性及用法和set完全相同，唯一的差别在于它允许键值重复。set和multiset的底层实现是红黑树，红黑树为平衡二叉树的一种。

set容器不可以通过迭代器修改里面的值，因为默认有排序规则

set常用功能代码接口

set构造函数

set<T> st;//set默认构造函数：
mulitset<T> mst; //multiset默认构造函数: 
set(const set &st);//拷贝构造函数

set赋值操作

set& operator=(const set &st);//重载等号操作符
swap(st);//交换两个集合容器

set大小操作

size();//返回容器中元素的数目
empty();//判断容器是否为空

set插入和删除操作

insert(elem);//在容器中插入元素。
clear();//清除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(elem);//删除容器中值为elem的元素。

由于，set不可以插入相同的值。我们可以用下面的代码查看set是否成功插入

set<int>se;
	pair<set<int>::iterator,bool> pa=se.insert(10);
	cout << pa.second << endl;
	pa = se.insert(10);
	cout << pa.second << endl;

set查找操作

find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
count(key);//查找键key的元素个数,对于set来说，结果只有0和1；
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。返回队组。

关于equal_range的用法，详见下面的例子：

set<int>se;

	se.insert(10);
	se.insert(20);
	se.insert(50);
	se.insert(30);
	se.insert(40);

	pair<set<int>::iterator,set<int>::iterator> it = se.equal_range(50); //返回对组

	if (it.first!=se.end())
	{
		cout << "找到lower" << *(it.first) << endl;
	}
	else
	{
		cout << "没有找到" << endl;
	}


	if (it.second != se.end())
	{
		cout << "找到upper" << *(it.second) << endl;
	}
	else
	{
		cout << "没有找到" << endl;

利用仿函数，让set从大到小排序

class mycmp
{
public:
	bool operator()(int a, int b)
	{
		return a > b;
	}
};

void f05()
{
	//利用仿函数，让set从大到小排序
	set<int, mycmp>s;
	s.insert(10);
	s.insert(20);
	s.insert(50);
	s.insert(30);
	s.insert(40);
	for (set<int,mycmp>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << *it << endl;
	}
}

对组(pair)

对组(pair)将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的两个公有属性first和second访问。
类模板：template <class T1, class T2> struct pair.
如何创建对组?
//第一种方法创建一个对组

pair<string, int> pair1(string("name"), 20);
cout << pair1.first << endl; //访问pair第一个值
cout << pair1.second << endl;//访问pair第二个值

//第二种

pair<string, int> pair2 = make_pair("name", 30);
cout << pair2.first << endl;
cout << pair2.second << endl;
//pair=赋值
pair<string, int> pair3 = pair2;
cout << pair3.first << endl;
cout << pair3.second << endl;

map容器

Map的特性是，所有元素都会根据元素的键值自动排序。Map所有的元素都是pair,同时拥有实值和键值，pair的第一元素被视为键值，第二元素被视为实值，map不允许两个元素有相同的键值。
我们可以通过map的迭代器改变map的键值吗？答案是不行，因为map的键值关系到map元素的排列规则，任意改变map键值将会严重破坏map组织。如果想要修改元素的实值，那么是可以的。
Map和list拥有相同的某些性质，当对它的容器元素进行新增操作或者删除操作时，操作之前的所有迭代器，在操作完成之后依然有效，当然被删除的那个元素的迭代器必然是个例外。
Multimap和map的操作类似，唯一区别multimap键值可重复。
Map和multimap都是以红黑树为底层实现机制。

map常用功能代码接口

map构造函数

map<T1, T2> mapTT;//map默认构造函数: 
map(const map &mp);//拷贝构造函数

map赋值操作

map& operator=(const map &mp);//重载等号操作符
swap(mp);//交换两个集合容器

map大小操作

size();//返回容器中元素的数目
empty();//判断容器是否为空

map插入数据元素操作

map.insert(...); //往容器插入元素，返回pair<iterator,bool>
map<int, string> mapStu;
// 第一种 通过pair的方式插入对象
mapStu.insert(pair<int, string>(3, "小张"));
// 第二种 通过pair的方式插入对象
mapStu.inset(make_pair(-1, "校长"));
// 第三种 通过value_type的方式插入对象
mapStu.insert(map<int, string>::value_type(1, "小李"));
// 第四种 通过数组的方式插入值
mapStu[3] = "小刘";
mapStu[5] = "小王";

不建议使用[]访问，因为如果没有这个键值，就会自动创建

map删除操作

clear();//删除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg,end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(keyElem);//删除容器中key为keyElem的对组。

map查找操作

find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；/若不存在，返回map.end();
count(keyElem);//返回容器中key为keyElem的对组个数。对map来说，要么是0，要么是1。对multimap来说，值可能大于1。
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。

容器的使用时机

vector deque list set multiset map multimap
典型内存结构 单端数组 双端数组 双向链表 二叉树 二叉树 二叉树 二叉树
可随机存取 是 是 否 否 否 对key而言：不是 否
元素搜寻速度 慢 慢 非常慢 快 快 对key而言：快 对key而言：快
元素安插移除 尾端 头尾两端 任何位置 - - - -

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

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

  • vector与deque的比较：

    • 一：vector.at()比deque.at()效率高，比如vector.at(0)是固定的，deque的开始位置 却是不固定的。
    • 二：如果有大量释放操作的话，vector花的时间更少，这跟二者的内部实现有关。
    • 三：deque支持头部的快速插入与快速移除，这是deque的优点。

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

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

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

常用算法

函数对象（仿函数）

重载函数调用操作符的类，其对象常称为函数对象（function object），即它们是行为类似函数的对象，也叫仿函数(functor),其实就是重载“()”操作符，使得类对象可以像函数那样调用。

注意:

1.函数对象(仿函数)是一个类，不是一个函数。

2.函数对象(仿函数)重载了”() ”操作符使得它可以像函数一样调用。

分类:假定某个类有一个重载的operator()，而且重载的operator()要求获取一个参数，我们就将这个类称为“一元仿函数”（unary functor）；相反，如果重载的operator()要求获取两个参数，就将这个类称为“二元仿函数”（binary functor）。

函数对象的作用主要是什么？STL提供的算法往往都有两个版本，其中一个版本表现出最常用的某种运算，另一版本则允许用户通过template参数的形式来指定所要采取的策略。

  • 函数对象很像函数调用方式，因此也称为 仿函数
class myp
{
public:
	void operator()(int num)
	{
		cout << num << endl;
	}
};
void f01()

	myp m1;
	m1(1212);
}
  • 函数对象，超出普通函数的概念，内部可以拥有自己的状态。比如，统计打印次数
class myp2
{
public:
	int cot=0;
	void operator()(int num)
	{
		cout << num << endl;
		cot++;
	}
};
void f02()
{
	myp2 m2;
	m2(1212);
	m2(1213);
	m2(1214);
	m2(1210);
	m2(1233);

	cout << m2.cot << endl;
}
  • 函数对象可以作为函数的参数传递
void work01(myp mp, int n)
{
	mp(n);
}

void f03()
{
	work01(myp(), 100);
}


int main()
{
	f03();

	return 0;
}

总结：

1、函数对象通常不定义构造函数和析构函数，所以在构造和析构时不会发生任何问题，避免了函数调用的运行时问题。

2、函数对象超出普通函数的概念，函数对象可以有自己的状态

3、函数对象可内联编译，性能好。用函数指针几乎不可能

4、模版函数对象使函数对象具有通用性，这也是它的优势之一

谓词

谓词是指普通函数或重载的operator()返回值是bool类型的函数对象(仿函数)。如果operator接受一个参数，那么叫做一元谓词,如果接受两个参数，那么叫做二元谓词，谓词可作为一个判断式。

class GreaterThenFive
{
public:
	bool operator()(int num)
	{
		return num > 5;
	}

};
//一元谓词
void test01()
{
	vector<int> v;
	for (int i = 0; i < 10;i ++)
	{
		v.push_back(i);
	}
	
	 vector<int>::iterator it =  find_if(v.begin(), v.end(), GreaterThenFive());
	 if (it == v.end())
	 {
		 cout << "没有找到" << endl;
	 }
	 else
	 {
		 cout << "找到了: " << *it << endl;
	 }
}

//二元谓词
class MyCompare
{
public:
	bool operator()(int num1, int num2)
	{
		return num1 > num2;
	}
};

void test02()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(40);
	v.push_back(20);
	v.push_back(90);
	v.push_back(60);

	//默认从小到大
	sort(v.begin(), v.end());
	for (vector<int>::iterator it = v.begin(); it != v.end();it++)
	{
		cout << *it << " ";
	}
	cout << endl;
	cout << "----------------------------" << endl;
	//使用函数对象改变算法策略，排序从大到小
	sort(v.begin(), v.end(),MyCompare());
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

匿名函数（lambda表达式）{}

普通函数与lambda函数对比
匿名函数是许多编程语言都支持的概念，有函数体，没有函数名。
函数对象能维护状态，但语法开销大，而函数指针语法开销小，却没法保存范围内的状态。
仅展示基本使用方法

[]是该表达式的声明
()是函数的参数
{}是函数的实现

内建函数对象

需要引入头文件 #include<functional>。
STL内建了一些函数对象。分为:
算数类函数对象,关系运算类函数对象，逻辑运算类仿函数。这些仿函数所产生的对象，用法和一般函数完全相同，当然我们还可以产生无名的临时对象来履行函数功能。使用内建函数对象，需要引入头文件 #include。

  • 6个算数类函数对象,除了negate是一元运算，其他都是二元运算。
template<class T> T plus<T>//加法仿函数
template<class T> T minus<T>//减法仿函数
template<class T> T multiplies<T>//乘法仿函数
template<class T> T divides<T>//除法仿函数
template<class T> T modulus<T>//取模仿函数
template<class T> T negate<T>//取反仿函数
  • 6个关系运算类函数对象,每一种都是二元运算。
template<class T> bool equal_to<T>//等于
template<class T> bool not_equal_to<T>//不等于
template<class T> bool greater<T>//大于 //可以用于部分容器排序
template<class T> bool greater_equal<T>//大于等于
template<class T> bool less<T>//小于 
template<class T> bool less_equal<T>//小于等于
  • 逻辑运算类运算函数,not为一元运算，其余为二元运算。
template<class T> bool logical_and<T>//逻辑与
template<class T> bool logical_or<T>//逻辑或
template<class T> bool logical_not<T>//逻辑非