目录
一、map系列
1、map介绍
底层实现：map 是基于红黑树实现的，它保持元素的有序性，插入、删除和查找的时间复杂度 为 O(log n)；
有序性：map 中的元素是按照键的大小有序排列的
2、unordered_map介绍
底层实现： unordered_map 是基于哈希表实现的，它不保持元素的顺序，插入、删除和查找的 时间复杂度为平均 O(1)。
有序性： unordered_map 中的元素是无序的。
内存占用：unordered_map 通常会占用更多的内存，因为哈希表需要额外的空间来存储哈希函 数。
3、map和unordered_map的选择
-
有序性要求：如果需要元素按照键的顺序排列，应该选择
map；如果对元素的顺序没有要求，可以选择unordered_map。 -
时间复杂度：如果对插入、删除和查找操作的时间复杂度有严格要求，且数据量较大，可以选择
unordered_map，因为它的平均时间复杂度更低；如果数据量较小或对时间复杂度要求不高，可以选择map。 -
内存占用：
unordered_map通常会占用更多的内存，因为哈希表需要额外的空间来存储哈希函数，如果内存占用是考虑的因素，可以选择map。
二、set系列
1、set介绍
底层实现：set 是基于红黑树实现的，插入、删除和查找的时间复杂度为 O(log n)；
有序性：set 中的元素是按照键的大小有序排列的;
2、unordered_set介绍
底层实现: unordered_set 是基于哈希表实现的，插入、删除和查找的时间复杂度为平均 O(1)。
有序性： unordered_set 中的元素是无序的。
内存占用：unordered_set 通常会占用更多的内存，因为哈希表需要额外的空间来存储哈希函数。
3、set和unordered_set的选择
-
有序性要求：如果需要元素按照键的顺序排列，应该选择
set；如果对元素的顺序没有要求，可以选择unordered_set。 -
时间复杂度：
unordered_set的插入、删除和查找操作的平均时间复杂度通常比set低，因为unordered_set基于哈希表实现；如果对操作的时间复杂度有要求，可以选择unordered_set。 -
内存占用：
unordered_set通常会占用更多的内存，因为哈希表需要额外的空间来存储哈希函数；如果内存占用是考虑的因素，可以选择set。 -
遍历顺序：如果需要按照键的顺序遍历元素，应该选择
set；如果对遍历顺序没有要求，可以选择unordered_set。
三、如何遍历和查询map和set
有很多方法能遍历，这里只介绍最本人认为最简单的range for法：
1、map的遍历
first是键，second是值
#include <bits/stdc++.h>
using namespace std;
int main() {
unordered_map<string, int> mp;
for (auto it : mp) {
cout << it.first << " " << it.second << endl;
}
}2、map的查询
#include <bits/stdc++.h>
using namespace std;
int main() {
unordered_map<string, int> mp;
int x;
cin>>x;
cout<<mp[x]<<endl;
}
如果输入的x存在于map中，会输出他的值，如果输入的 x 不在 mp 中，程序会输出0。
3、set的遍历
#include <bits/stdc++.h>
using namespace std;
int main() {
unordered_map<int> set;
for (auto it : set) {
cout << it<< endl;
}
}
4、set的查询
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> mySet = {3, 1, 4, 1, 5, 9};
int value = 4;
auto it = mySet.find(value);
if (it != mySet.end()) {
cout << "Value " << value << " found in the set" << endl;
} else {
cout << "Value " << value << " not found in the set" << endl;
}
return 0;
}
使用 find 函数来查找该值是否存在于 set中 如果这个it=mySet.end()说明没找到
四、stack介绍和操作stack的方法
1、stack的介绍
栈（stack）是一种数据结构，遵循后进先出原则，即最后放入栈的元素最先被取出。
可以把这个当做一个只有一个开口的容器，我们往每次往里面放东西都会压到之前放的上面，如果要取东西则只能取最上面的。
2、操作stack的方法
push(element): 将元素压入栈顶。pop(): 弹出栈顶元素。top(): 返回栈顶元素的引用，但不将其从栈中移除。empty(): 检查栈是否为空，返回true如果栈为空，否则返回false。size(): 返回栈中元素的个数。
以下是一个简单代码示例演示：
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> myStack;
// 压入元素
myStack.push(10);
myStack.push(20);
myStack.push(30);
// 访问栈顶元素
cout << "Top element: " << myStack.top() << endl;
// 弹出栈顶元素
myStack.pop();
// 访问栈顶元素
cout << "Top element after pop: " << myStack.top() << endl;
// 检查栈是否为空
if (myStack.empty()) {
cout << "Stack is empty" <<endl;
} else {
cout << "Stack is not empty" << endl;
}
// 获取栈中元素个数
cout << "Stack size: " << myStack.size() << endl;
return 0;
}