友情链接:C/C++系列系统学习目录


文章目录


🚀一、STL概述

STL 主要分为分为三类:

  1. algorithm(算法) - 对数据进行处理(解决问题) 步骤的有限集合
  2. container(容器) - 用来管理一组数据元素
  3. Iterator (迭代器) - 可遍历 STL 容器内全部或部分元素”的对象

容器和算法通过迭代器可以进行无缝地连接。在 STL 中几乎所有的代码都采用了模板类和模板函数的方式,这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。

STL 最早源于惠普实验室,早于 C++存在,但是 C++引入 STL 概念后,STL 就成为 C++的一部分,因为它被内建在你的编译器之内,不需要另行安装。

STL 被组织为下面的 13 个头文件:

<algorithm>
<deque>
<functional>
<iterator>
<vector>
<list><map><memory><numeric><queue><set><stack><utility>
#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class student{
public:
    student(int age, const char *name){
        this->age = age;
        strncpy(this->name, name, 64);
    }
    
    student(const student &s){
        this->age = s.age;
        strncpy(this->name, s.name, 64);
        cout<<"拷贝构造函数被调用!"<<endl;
    }
public:
    int age;
    char name[64];
};

//容器中存放对象
void demo2(){
	vector<student> v1;
	
	student s1(18, "李小美");
	student s2(19, "王大帅");
	
	v1.push_back(s1);
	v1.push_back(s2);
	
	cout<<"v1 的学生的个数:"<<v1.size()<<endl;
	
    //方式 1,下标访问
    //for(unsigned int i=0; i<v1.size(); i++){
    // cout<<v1[i].name<<": "<<v1[i].age<<endl;
    //}
   
    vector<student>::iterator it = v1.begin();
    for( ; it != v1.end(); it++){
    	cout<< (*it).name<<": "<<(*it).age <<endl;
    }
    
}
    
//容器中存放指针
void demo3(){
    vector<student *> v1;
    
    student s1(18, "李小美");
    student s2(19, "王大帅");
    
    v1.push_back(&s1);
    v1.push_back(&s2);
    
    cout<<"v1 的学生的个数:"<<v1.size()<<endl;
    //方式 1,下标访问
    //for(unsigned int i=0; i<v1.size(); i++){
    // cout<<v1[i].name<<": "<<v1[i].age<<endl;
    //}
    
    vector<student *>::iterator it = v1.begin();
    for( ; it != v1.end(); it++){
    	cout<< (**it).name<<": "<<(**it).age <<endl;
    }
    
}

void demo1(){
    //第一部分 容器
    vector<int> v1;
    
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(3);
    
    cout<<"v1 的元素个数:"<<v1.size()<<endl;
    
    cout<<"v1 中保存的元素:"<<endl;
    
    //方式 1,下标访问
    //for(unsigned int i=0; i<v1.size(); i++){
    // cout<<v1[i]<<endl;
    //}
    
    //方式 2,迭代器访问
    //第二部分 迭代器
    //1 2 3 4
    //it
    vector<int>::iterator it = v1.begin();
    for( ; it != v1.end(); it++){
    	cout<< *it <<endl;
    }
    
    //第三部分 算法
    int ncount = count(v1.begin(), v1.end(), 90);
    cout<<"v1 中数值为 90 的元素个数:"<< ncount<< endl;
}
    
void main(){
    demo3();
    
    system("pause");
    return ;
}

⛳(一)容器

在实际的开发过程中,数据结构本身的重要性完全不逊于算法的重要性,当程序中存在着对时间要求很高的部分时,数据结构的选择就显得更加重要。

试想: 一条死胡同里面停车,这样的效率会很高嘛?

【C++篇】STL标准模板库-LMLPHP

几乎可以说,任何特定的数据结构都是为了实现某种特定的算法。经典的数据结构数量有限,但是在项目实战中,我们常常重复着一些为了存放不同数据类型而实现顺序表、链表等结构而重复编写的代码,这些代码都十分相似,只是为了适应不同数据类型的变化而在细节上有所出入。STL 容器就为我们提供了这样的方便,它允许我们重复利用已有的实现构造自己的特定类型下的数据结构,通过设置一些模板,STL 容器对最常用的数据结构提供了支持,这些模板的参数允许我们指定容器中元素的数据类型,避免重复编码

常用的数据结构:数组(array) , 链表(list), (tree),(stack), 队列(queue), 集合(set),映射表(map), 根据数据在容器中的排列特性,这些数据分为序列式容器和关联式容器两种。

  • 序列式容器强调值的排序,序列式容器中的每个元素均有固定的位置,除非用删除或插入的操作改变这个位置。Vector容器、Deque容器、List容器等。

  • 关联式容器是非线性的树结构,更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系,也就是说元素在容器中并没有保存元素置入容器时的逻辑顺序。关联式容器另一个显著特点是:在值中选择一个值作为关键字key,这个关键字对值起到索引的作用,方便查找。Set/multiset容器 Map/multimap容器

细分可按C/C++帮助手册中分为:

  • 顺序容器:顺序容器实现能按顺序访问的数据结构。

  • 关联容器:关联容器实现能快速查找( O(log n) 复杂度)的数据结构。

  • 无序关联容器:无序关联容器提供能快速查找(均摊 O(1) ,最坏情况 O(n) 的复杂度)的无序(哈希)数据结构。

  • 容器适配器:容器适配器提供顺序容器的不同接口。

  • span:span 是相接的对象序列上的非占有视图,某个其他对象占有序列的存储。

span(C++20) 描述: 对象的连续序列上的无所有权视图 实现头文件:<span>

对应底层数据结构:

顺序容器

  1. array 底层数据结构是一个固定数组,是封装固定大小数组的容器。

  2. vector 底层数据结构是一个动态数组,是我们用到最多的数据结构,支持快速随机访问

  3. deque 底层数据结构为一个中央控制器和多个缓冲区,详细见STL源码剖析P146,支持首尾(中间不能)快速增删,也支持随机访问
    (deque是双端数组,vector是单端的)

  4. forward_list 底层数据结构为单向链表

  5. list 底层数据结构为双向链表,支持快速增删

关联容器

  1. set 底层数据结构为红黑树,有序,不重复
  2. map 底层数据结构为红黑树,有序,不重复
  3. multiset 底层数据结构为红黑树,有序,可重复
  4. multimap 底层数据结构为红黑树,有序,可重复

无序关联容器

  1. unordered_set(hash_set )底层数据结构为hash表,无序,不重复
  2. unordered_multiset(hash_multiset )底层数据结构为hash表,无序,可重复
  3. unordered_map(hash_map )底层数据结构为hash表,无序,不重复
  4. unordered_multimap(hash_multimap) 底层数据结构为hash表,无序,可重复

括号中的 API 已废弃不用,在某些地方还能看见,写出来以作了解。

容器适配器

  1. stack 底层一般用list或deque实现,封闭头部即可,不用vector的原因应该是容量大小有限制,扩容耗时

  2. queue 底层一般用list或deque实现,封闭头部即可,不用vector的原因应该是容量大小有限制,扩容耗时

    (stack和queue其实是适配器,而不叫容器,因为是对容器的再封装)

  3. priority_queue 的底层数据结构一般为vector为底层容器,堆heap为处理规则来管理底层容器实现

⛳(二)迭代器

迭代器也是一种类类型,嵌入在容器类中组合使用

迭代器(iterator)是一种可以遍历容器元素的数据类型。迭代器是一个变量,相当于容器和操纵容器的算法之间的中介。C++更趋向于使用迭代器而不是数组下标操作,因为标准库为每一种标准容器(如vector、map和list等)定义了一种迭代器类型,而只有少数容器(如vector)支持数组下标操作访问容器元素。可以通过迭代器指向你想访问容器的元素地址,通过*x打印出元素值。这和我们所熟知的指针极其类似。

C语言有指针,指针用起来十分灵活高效。C++语言有迭代器,迭代器相对于指针而言功能更为丰富,例如:vector,是数组实现的,也就是说,只要知道数组的首地址,就能访问到后面的元素。所以,我们可以通过访问vector的迭代器来遍历vector容器元素。List,是链表实现的,我们知道,链表的元素都存储在一段不是连续的地址空间中。我们需要通过next指针来访问下一个元素。那么,我们也可以通过访问list的迭代器来实现遍历list容器元素。

迭代器的使用:

容器都有成员begin和end,其中begin成员复制返回指向第一个元素的迭代器(用*迭代器打印出元素值),而end成员返回指向容器尾元素的下一个位置的迭代器,它是一个不存在的元素位置。

std::vector<int>::iterator it;     //it能读写vector<int>的元素
std::vector<int>::const_iterator it;//it只能读vector<int>的元素,不可以修改vector<int>中的元素

//遍历容器元素
for( it = vector.begin(); it != vector.end(); it++ )
	cout<< *it <<endl;

//逆序迭代
 for(std::vector<int>::reverse_iterator it = v.rbegin(); it!=v.rend();it++ )
    cout<<*it<<endl;

不同容器的迭代器(iterator)的功能:

代码示例(其他容器用法类似):

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	//要使用的vector容器应该位于所有定义容器语句的最后一句,应在1而不是2 
	vector<int> c;      //1
	vector<int> vector;
	                    //2
	vector.push_back(1);//插入尾部 
	vector.push_back(9);
	vector.push_back(5); 
	
	sort(vector.begin(),vector.end());
	for( int i=0; i<vector.size(); i++ )
		cout<<"sort_result: "<<vector[i]<<endl;
	
	cout<<"头部元素为:"<<vector.front()<<endl;//头部元素 
	cout<<"尾部元素为:"<<vector.back()<<endl;//尾部元素
	cout<<"容器尺寸大小为:"<<vector.size()<<endl;//容器尺寸大小
	 
	vector.front()=11;//修改容器头部元素值 
	vector.back()= 15;//修改容器尾部元素值
	
	cout<<"修改后头部元素为:"<<vector.front()<<endl;//头部元素
	vector.pop_back();//删除尾部元素
	 
	cout<<"修改+删除后尾部元素为:"<<vector.back()<<endl;//尾部元素
	vector.push_back(16);
	
	for( int i=0; i<vector.size(); i++ )
		cout<<"用数组输出vector["<<i<<"]:"<<vector[i]<<endl;
	
	std::vector<int>::const_iterator it;
	for( it = vector.begin(); it != vector.end(); it++ )
		cout<<"用迭代器输出:"<<*it<<endl;
	
	vector.insert(vector.begin(),100);//插入开始位置 
	for( int i=0; i<vector.size(); i++ )
		cout<<"insert_result:"<<vector[i]<<endl;
	cout<<"头部元素为:"<<vector.front()<<endl;
	
	return 0;
}

🚀二、常见容器的使用

⛳(一)vector容器

🎈1.概念

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

  • vector 可以随机存取元素,支持索引值直接存取, 用[]操作符或 at()方法对元素进行操作

【C++篇】STL标准模板库-LMLPHP

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

【C++篇】STL标准模板库-LMLPHP

🎈2.vector对象的构造

vector 采用模板类实现,vector 对象的默认构造形式:

vector<T> vecT;
//使用默认构造函数
vector<int> v1; //一个存放 int 的 vector 容器
vector<float> v2; //一个存放 float 的 vector 容器
vector<student> v2; //一个存放 student 的 vector 容器

//使用带参构造函数
vector(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。注意该区间是左闭右开的区间
vector(n,elem); //构造函数将 n 个 elem 拷贝给本身
vector(const vector &v1); //拷贝构造函数

vector<int> v2(10);    //元素大小为0
vector<int> v2(10, 666);  //10个666
vector<int> v3(v2.begin()+3, v2.end());
vector<int> v3(v2);

用法:

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

void demo1(){
    //vector 对象的默认构造
    //默认构造函数 元素个数为 0, 所占内存空间为 0
    /*
    vector<int> v1;
    //vector<float> v2;
    
    cout<<"v1 的元素个数: "<<v1.size()<<endl;
    cout<<"v1 容器的大小:"<<v1.capacity()<<endl;
    
    //当我们使用 vector 的默认构造函数时,切记,不能直接通过下标去访问
    //v1[0]=1;
    
    v1.push_back(1);
    cout<<"尾部插入 1 个元素后:"<<endl;
    cout<<"v1 的元素个数:"<<v1.size()<<endl;
    cout<<"v1 容器的大小:"<<v1.capacity()<<endl;
    
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    
    cout<<"尾部插入 5 个元素后:"<<endl;
    cout<<"v1 的元素个数:"<<v1.size()<<endl;
	cout<<"v1 容器的大小:"<<v1.capacity()<<endl;
    */
    
    //vector 带参构造函数
    //vector<int> v2(10); //构造时就分配空间,同时插入 10 个元素,元素大小为 0
    vector<int> v2(10, 666);
    //vector<int> v3(v2);
    //vector<int> v3(v2.begin()+3, v2.end());
    int test[]={1, 2, 3, 4, 5};
    vector<int> v3(test, test+2);
    
    
    cout<<"v2 的元素个数:"<<v2.size()<<endl;
    cout<<"v2 容器的大小:"<<v2.capacity()<<endl;
    
    cout<<"v2 调用 assign 后:"<<endl;
    cout<<"v2 的元素个数:"<<v2.size()<<endl;
    cout<<"v2 中存储的元素是: "<<endl;
    for(int i=0; i<v2.size(); i++){
    	cout<<v2[i]<<endl;
    }
    
    cout<<"v3 中存储的元素是: "<<endl;
    for(int i=0; i<v3.size(); i++){
    	cout<<v3[i]<<endl;
    }
}
    
void main(){

    demo1();
    
    system("pause");
    return ;
}

🎈3.vector对象的相关接口

(1)vector的赋值

v2.assign(2, 888);//第一种玩法 改变原来 vector 中的元素个数和值
v2.assign(v3.begin(), v3.end());//第二种玩法,使用迭代器重新赋值

int test1[]={1, 2, 3, 4, 5};
v2.assign(test1, test1+3);//第三种玩法,使用指针赋值
v2 = v3;//第四种玩法,赋值运算

(2)vector的大小

vector.size(); //返回容器中元素的个数
vector.empty(); //判断容器是否为空
vector.resize(num); //重新指定容器的长度为 num,若容器变长,则以默认值(0)填充新位置。如果容器变短,则末尾超出容器长度的元素被删除
vector.resize(num, elem); //重新指定容器的长度为 num,若容器变长,则以 elem值填充新位置。如果容器变短,则末尾超出容器长度的元素被删除
vector.capacity(); //根据该方法内部提供的算法自动扩容,返回容器的大小

(3)vector 末尾的添加移除操作

v2.push_back(1); //在容器尾部加入一个元素
v2.pop_back(); //移除容器中最后一个元素

(4)vector 的数据存取

v2[0] = 100; //第一 使用下标操作
v2.at(2) = 100; //第二 使用 at 方法 
v2.front() 和 v2.back() //第三 接口返回的引用 (front返回第一个元素的引用,back返回最后一个元素的引用)
//注意: 第一和第二种方式必须注意越界

(5)vector 的插入

注意:pos是指向某个位置的迭代器

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

(6)vector 的删除

除了begin和end还有rbegin和rend,就是反过来的,++操作就是往前。–操作就是往后

//1. 把整个 vector 都干掉,元素个数清0,但空间仍然不变
v2.clear();
cout<<"调用 v2.clear() 后"<<endl;

//2.干掉单个元素
v2[1] = 888;
v2.erase(v2.begin()+1);

//3. 干掉多个元素,同样是左闭右开
v2.erase(v2.begin(), v2.begin()+3);

⛳(二)deque容器

🎈1.概念

deque 是“double-ended queue”的缩写,和 vector 一样都是 STL 的容器,唯一不同的是:deque 是双端数组,而 vector 是单端的。

【C++篇】STL标准模板库-LMLPHP

Deque 特点:

  • deque 在接口上和 vector 非常相似,在许多操作的地方可以直接替换。
  • deque 也可以随机存取元素(支持索引值直接存取,用[]操作符或 at()方法)
  • deque 头部和尾部添加或移除元素都非常快速, 但是在中部安插元素或移除元素比较费时。(vector头部插入元素也费时)

使用时,包含头文件:#include

🎈2.deque对象的构造

deque 也是采用模板类实现。deque 对象的默认构造形式:

deque<T> deqT
//默认构造
deque <int> deqInt; //存放 int 的 deque 容器。
deque <float> deqFloat; //存放 float 的 deque 容器。
deque <student> deqStu; //存放 student 的 deque 容器

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

//deque 对象的带参数构造
deque(beg,end); //方式 1:构造函数将[beg, end)区间中的元素拷贝给本身。
deque(n,elem); //方式 2:构造函数将 n 个 elem 拷贝给本身。
deque(const deque &deq); //方式 3:拷贝构造函数。

用法:

deque<int> deqIntA;
deqIntA.push_back(1);
deqIntA.push_back(2);
deqIntA.push_back(3);
deqIntA.push_back(4);

deque<int> deqIntB(deqIntA.begin(),deqIntA.end()); //1 2 3 4,使用了迭代器
deque<int> deqIntC(8, 666); //8 8 8 8 8
deque<int> deqIntD(deqIntA); //1 2 3 4

🎈3.deque对象的相关接口

(1)deque 头部和末尾的添加移除操作

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

//例如:
deque<int> deqIntA;
deqIntA.push_back(1);
deqIntA.push_back(2);
deqIntA.push_back(3);
deqIntA.push_back(4);
deqIntA.push_back(5);
deqIntA.push_back(6);
deqIntA.pop_front();
deqIntA.pop_front();
deqIntA.push_front(7);
deqIntA.push_front(8);
deqIntA.pop_back();
deqIntA.pop_back();
//deqIntA 中剩余元素: 8 7 3 4

(2)deque 的数据存取

deqIntA[0] = 100; //第一 使用下标操作
deqIntA.at(2) = 100; //第二 使用 at 方法
deqIntA.front() 和 deqIntA.back() //第三 接口返回的引用
//注意: 第一和第二种方式必须注意越界,和vector也一样,支持随机访问
    
//例如:
deque<int> deqIntA;
deqIntA.push_back(1);
deqIntA.push_back(2);
deqIntA.push_back(3);
deqIntA.push_back(4);
deqIntA.push_back(5);

int i1 = deqIntA.at(0); //i1 = 1
int i2 = deqIntA[1]; //i2 = 2
deqIntA.at(0) = 666; //第一个元素改成 666
deqIntA[1] = 888; //第二个元素改成 888

int iFront = deqInt.front(); //666
int iBack = deqInt.back(); //5
deqInt.front() = 888; //第一个元素改成 888
deqInt.back() = 666; //最后一个元素改成 66

(3)deque 与迭代器

deque.begin(); //返回容器中第一个元素的迭代器。
deque.end(); //返回容器中最后一个元素之后的迭代器。
deque.rbegin(); //返回容器中倒数第一个元素的迭代器。
deque.rend(); //返回容器中倒数最后一个元素之后的迭代器。
deque.cbegin(); //返回容器中第一个元素的常量迭代器。
deque.cend(); //返回容器中最后一个元素之后的常量迭代器

//例如:
deque<int> deqIntA;
deqIntA.push_back(1);
deqIntA.push_back(2);
deqIntA.push_back(3);
deqIntA.push_back(4);
deqIntA.push_back(5);

//普通迭代器
for(deque<int>::iterator it = deqIntA.begin(); it!=deqIntA.end(); ++it){
    (*it)++; //*it++ (*it)++
    cout<<*it;
    cout<<" ";
}

//常量迭代器
deque<int>::const_iterator cit = deqIntA.cbegin();
    for( ; cit!=deqIntA.cend(); cit++){
    cout<<*cit;
    cout<<" ";
}

//逆转的迭代器
for(deque<int>::reverse_iterator rit=deqIntA.rbegin(); rit!=deqIntA.rend();++rit){
    cout<<*rit;
    cout<<" ";
}

(4)deque 的赋值

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

//例如:
deque<int> deqIntA,deqIntB,deqIntC,deqIntD;
deque<int> deqIntA;
deqIntA.push_back(1);
deqIntA.push_back(2);
deqIntA.push_back(3);
deqIntA.push_back(4);
deqIntA.push_back(5);

deqIntB.assign(deqIntA.begin(),deqIntA.end());// 1 2 3 4 5
deqIntC.assign(4,888); //888 888 888 888
deqIntD = deqIntA; //1 2 3 4 5
deqIntC.swap(deqIntD); //互换

(5)deque的大小

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

//例如:
deque<int> deqIntA;
deqIntA.push_back(1);
deqIntA.push_back(2);
deqIntA.push_back(3);
deqIntA.push_back(4);
deqIntA.push_back(5);

int iSize = deqIntA.size(); //5

deqIntA.resize(7); //1 2 3 4 5 0 0
deqIntA.resize(8,1); //1 2 3 4 5 0 0 1
deqIntA.resize(2); //1 2

(6)deque的插入

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

//例如:
deque<int> deqIntA;
deque<int> deqIntB;
deqIntA.push_back(1);
deqIntA.push_back(2);
deqIntA.push_back(3);
deqIntA.push_back(4);
deqIntB.push_back(11);
deqIntB.push_back(12);
deqIntB.push_back(13);
deqIntB.push_back(14);

deqIntA.insert(deqIntA.begin(), 0); // {0,1,2,3,4}
deqIntA.insert(deqIntA.begin()+1, 2, 88); //{0,88,88,1,2,3,4}
deqIntA.insert(deqIntA.begin(), deqIntB.rbegin(),deqIntB.rend());//{11,12,13,14,0,88,88,1,2,3,4}

for(deque<int>::iterator it = deqIntA.begin(); it!=deqIntA.end();++it){
    cout<<*it;
    cout<<" ";
}

(7)deque的删除

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

//例如:
deque<int> deqIntA;
deqIntA.push_back(1);
deqIntA.push_back(2);
deqIntA.push_back(3);
deqIntA.push_back(4);
deqIntA.push_back(5);

//方式一 单独使用擦除的接口
//deqIntA.erase(deqIntA.begin()+1); //干掉第二个元素 {1,3,4,5}
//deqIntA.erase(deqIntA.begin()+1, deqIntA.begin()+3);// 干掉 3 和4, 剩下{1, 5}
//deqIntA.clear(); //干掉所有的元素

//方式二 使用迭代器遍历删除
for(deque<int>::iterator it = deqIntA.begin(); it!=deqIntA.end();){
    if(*it == 4){
    	it = deqIntA.erase(it);  
    }else {
        cout<<*it;
        cout<<" ";
        it++;  
    }
}

这里需要注意一点:it++不能放在循环条件中:

  • 漏掉元素的问题:比如[1,2,3,3,3,5,6] 要删除3 ,如果你把第一个3删掉后,迭代器执行++他就会忽略第二个3,导致删除不彻底。如果放在循环条件中,erase后就会递增导致漏掉元素
  • 程序崩溃的问题:比如 [1,2,5,6,5,6,3] 要删除3,删掉后此时迭代器就是指向的end位置(最后一个元素的下一个位置),但是循环提结束执行++操作,导致内存越界,出现问题。

⛳(三)list容器

🎈1.概念

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

【C++篇】STL标准模板库-LMLPHP

List 特点:

  • list 不可以随机存取元素,所以不支持 at.(position)函数与[]操作符。可以对其迭代器执行++,但是不能这样操作迭代器:it+3(因为不连续,不支持随机访问)
  • vector是数组,list是链表,vector的内存空间是预先分配好的,但list并没有,所以vector有capacity()方法,而list并没有

使用时包含 #include <list>

🎈2.list对象的构造

list 同样采用模板类实现,对象的默认构造形式:list<T> listT; 如:

//默认构造
list<int> lstInt; //定义一个存放 int 的 list 容器。
list<float> lstFloat; //定义一个存放 float 的 list 容器。
list<string> lstString; //定义一个存放 string 的 list 容器
//注意:尖括号内还可以设置指针类型或自定义类型。

//带参构造
list(beg,end); //方式一:将[beg, end)区间中的元素拷贝给本身。
list(n,elem); //方式二:构造函数将 n 个 elem 拷贝给本身。
list(const list &lst); //方式三:拷贝构造函数。

//例如:
list<int> lstInt1;
lstInt1.push_back(1);
lstInt1.push_back(2);
lstInt1.push_back(3);

list<int> lstInt2(lstInt1.begin(),lstInt1.end()); //1 2 3
list<int> lstInt3(5,8); //8 8 8 8 8
list<int> lstInt4(lstIntA); //1 2 3

🎈3.list对象的相关接口

(1)list 头尾的添加移除操作

list.push_back(elem); //在容器尾部加入一个元素
list.pop_back(); //删除容器中最后一个元素
list.push_front(elem); //在容器开头插入一个元素
list.pop_front(); //从容器开头移除第一个元素

//例如:
list<int> lstInt;
lstInt.push_back(1);
lstInt.push_back(2);
lstInt.push_back(3);
lstInt.push_back(4);
lstInt.push_back(5);
lstInt.pop_front();
lstInt.pop_front();
lstInt.push_front(11);
lstInt.push_front(12);
lstInt.pop_back();
lstInt.pop_back();
// lstInt {12,11, 3}

(2)list 的数据存取(只允许上一种头尾添加的操作)

//不支持at和[]方法
list.front(); //返回第一个元素。
list.back(); //返回最后一个元素。

//例如:
list<int> lstInt;
lstInt.push_back(1);
lstInt.push_back(2);
lstInt.push_back(3);
lstInt.push_back(4);
lstInt.push_back(5);

int iFront = lstInt.front(); //1
int iBack = lstInt.back(); //5
lstInt.front() = 11; //11
lstInt.back() = 19; //19

(3)list 与迭代器

list.begin(); //返回容器中第一个元素的迭代器。
list.end(); //返回容器中最后一个元素之后的迭代器。
list.rbegin(); //返回容器中倒数第一个元素的迭代器。
list.rend(); //返回容器中倒数最后一个元素的后面的迭代器。
list.cbegin(); //返回容器中第一个元素的常量迭代器。
list.cend(); //返回容器中最后一个元素之后的常量迭代器

//例如:
list<int> lstInt;
lstInt.push_back(1);
lstInt.push_back(3);
lstInt.push_back(5);
lstInt.push_back(7);
lstInt.push_back(9);

for (list<int>::iterator it=lstInt.begin(); it!=lstInt.end(); ++it)
{
    cout << *it;
    cout << " ";
}

for (list<int>::reverse_iterator rit=lstInt.rbegin(); rit!=lstInt.rend(); ++rit)
{
    cout << *rit;
    cout << " ";
}

(4)list 的赋值

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

//例如:
llist<int> lstIntA,lstIntB,lstIntC,lstIntD;
lstIntA.push_back(1);
lstIntA.push_back(3);
lstIntA.push_back(5);
lstIntA.push_back(7);
lstIntA.push_back(9);

lstIntB.assign(lstIntA.begin(),lstIntA.end()); //1 3 5 7 9
lstIntB.assign(++lstIntA.begin(),--lstIntA.end()); //3 5 7

lstIntC.assign(5,8); //8 8 8 8 8
lstIntD = lstIntA; //1 3 5 7 9
lstIntC.swap(lstIntD); //互换

(5)list 的大小

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

//例如:
list<int> lstIntA;
lstIntA.push_back(1);
lstIntA.push_back(2);
lstIntA.push_back(3);
	
if (!lstIntA.empty())
{
    int iSize = lstIntA.size(); //3
    lstIntA.resize(5); //1 2 3 0 0
    lstIntA.resize(7,1); //1 2 3 0 0 1 1
    lstIntA.resize(5); //1 2 3 0 0
}

(6)list 的插入

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

//例如:
list<int> listA;
list<int> listB;

listA.push_back(1);
listA.push_back(2);
listA.push_back(3);
listA.push_back(4);
listA.push_back(5);

listB.push_back(11);
listB.push_back(12);
listB.push_back(13);
listB.push_back(14);

listA.insert(listA.begin(), -1); //{-1, 1, 2, 3, 4, 5}
listA.insert( ++listA.begin(), 2, -2); //{-1, -2, -2, 1, 2, 3, 4, 5}
listA.insert(listA.begin() , listB.begin() , listB.end()); //{11, 12, 13,14, -1, -2, -2, 1, 2, 3, 4, 5}

for(list<int>::iterator it = listA.begin(); it!=listA.end(); it++){
	cout<< *it<<endl;
}

(7)list 的删除

list.clear(); //移除容器的所有数据
list.erase(beg,end); //删除[beg,end)区间的数据,返回下一个数据的位置。
list.erase(pos); //删除 pos 位置的数据,返回下一个数据的位置。
lst.remove(elem); //删除容器中所有与 elem 值匹配的元素。

//例如:
//list 删除元素
list<int> listA;

listA.push_back(1);
listA.push_back(2);
listA.push_back(3);
listA.push_back(4);
listA.push_back(5);

//erase 的用法
list<int>::iterator itBegin = listA.begin();
++ itBegin;
list<int>::iterator itEnd = listA.begin();
++ itEnd;
++ itEnd;
++ itEnd;
listA.erase(itBegin,itEnd);//此时容器 lstInt 包含按顺序的 1, 4, 5 三个元素。

listA.erase(listA.begin());//此时容器 lstInt 包含按顺序的 4, 5 三个元素。
listA.push_back(4); // 4, 5, 4
listA.insert(listA.end(), 5, 4); //4, 5, 4, 4, 4, 4, 4, 4
/*remove 删除元素*/
//方式一 直接调用 remove 方法
//listA.remove(4);

//方式二 遍历然后逐个删除
for(list<int>::iterator it=listA.begin(); it!=listA.end(); ){
    if(*it == 4){
    	it =listA.erase(it); //相当于执行了++
    }else {
    	it++;
    }
}

for (list<int>::iterator it=listA.begin(); it!=listA.end(); ++it)
{
    cout << *it;
    cout << " ";
}

(8)list 的反序排列

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

//例如:
list<int> listA;
listA.push_back(1);
listA.push_back(2);
listA.push_back(3);
listA.push_back(4);
listA.push_back(5);

listA.reverse(); //5, 4, 3, 2, 1

⛳(四)set和multiset容器

🎈1.概念

set 和 multiset 是一个集合容器,其中 set 所包含的元素是唯一的,集合中的元素按一定的顺序排列。set 采用红黑树变体的数据结构实现,红黑树属于平衡二叉树。在插入操作和删除操作上比 vector 快。在 n 个数中查找目标数的效率是 log2n

红黑树定义 是每个节点都带有颜色属性(颜色为红色或黑色)的自平衡二叉查找树,

  • 满足下列性质:
  • 节点是红色或黑色;
  • 根节点是黑色;
  • 所有叶子节点都是黑色节点(NULL);\
  • 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
  • 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

【C++篇】STL标准模板库-LMLPHP

Set multiset 特点

  • set 中元素插入过程是按排序规则插入,所以不能指定插入位置。
  • set 不可以直接存取元素。(不可以使用 at.(pos)与[]操作符)。

multiset与set的区别:

  • set支持唯一键值,每个元素值只能出现一次;而multiset中同一值可以出现多次
  • 不可以直接修改set或multiset容器中的元素值,因为该类容器是自动排序的。
  • 如果希望修改一个元素值,必须先删除原有的元素,再插入新的元素
#include <set>
#include <iostream>
#include <functional>
#include <algorithm>

using namespace std;

int main(void) {

    set<int> setInt;
    
    multiset<int> msetInt;
    multiset<int> msetInt1(msetInt.begin(), msetInt.end());
    
    for(int i=0; i<10; i++){
    	msetInt.insert(100-i);
    }
    
    //set 不允许插入相同的元素,而 multiset 是支持插入多个相同元素的.
    msetInt.insert(99);
    multiset<int>::iterator it = msetInt.begin();
    
    for( ; it!=msetInt.end(); it++){
        cout<<*it;
        cout<<" ";
    }
    cout<<endl;
    system("pause");
    return 0;
}

🎈2.set和multiset对象的构造

set/multiset 对象的默认构造

set<int> setInt; //一个存放 int 的 set 容器。
set<float> setFloat; //一个存放 float 的 set 容器。
set<string> setString; //一个存放 string 的 set 容器。
multiset<int> mulsetInt; //一个存放 int 的 multi set 容器。
multiset<float> multisetFloat; //一个存放 float 的 multi set 容器。
multiset<string> multisetString; //一个存放 string 的 multi set 容器。

Set/multiset 对象的带参构造函数

set(beg,end); //将[beg, end)区间中的元素拷贝给本身。
set(const set &s); //拷贝构造函数。
multiset(beg,end); //将[beg, end)区间中的元素拷贝给本身。
multiset(const multiset &s); //拷贝构造函数。

set 对象的拷贝构造与赋值

set(const set &st); //拷贝构造函数
set& operator=(const set &st); //重载等号操作符
set.swap(st); //交换两个集合容器

//例如
setIntA.insert(5);
set<int> setIntA;
setIntA.insert(1);
setIntA.insert(2);
setIntA.insert(3);
setIntA.insert(4);

set<int> setIntB(setIntA); //1 2 3 4 5

set<int> setIntC;
setIntC = setIntA; //1 2 3 4 5

setIntC.insert(6); //1 2 3 4 5 6
setIntC.swap(setIntA); //交换

🎈3.set和multiset对象的相关接口

set 的插入和 pair 的用法

  • pair 表示一个对组,它将两个值视为一个单元,把两个值捆绑在一起。
  • pair<T1,T2>用来存放的两个值的类型,可以不一样,也可以一样,如 T1 为 int,T2 为float。T1,T2 也可以是自定义类。
  • pair.first 是 pair 里面的第一个值,是 T1 类型。pair.second 是 pair 里面的第二个值,是 T2 类型。
set<int> setInt;

//setInt.insert(i);返回一个对组
for(int i=5; i>0; i--){
	pair<set<int>::iterator, bool> ret = setInt.insert(i);
    if(ret.second){
    	cout<<"插入 "<<i<<" 成功!"<<endl;
    }else {
    	cout<<"插入 "<<i<<" 失败!"<<endl;
    }
}

set 与迭代器

set.insert(elem); //在容器中插入元素。
set.begin(); //返回容器中第一个数据的迭代器。
set.end(); //返回容器中最后一个数据之后的迭代器。
set.rbegin(); //返回容器中倒数第一个元素的迭代器。
set.rend(); //返回容器中倒数最后一个元素的后面的迭代器。

set<int> setInt;
setInt.insert(3);
setInt.insert(4);
setInt.insert(1);
setInt.insert(5);
setInt.insert(2)

//顺序输出 1 2 3 4 5
for(set<int>::iterator it=setInt.begin(); it!=setInt.end(); ++it)
{
    int elem = *it;
    cout << elem; //或直接使用 cout << *it
}

set/multiset 的大小

  • set.size(); //返回容器中元素的数目
  • set.empty();//判断容器是否为空
  • 注意事项:它们没有 resize 方法
set<int> setIntA;
setIntA.insert(3);
setIntA.insert(1);
setIntA.insert(7);
setIntA.insert(5);
setIntA.insert(9);

if (!setIntA.empty())
{
	int iSize = setIntA.size(); //5
}

set/multiset 的删除

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

//删除区间内的某个或某些元素
setInt 是用 set<int>声明的容器,假设它内部现已包含按顺序的 1, 2, 3, 4, 5, 6 元素。
set<int>::iterator itBegin=setInt.begin();
++ itBegin;
set<int>::iterator itEnd=setInt.begin();
++ itEnd;
++ itEnd;
++ itEnd;
setInt.erase(itBegin,itEnd);
//此时容器 setInt 包含按顺序的 1, 4, 5, 6 四个元素。

//删除容器中第一个元素
setInt.erase(setInt.begin()); //4, 5, 6

//删除容器中值为 5 的元素
setInt.erase(5); //4, 6

//删除 setInt 的所有元素
setInt.clear(); //容器为空

set/multiset 的查找

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 中。

//例如
set<int> setInt;
setInt.insert(1);
setInt.insert(2);
setInt.insert(3);
setInt.insert(4);
setInt.insert(5);

set<int>::iterator it1 = setInt.find(4);
int elem1 = *it1; //elem1 == 4
int iCount = setInt.count(3); //iCount == 1

set<int>::iterator it2 = setInt.lower_bound(3);
set<int>::iterator it3 = setInt.upper_bound(3);
int elem2 = *it2; //i2 == 3
int elem3 = *it3; //i3 == 4

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

⛳(五)map和multimap容器

🎈1.概念

map 是标准的关联式容器,一个 map 里存储的元素是一个键值对序列,叫做(key,value)键值对。它提供基于 key 快速检索数据的能力。

  • map 中 key 值是唯一的。集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入,所以不能指定插入位置。
  • map 底层的具体实现是采用红黑树变体的平衡二叉树的数据结构。在插入操作、删除和检索操作上比 vector 快很多。
  • map 可以直接存取 key 所对应的 value,支持[]操作符,如 map[key]=value。
  • #include

multimap map 的区别

map 支持唯一键值,每个键只能出现一次;而 multimap 中相同键可以出现多次。multimap不支持[]操作符。

#include <map>
#include <iostream>
#include <functional>
#include <algorithm>
#include <string>

using namespace std;

int main(void) {
	multimap<int, string> mapStu;
	
	mapStu.insert(pair<int, string>(1, "张三"));
	mapStu.insert(pair<int, string>(2, "李四"));
	mapStu.insert(pair<int, string>(3, "王五"))
	
	//multimap 不支持[]操作,map 支持
	//mapStu[4] = "赵六";

	//multimap 支持相同的 key 插入
	mapStu.insert(pair<int, string>(3, "小王五"));

    for(multimap<int, string>::iterator it=mapStu.begin();it!=mapStu.end(); it++){
        cout<<"key: "<<(*it).first << " value: "<<(*it).second <<endl;
    }
    
    system("pause");
	return 0;
}

🎈2.map和multimap对象的构造

map/multimap 对象的默认构造

map/multimap 采用模板类实现,对象的默认构造形式:
map<T1,T2> mapTT;
multimap<T1,T2> multimapTT;
//如:
map<int, char> mapA;
map<string,float> mapB;
//其中 T1,T2 还可以用各种指针类型或自定义类型

map multimap 对象的带参数构造

map(beg,end); //方式一:将[beg, end)区间中的元素拷贝给本身。
map(const map &mapObject); //方式二:拷贝构造函数

map 的插入与迭代器

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

//map 中插入元素的四种方式:
假设 map<int, string> mapStu;
方式一、通过 pair 的方式插入对象
	mapStu.insert( pair<int,string>(1,"张三") );
方式二、通过 pair 的方式插入对象
	mapStu.inset(make_pair(2, “李四”));
方式三、通过 value_type 的方式插入对象
	mapStu.insert( map<int,string>::value_type(3,"王五") );
方式四、通过数组的方式插入值
    mapStu[4] = "赵六";
    mapStu[5] = “小七";
  • 前三种方法,采用的是 insert()方法,该方法返回值为 pair<iterator,bool>
  • 第四种方法非常直观,但碰到相同的键时会进行覆盖操作。比如插入 key 为 4 的键值时,先在 mapStu 中查找主键为 4 的项,若不存在,则将一个键为 4,值为默认初始化值的对组插入到 mapStu 中,然后再将值修改成“赵六”。若发现已存在 4 这个键,则修改这个键对应的 value。
  • string strName = mapStu[8]; //取值操作或插入操作
  • 只有当 mapStu 存在 8 这个键时才是正确的取操作,否则会自动插入一个实例,键为 8,值为默认构造时的初始化值。

迭代器

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

🎈3.map和multimap对象的相关接口

map/multimap 排序

map<T1,T2,less<T1> > mapA; //该容器是按键的升序方式排列元素。未指定函数对象,默认采用 less<T1>函数对象。
map<T1,T2,greater<T1>> mapB; //该容器是按键的降序方式排列元素。
less<T1>与 greater<T1> 可以替换成其它的函数对象 functor。
可编写自定义函数对象以进行自定义类型的比较,使用方法与 set 构造时所用的函数对象一样

map 对象的拷贝构造与赋值

map(const map &mp); //拷贝构造函数
map& operator=(const map &mp);//重载等号操作符
map.swap(mp); //交换两个集合容器

//例如:
map<int, string> mapA;
mapA.insert(pair<int,string>(2, "李四"));
mapA.insert(pair<int,string>(1, "张三"));
mapA.insert(pair<int,string>(3, "王五"));
mapA.insert(pair<int,string>(4, "赵六"));

map<int ,string> mapB(mapA); //拷贝构造,此时 mapB 和 mapA 中元素一致

map<int, string> mapC;
mapC = mapA; //赋值,此时 mapC 和 mapA 中元素一致

mapC[3] = "老张"; //mapC 中,此时包含 张三, 李四, 老张, 赵六
mapC.swap(mapA); //mapA 和 mapC 交换

⛳(六)queue容器

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

  • 默认情况下 queue 是利用 deque 容器实现的一种容器。
  • 它只允许在队列的前端(front)进行删除操作,而在队列的后端(back)进行插入操作
  • #include <queue>

⛳(七)stack容器

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

  • stack 是基于 deque 容器而实现的容器。
  • #include <stack>

⛳(八)array容器(C++11)新增

  • array 是将元素置于一个固定数组中加以管理的容器。
  • array 可以随机存取元素,支持索引值直接存取, 用[]操作符或 at()方法对元素进行操作,也可以使用迭代器访问
  • 不支持动态的新增删除操作
  • array 可以完全替代 C 语言中的数组,使操作数组元素更加安全!

🚀三、容器与类

再看我们开篇提到的代码:

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class student{
public:
    student(int age, const char *name){
        this->age = age;
        strncpy(this->name, name, 64);
    }
    
    student(const student &s){
        this->age = s.age;
        strncpy(this->name, s.name, 64);
        cout<<"拷贝构造函数被调用!"<<endl;
    }
public:
    int age;
    char name[64];
};

//容器中存放对象
void demo2(){
	vector<student> v1;
	
	student s1(18, "李小美");
	student s2(19, "王大帅");
	
	v1.push_back(s1);
	v1.push_back(s2);
	
	cout<<"v1 的学生的个数:"<<v1.size()<<endl;
	
    //方式 1,下标访问
    //for(unsigned int i=0; i<v1.size(); i++){
    // cout<<v1[i].name<<": "<<v1[i].age<<endl;
    //}
   
    vector<student>::iterator it = v1.begin();
    for( ; it != v1.end(); it++){
    	cout<< (*it).name<<": "<<(*it).age <<endl;
    }
    
}
    
//容器中存放指针
void demo3(){
    vector<student *> v1;
    
    student s1(18, "李小美");
    student s2(19, "王大帅");
    
    v1.push_back(&s1);
    v1.push_back(&s2);
    
    cout<<"v1 的学生的个数:"<<v1.size()<<endl;
    //方式 1,下标访问
    //for(unsigned int i=0; i<v1.size(); i++){
    // cout<<v1[i].name<<": "<<v1[i].age<<endl;
    //}
    
    vector<student *>::iterator it = v1.begin();
    for( ; it != v1.end(); it++){
    	cout<< (**it).name<<": "<<(**it).age <<endl;
    }
    
}

void demo1(){
    //第一部分 容器
    vector<int> v1;
    
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(3);
    
    cout<<"v1 的元素个数:"<<v1.size()<<endl;
    
    cout<<"v1 中保存的元素:"<<endl;
    
    //方式 1,下标访问
    //for(unsigned int i=0; i<v1.size(); i++){
    // cout<<v1[i]<<endl;
    //}
    
    //方式 2,迭代器访问
    //第二部分 迭代器
    //1 2 3 4
    //it
    vector<int>::iterator it = v1.begin();
    for( ; it != v1.end(); it++){
    	cout<< *it <<endl;
    }
    
    //第三部分 算法
    int ncount = count(v1.begin(), v1.end(), 90);
    cout<<"v1 中数值为 90 的元素个数:"<< ncount<< endl;
}
    
void main(){
    demo3();
    
    system("pause");
    return ;
}
  1. 首先注意一点:所有容器提供的都是“value语意”而非“reference语意”。容器内进行元素的安插操作时,内部实施的是拷贝操作,置于容器内。因此STL容器的每一个元素都必须能够拷贝

  2. 基于第一点,我们在数据类型为普通类类型的情况下使用pushback方法时,都将调用元素类的拷贝构造函数,vector存的是其副本,当vector走出生存期时(),会自动调用其中每个元素的析构函数。删除元素时也会调用析构函数

  3. 以默认构造函数的方式创建一个容器对象时,容器的元素个数以及空间大小都为0,但是当我们以带参构造函数创建对象时:

    //构造时就分配空间,表示将10个Student默认对象拷贝给本身,那么会创建10个Student对象,会调用10次Student默认构造函数(直接存进去,不会调用拷贝构造函数存副本)
    vector<Student> v2(10); 
    
    //这种会调用拷贝构造函数存副本,因为表示将10个s给v2,会调用 Student 的拷贝构造函数来初始化 10 个元素,都是值传递
    Student s;
    vector<Student> v2(10, s); 
    
  4. 当我们用第3点中的带参构造函数初始化容器后,或者在某些已经存了一些类对象数据的情况下,如果我们此时调用pushback方法,除了传参需要副本会调用一次拷贝构造函数之外,还需要调用容器中相应个数的类对象元素的拷贝构造函数:

    vector<student> vectStu(10); //调用10次默认构造函数
    student xiaoHua(18, "李校花");//调用1次带参构造函数
    vectStu.push_back(xiaoHua); //调用11次拷贝构造函数,和12次析构函数(有一次是xiaohua实参的析构)
    

    解释:当使用 push_back() 向一个 vector 容器中添加元素时,如果该容器已经满了,就需要对其进行扩容。扩容的过程中,会重新分配内存,并将原来的元素复制到新的内存中。因此,如果在容器中已经存储了一些元素,再使用 push_back() 添加元素时,可能会调用元素类型的拷贝构造函数多次。由于添加新元素可能导致容器大小的变化,因此建议在使用 push_back() 方法之前,使用 reserve() 方法预留足够的空间,这样可以避免重复的内存分配和数据复制,从而提高程序的性能。具体而言,使用 reserve() 方法来预留容器能够容纳的元素数量,例如:

    vector<Student> v2;
    v2.reserve(11); // 预留能够容纳 11 个元素的空间
    v2.push_back(Student()); // 只调用一次 Student 的拷贝构造函数
    
  5. 如果容器是存储类指针,传递时需要传递地址,那么pushback不会调用拷贝构造函数:

    使用 vector<Student> v2(10); 语法创建容器时,会根据提供的元素数量自动调用默认构造函数来初始化每个元素。具体而言,这行代码会调用 vector 类的 (size_t, const T& = T()) 版本的构造函数,该构造函数会使用提供的参数在容器中创建指定的元素数量,并使用元素类型的默认构造函数来初始化每个元素。例如,vector<Student> v2(10) 创建了一个包含 10 个 Student 元素的容器,因此会调用 Student 类的默认构造函数 10 次,以创建并初始化每个元素。相比之下,使用 vector<Student*> v2(10); 语法创建的容器是包含指针类型的元素,而不是对象类型的元素。指针类型的元素在创建时并不会自动调用默认构造函数进行初始化,而是会被赋予默认值 nullptr,即空指针。因此,使用 vector<Student*> v2(10); 创建的容器中的元素都是指向空地址的空指针,不需要调用默认构造函数。

🚀四、仿函数(函数对象)functor 的用法

⛳(一)仿函数概念

  1. 尽管函数指针被广泛用于实现函数回调,但 C++还提供了一个重要的实现回调函数的方法,那就是函数对象。
  2. functor,翻译成函数对象,伪函数,它是是重载了“()”操作符的普通类对象。从语法上讲,它与普通函数行为类似。
  3. functional 头文件中包含的 greater<>与 less<>就是函数对象。
#include <set>
#include <iostream>
#include <functional>
#include <algorithm>

using namespace std;

class student {
public:
    student(int age) {
    	this->age = age;
    }
    //重载比较运算符,在less和greater函数中进行比较对象
    bool operator < (const student &right) const{
    	return this->age < right.age;
    }
    
    bool operator > (const student &right) const{
    	return this->age > right.age;
    }
    
    int getAge() const { return age; }
private:
    int age;
    string name;
};
	
int main(void) {
    //less 函数对象实现比较,为排序提供依据
    //set<int,less<int>> set1;  默认提供一个less函数,从小到大排列
    
    set<int,greater<int>> set1;  //从大到小排列
    
    for(int i=5; i>0; i--){
    	set1.insert(i);
	}

	set<student> setStu; //等同于 set<student,less<student>>
    setStu.insert(student(18));
    setStu.insert(student(19));
    
    /*for (set<int,greater<int>>::iterator it = set1.begin(); it !=set1.end(); it++) {
    	cout << *it << endl;
    }*/
    
    for (set<student>::iterator it = setStu.begin(); it != setStu.end();it++) {
        cout << it->getAge() ;
        cout << " ";
    }
    
    system("pause");
    return 0;
}

⛳(二)greater<int> 和 less<int>的简易实现原理

struct greater
{
    bool operator() (const int& iLeft, const int& iRight)
    {
    	return (iLeft>iRight);
    }
}

struct less
{
    bool operator() (const int& iLeft, const int& iRight)
    {
    	return (iLeft<iRight);
    }
}

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

#include <set>
#include <iostream>
#include <functional>
#include <algorithm>

using namespace std;

class student {
public:
    student(int age) {
    	this->age = age;
    }
    
    bool operator > (const student &right) const{
    	return this->age > right.age;
    }
    
    int getAge() const { return age; }
private:
    int age;
    string name;
};

class FunStudent{
public:
    bool operator () (const student &left, const student &right){
        cout<<"调用了 FunStudent ."<<endl;
        ret = left.getAge() < right.getAge();
        return ret;
    }
public:
	int ret;
};

int main(void) {
	//less 函数对象实现比较,为排序提供依据
	//less 和 greater 都是函数对象,有叫仿函数
	//set<int,less<int>> set1;
	
	set<int,greater<int>> set1;   
	
    for(int i=5; i>0; i--){
		set1.insert(i);
	}
	
    //less<student>
    set<student, FunStudent> setStu; //等同于
    set<student,less<student>>
    student lixiaohua(18);
    student wangdachui(19);
    
    //函数对象(仿函数)可以像函数一样直接调用
    FunStudent funStu;
    funStu(lixiaohua, wangdachui);
    cout<<"比较结果:"<<funStu.ret<<endl;
    
    setStu.insert(lixiaohua);
    setStu.insert(wangdachui);
    
    for (set<student, FunStudent>::iterator it = setStu.begin(); it != setStu.end(); it++) {
        cout << it->getAge() ;
        cout << " ";
    }
    
    system("pause");
    return 0;
}

🚀五、C++11 新特性 变参模板、完美转发和 emplace

变参模板 - 使得 emplace 可以接受任意参数,这样就可以适用于任意对象的构建

完美转发 - 使得接收下来的参数 能够原样的传递给对象的构造函数,这带来另一个方便性

emplace_back用到了c++11的三大特性:右值引用(&&)、可变模板参数、模板参数的完美转发,其中后两点是emplace_back区别于push_back的关键所在,为什么?因为push_back也随着C++11进化了,它也有了右值引用的版本!

⛳(一)emplace_back()用法

功能:和 push_back() 相同,都是在 vector 容器的尾部添加一个元素。

emplace_back函数原型:

template <class... Args>  
void emplace_back (Args&&... args);

举例:

#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<int> values{};    
    values.emplace_back(1);    
    values.emplace_back(2);    
    for (int i = 0; i < values.size(); i++) {
            cout << values[i] << " ";    
    }    
    return 0;
}

⛳(二)为什么要使用emplace_back()

即:与push_back()对比有什么可取之处

🎈1.考虑是否原地构造

push_back():向容器中加入一个右值元素(临时对象)时,首先会调用构造函数构造这个临时对象,然后需要调用拷贝构造函数将这个临时对象放入容器中。原来的临时变量释放。这样造成的问题就是临时变量申请资源的浪费。

emplace_back():引入了右值引用,转移构造函数,在插入的时候直接构造,只需要构造一次即可。

也就是说,两者的底层实现的机制不同。push_back() 向容器尾部添加元素时,首先会创建这个元素,然后再将这个元素拷贝或者移动到容器中(如果是拷贝的话,事后会自行销毁先前创建的这个元素);而 emplace_back() 在实现时,则是直接在容器尾部创建这个元素,省去了拷贝或移动元素的过程。

代码如下:

#include <vector> 
#include <iostream> 
using namespace std;
class testDemo
{
public:
    testDemo(int num):num(num){
        std::cout << "调用构造函数" << endl;
    }
    testDemo(const testDemo& other) :num(other.num) {
        std::cout << "调用拷贝构造函数" << endl;
    }
    testDemo(testDemo&& other) :num(other.num) {
        std::cout << "调用移动构造函数" << endl;
    }
private:
    int num;
};

int main()
{
    cout << "emplace_back:" << endl;
    std::vector<testDemo> demo1;
    demo1.emplace_back(2);  

    cout << endl;
    
    cout << "push_back:" << endl;
    std::vector<testDemo> demo2;
    demo2.push_back(2);
}

输出结果为

emplace_back:
调用构造函数
    
push_back:
调用构造函数
调用移动构造函数

若将 testDemo 类中的移动构造函数注释掉,再运行程序会发现,输出结果变为:

emplace_back:
调用构造函数
    
push_back:
调用构造函数
调用拷贝构造函数
  • 结果分析:emplace_back 接收参数时,可以调用匹配的构造函数实现在容器内的原地构造。由此可以看出,push_back() 在底层实现时,会优先选择调用移动构造函数,如果没有的话,则直接在容器的末尾构造对象,这样就省去了拷贝的过程。显然完成同样的操作,push_back() 的底层实现过程比 emplace_back() 更繁琐,换句话说,emplace_back() 的执行效率比 push_back() 高。

🎈2.考虑尾插左值和右值

代码如下(示例):

#include <vector> 
#include <iostream> 
using namespace std;
class testDemo
{
public:
    testDemo(int num):num(num){
        std::cout << "调用构造函数" << endl;
    }
    testDemo(const testDemo& other) :num(other.num) {
        std::cout << "调用拷贝构造函数" << endl;
    }
    testDemo(testDemo&& other) :num(other.num) {
        std::cout << "调用移动构造函数" << endl;
    }
private:
    int num;
};

int main()
{  
    testDemo t1(2);
    cout << "emplace_back:" << endl;
    std::vector<testDemo> demo1;
    demo1.emplace_back(t1);  
    //demo1.emplace_back(move(t1));  

    cout << endl;
    
    cout << "push_back:" << endl;
    std::vector<testDemo> demo2;
    demo2.push_back(t1);
    //demo1.push_back(move(t1));  
}

输出结果为:

调用构造函数
emplace_back:
调用拷贝构造函数

push_back:
调用拷贝构造函数

去掉代码中注释部分,并注释掉容器接收t1的语句,即让push_back()和emplace_back() 直接接收右值。

输出结果如下:

调用构造函数
emplace_back:
调用移动构造函数

push_back:
调用移动构造函数
调用拷贝构造函数

从执行结果中,我们可以得出以下结论

  1. push_back 可以接收左值也可以接受右值,接收左值时使用拷贝构造,接收右值时使用移动构造
  2. emplace_back 接收右值时调用类的移动构造
  3. emplace_back 接收左值时,实际上的执行效果是先对传入的参数进行拷贝构造,然后使用拷贝构造后的副本,也就是说,emplace_back在接收一个左值的时候其效果和push_back一致!所以在使用emplace_back 时需要确保传入的参数是一个右值引用,如果不是,请使用std::move()进行转换

补充代码:

#include <iostream>
using namespace std;

#include <vector>
#include <list>
#include <deque>
#include <algorithm>

class student {
public:
    student() {
    	cout << "无参构造函数被调用!" << endl;
    }
    
    student(int age, string name) {
        this->age = age;
        //strncpy_s(this->name, name, 64);
        cout << "有参构造函数被调用!" << endl;
        cout << "姓名:" << name.c_str() << " 年龄:" << age << endl;
    }
    
    student(const student &s) {
        this->age = s.age;
        //strncpy_s(this->name, s.name, 64);
        cout << "拷贝构造函数被调用!" << endl;
    }
    
    ~student() {
    	cout << "析构函数被调用" << endl;
    }
public:
    int age;
    string name;
};
int main(void) {
    //vector<int> vectInt(10);
    vector<student> vectStu(10);
    
    cout << "vectStu size:" << vectStu.size() << endl;
    cout << "vectStu capacity:" << vectStu.capacity() << endl;
    
    //插入学生
    
    //方法一 先定义对象,再插入
    //student xiaoHua(18, "李校花");         //调用有参构造函数
    //vectStu.push_back(xiaoHua);           //调用拷贝构造函数
    
    //方法二 直接插入临时对象
    //vectStu.push_back(student(19, "王大锤"));
    
    //c++11 新特性: 变参模板和完美转发的表演啦
    vectStu.emplace_back(19, "王大锤", 11); //push_back
    cout << "vectStu size (1):" << vectStu.size() << endl;
    cout << "vectStu capacity(1):" << vectStu.capacity() << endl;
    
    vectStu.emplace(vectStu.end(), 18, "lixiaohua", 12); //相当于insert.
    cout << "vectStu size (2):" << vectStu.size() << endl;
    cout << "vectStu capacity (2):" << vectStu.capacity() << endl;
    
    system("pause");
    return 0;
}


06-22 06:16