3.deque容器

1.deque容器的基本概念

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

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

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

2.deque容器常用操作

1.deque构造函数

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

2.deque赋值操作

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

3.deque大小操作

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

4.deque双端操作和删除

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

5.deque数据存取

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

6.deque插入操作

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

7.deque删除操作

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

#include<iostream>
#include<deque>
using namespace std;

void printDeque(deque<int>& deq) {
	//使用迭代器
#if 0
			//deque<int>::iterator可以写成auto
	for (deque<int>::iterator it = deq.begin(); it != deq.end(); it++) {
		cout << *it << ", ";

	}
	cout << endl;
}
#else
	for (int& ele : deq) {
		cout << ele << ",";
	}
	cout << endl;
#endif
}

int main() {
	int array[5] = { 1,2,3,4,5 };
	//构造
	deque<int> deq(array, array + 5);
	printDeque(deq);//1,2,3,4,5,


	deque<int> deq2(5, 3);
	printDeque(deq2);//3,3,3,3,3,

	//赋值
	deq2.assign(array, array + 3);
	printDeque(deq2);//1,2,3,

	deq.swap(deq2);

	//大小
	cout << deq.size() << endl;//3
	cout << deq.empty() << endl;//0

	deq.resize(10, 1);

	//
	deq.push_front(100);
	deq.push_back(200);

	deq.pop_front();
	deq.pop_back();

	//
	int& ele = deq.at(3);
	ele = 10;

	system("pause");
	return 0;
}

4.stack容器

stack容器基本概念

stack是一种先进后出（First In Last Out，FILO）的数据结构，它只有一个出口，形式如图所示。stack容器允许新增元素，移除元素，取得栈顶元素，但是除了最顶端外，没有任何其他方法可以存取stack的其他元素。换言之，stack不允许有遍历行为。

有元素推入栈的操作称为：push,将元素推出stack的操作称为pop。

stack时没有迭代器的：

stack所有元素的进出都必须符合“先进后出”的条件，只有stack栈顶的元素，才有机会被外界取用。stack不提供迭代器。

stack容器常用操作

1.构造函数

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

2.赋值操作

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

3.数据存取操作

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

4.大小操作

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

#include<iostream>
#include<stack>
using namespace std;
int main30() {

	//构造函数
	//		-无参构造
	//		-拷贝构造函数

	stack<int> s1;

	//压栈
	s1.push(10);
	s1.push(20);
	s1.push(30);

	//获取栈顶元素
	int& ele = s1.top();
	cout << ele << endl;
	ele = 300;
	cout << s1.top() << endl;

	//出栈
	s1.pop();
	cout << s1.top() << endl;

	//大小
	cout << s1.size() << endl;
	cout << s1.empty() << endl;

	/*int len = s1.size();
	for (int i = 0; i < len; i++) {
		cout << s1.top() << endl;
		s1.pop();
	}

	cout << s1.empty << endl;*/

	system("pause");
	return 0;

5.queue容器

queue容器的基本概念

Queue是一种先进先出（First In First Out, FIFO)的数据结构，它有两个出口，queue容器允许从一端新增元素，从另一端移除元素。

queue容器没有迭代器：Queue所有元素的进出都必须符合“先进先出“的条件，只有queue的顶端元素，才有机会被外界取用。queue不提供遍历功能，也不提供迭代器。

queue的常用操作

1.构造函数

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

2.存取、插入、删除操作

push(elem);//往队尾添加元素
pop();//从队头移除第一个元素
front();//获取对头元素
back();//获取队尾元素

3.大小

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

6.list容器

list容器基本概念

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素成为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分；一个是存储元素的数据域，另一个是存储下一个结点地址的指针域。

相较于vector的连续线性空间。list就显得复杂许多，它的好处是每次插入或者删除一个元素，就是配置或者释放一个元素的空间。因此，list对于空间的运用由绝对的精准一点也不浪费。而且，对于任何位置的元素插入或元素的移除，list永远是常数时间。

List和vector是两个最常使用的容器。

增删list 查询遍历vector

List容器是一个双向链表。

采用动态存储分配，不会造成内存浪费和溢出

链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素

链表灵活，但是空间和时间额外耗费较大

list的迭代器

List容器不能想vector一样以普通指针作为迭代器，因为其结点不饿能保证在同一块连续的内存空间上。List迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取操作。所谓：list正确的递增，递减、取值、成员取用”是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取得时节点的成员。

由于list是一个双向链表，迭代器必须能够具备前移、后裔的能力，所以list容器提供的是Bidirectional Iterators.

List有一个重要的性质，插入操作和删除操作都不会造成原有的迭代器失效。这在vector是不成立的，因为vector的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效，甚至List元素的删除，也只有被删除的那个元素的迭代器失效，其他迭代器不受任何影响。

list容器常用操作

1.构造函数

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

2.元素插入和删除操作

push_back(elem);//在容器尾部加入一个元素
pop_back();//删除容器中最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_fron();//从容器开头移除第一个元素
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值匹配的元素

3.大小操作

empty();//判断容器是否为空
resize(num);//重新指定容器的长度为num
//若容器变长，则默认填充新位置
//若容器变短，则末尾超出容器长度的元素被删除

resize(nem,elem);//重新指定容器的长度为num
//若容器变长，则以elem值填充新位置
//若容器变短，则末尾超出容器长度的元素被删除

4.赋值操作

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

5.数据存取操作

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

6.反转、排序

reverse();//反转链表，比如lst包含1，3，5元素，运行此方法后lst就包含5，3，1元素
sort();//list排序

7.set/multiset容器

1.set/multiset容器基本概念

Set的特性是：所有元素都会根据元素的值自动被排序。Set不允许两个元素有相同的值

不能通过set迭代器改变set元素的值，关系到set元素的排序的排序规则。如果任意改变set元素值，会严重破坏set组织。换句话说，set的iterator是一种const_iterator.

set拥有和list某些相同的性质，当对容器中的元素进行插入操作或者删除操作的时候，操作之前所有的迭代器在曹祖之后仍然有效，被删除的那个元素的迭代器必然是一个例外。

multiset特性及用法和set完全相同，唯一的差别在于它允许之重复。set和multise的底层实现是红黑树，红黑树为平衡二叉树的一种。

#include<iostream>
#include<set>
using namespace std;
void printSet(set<int>& s) {
#if 1
	//set迭代器是一个只读的迭代器，只可以通过迭代器获取到元素的值，但是不能修改
	for (auto it = s.begin(); it != s.end(); it++) {
		cout << *it << ",";
	}
	cout << endl;
#else
	for (int ele : s) {
		cout << ele << ",";
	}
	cout << endl;
#endif
}



int main32() {


	//构造函数
	set<int> s;
	multiset<int> ms;

	//插入元素
	s.insert(123);
	s.insert(111);
	s.insert(100);
	s.insert(111);

	//删除元素
	set<int>::iterator it = s.begin();
	s.erase(it);

	//s.erase();
	//s.clear();

	//查找：set容器中没有下标
	set<int>::iterator target = s.find(100);//查找元素是否存在，如果存在返回这个元素的迭代器；如果不存在，返回set.end()
	cout << s.count(100) << endl;//查找元素的个数

	set<int>::iterator res1 = s.lower_bound(111);//返回第一个元素<=指定元素的迭代器
	set<int>::iterator res2 = s.upper_bound(111);//返回第一个元素>指定元素的迭代器

	//
	cout << s.size() << endl;
	cout << s.empty() << endl;

	printSet(s);//100,111,123,
	system("pause");
	return 0;
}

8.map容器

#include<iostream>
#include<map>
using namespace std;

void test_pair() {
	//pair:将两个数据整合到一起，成为一个整体
	//		-这两个数据的数据类型可以不同
	//		-这两个数据，一个是键(Key),一个是值（Value)

	//第一种方式构建pair:
	pair<string, int> p1("chinese", 99);
	cout << p1.first << endl;
	cout << p1.second << endl;

	//第二种方式构建pair
	pair<string, int> p2 = make_pair("math", 98);
}

//map存储特点：
// 1.存储的元素是一个个pair，pair键值对
// 2.存储的所有的键值对，会按照key进行排序
// 3.map容器中，不允许出现重复的键。（multimap中允许存在重复的键）
//map能够通过迭代器修改元素么
//可以通过迭代器修改值，不能修改键


void printMap(map<string, int>& m) {
#if 1
	for (map<string, int>::iterator it = m.begin(); it != m.end(); it++) {
		cout << "key = " << (*it).first << ", value = " << (*it).second << '\t';
	}
	cout << endl;
#else
	for (pair<string, int>::iterator it = m.begin(); it != m.end(); it++) {
		cout << "key = " << p.first << ", value = " << p.second << '\t';

	}
#endif // 1

}

int main() {

	
//1.构造函数
	map<string, int> m;

		//2.插入元素
	m.insert(pair<string, int>("chinese", 99));
	m.insert(make_pair("math", 98));
	m.insert(map<string, int>::value_type("endlish", 100));
	m["history"] = 89;
	m["history"] = 80;//如果添加的键值对，键已经存在了，此时是一个修改操作。用新的值覆盖原来的值

	//3.删除操作
	//m.erase(m.begin());
	m.erase("history");//按照键删除，删除键值对

	//4.查找操作
	map<string, int>::iterator it1 = m.find("english");//查找具有指定的键的键值对的迭代器
	cout << m.count("english") << endl;//查找有多少个指定键的键值对

	printMap(m);


	system("pause");
	return 0;
}