绵阳梓潼网站制作公司

第十九章-创新互联

目录

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

一、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://myzitong.com/article/jecig.html

其他资讯