序列式容器和关联式容器

• 序列式容器在逻辑上是线性的，在物理上不一定连续，它们的数据之间没有太大的关联，比如交换两个位置的数，依旧是序列式容器，比如vector,list,deque等
• 关联式容器在逻辑上是非线性的，两个位置的关系是紧密相关的，比如二叉搜索树，随意交换两个位置就破坏了这棵树的结构

map和set的介绍

map和set底层是红黑树，红黑树是平衡二叉搜索树，平衡二叉搜索树接近完全二叉树的结构，但不是完全二叉树，查找效率提高了，等于logN次，set是key的场景，map是key/value的场景。

set

支持增删查，不支持改，修改会改变树的性质

构造和迭代器遍历和insert

int main()
{// 降序排序+去重 Greater > set<int, greater<int>> t;// 升序排序+去重 Less <// set<int> t;t.insert(5);t.insert(7);t.insert(2);t.insert(5);// set<int>::iterator it = t.begin();auto it = t.begin();while(it != t.end()){// set不管什么迭代器都不支持修改// 修改会改变其内部结构// 按二叉搜索树的排序,中序，升序排序// *it = 10;cout << *it << " ";++it;}cout << endl;// initializer list 相同的值会插入失败t.insert({ 1,2,9,2,7 });for (auto e : t){cout << e << " ";}cout << endl;// void insert(initializer_list<value_type> ls);set<string> strset = { "sort","insert","add" };// 语法上隐式类型转换生成临时对象，临时对象拷贝构造strset// 编译器直接优化为构造// set<string> strset({ "sort","insert","add" });// 语法上构造for (auto& e : strset){cout << e << " ";}cout << endl;return 0;
}

find

// 算法库的find O(N)
auto pos = find(t.begin(), t.end(), x);
// set的find O(logN)
auto pos = t.find(x);

erase

1. 删除某个位置的迭代器
2. 删除某个值，返回成功删除数据的个数，删除失败返回0，为了兼容multiset(有数据冗余的set),这里面有多个相同的x
3. 删除迭代器区间
   迭代器失效：
   1.删除的是根节点或只有一个孩子的节点，父亲节点已经链接其他节点了，去访问删除的节点是野指针，节点已经变了，意义变了
   2.删除的节点是有两个孩子的节点，替代法删除，把替代的节点删除，原来要删的节点的位置的迭代器失效，访问会崩溃，节点已经变了，意义变了
   

int main()
{// 1.删除某个位置的迭代器set<int> t = { 1,2,93,403,43 };for (auto e : t){cout << e << " ";}cout << endl;// 删除最小值 [first,end),升序排序t.erase(t.begin());for (auto e : t){cout << e << " ";}cout << endl;// 2.删除某个值int x;/*cin >> x;int num = t.erase(x);if (num == 0){cout << num << "不存在" << endl;}else{cout << num << "删除成功" << endl;}cout << endl;for (auto e : t){cout << e << " ";}cout << endl;*/// 3.删除一个迭代器区间cin >> x;auto pos = t.find(x);if(pos != t.end()){// 删除这个节点后,该点迭代器失效t.erase(pos);// 不要访问,vs强制检查会崩溃cout << *pos << endl;// 访问Node节点}else{cout << "不存在" << endl;}for (auto e : t){cout << e << " ";}cout << endl;return 0;
}

swap

交换两个树的根节点

clear

清掉数据不清空间

count

value_type其实是为multiset准备的
功能：这个值在的话返回1，不在返回0

cin >> x;
if (t.count(x))
{cout << x << "在" << endl;
}
else
{cout << x << "不在" << endl;
}

lower_bound和upper_bound

lower_bound和upper_bound底层是按照二叉搜索树的逻辑进行查找的，logN

int main()
{std::set<int> myset;for (int i = 1; i < 10; i++){myset.insert(i * 10);// 10 20 30 40 50 60 70 80 90}for (auto e : myset){cout << e << " ";}cout << endl; 返回 >= 30//auto lowit = myset.lower_bound(30); 返回 > 50//auto upit = myset.upper_bound(50); 30 40 50 // 返回 >= 25auto lowit = myset.lower_bound(25);// 返回 > 55auto upit = myset.upper_bound(55);// 30 40 50 // 删除这段区间的值, 迭代器区间的都是[)myset.erase(lowit, upit);for (auto e : myset){cout << e << " ";}cout << endl;return 0;
}

multiset和set的对比

• multiset和set都在set头文件下，multiset允许键值冗余,insert/find/count/erase都围绕着支持值冗余有所差异
  

int main()
{// 排序但是不去重multiset<int> t = { 1,2,1,2,342 };auto it = t.begin();while (it != t.end()){cout << *it << " ";++it;}cout << endl; 有多个x的话,find查找的是中序的第一个int x;cin >> x;//auto pos = t.find(x);//while (pos != t.end() && *pos == x)//{//	cout << *pos << " ";//	++pos;//}//cout << endl;//auto pos = t.find(x);//while (pos != t.end() && *pos == x)//{//	pos = t.erase(pos);//	// 删除后返回当前位置的下一个迭代器//}//cout << endl;cout << t.count(x) << endl;t.erase(x);// erase把所有x都删除it = t.begin();while (it != t.end()){cout << *it << " ";++it;}cout << endl;// 返回x的个数cout << t.count(x) << endl;return 0;
}

set的二个题目

题目链接

题目解析

算法原理

代码

class Solution 
{
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {// 用set进行去重+排序set<int> s1(nums1.begin(),nums1.end());set<int> s2(nums2.begin(),nums2.end());vector<int> ret;auto it1 = s1.begin();auto it2 = s2.begin();while(it1 != s1.end()&& it2 != s2.end()){if(*it1 == *it2){ret.push_back(*it1);++it1;++it2;}else if(*it1 > *it2){++it2;}else{++it1;}}return ret;}
};

介绍一个找差集的算法

差集：是一个集合有，另一个集合没有的数据（去除两个集合共同有的数据）

同步算法

题目解析

题目链接

算法原理

让节点一个一个地插入set中，如果set中第一次存在一个重复的节点的话，返回这个重复的节点就是循环的开始

代码

class Solution 
{
public:ListNode *detectCycle(ListNode *head) {set<ListNode*> p;ListNode* cur = head;while(cur){if(p.count(cur))return cur;elsep.insert(cur);cur = cur->next;}return nullptr;}
};

map

map也有map和multimap之分
map支持修改，但是修改的是value的值，迭代器也支持修改value
key->key
T->value
在二叉搜索树那里就是把两个参数分开放
在map这里是把两个参数放在一个pair中，封装了一层
第一个参数是key，第二个参数是value

构造

int main()
{// 1.构造对象pair插入dict(有名对象)map<string, string> dict;pair<string, string> kv1("auto", "一");dict.insert(kv1);// 2.匿名对象dict.insert(pair<string, string>("string", "二"));// 3.make_pair模版dict.insert(make_pair("vector", "三"));// 4.C++11dict.insert({ "map","三" });// 插入时只看key,value不相等时不会更新// key相等时插入失败,map是不允许冗余的dict.insert({ "map","三二" });return 0;
}

遍历

结构体指针用->
对象用 .
map不允许冗余，unordered_map允许冗余

map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{// 只支持修改value,不支持修改key// first不支持修改// 底层存的是const first // 这里是const string// it->first += 'x';it->second += 'x';// map不支持*it// cout << *it << " ";// cout << (*it).first << ":" << (*it).second << endl;cout << it->first << ":" << it->second << endl;//cout << it.operator->()->first << ":" << it.operator->()->second << endl;// operator* 返回数据的引用 pair// operator-> 返回数据的指针 pair*++it;
}
cout << endl;

initiaizer_list

都用第一种，不会用第二种的

// 1
map<string, string> dict = { {"left", "左边"}, {"right", "右边"}, {"insert", "插入"},{ "string", "字符串" } };
// 2
pair<string, string> kv1("string", "一");
map<string, string> dict = { kv1, pair<string, string>("一", "二") };

用最外层括号给给initiaizer_list，里面的{}隐式类型转换为pair的两个参数