江苏手机网站建设公司wordpress主题图片路径

当前位置： 首页 > news >正文

江苏手机网站建设公司,wordpress主题图片路径,中国能源建设集团招聘网站,专业的外贸行业网站设计目录 一.序列式容器和关联式容器 二.set系列的使用 2.1set容器的介绍 2.2set的构造和迭代器 2.3set的增删查 2.4insert和迭代器遍历的样例 2.5find和erase的样例 ​编辑 2.6multiset和set的差异 2.7简单用set解决两道题 两个数组的交集 环形链表二 三.map系列的使用…目录 一.序列式容器和关联式容器 二.set系列的使用 2.1set容器的介绍 2.2set的构造和迭代器 2.3set的增删查 2.4insert和迭代器遍历的样例 2.5find和erase的样例 ​编辑 2.6multiset和set的差异 2.7简单用set解决两道题 两个数组的交集 环形链表二 三.map系列的使用 3.1map类的介绍 3.2pair类型介绍 3.3map的构造 3.4map的增删查 3.5map的数据修改 3.6构造遍历和增删查使用样例 3.7map的迭代器和[]功能样例 3.8multimap和map的差异 3.9用map解决两道题 随机链表的复制 前k个高频单词  一.序列式容器和关联式容器 关于序列式容器STL中的如string、vector、list、deque、array、forward_list等因为逻辑结构为线性序列的数据结构两个位置存储的值之间一般没有紧密的关联关系比如交换一下他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位 置来顺序保存和访问的。 关联式容器也是用来存储数据的与序列式容器不同的是关联式容器逻辑结构通常是非线性结构 两个位置有紧密的关联关系交换一下他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。 map和set底层是红黑树红黑树是⼀颗平衡二叉搜索树。set是key搜索场景的结构 map是key/value搜索场景的结构。 二.set系列的使用 2.1set容器的介绍 • set的声明如下T就是set底层关键字的类型 • set默认要求T支持小于比较如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数 • set底层存储数据的内存是从空间配置器申请的如果需要可以自己实现内存池传给第三个参 数。 • 一般情况下我们都不需要传后两个模版参数。 • set底层是用红黑树实现增删查效率是O(logN) 迭代器遍历是走的搜索树的中序所以是有序 的。 template class T, // set::key_type/value_typeclass Compare lessT, // set::key_compare/value_compareclass Alloc allocatorT // set::allocator_type class set; 2.2set的构造和迭代器 set的支持正向和反向迭代遍历遍历默认按升序顺序因为底层是二叉搜索树迭代器遍历走的中序支持迭代器就意味着支持范围forset的iterator和const_iterator都不支持迭代器修改数据修改关键字数据破坏了底层搜索树的结构。 //默认构造 explicit set(const key_compare comp key_compare(),const allocator_type alloc allocator_type()); //迭代器构造 template class InputIterator set(InputIterator first, InputIterator last,const key_compare comp key_compare(),const allocator_type alloc allocator_type()); //拷贝构造 set(const set x); // 正向迭代器 iterator begin(); iterator end(); // 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend(); 2.3set的增删查 以下是一些我们需要关注的接口 // 单个数据插入如果已经存在则插入失败 pairiterator, bool insert(const value_type val);// 列表插入已经在容器中存在的值不会插入 void insert(initializer_listvalue_type il);// 迭代器区间插入已经在容器中存在的值不会插入 template class InputIterator void insert(InputIterator first, InputIterator last);// 查找val返回val所在的迭代器没有找到返回end() iterator find(const value_type val);// 查找val返回Val的个数 size_type count(const value_type val) const;// 删除一个迭代器位置的值 iterator erase(const_iterator position);// 删除valval不存在返回0存在返回1 size_type erase(const value_type val);// 删除⼀段迭代器区间的值 iterator erase(const_iterator first, const_iterator last);// 返回大于等于val位置的迭代器 iterator lower_bound(const value_type val) const;// 返回大于val位置的迭代器 iterator upper_bound(const value_type val) const; 2.4insert和迭代器遍历的样例 #includeiostream #includeset using namespace std; int main() {// 去重升序排序 setint s;// 去重降序排序给一个大于的仿函数 //setint, greaterint s;s.insert(5);s.insert(2);s.insert(7);s.insert(5);//setint::iterator it s.begin();auto it s.begin();while (it ! s.end()){// error C3892: “it”: 不能给常量赋值 // *it 1;cout *it ;it;}cout endl;// 插入一段initializer_list列表值已经存在的值插入失败 s.insert({ 2,8,3,9 });for (auto e : s){cout e ;}cout endl;setstring strset { sort, insert, add };// 遍历string比较ascll码大小顺序遍历的 for (auto e : strset){cout e ;}cout endl; } 输出 2.5find和erase的样例 #includeiostream #includeset using namespace std;int main() {setint s { 4,2,7,2,8,5,9 };for (auto e : s){cout e ;}cout endl;// 删除最小值 s.erase(s.begin());for (auto e : s){cout e ;}cout endl;// 直接删除xint x;cin x;//9int num s.erase(x);//删除失败返回0if (num 0){cout x 不存在 endl;}for (auto e : s){cout e ;}cout endl;// 直接查找再利用迭代器删除x cin x;//8auto pos s.find(x);if (pos ! s.end())//没有查找到返回end(){s.erase(pos);}else{cout x 不存在 endl;}for (auto e : s){cout e ;}cout endl;// 算法库的查找 O(N) auto pos1 find(s.begin(), s.end(), x);// set自身实现的查找 O(logN) auto pos2 s.find(x);// 利用count间接实现快速查找 cin x;//5if (s.count(x)){cout x 在 endl;}else{cout x 不存在 endl;}return 0; } 输出  当然也可以使用lower_bound和upper_bound 来进行区间删除。 #includeiostream #includeset using namespace std;int main() {std::setint myset;for (int i 1; i 10; i)myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90for (auto e : myset){cout e ;}cout endl;// 实现查找到的[itlow,itup)包含[30, 60]区间 // 返回 30 auto itlow myset.lower_bound(30);// 返回 60 auto itup myset.upper_bound(60);// 删除这段区间的值 myset.erase(itlow, itup);for (auto e : myset){cout e ;}cout endl;return 0; } 2.6multiset和set的差异 multiset和set的使用基本一样但是multiset支持冗余 #includeiostream #includeset using namespace std;int main() {// 相比set不同的是multiset是排序但是不去重 multisetint s { 4,2,7,2,4,8,4,5,4,9 };auto it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;// 相比set不同的是x可能会存在多个find查找中序的第一个 int x;cin x;//4auto pos s.find(x);while (pos ! s.end() *pos x){cout *pos ;pos;}cout endl;// 相比set不同的是count会返回x的实际个数 cout s.count(x) endl;// 相比set不同的是erase给值时会删除所有的x s.erase(x);for (auto e : s){cout e ;}cout endl;return 0; } 输出 2.7简单用set解决两道题 两个数组的交集 class Solution { public:vectorint intersection(vectorint nums1, vectorint nums2) {setint s1(nums1.begin(), nums1.end());setint s2(nums2.begin(), nums2.end());//进入set后自动去重vectorint ret;setint::iterator it1s1.begin();setint::iterator it2s2.begin();while(it1!s1.end()it2!s2.end()){if(*it1*it2){it1;}else if(*it1*it2){it2;}else{ret.push_back(*it1);it1;it2;}}return ret;} }; 环形链表二 class Solution { public:ListNode *detectCycle(ListNode head) {setListNode s;ListNode* curhead;while(cur){pairsetListNode*::iterator,bool rets.insert(cur);if(ret.secondfalse){return cur;}curcur-next;}return nullptr;} }; 三.map系列的使用 3.1map类的介绍 map的声明如下Key就是map底层关键字的类型T是map底层value的类型map默认要求Key支持小于比较如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数map底层存储数据的内存是从空间配置器申请的。⼀般情况下我们都不需要传后两个模版参数。map底层是用红黑树实 现增删查改效率是O(logN) 迭代器遍历是走的中序所以是按key有序顺序遍历的。 template class Key, // map::key_typeclass T, // map::mapped_typeclass Compare lessKey, // map::key_compareclass Alloc allocatorpairconst Key, T // map::allocator_type class map; 3.2pair类型介绍 介绍pair类型之前要先了解pair是什么。map底层的红⿊树节点中的数据使用pair存储键值对数据。 typedef pairconst Key, T value_type; templateclass 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){}//用另一个pair拷贝构造templateclass U, class Vpair(const pairU, V pr) : first(pr.first), second(pr.second){} }; template class T1, class T2 inline pairT1, T2 make_pair(T1 x, T2 y) {return (pairT1, T2(x, y)); } 3.3map的构造 map的支持正向和反向迭代遍历遍历默认按key的升序顺序因为底层是二叉搜索树迭代器遍历走的中序支持迭代器就意味着支持范围formap支持修改value数据不支持修改key数据修改关键字数据破坏了底层搜索树的结构。 //无参默认构造 explicit map(const key_compare comp key_compare(),const allocator_type alloc allocator_type()); //迭代器区间构造 template class InputIterator map(InputIterator first, InputIterator last,const key_compare comp key_compare(),const allocator_type alloc allocator_type()); //拷贝构造 map(const map x); //列表构造 map(initializer_listvalue_type il,const key_compare comp key_compare(),const allocator_type alloc allocator_type()); // 正向迭代器 iterator begin(); iterator end(); // 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend(); 3.4map的增删查 map增接口插入的pair键值对数据跟set所有不同但是查和删的接口只⽤关键字key跟set是完全类似的不过find返回iterator不仅仅可以确认key在不在还找到key映射的value同时通过迭代器还可以修改value。 key_type-The first template parameter(Key) mapped_type-The second template parameter(T) value_type-pairconst key_type, mapped_type // 单个数据插入如果已经key存在则插入失败,key存在相等value不相等也会插入失败 pairiterator, bool insert(const value_type val);// 列表插入已经在容器中存在的值不会插入 void insert(initializer_listvalue_type il);// 迭代器区间插入已经在容器中存在的值不会插入 template class InputIterator void insert(InputIterator first, InputIterator last);// 查找k返回k所在的迭代器没有找到返回end() iterator find(const key_type k);// 查找k返回k的个数 size_type count(const key_type k) const;// 删除⼀个迭代器位置的值 iterator erase(const_iterator position);// 删除kk存在返回0存在返回1 size_type erase(const key_type k);// 删除一段迭代器区间的值 iterator erase(const_iterator first, const_iterator last);// 返回大于等k位置的迭代器 iterator lower_bound(const key_type k);// 返回大于k位置的迭代器 const_iterator lower_bound(const key_type k) const; 3.5map的数据修改 map支持修改mapped_type数据不支持修改key数据修改关键字数据破坏了底层搜索树的结构。 map第一个支持修改的方式时通过迭代器迭代器遍历时或者find返回key所在的iterator修改map还有一个非常重要的修改接口operator[]但是operator[]不仅仅支持修改还支持插入数据和查找数据所以他是一个多功能复合接口 // 查找k返回k所在的迭代器没有找到返回end()如果找到了通过iterator可以修改key对应的 //mapped_type值 iterator find(const key_type k); // insert插入⼀个pairkey, T对象 // 1、如果key已经在map中插入失败则返回一个pairiterator,bool对象返回pair对象 //first是key所在结点的迭代器second是false // 2、如果key不在在map中插入成功则返回一个pairiterator,bool对象返回pair对象 //first是新插入key所在结点的迭代器second是true // 也就是说无论插入成功还是失败返回pairiterator,bool对象的first都会指向key所在的迭 //代器 // 那么也就意味着insert插入失败时充当了查找的功能正是因为这一点insert可以用来实现 //operator[] // 需要注意的是这里有两个pair不要混淆了一个是map底层红黑树节点中存的pairkey, T另 //一个是insert返回值pairiterator, boolpairiterator, bool insert(const value_type val); mapped_type operator; // operator的内部实现 mapped_type operator {// 1、如果k不在map中insert会插入k和mapped_type默认值同时[]返回结点中存储//mapped_type值的引用那么我们可以通过引用修改返映射值。所以[]具备了插入 修改功能// 2、如果k在map中insert会插入失败但是insert返回pair对象的first是指向key结点的//迭代器返回值同时[]返回结点中存储mapped_type值的引用所以[]具备了查找 修改的功能pairiterator, bool ret insert({ k, mapped_type() });iterator it ret.first;return it-second; } 3.6构造遍历和增删查使用样例 #includeiostream #includemap using namespace std; int main() {mapstring,string dict { {left, 左边}, {right, 右边}, {insert, 插入},{ string, 字符串 } };//mapstring, string::iterator it dict.begin();auto it dict.begin();while (it ! dict.end()){//cout (*it).first :(*it).second endl;// map的迭代基本都使用operator-,这里省略了一个- // 第一个-是迭代器运算符重载返回pair第二个箭头是结构指针解引用取pair数据//cout it.operator-()-first : it.operator-()- second endl;cout it-first : it-second endl;it;}cout endl;// insert插入pair对象的4种方式对比之下最后一种最方便 pairstring, string kv1(first, 第一个);dict.insert(kv1);dict.insert(pairstring, string(second, 第二个));dict.insert(make_pair(sort, 排序));dict.insert({ auto, 自动的 });// left已经存在插入失败 dict.insert({ left, 左边剩余 });// 范围for遍历 for (const auto e : dict){cout e.first : e.second endl;}cout endl;string str;while (cin str){auto ret dict.find(str);if (ret ! dict.end()){cout - ret-second endl;}else{cout 无此单词请重新输入 endl;}} return 0; } 输出  3.7map的迭代器和[]功能样例 #includeiostream #includemap #includestring using namespace std; int main() {// 利用find和iterator修改功能统计水果出现的次数 string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (const auto str : arr){// 先查找水果在不在map中 // 1、不在说明水果第⼀次出现则插入{水果, 1} // 2、在则查找到的节点中水果对应的次数 mapstring,int::iterator ret countMap.find(str);if (ret countMap.end()){countMap.insert({ str, 1 });}else{ret-second;}}for (const auto e : countMap){cout e.first : e.second endl;}cout endl;return 0; } #includeiostream #includemap #includestring using namespace std;int main() {// 利用[]插入修改功能巧妙实现统计水果出现的次数 string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (const auto str : arr){// []先查找水果在不在map中 // 1、不在说明水果第一次出现则插入{水果, 0}同时返回次数的引用一下就变成1次了// 2、在则返回水果对应的次数 countMap[str];}for (const auto e : countMap){cout e.first : e.second endl;}cout endl;return 0; } #includeiostream #includemap #includestring using namespace std;int main() {mapstring, string dict;dict.insert(make_pair(sort, 排序));// key不存在-插入 {insert, string()} dict[insert];// 插入修改 dict[left] 左边;// 修改 dict[left] 左边、剩余;// key存在-查找 cout dict[left] endl;for (const auto e : dict){cout e.first : e.second endl;}return 0; } 3.8multimap和map的差异 multimap和map的使用基本完全类似主要区别点在于multimap支持关键值key冗余那么 insert/find/count/erase都围绕着支持关键值key冗余有所差异这里跟set和multiset完全⼀样比如find时有多个key返回中序第一个。其次就是multimap不支持[]因为支持key冗余[]就只能支持插入了不能支持修改。 3.9用map解决两道题 随机链表的复制 class Solution { public:Node copyRandomList(Node* head) {mapNode,Node nodemap;Node* copyheadnullptr;Node* copytailnullptr;Node* curhead;//先不管random把所有节点复制下来while(cur){if(copytailnullptr){copyheadcopytailnew Node(cur-val);}else{copytail-nextnew Node(cur-val);copytailcopytail-next;}//原链表节点与copy的链表节点一一赋值给mapnodemap[cur]copytail;curcur-next;}curhead;Node* copycopyhead;//之后再去管randomwhile(cur){if(cur-randomnullptr){copy-randomnullptr;}else{//因为原链表的random指针指向的位置我们都知道//在nodemap里节点是一一对应的cur的random指向我们可以利用map得到我们复制链表里的位置//nodemap[cur-random]我们复制链表里的与原链表random指向对应的节点copy-randomnodemap[cur-random];}curcur-next;copycopy-next;}return copyhead;} }; 前k个高频单词  class Solution {typedef pairstring,int PSI;struct cmp{bool operator()(const PSI a,const PSI b){if(a.secondb.second)//频次相同创建大根堆{return a.first b.first;//比较字典序}//创建小根堆return a.second b.second;//比较频次}}; public:vectorstring topKFrequent(vectorstring words, int k) {mapstring,int hash;//用哈希表统计每个单词出现的次数for(auto e:words){hash[e];}priority_queuePSI,vectorPSI,cmp heap;//heap里只保存k个PSIfor(auto s:hash){heap.push(s);if(heap.size()k) heap.pop();}vectorstring ret(k);//注意顺序因为升序建大堆降序建小堆堆顶元素与我们想要的是反着的for(int ik-1;i0;i–){ret[i]heap.top().first;heap.pop();}return ret;} };