第十九章-创新互联

目录

创新互联专注于瀍河企业网站建设,响应式网站设计,成都商城网站开发。瀍河网站建设公司,为瀍河等地区提供建站服务。全流程按需求定制制作,专业设计,全程项目跟踪,创新互联专业和态度为您提供的服务

一、STL概述

二、STL基本概念

三、STL六大组件

四、string(类)容器

1.string容器基本概念

2.string容器常用操作

五、vector(类模板)容器

1.vector的概述

2.vector的数据结构

3..vector常用的API操作

六、deque容器

1.deque容器基本概念

2.deque容器实现原理

3.deque常用API

七、stack容器

1.stack容器的基本概念

2.stack常用API

八、queue容器

1.queue容器的基本概念

2.queue常用API

九、list容器

1.list容器的基本概念

2.list常用API

十、set/multiset容器

1.set/multiset容器的基本概念

2.set/multiset常用API

3.对组(pair)

十一、map/multimap容器

1.map/multimap容器的基本概念

2.map/multimap常用API

3.multimap案例


一、STL概述

STL(Standard Template Library标准模版库),是惠普实验室开发的一系列软件的统称。

为了建立数据结构和算法的一套标准,降低它们之间的耦合关系,以提升各自的独立性、弹性、交互操作性(相互合作性,interoprrability),诞生了ST

其实就是提高 代码复用性,制造出可重复运用的代码,而不需要自己再去写已经存在的代码。  

二、STL基本概念

STL从广义上分为:容器(container)、算法(alhorithm)、迭代器(iterator)

【容器和算法之间通过迭代器进行无缝连接,算法 其实是 通过迭代器 操作 容器数据】

  • STL主要出现在c++中,但在c++引入前该技术已经存在很长时间了。 
  • STL几乎所有代码都采用了 模板类 或者 模板函数 。这相比传统的 由函数和类组成的库 来说,提供了更好的 代码重用机会。
  • 在c++标准程序库中,隶属于STL的占到了80%以上。
三、STL六大组件

容器、算法、迭代器、仿函数、适配器(配接器)、空间配置器

STL的一个重要特性是 将数据和操作分离,数据由 容器类别 加以管理,操作则由 特定算法 完成。 

1.容器:存放数据

2.算法:操作数据

算法分为 质变算法 和 非质变算法。

质变算法:运算过程中,会更改区间内的元素内容。例如拷贝、替换、删除等等。

非质变算法:运算过程中,不会更改区间内元素内容。例如查找、计数、遍历、寻找极值等。

3.迭代器:算法 只能借助迭代器 操作容器数据(容器和迭代器一一对应)。

4.仿函数:为算法提供更多策略

eg:排序函数默认是从小到大排序,用仿函数让它可以从大到小排序,提供更多的策略。 

5.适配器(配接器):为算法提供更多参数的接口

eg:函数默认是传1个参数,用适配器让它可以传2个参数,这样的

6.空间配置器:为算法和容器 动态分配、管理空间

最常用的容器是 vector 和 lis t容器。 

四、string(类)容器 1.string容器基本概念

c字符串是 以空字符结尾的字符数组,不适合大程序开发,所以c++标准库定义了一种string类。

  • char*是一个指针,string是一个类;
  • string封装了char*,管理这个字符串,是一个char型的容器;
  • string封装了很多实用的成员方法:

 【查找find,拷贝copy,删除delete,替换replace,插入insert】

  • 不用考虑内存释放和越界

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

2.string容器常用操作

(以下都是函数定义。string&是返回值,调用的时候用的是函数名,也就是operator、assign这样的,懂吧)

【不管什么容器,看到assign就是赋值,operator是运算符重载】

【3.[ ]越界不会抛出异常,at方法会】

【5.find返回第一次出现位置,rfind返回最后一次出现位置,没找到返回-1;没传pos默认从头开始找】

#include#include//string.h是c的头文件,string是类的
using namespace std;

#include//input output manipulator:输入输出格式控制

void test1()
{
	string str;//1.1
	cout<< str<< endl;
	string str1("hello");//1.3
	cout<< str1<< endl;
	string str2(5, 'A');//1.4
	cout<< str2<< endl;
	string str3=str2;//1.2 拷贝构造
	cout<< str3<< endl;

	string str4;
	str4 = "hello";//2.1
	cout<< str4<< endl;
	str4.assign("world");//2.4
	cout<< str4<< endl;
	str4 = "W";//2.3
	cout<< str4<< endl;
	str4.assign("hello",3);//2.5
	cout<< str4<< endl;

	string str5 = "hello";
	str4.assign(str5, 2, 2);//2.8
	cout<< str4<< endl;
}
void test2()
{
	//3.1+3.2
	string str1 = "hello";
	cout<< str1[1]<<" "<0)
		cout<< "大于"<< endl;
	else if (str1.compare(str2)< 0)
		cout<< "小于"<< endl;
	//>、=、<重载
	if (str1==str2)
		cout<< "相等"<< endl;
	else if (str1>str2)
		cout<< "大于"<< endl;
	else if (str1
五、vector(类模板)容器 1.vector的概述

vector和array的数据安排和操作方式非常相似,两者的唯一差别在于空间运用的灵活性。 array是静态空间,vector随元素的加入,内部会自动扩充空间,以容纳新元素。

v.begin():获取容器的起始迭代器(指向第0个元素)

v.end()   :获取容器的结束迭代器(指向最后一个元素的下一个位置) 

只能尾插尾出

2.vector的数据结构

线性连续空间

一旦满载,vector会开辟 现有空间容量两倍大小的空间(未雨绸缪机制),将原内容复制到新空间内

3..vector常用的API操作

#includeusing namespace std;
#includevoid test1()
{
	//类的类型是类,类模板的类型是<类型>vectorv1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);

	//遍历该容器
	//定义一个迭代器iterator 保存起始迭代器
	vector::iterator it = v1.begin();
	for (; it != v1.end(); it++)
	{
		//*it==int
		cout<< *it<< " ";
	}
	cout<< endl;
}
void test2()
{
	vectorv1;
	//可以事先预留足够空间,省的多次开辟
	v1.reserve(1000);//3.6
	cout<< "容量:"<::iterator it;

	int i = 0;
	int count = 0;

	for (i = 0; i< 1000; i++)
	{
		v1.push_back(i);
		if (it != v1.begin())//如果开辟空间,v1.begin指向新空间,迭代器仍指向旧空间,v1.begin和迭代器不相等。可以通过这个来判断是否开辟了空间。 
		{
			count++;
			cout<< "第"<< count<< "次开辟空间容量:"<< v1.capacity()<< endl;
			it = v1.begin();
		}
	}
}
void printVectorInt(vector& v)
{
	vector::iterator it = v.begin();
	for (; it != v.end(); it++)
		cout<< *it<< " ";
	cout<< endl;
}
void test3()
{
	vectorv1(5,100);//1.3
	printVectorInt(v1);

	vectorv2(v1.begin(), v1.end());//1.2
	printVectorInt(v2);

	vectorv3;//1.1
	//v3=v2;       //2.3
	//v3.assign(v2.begin(),v2.end());    //2.1
	v3.assign(10, 10);
	printVectorInt(v3);

	v3.swap(v2);//2.4
	printVectorInt(v2);
	printVectorInt(v3);

	vectorv4;
	if (v4.empty())//3.2
	{
		cout<< "空"<< endl;
	}
	else
		cout<< "非空"<< endl;
	vectorv5(10,30);
	cout<< "容量:"<< v5.capacity()<< " 大小:"<< v5.size()<< endl;//3.5 3.1
	printVectorInt(v5);
	//v5.resize(15);//过大 补零 3.3
	v5.resize(15, 2);//过大 补二 3.4
	v5.resize(5);//过小 删除多余
	printVectorInt(v5);
}
void test4()
{
	vectorv1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);//10 20 30 40 50

	cout<< "头元素:"<< v1.front()<< " 尾元素:"<v1;
	v1.reserve(1000);
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	cout<< "容量:"<< v1.capacity()<< " 大小:"<< v1.size()<< endl;
	//resize只能修改大小,不能修改容量 
	//v1.resize(4);
	vector(v1).swap(v1);//vector(v1)为匿名对象,发生拷贝构造,用旧对象v1给新对象赋值(只有size大小的被赋值过去了,而不是capacity大小),
	//和v1 swap后,v1指向匿名对象的size大小空间
	cout<< "容量:"<< v1.capacity()<< " 大小:"<< v1.size()<< endl;
}

void test6()
{
	vectorv1(5, 10);
	vectorv2(5, 100);
	vectorv3(5, 1000);

	//定义一个vector容器存放v1 V2 V3
	vector>v;
	v.push_back(v1);
	v.push_back(v2);
	v.push_back(v3);

	//遍历
	vector>::iterator it = v.begin();
	for (; it != v.end(); it++)
	{
		//*it==vectorvector::iterator mit = (*it).begin();
		for (; mit != (*it).end(); mit++)
		{
			cout<< *mit<< " ";
		}
		cout<< endl;
	}
}

#include;
void test7()
{
	vectorv1;
	v1.push_back(20);
	v1.push_back(60);
	v1.push_back(50);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(10);
	printVectorInt(v1);

	//排序算法
	sort(v1.begin(), v1.end());
	printVectorInt(v1);
}

#includeclass Person
{
	friend bool comparePerson(Person ob1, Person ob2);
	friend void printVectorPerson(vector&v);
private:
	int num;
	string name;
	float score;
public:
	Person() {}
	Person(int num, string name, float score)
	{
		this->num = num;
		this->name = name;
		this->score = score;
	}
};

void printVectorPerson(vector&v)
{
	vector::iterator it = v.begin();
	for (; it != v.end(); it++)
	{
		//*it==Person
		cout<< (* it).num<< " "<<(*it).name<<" "<<(*it).score<v1;
	v1.push_back(Person(100,"lucy",77.7f));
	v1.push_back(Person(103, "bob", 77.7f));
	v1.push_back(Person(101, "tom", 77.7f));
	v1.push_back(Person(104, "德玛", 77.7f));
	v1.push_back(Person(105, "小法", 77.7f));

	printVectorPerson(v1);

	//对自定义类型的vector类型排序,需要修改排序规则
	sort(v1.begin(),v1.end(),comparePerson);
	printVectorPerson(v1);

}
int main(int argc,char *argv[])
{
	test8();
	return 0;
}
六、deque容器 1.deque容器基本概念

double ended queue,双端队列

vector与deque容器的大差异:

(1)deque允许在 头尾两端 分别做元素的插入和删除操作,且 所用时间 仅 常数项时间。

【vector也可以头部插入,但效率太低】

(2)没有容量的概念。它是动态的,以 分段定量连续空间 组合而成,随时可以增加一段新的空间并连接起来,不存在容量限制。

【也就是说,

像vector那样 “空间不足而重新配置一块更大空间,然后复制元素,再释放旧空间” 的事情在deque这不存在。

因此deque不需要空间保留(reserve)功能,虽然deque容器也提供了Random Access Iterator,但它的迭代器并不是普通的指针,其复杂度和vector不是一个量级。

因此,除非有必要,尽量使用vector而不是deque。

对deque进行排序操作,为了提高效率。可以将deque完整复制到一个vector中,对vector容器进行排序,再复制回deque。】

2.deque容器实现原理

array无法扩张

vector尾端假扩张:申请更大空间-->原数据复制新空间-->释放原空间

deque双端真扩张

deque采取一块map作为主控(注意不是STL的map容器,是一小段连续的内存空间),其中每一个元素(结点)都是一个指针,指向另一段连续性内存空间,称作缓冲区。缓冲区才是deque的存储空间主体。

Deque由一段段定量连续空间构成。当在deque前端或尾端增加新空间时,便串接一段连续定量的空间。

deque避开了重新配置空间、复制、释放的轮回,代价就是复杂的迭代器架构和数据结构设计。

3.deque常用API

#includeusing namespace std;
#includevoid printDequeInt(deque& d)
{
	deque::iterator it = d.begin();
	for (; it != d.end(); it++)
	{
		cout<< *it<< " ";
	}
	cout<< endl;
}

void test1()
{	
	dequed1;
	d1.push_back(1);//4.1
	d1.push_back(2);
	d1.push_back(3);
	d1.push_front(4);//4.2
	d1.push_front(5);
	d1.push_front(6);
	printDequeInt(d1);
	cout<< "大小:"<< d1.size()<< endl;
	d1.pop_front();//4.4
	printDequeInt(d1);
	d1.pop_back();//4.3
	printDequeInt(d1);

	d1.insert(d1.begin() + 1, 3, 100);//6.2
	printDequeInt(d1);
}

//8
#include#include
class Person
{
public:
	string name;
	float score;
public:
	Person() {}
	Person(string name, float score)
	{
		this->name = name;
		this->score = score;
	}
};

void createPerson(vector& v)
{
	string tmpName = "ABCDE";
	int i = 0;
	for (i = 0; i< 5; i++)
	{
		string name = "选手";
		name += tmpName[i];
		v.push_back(Person(name, 0.0f));
	}
}

void showPerson(vector&v)
{
	vector::iterator it = v.begin();
	for (; it != v.end(); it++)
	{
		//*it==Person
		cout<< (*it).name<< " "<< (*it).score<< endl;
		//以下写法也可以,但是是把迭代器看成了指针,容易出错,其他迭代器上可能就不能用了。 
		//cout<< it->name<< " "<< it->score<< endl;
	}
}

void playGame(vector&v)
{
	//每人逐个比赛
	vector::iterator it = v.begin();
	for (; it != v.end(); it++)
	{
		//定义一个deque容器存放10个评委的分数
		dequed;
		int i = 0;
		for (i = 0; i< 10; i++)
		{
			d.push_back((float)(rand() % 41 + 60));//rand() % 41:生成0-41间的一个随机数。 
		}
		//对deque排序
		sort(d.begin(), d.end());

		//去掉最低最高分
		d.pop_back();
		d.pop_front();
		//求平均分
		(*it).score = (float)accumulate(d.begin(), d.end(),0)/d.size();
	}
}
#includevoid test2()
{
	vectorv;
	//srand设置随机数种子
	srand(time(NULL));
	//创建五名选手
	createPerson(v);

	//比赛
	playGame(v);
	//显示选手成绩
	showPerson(v);
}

int main(int argc, char* argv[])
{
	test2();
	return 0;
}
七、stack容器 1.stack容器的基本概念

stack是一种 先进后出 的数据结构,stack容器只能 新增、删除、取得 栈顶元素。

stack不允许 遍历,没有迭代器。【只有一个出口,除了最顶端外,没有其他方法可以存取stack的其他元素】

2.stack常用API

八、queue容器 1.queue容器的基本概念

queue是一种 先进先出 的数据结构,允许元素从队尾新增入队,从队头移除出队。

2.queue常用API

九、list容器 1.list容器的基本概念

list容器是一个双向链表。

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

插入和删除元素是常数时间,无需像静态链表(数组)那样移动大量元素。

采用动态存储分配。灵活,但消耗了空间和时间。

2.list常用API

list容器的迭代器是双向迭代器,

  • 不支持 +2 这种(随机访问迭代器支持,像vector的),支持++(因为++运算符可以重载);
  • 不支持 STL提供的算法(STL提供的算法(像sort)只支持随机访问迭代器)

【可以写(对象)h1.sort();】

十、set/multiset容器 1.set/multiset容器的基本概念

特征:set的所有元素会根据 键值 自动排序。

  • set的元素既是键值又是实值,或者可以认为它只有键值。
  • set不允许两个元素有相同的键值。multiset 特性及用法 与 set 完全相同,唯一差别在于它允许键值重复(即可以插入相同元素)。
  • set迭代器 是 只读迭代器,不允许修改键值,会破坏set的内存布局。【因为set插入元素时才排序,如果修改元素内容,就无序了,容器布局就变了】

2.set/multiset常用API

因为set插入元素就自动排序好了,所以没有push_back/push_front这种。

修改排序规则:

  • 应该在定义类对象时修改,set

【先定义类对象,再插入元素。因为插入时就自动排序了,所以应该在插入之前修改排序规则,也就是在定义类对象时修改】

  • 因为在尖括号内,排序规则须是一个类,同时也是一个函数,所以我们用 仿函数 来写规则。

【仿函数:重载函数调用运算符()的类】

  • set存放自定义数据必须修改排序。

【同vector实操最后面出现的。自定义类型不指定排序规则的话,sort不知道你是依据哪个成员变量来排序】

3.对组(pair)

将一对值组合成一个值,这一对值可以具有不同的数据类型,两个值可以分别用pair的两个公用属性 first 和 second 。

模板:templatestruct pair

void test()
{
//方式一:
pairp1(10086,"移动");
pairp2(10010,"联通");
pairp3(10000,"电信");

//方式二:(推荐)
pairp4=make_pair(9527,"星爷");

cout<
十一、map/multimap容器 1.map/multimap容器的基本概念
  • map的所有元素都是pair。【pair的第一元素被认为是 键值 ,第二元素被认为是 实值】
  • 所有元素会根据键值自动排序。
  • map键值不能重复、不能修改。

multimap和map唯一区别在于,multimap键值可重复。

map和multimap都是以 红黑树 为底层实现机制。 

2.map/multimap常用API

3.multimap案例

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


标题名称:第十九章-创新互联
标题来源:http://pwwzsj.com/article/jecig.html