导航窗格

map、unordered_map和multimap

实现机理：

map是基于红黑树来实现的（红黑树是很是严格的平衡二叉搜索树），红黑树具备自动排序功能，红黑树的每个节点都表明着map中的一个元素，所以对于map的查找，删除和插入操做都是对红黑树的操作。
unordered_map是基于哈希表来实现的，查找的时间复杂度是O(1),在海量数据处理中有着普遍的应用。
multimap是关联式容器，它按特定的次序（按照key来比较）存储由键key和值value组合而成的元素,多个键值对之间的key可以重复。multimap的底层通常是红黑树（平衡二叉搜索树）;
multimap和map的唯一区别是multimap中的key可以重复，而map的key是唯一的.

优缺点

map的优势：（1）map是有序的（2）基于红黑树实现，查找的时间复杂度是O(N)；
map的缺点：空间占用率比较高，由于内部实现了红黑树，虽然提升了运行效率，可是每一个节点都要保存父亲节点和孩子节点和红黑树的性质，使得每个节点都占用大量的空间。适用的状况：对于要有序的结构，适用map；
unordered_map的优势：由于内部是哈希表来实现的，因此查找效率会很高。
unordered_map的缺点：哈希表的创建比较费时。适用的状况：对于查找问题，适用unordered_map会更好一点。

map的常用操作(代码)

/*map中经常使用的操作
*begin()	还回指向map头部的迭代器
*clear()	删除全部元素，注意是全部元素
*count()	还回指定元素出现的次序
*empty()	若是map为空则还回true
*end()		还回指向map末尾的迭代器
*erase()	删除一个元素
*find()		查找一个元素
*insert()	插入一个元素
*max_size()	还回能够容纳的最大元素个数
*size()		还回map中元素的个数
*swap()		交换两个map
*/

int main() {
	map<int, char> m;
	//1、数据的插入
	m.insert(pair<int, char>(1, 'a'));
	m.insert(pair<int, char>(3, 'b'));
	m.insert(pair<int, char>(2, 'c'));
	m.insert(pair<int, char>(-1, 'd'));
	map<int, char>::iterator it = m.begin();
	for (; it != m.end(); it++) {
		cout << it->first << ":" << it->second << endl;
	}
	//2、数据的查找
	/*（1）使用find()函数，该函数能够找到key对应的value
	（2）使用count()函数,该函数的返回值只有0和1，1为找到，可返回要查找的值*/
	it = m.find(1);
	if (it != m.end()) { 
		cout << "find" << it->second << endl; 
	}
	else { 
		cout << "not find" << endl; 
	}

	//3、map的清空
	//m.clear(m.begin(), m.end());

	//4、数据的删除
	//m.erase(it);

	//5、map的反向遍历，使用反向迭代容器
	
	for (map<int, char>::reverse_iterator Rit = m.rbegin(); Rit!=m.rend(); Rit++) {
		cout << Rit->first << ":" << Rit->second;
	}
	return 0;
}

感谢CSDN大佬浮生勿语，该文章部分由本人根据大佬的文章整理而成。原文链接：C++ map和unordered_map的区别和联系以及map的使用

哈希表的底层逻辑

hash_map首先分配一大片内存，形成许多桶。哈希表利用hash函数，对key进行映射到不同区域（桶）进行保存。其插入过程是：

得到key
通过hash函数得到hash值
得到桶号(一般都为hash值对桶数求模)
存放key和value在桶内。

其取值过程是:

得到key
通过hash函数得到hash值
得到桶号(一般都为hash值对桶数求模)
比较桶的内部元素是否与key相等，若都不相等，则没有找到。
取出相等的记录的value。

hash_map中直接地址用hash函数生成，解决冲突，用比较函数解决。这里可以看出，如果每个桶内部只有一个元素，那么查找的时候只有一次比较。当许多桶内没有值时，许多查询就会更快了(指查不到的时候).

set、unordered_set和multiset

unordered_set基于哈希表，是无序的，数据插入和查找的时间复杂度很低，几乎是常数时间，而代价是消耗比较多的内存，无自动排序功能。底层实现上，使用一个下标范围比较大的数组来存储元素，形成很多的桶，利用hash函数对key进行映射到不同区域进行保存。
set基于红黑树实现，红黑树具有自动排序的功能，因此map内部所有的数据，在任何时候，都是有序的。它实现了红黑树的平衡二叉搜索树的数据结构，插入元素时，它会自动调整二叉树的排列，把元素放到适当的位置，以保证每个子树根节点键值大于左子树所有节点的键值，小于右子树所有节点的键值；另外，还得保证根节点左子树的高度与右子树高度相等。平衡二叉搜索树使用中序遍历算法，搜索效率高于vector、deque和list等容器，另外使用中序遍历可将键值按照从小到大遍历出来。
set比unordered_set使用更少的内存来存储相同数量的元素。
对于少量的元素，在set中查找可能比在unordered_set中查找更快。
尽管许多操作在unordered_set的平均情况下更快，但通常需要保证set在最坏情况下有更好的复杂度(例如insert)。
如果我想按顺序访问元素，那么set对元素进行排序的功能是很有用的。
我可以用<、<=、>和>=从字典顺序上比较不同的set集。unordered_set集则不支持这些操作。

通用输入数据如下：

vector<int> list;
    list.push_back(5);
    list.push_back(14);
    list.push_back(34);
    list.push_back(22);
    list.push_back(39);
    list.push_back(5);

set

头文件：#include
介绍：
时间复杂度： O(logN)

unordered_set

头文件：#include
介绍：std::unordered_set 是基于hash表的，因此并不是顺序存储，甚至是杂乱无章的(顺序依赖于 hash function)。
时间复杂度：平均O(1)，最差O(n)。
代码：

 unordered_set<int> set;
	for (int i=0; i<list.size(); i++)
	{
		set.insert(list[i]);
	}
	for (unordered_set<int>::iterator i = set.begin(); i != set.end(); i++) 
	{
		cout << *i << endl;
	}
	cout << " find 39: " << *set.find(39) << endl;
	cout << "count 14:" << set.count(14) << endl;

结果如下：

UnorderdSet
22
39
34
14
5
find 39: 39
count 14:1

在如下情况下，适合使用set

我们需要有序的数据(不同元素)。
我们必须打印/访问数据(按排序顺序)。
我们需要知道元素的前任/继承者。

在如下情况下，适合使用unordered_set

我们需要保留一组元素，不需要排序。
我们需要单元素访问，即不需要遍历。
仅仅只是插入、删除、查找的话。

vector

vector中的erase()函数也只能做到“移动”元素(将目标元素后面的元素整体向前移动)，并将size–。这样一个操作使得数组元素只是看上去被删掉了，实际上和双指针操作是一致的。这个操作的时间复杂度为O(n)而不是O(1)。
vector中所采用的数据结构非常简单：线性连续空间。当分配空间被占满而仍然需要添加元素时，vector便会进行一场空间重新配置的大工程！
在这里，程序员需要注意的是，一旦引起空间重新配置，之前指向原vector的所有迭代器就都失效了，这一点在工程中容易引起bug(!!)。

vector的特点

将元素置于一个动态数组中加以管理。
可以随机存取元素（用索引字节存取）
数组尾部添加或移除元素非常快速。当在头部或中部安插元素比较费时。

vector和数组的区别(考到了！！)

内存中的位置不同。
C++中数组为内置的数据类型，存放在栈中，其内存的分配和释放完全由系统自动完成；vector存放在堆中，由STL库中程序负责内存的分配和释放，使用方便。
数组的大小在初始化后就固定不变，而vector可以通过push_back或pop等操作进行变化。
能否初始化。数组不能将数组的内容拷贝给其他数组作为初始值，也不能用数组为其他数组赋值；而vector可以。
执行效率。数组的执行效率>vector向量。主要原因是vector的扩容过程要消耗大量的时间。

push_back()emplace_back()的区别

push_back()向容器尾部添加元素时，⾸先会创建这个元素，然后再将这个元素拷贝（调⽤拷贝构造函数）或者移动（调⽤移动构造函数）到容器中（如果是拷贝的话，事后会⾃⾏销毁先前创建的这个元素）；
⽽emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。

vector的底层实现(多看一看！)

#include <iostream>
using namespace std;

template<typename T>

class Myvector {
public:
	typedef T value;
	typedef T* iterator;//vector里面的iterator本身就是一个指针
	typedef T& reference;

	Myvector(int len = 0) :m_Data(nullptr), start(nullptr), m_len(len), pos(0) 
	{
		if (len > 0) {
			//创建一个数组
			m_Data = new value[len];
			start = m_Data;
		}
	}

	//在堆上new的内存空间，必须要写一个析构函数delete掉
	~Myvector()
	{
		delete[]m_Data;//注意这里删去的是m_Data
	}

	//先写一个push_back叭
	void push_back(const value& v)
	{
		//这个if语句是为了防止数组越界
		if (m_len != pos) {
			*(start + pos) = v;
			pos++;
		}
		else {
			cout << "越界了" << endl;
		}
		
	}

	//再写一个pop_back。这个函数的返回类型是value
	//这个函数只是缩短了pos，使我们访问不到这个元素，就默认把它pop了。
	//前面加一个inline，内联函数可以加快这个函数的访问速度！
	inline value pop_back()
	{
		--pos;
		return *(start + pos);
	}

	//接下来是vector的数组长度size
	int size()
	{
		return this->m_len;
	}


	//begin函数，你看他就是个迭代器，因此函数类型也是迭代器
	//iterator类型的函数没有返回类型吗。。应该是有的吧
	iterator begin()
	{
		return this->start;
	}

	iterator end()
	{
		return this->start + pos;
	}

	//vector"随机访问"功能
	//要传一个引用值，这样才能在调用的时候对vector对应的元素做修改。
	value& operator[] (int n) {
		if (n <= pos) {
			return *(start + n);
		}
		else {
			cout << "数组越界" << endl;
		}
	}

protected:
	iterator m_Data;
	iterator start;
	int m_len;
	int pos;
};


int main() {
	Myvector <int> vec(10);
	for (int i = 0; i < vec.size(); i++) {
		vec.push_back(i);
	}

	for (Myvector<int> ::iterator it = vec.begin(); it != vec.end(); it++) {
		cout << *it << endl;
	}
}
//输出结果为123456789

stack

栈是一种运算受限的线性表。限定仅在表尾进行插入和删除的操作，是一种符合“后进先出”规则的数据结构。
栈没有自己的迭代器。

queue

定义

用户只能访问 queue 容器适配器的第一个和最后一个元素。只能在容器的末尾添加新元素，只能从头部移除元素。
许多程序都使用了queue容器。queue容器可以用来表示超市的结账队列或服务器上等待执行的数据库事务队列。对于任何需要用FIFO(先入先出)准则处理的序列来说，使用queue容器适配器都是好的选择。
和 stack 一样，queue 也没有迭代器。访问元素的唯一方式是遍历容器内容，并移除访问过的每一个元素。
queue的生成方式和stack相同。queue容器和一些基本操作如下图所示：

	//队列访问元素的方式：如果队列非空，一个个从队列最前面取出
	deque<int> values {9, 6, 8, 0, 8};  
	queue<int> numbers(values);  
	while (!numbers, empty())
	{
	    cout << numbers. front() << " "; // Output the 1st element 
	    numbers. pop();  // Delete the 1st element
	}
	cout << std::endl;

延伸

priority queue——优先队列。普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出（first in, largest out）的行为特征。通常采用堆数据结构来实现。
优先队列一般会和堆划等号，均具有选择出最大/最小的元素以及删除该元素的功能。
参考题目：LC215题——数组中的第K大元素
实际应用场景：统计每个月热歌榜Top10。我不需要知道后面歌曲的热度排名，而仅统计排名前十的歌曲。

deque

双端队列(deque)，顾名思义，两端都可以操作,插入和删除。而且，还可以在中间进行操作。内部采用线性表顺序结构，与vector不同的是，deque采用分块的线性存储结构存储数据，每块大小512字节。所有的deque块使用一个Map块进行管理，每个Map数据项纪录各个deque块的首地址。当考虑容器内部的内存分配策略和操作性能时，deque相对于vector更有优势，同时，也可以用下标来访问。

deque是“double-ended queue的缩写
可以随机存取元素（用索引直接存取）
数组头部和尾部添加或移除元素都非常快，当在中部或头部安插元素比较费时。
Deque相比于vector而言，它没有容量的概念，因为deque是动态地以分段连续空间组合而成，随时都可以增加一段新的空间并链接起来。
(仅作了解)为了使得deque在逻辑上看起来是连续空间，在STL内部实现实际是使用了一块map(不是STL中的map容器)作为主控，map是一小块连续空间，其中每个元素都是指针，指向另一段较大的连续线性空间，称为缓冲区，这些缓冲区才是真正存放deque元素的主体。

list

list是双向链表,有vector,deque的特征,而且效率高。它有插入(前插，后插，中间插)，删除（前删，后删，清空等），排序等功能。而且，可以剔除连续相同元素，保留一个。
list则对空间的使用有绝对的精准，一点也不浪费。注意，list内部构成的实际是一个环状的双向链表。所以只需要一个指针，便可以完整地表现整个链表。

list的特点：

双向链表
不提供随机存取（按顺序走到需要存取的元素，O（n））
在任何位置上执行插入和删除动作都非常块，内部只需要调整一下指针。

STL底层逻辑汇总

NONE