徐州手机网站建设,手机网站制作相关文章,长春平面网站建设,从化建网站文章目录#x1f31f; 前言#x1f351; 树型结构和哈希结构#x1f351; 键值对1. set的介绍和使用#x1f351; set的模板参数列表#x1f351; set的构造#x1f351; set的使用#x1f345; insert#x1f345; find#x1f345; erase#x1f345; swap#x1…
文章目录 前言 树型结构和哈希结构 键值对1. set的介绍和使用 set的模板参数列表 set的构造 set的使用 insert find erase swap empty size count lower_bound upper_bound2. multiset的介绍和使用 multiset的使用 find erase count3. 两个数组的交集前言
在 STL 中主要有两种类型的容器序列式容器 和 关联式容器
序列式容器里面存储的是元素本身其底层为线性序列的数据结构。比如vectorlistdequeforward_list 等。关联式容器里面存储的是 key, value 结构的键值对在数据检索时比序列式容器效率更高。比如setmapunordered_setunordered_map 等。
但是有一点需要注意STL 当中的 stackqueue 和 priority_queue 属于容器适配器。
stack 和 queue 默认使用的基础容器是 deque而 priority_queue 使用的基础容器是 vector。 树型结构和哈希结构
根据应用场景的不同STL 总共实现了两种不同结构的关联式容器树型结构 和 哈希结构 其中树型结构容器中的元素是一个有序的序列而哈希结构容器中的元素是一个无序的序列。 键值对
键值对是用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量 key 和 valuekey 代表 键值value 表示与 key 对应的信息。
比如现在要建立一个英汉互译的字典那该字典中必然有英文单词与其对应的中文含义而且英文单词与其中文含义是一一对应的关系即通过该应该单词在词典中就可以找到与其对应的中文含义。
SGI-STL 中关于键值对的定义方式如下
template class T1, class T2
struct pair
{typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair() : first(T1()), second(T2()){}pair(const T1 a, const T2 b) : first(a), second(b){}
};1. set的介绍和使用
set 的介绍
set 是按照一定顺序存储元素的容器。在 set 中元素的 value 也标识它value 就是 key类型为 T)并且每个 value 必须是唯一的。set 中的元素不能在容器中修改元素总是 const 类型但是可以从容器中插入或删除它们。在内部set 中的元素总是按照其内部比较对象类型为Compare所指示的特定严格弱排序准则进行排序。set 容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢但 set 容器允许根据顺序对子集进行直接迭代。set 在底层是用二叉搜索树红黑树实现的。
注意
与 map/multimap 不同map/multimap 中存储的是真正的键值对 key, valueset 中只放 value但在底层实际存放的是由 value, value构成的键值对。set 中插入元素时只需要插入 value 即可不需要构造键值对。set 中的元素不可以重复因此可以使用 set 进行去重。使用 set 的迭代器遍历 set 中的元素可以得到有序序列set 中的元素默认按照小于来比较set 中查找某个元素时间复杂度为logNlogNlogNset中的元素不允许修改因为 set 在底层是用二叉查找树来实现的若是对二叉查找树当中某个结点的值进行了修改那么这棵树将不再是二叉查找树。 set的模板参数列表
如下图所示 Tset 中存放元素的类型实际在底层存储 value, value 的键值对。Compareset 中元素默认按照小于来比较。Allocset 中元素空间的管理方式使用 STL 提供的空间配置器管理。 set的构造
这里主要有 3 种方式 1无参构造一个空容器
setint s1; // 构造一个int类型的空容器2拷贝构造某类型容器
setint s2(s1); // 拷贝构造int类型s1容器的复制品3使用迭代器区间进行初始化构造
vectorint v1 { 1,2,3,4,5 };
setint s3(v1.begin(), v1.end()); // 构造vector对象某段区间的复制品set的使用
set 的成员函数主要分为迭代器容量操作修改操作。
需要注意的是对于 set 而言它的普通迭代器和 const 迭代器都不支持修改。 我这里只列举几个常用的其它的可以看文档学习。 insert
在 set 中插入元素 val实际插入的是 val, val 构成的键值对
如果插入成功返回 val在set中的位置, true如果插入失败说明 val 在 set 中已经存在返回 val在set中的位置, false 代码示例
void testset()
{setint s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(2);s.insert(1);s.insert(3);s.insert(3);// 遍历for (auto e : s){cout e ;}
}可以看到当插入重复元素时set 的去掉了的并且还进行了升序的排序 find
在容器中搜索查找 val 元素如果找到则返回一个迭代器否则返回 set::end 的迭代器。 代码示例
void testset()
{setint s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(2);s.insert(1);s.insert(3);s.insert(3);auto pos s.find(5);if (pos ! s.end()){cout 找到了 endl;}
}运行结果 erase
删除 set 中的元素这里有 3 种删除方式。 1从 set 容器中删除单个元素搭配 find 使用
void testset()
{setint s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(6);s.insert(3);s.insert(8);s.insert(7);auto pos s.find(5);if (pos ! s.end()){s.erase(pos); // 删除元素5cout 删除成功 endl;}else{cout 删除失败 endl;}// 遍历for (auto e : s){cout e ;}
}可以看到元素 5 已经被删除了 2从 set 容器中删除单个元素直接传要删除的元素
void testset()
{setint s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(6);s.insert(3);s.insert(8);s.insert(7);s.erase(5);// 遍历for (auto e : s){cout e ;}
}可以看到 5 已经被删除 那么它和第 1 种的区别是什么呢
erase(x)如果 x 存在就删除如果不存在不做任何改变erase(pos)如果 x 存在就删除如果不存在此时 pos 位置指向 set::end 的迭代器那么程序运行就会报错。
其实这种方式本质上可以理解为 erase 去调用了迭代器和 find。
3从 set 容器中删除一组元素传的是迭代器区间 [first,last)
void testset()
{setint s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(6);s.insert(3);s.insert(8);s.insert(7);auto pos s.find(5);if (pos ! s.end()){s.erase(pos, s.end()); // 从5开始所有的元素全部删除cout 删除成功 endl;}else{cout 删除失败 endl;}// 遍历for (auto e : s){cout e ;}
}可以看到从 5 开始所有的元素都已经被删除 swap
交换 set 容器中的元素 代码示例
void testset()
{setint s1;s1.insert(4);s1.insert(5);s1.insert(2);s1.insert(1);setint s2;s2.insert(6);s2.insert(3);s2.insert(8);s2.insert(7);s1.swap(s2);cout s1:;// 遍历for (auto e1 : s1){cout e1 ;}cout s2:;// 遍历for (auto e2 : s2){cout e2 ;}
}可以看到 s1 和 s2 的元素已经被交换了 empty
判断 set 容器是否为空空返回 true非空返回 false。 代码示例
void testset()
{setint s1;s1.insert(4);s1.insert(5);s1.insert(2);s1.insert(1);setint s2;cout s1.empty() endl; // s1容器不为空,输出0cout s2.empty() endl; // s2容器为空,输出1
}运行结果 size
返回 set 中有效元素的个数 代码示例
void testset()
{setint s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(6);s.insert(3);s.insert(8);s.insert(7);// 打印元素个数cout s.size() endl;
}运行结果 count
返回 set 中值为 x 的元素的个数。 代码示例
void testset()
{setint s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(6);s.insert(3);s.insert(8);s.insert(7);// 元素3的个数cout s.count(3) endl;// 元素7的个数cout s.count(10) endl;
}
可以看到 3 出现了一次10 不存在 这个接口对于 set 容器其实没有太大用处因为 set 当中的每个 value 都是唯一的。 lower_bound
返回一个指向容器中第一个元素的迭代器该迭代器不被认为在val之前它是等于或在val之后
其实就是返回大于等于 val 位置的迭代器。 代码示例一
void testset()
{setint s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(3);s.insert(8);s.insert(7);// 如果3存在就返回3位置的迭代器auto lowIt s.lower_bound(3);cout *lowIt endl;// 如果6不存在就返回比6大的位置的迭代器lowIt s.lower_bound(6);cout *lowIt endl;
}运行结果 代码示例二
void testset()
{setint s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(3);s.insert(8);s.insert(7);// 删除大于等于4的所有值auto lowIt s.lower_bound(4);s.erase(lowIt, s.end());// 遍历for (auto e : s){cout e ;}
}可以看到大于等于 4 的所有值都被删除了 upper_bound
返回指向容器中第一个元素的迭代器该元素被认为是 val 之后的元素。
也就是说不管 val 存在还是不存在都返回比 val 大的那个值。 代码示例
void testset()
{setint s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(3);s.insert(8);s.insert(7);// 如果3存在就返回大于3位置的迭代器auto lowIt s.upper_bound(3);cout *lowIt endl;// 如果6不存在就返回比6大的位置的迭代器lowIt s.upper_bound(6);cout *lowIt endl;
}运行结果 其实 lower_bound 和 upper_bound 可以搭配使用删除元素中间的一段区间。
void testset()
{setint s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(6);s.insert(1);s.insert(3);s.insert(8);s.insert(7);// 删除 [3, 7] 这段区间中的所有数auto leftIt s.lower_bound(3); // 返回3位置的迭代器auto rightIt s.upper_bound(7); // 返回8位置的迭代器s.erase(leftIt, rightIt);// 遍历for (auto e : s){cout e ;}
}注意erase 删除的迭代器区间是左闭右开也就是说 rightIt 是 8 位置的迭代器但是 erase 只会删除到 7。
[3, 8) ⇒ [3, 7] 2. multiset的介绍和使用
multiset 的介绍
multiset 是按照特定顺序存储元素的容器其中元素是可以重复的。在 multiset 中元素的 value 也会识别它因为 multiset 中本身存储的就是 value, value 组成的键值对因此 value 本身就是 keykey 就是 value类型为 T)multiset 元素的值不能在容器中进行修改因为元素总是 const 的)但可以从容器中插入或删除。在内部multiset 中的元素总是按照其内部比较规则类型比较所指示的特定严格弱排序准则进行排序。multiset 容器通过 key 访问单个元素的速度通常比 unordered_multiset 容器慢但当使用迭代器遍历时会得到一个有序序列。multiset 底层结构为二叉搜索树(红黑树)。
注意
multiset 中再底层中存储的是 value, value 的键值对mtltiset 的插入接口中只需要插入即可与 set 的区别是multiset 中的元素可以重复set 是中 value 是唯一的使用迭代器对 multiset 中的元素进行遍历可以得到有序的序列multiset 中的元素不能修改在 multiset 中找某个元素时间复杂度为O(logN)O(logN)O(logN)multiset 的作用可以对元素进行排序
multiset的模板参数列表如下 multiset的使用
当我们插入多个元素时multiset 允许键值冗余也就说 multiset 容器当中存储的元素是可以重复的。
代码示例
void testmultiset()
{multisetint ms;ms.insert(4);ms.insert(5);ms.insert(2);ms.insert(2);ms.insert(1);ms.insert(3);ms.insert(3);// 遍历for (auto e : ms){cout e ;}
}可以看到是存在多个相同元素的。 另外它和 set 容器所提供的成员函数的接口都是基本一致的所以就不全部列举了只列举几个稍微有点小差别的函数接口。 find
在容器中搜索 val 元素如果找到则返回中序位置的第一个迭代器否则返回 multiset::end 的迭代器。 代码示例
void testmultiset()
{multisetint ms;ms.insert(4);ms.insert(5);ms.insert(2);ms.insert(2);ms.insert(5);ms.insert(7);ms.insert(1);ms.insert(5);ms.insert(6);ms.insert(5);ms.insert(3);ms.insert(3);for (auto e : ms){cout e ;}cout endl;auto pos ms.find(5); // 多个5的话,返回中序第一个5// 打印pos位置后面的所有元素while (pos ! ms.end()){cout *pos ;pos;}
}可以看到确实是从第一个 5 开始打印的 erase
从容器中删除单个元素直接传要删除的话erase 是的返回值是 size_type
它会把容器中所有的 val 全部删除并且返回删除的 val 的个数。 代码示例
void testmultiset()
{multisetint ms;ms.insert(4);ms.insert(5);ms.insert(2);ms.insert(2);ms.insert(5);ms.insert(7);ms.insert(1);ms.insert(5);ms.insert(6);ms.insert(5);ms.insert(3);ms.insert(3);// 删除容器中所有的5,并返回5的个数cout ms.erase(5) endl;for (auto e : ms){cout e ;}
}可以看到元素 5 已经被删除了并且元素个数是 4。 count
在容器中搜索等同于 val 的元素并返回匹配的个数。 代码示例
void testmultiset()
{multisetint ms;ms.insert(4);ms.insert(3);ms.insert(2);ms.insert(2);ms.insert(5);ms.insert(7);ms.insert(1);ms.insert(3);ms.insert(6);ms.insert(5);ms.insert(3);// 统计3的个数cout ms.count(3) endl;// 遍历for (auto e : ms){cout e ;}
}运行结果 3. 两个数组的交集
题目描述 解题思路
对于求并集、交集、差集其实有一种特定的方法如下图所示 代码实现
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {// 去掉num1当中重复的元素并排序setint s1;for (auto e1 : nums1){s1.insert(e1);}// 去掉num2当中重复的元素并排序setint s2;for (auto e2 : nums2){s2.insert(e2);}vectorint ret; // 存放交集auto it1 s1.begin(); // 指向s1的起始位置auto it2 s2.begin(); // 指向s2的起始位置while (it1 ! s1.end() it2 ! s2.end()) // 当s1和s2都没有遍历完时{if (*it1 *it2) {it1;}else if (*it2 *it1){it2;}else // 当it1和it2指向的元素相等时,就是交集{ret.push_back(*it1); // 把元素尾插到ret中,然后同时向后挪动it1;it2;}}return ret; // 返回交集}
};
