【C++】STL容器

deque容器是双端队列，支持快速随机访问，在头尾位置插入/删除元素速度很快。

• vector容器对于在头部的插入、删除效率低，且数据量越大，效率越低。相对而言，deque容器对于在头部的插入、删除速度比vector容器快
• vector容器访问元素的速度比deque容器快
• deque容器的内存重分配优于vector容器，因为其内部结构不需要复制所有元素
  

deque容器内部有一个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据。中控器维护的是每个缓冲区的地址，使得使用deque容器时像是一片连续的内存空间。

STL中的list容器是一个双向循环链表，只支持双向顺序访问，在list容器中任何位置插入/删除速度很快。

• 链表中的迭代器只支持前移和后移
• 插入/删除操作不会造成原有的迭代器失效

所有不支持随机访问迭代器的容器, 不可以用标准算法, 但内部会提供对应一些算法！

#include 
#include 
using namespace std;

void printList(const list& L)
{
	for (list::const_iterator it = L.begin(); it != L.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main()
{
	list L;
	L.push_back(90);
	L.push_back(30);
	L.push_back(20);
	L.push_back(70);
	printList(L);	// 90 30 20 70

	// 反转
	L.reverse();
	printList(L);	// 70 20 30 90

	// 排序，默认升序
	L.sort();
	printList(L);	// 20 30 70 90

	// 排序，降序排序
	L.sort([](const int& num1, const int& num2) {return num1 > num2; });
	printList(L);	// 90 70 30 20
	system("pause");
	return 0;
}

什么情况下用vector，什么情况下用list，什么情况下用deque？

• vector支持快速随机访问，但在非尾部插入/删除数据时效率很低，适合对象简单，对象数量变化不大，随机访问频繁的情况
• 需要从首尾两端进行插入/删除操作的时候可以选择deque
• 除非必要，我们尽可能选择使用vector而非deque，因为deque的迭代器比vector迭代器复杂很多
• list不支持随机访问，适用于对象大，对象数量变化频繁，插入和删除频繁的情况。

栈是一种先进后出的数据结构，栈中只有顶端的元素才可以被外界使用，因此栈不允许有遍历行为。

#include 
#include 
using namespace std;

int main()
{
	stack s;
	// 入栈
	s.push(10);
	s.push(20);
	s.push(30);

	// 栈是否为空
	while (!s.empty())
	{
		// 返回栈顶元素
		cout << "栈顶元素为: " << s.top() << endl;
		// 出栈
		s.pop();
	}
	// 返回栈的大小
	cout << "栈的大小为：" << s.size() << endl;
	system("pause");
	return 0;
}

队列是一种先进先出的数据结构，队列允许从一端新增元素，从另一端移除元素，队列中只有队头和队尾才可以被外界使用，因此队列不允许有遍历行为。

#include 
#include 
#include 
using namespace std;

class Person
{
	friend ostream& operator<<(ostream& out, const Person& p);
public:
	Person(string name, int age) {
		this->m_Name = name;
		this->m_Age = age;
	}
private:
	string m_Name;
	int m_Age;
};

ostream& operator<<(ostream& out, const Person& p)
{
	out << "姓名：" << p.m_Name << " 年龄：" << p.m_Age;
	return out;
}

int main()
{
	queue q;

	Person p1("唐僧", 30);
	Person p2("孙悟空", 1000);
	Person p3("猪八戒", 900);
	Person p4("沙僧", 800);

	// 入队
	q.push(p1);
	q.push(p2);
	q.push(p3);
	q.push(p4);

	// 队列是否为空
	while (!q.empty())
	{
		// 返回队头元素
		cout << q.front() << endl;
		// 返回队尾元素
		cout << q.back() << endl;
		// 出队
		q.pop();
	}

	// 返回队列大小
	cout << "队列大小为: " << q.size() << endl;
	system("pause");
	return 0;
}

• set/multiset属于关联式容器，底层结构是用红黑树实现
• 所有元素在插入时自动按升序排序
• set不允许容器中有重复的元素，multiset允许容器中有重复的元素
• 对于自定义数据类型，set容器必须指定排序规则

// 基本使用
#include 
#include 
using namespace std;

void printSet(set& s)
{
	for (set::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main()
{
	set s;

	// 插入
	s.insert(10);
	s.insert(30);
	s.insert(20);
	s.insert(40);
	s.insert(50);
	s.insert(60);

	// 容器是否为空
	if (s.empty()) {
		cout << "set为空" << endl;
	}
	else {
		// 返回容器中元素的数目
		cout << "set的大小为： " << s.size() << endl;	// 6
	}

	// 删除
	s.erase(s.begin());
	printSet(s);	// 20 30 40 50 60

	s.erase(60);
	printSet(s);	// 20 30 40 50

	// 查找
	set::iterator pos = s.find(30);

	// 统计
	// 对于set容器来说，结果为0或1
	int num = s.count(30);
	cout << "num = " << num << endl;	// 1

	system("pause");
	return 0;
}

// set不允许容器中有重复的元素，multiset允许容器中有重复的元素
#include 
#include 
using namespace std;

int main()
{
	// set不允许插入重复值
	// set插入数据的同时会返回插入结果
	set s;
	pair::iterator, bool> ret = s.insert(10);
	if (ret.second) {
		cout << "第一次插入成功!" << endl;	// √
	}
	else {
		cout << "第一次插入失败!" << endl;
	}

	ret = s.insert(10);
	if (ret.second) {
		cout << "第二次插入成功!" << endl;
	}
	else {
		cout << "第二次插入失败!" << endl;	// √
	}

	// multiset允许插入重复的值
	multiset ms;
	ms.insert(10);
	ms.insert(10);

	for (multiset::iterator it = ms.begin(); it != ms.end(); it++) {
		cout << *it << " ";		// 10 10
	}
	cout << endl;

	system("pause");
	return 0;
}

// 所有元素在插入时自动按升序排序
#include 
#include 
using namespace std;

class MyCompare
{
public:
	bool operator()(int v1, int v2) const {
		return v1 > v2;
	}
};

int main()
{
	set s1;
	s1.insert(10);
	s1.insert(40);
	s1.insert(20);
	s1.insert(30);
	s1.insert(50);

	// set容器默认升序排序
	for (auto v : s1)
		cout << v << " ";
	cout << endl;	// 10 20 30 40 50

	// 指定降序排序
	set s2;
	s2.insert(10);
	s2.insert(40);
	s2.insert(20);
	s2.insert(30);
	s2.insert(50);

	for (auto v : s1)
		cout << v << " ";
	cout << endl;
	system("pause");
	return 0;
}

// 对于自定义数据类型，set容器必须指定排序规则
#include 
#include 
using namespace std;

class Person
{
	friend ostream& operator<<(ostream& out, const Person& p);
	friend class ComparePerson;
public:
	Person(string name, int age) {
		this->m_Name = name;
		this->m_Age = age;
	}
private:
	string m_Name;
	int m_Age;
};

ostream& operator<<(ostream& out, const Person& p) {
	out << "姓名： " << p.m_Name << " 年龄： " << p.m_Age;
	return out;
}

class ComparePerson
{
public:
	// 按照年龄降序排序 
	bool operator()(const Person& p1, const Person& p2) const {
		return p1.m_Age > p2.m_Age;
	}
};

int main()
{
	// 对于自定义数据类型，必须指定排序规则
	set s;

	Person p1("刘备", 30);
	Person p2("关羽", 27);
	Person p3("张飞", 24);
	Person p4("赵云", 21);
	s.insert(p1);
	s.insert(p2);
	s.insert(p3);
	s.insert(p4);

	for (auto p : s)
		cout << p << endl;
	system("pause");
	return 0;
}

• map / multimap属于关联式容器，底层结构是用红黑树实现
• map中所有元素都是pair，第一个元素为键值，起到索引作用，第二个元素为实际值
• 所有元素都会根据元素的键值自动按升序排序
• map不允许容器中有重复键值元素，multimap允许容器中有重复键值元素
• 对于自定义数据类型，map容器必须指定排序规则

// 基本使用
#include 
#include 

// 更改排序方式
#include 
#include 

参考：https://www.bilibili.com/video/BV1et411b73Z