C++语言学习记录-33：容器与迭代器

容器

C++提供了一些自然、通用的容器，这些容器能够容纳用户定义的类型，并提供各种操作，而不需要强制用户定义的类型具有某种结构。例如向量、链表、队列都属于容器。这些容器提供的操作不依赖容器包含的类型

迭代器

迭代器是一种检查容器内的元素并遍历元素的数据类型，标准库为每一种标准容器定义了一种迭代器类型，迭代器类型提供了比下标操作更通用化的方法：所有标注库容器都定义了相应的迭代器类型。
迭代器主要分为五类：

1. 输入迭代器
2. 输出迭代器
3. 前向迭代器
4. 双向迭代器
5. 随机存取迭代器

顺序容器

向量

向量属于顺序容器，用于容纳不定长线性序列，提供对序列的快速随机访问。向量是一个动态结构，大小不固定，可以在程序运行时增加或减少
vector的主要操作有如下几种

• v.push_back(t)在数组的最后添加一个值为t的数据
• v.size()当前使用数据的大小
• v.empty()判断vector是否为空
• v[n]返回v中位置为n的元素
• v1=v2 把v1的元素替换为v2元素的副本
• v1==v2 判断v1、v2是否相等

对vector进行初始化时，如果没有指定元素初始化，标准库自行提供一个初始化值进行函数初始化。如果保存的是含有构造函数的类类型的元素，标准库产生一个带初始值的对象，使用这个对象进行值初始化

双端队列

双端队列是一种放松了访问权限的队列，元素可以从队列的两端入队和出队，也支持通过下标操作符[]直接访问
双端队列使用前须导入头文件deque
deque的操作，除了capacity和reverse两个功能没有之外，与vector相同，同时，deque还提供函数完成收尾函数的插入和删除

#include<iostream>
#include<deque>
using namespace std;
int main()
{ 
   
	deque<int>d;
	d.push_back(3);//插入三个元素
	d.push_back(1);
	d.push_back(2);
	cout << d[0] << " " << d[1] << " " << d[2] << endl;
	d.push_front(10);//从头部插入元素，也就是从头部向后“挤”，位于最后的元素会被挤出去
	d.push_front(20);
	cout << d[0] << " " << d[1] << " " << d[2] << endl;
	d.insert(d.begin() + 1, 88);//将1号位置的元素用88替代
	cout << d[0] << " " << d[1] << " " << d[2] << endl;
	return 0;
}

列表

列表主要用于存放双向链表，可以从任意一端开始遍历，此外还提供了拼接操作splicing，将一个序列中的元素插入到另一个序列中，使用前要导入list头文件

#include<iostream>
#include<list>
using namespace std;
int main()
{ 
   
	list<int>elements;//定义list
	list<int>::iterator iter;//定义list的迭代器
	//向list中当前的指针的位置插入，直到最后一位
	elements.push_back(8);
	elements.push_back(5);
	//向list中当前的指针的位置插入，直到最前一位
	elements.push_front(2);
	for (iter = elements.begin(); iter != elements.end(); iter++)
	{ 
   
		cout << *iter << endl;
	}
	cout << "After deleted the first place of the list" << endl;
	elements.erase(elements.begin());
	for (iter = elements.begin(); iter != elements.end(); iter++)
	{ 
   
		cout << *iter << endl;
	}
	if (!elements.empty())
	{ 
   
		cout << "elements is not empty" << endl;
	}
	cout << "the volume is" << elements.size() << endl;
	return 0;
}

关联容器

关联容器是通过键值存储和读取元素的数据集合，关联容器读取和存储与数据写入的顺序无关，只根据键来查找相对应的元素

集合和多集

一个集合是一个容器，其中所包含的元素按一定的顺序排列，并被作为集合中的实例。一个集合通过链表组织，在插入和删除操作上比向量快，但查找或添加末尾元素时会有些慢。集可以类比为Python中的字典
集和多集的区别是：集支持唯一键值，集中的值都是特定的且只出现一次，多集可以出现副本键，同一值可以出现多次
拓展：集和多集容器内部结构通常由平衡二叉树实现，当元素放入容器中时，会按照一定的排序法则自动排序，默认是按照less排序规则来排序。这种自动排序的特性加速了元素查找的过程，但是也带来了一个问题：不可以直接修改集或多集中的元素值，这样会可能违反元素自动排序的规则。如果要修改一个元素的值，必须先删除原有的元素，再插入新的元素
集的使用首先要插入头文件set

#include<iostream>
#include<set>
using namespace std;
int main()
{ 
   
	set<int>set1;
	for (int i = 0; i < 10; ++i)
	{ 
   
		set1.insert(i);
	}
	for (set<int>::iterator p = set1.begin(); p != set1.end(); ++p)
	{ 
   
		cout << *p << " ";
	}
	cout << endl;
	if (set1.insert(3).second)
		cout << "set insert seccess" << endl;
	else
		cout << "set insert failed" << endl;
	int a[] = { 
    4,1,1,1,1,1,0,5,1,0 };
	multiset<int>A;
	A.insert(set1.begin(), set1.end());
	A.insert(a, a + 10);
	cout << endl;
	for (multiset<int>::iterator p = A.begin(); p != A.end(); ++p)
	{ 
   
		cout << *p << " ";
	}
	cout << endl;
	return 0;
}

在本例中，把3插入set1步骤的操作时一定失败的，因为集合中已经有这个元素，后面将int型数组a中所有的值和set1中所有的元素全部插入多集合A中

映射和多重映射

映射和多重映射是基于某一类型key的键集的存在，提供对T类型数据的高效检索。对映射（map）而言，键只是指储存在容器中的某一成员。与集和多集类似，map不支持副本键，而multimap支持副本键。但是键和值的数据类型不相同，在这一点上与集合不同
键本身和集中的元素一样，是不能修改的，除非删除

#include<iostream>
#include<map>
using namespace std;
int main()
{ 
   
	map<char, int, less<char>>map1; //char是键的类型，int是值的类型
	map<char, int, less<char>>::iterator mapIter;
	map1['c'] = 3;
	map1['d'] = 4;
	map1['a'] = 1;
	map1['b'] = 2;
	for (mapIter = map1.begin(); mapIter != map1.end(); ++mapIter)
	{ 
   
		cout<< (*mapIter).first << ":" << (*mapIter).second<<" ";
	}
	map<char, int, less<char>>::const_iterator ptr;
	ptr = map1.find('d');
	cout << '\n' << (*ptr).first << ":" << (*ptr).second;
	return 0;
}

定义了map型的map1，以及map型的迭代器mapIter，map1的键类型是char，值类型是int。最后输出的时候，map按照简直从小到大排序

容器适配器

标准库中提供三种容器适配器：queue、priority_queue和stack，适配器是标准库中通用的概念，包括容器适配器、迭代器适配器和函数适配器。本质上适配器是使一类事物的行为类似于另一类事物行为的一种机制。容器适配器让一种已存在的容器类型才用另一种不同的抽象类型的工作方式实现。容器适配器是用来拓展7种基本容器的

栈 stack

栈允许在底层数据结构的一端执行插入和删除操作（遵循先入后出的原则）。堆栈可以用任何序列容器实现，主要操作有以下几个：

• push(x) x元素压入栈
• pop() 弹出栈顶元素
• top() 获取栈顶元素
• empty() 栈为空返回1，不空返回0
• size() 返回栈中元素个数

队列 queue

队列类允许在底层数据结构的末尾插入元素，也允许从前面插入元素（遵守先入先出）
队列能使用list和deque实现，在默认情况下是由deque实现的
主要操作：

• push(x) 将元素x压入队列
• pop() 弹出首部元素
• front() 获取首部元素
• back() 获取尾部元素
• empty()队列为空返回1，不空返回0
• size()返回元素个数
  可以看出主要操作与栈是一致的

优先级队列

优先级队列类能够按照有序的方式在底层数据结构的前面执行删除操作。
优先级队列能够用STL的序列容器vector和deque实现，默认情况下用vector做底层容器。当元素添加到priority_queue时，他们按优先级顺序插入
这样，就有最高优先级的元素，就是从priority_queue中首先被删除的元素，这通常是利用堆排序来实现的。堆排序总是将最大值（即优先级最高的元素）放在数据结构的前面。
优先级队列的操作与之前的基本相同，除了获取首部元素的函数变为top()以及没有back函数。

补充：

• 顺序容器与关联容器的区别
  关联容器通过键储存和读取元素，顺序容器通过元素在容器中的位置储存和读取元素
• 迭代器的范围
  每种容器都定义了一对begin和end函数，用于返回迭代器，如果容器中有元素，由begin返回的迭代器指向第一个元素，end操作返回的迭代器指向的是相应容器中最后一个元素的下一元素，也就是超出了末端的位置而指向了一个不存在的元素，，也因如此，迭代器的范围通常是左闭右开

今天的文章C++语言学习记录-33：容器与迭代器分享到此就结束了，感谢您的阅读。