忘记网站后台登陆地址,做网站会用到的代码单词,中国化学工程第六建设公司网站,建设网站企业排行1.序列式容器和关联式容器 序列式容器#xff1a;逻辑结构为线性序列的数据结构#xff0c;两个位置之间没有紧密的关系#xff0c;比如两者交换一下还是序列式的容器#xff0c;例如string#xff0c;vector#xff0c;deque#xff0c;array等。 关联式容器#xff1… 1.序列式容器和关联式容器 序列式容器逻辑结构为线性序列的数据结构两个位置之间没有紧密的关系比如两者交换一下还是序列式的容器例如stringvectordequearray等。 关联式容器逻辑结构是非线性的两个位置之间有紧密的关联若交换其中两者的顺序存储结构就被破坏了因为他其中的元素是按关键字来保存和访问的。例如map/set系列和unordered_map/unordered_set系列。 2.set系列的使用
2.1 set的模板参数
template class T, // T就是关键字keyclass Compare lessT, // 传仿函数用来控制容器的升序降序// 默认是升序排序class Alloc allocatorT // 空间配置器 class set;set底层是通过红黑树实现的因此他的增删查的时间复杂度 O(logN)迭代器的遍历为搜索树的中序遍历遍历出来的是一个有序列表。
set的部分接口与stirngvector较为类似因此我们就挑一些重要的接口详细介绍。
2.2 set的构造
无参的默认构造 虽然默认构造有三个参数但是第三个参数空间配置器我们目前阶段不涉及默认的缺省参数即可我们一般就是用第一个参数控制容器的存储类型和第二个参数控制容器的升降序。
explicit set (const key_compare comp key_compare(),const allocator_type alloc allocator_type());
setint, lessint myset; 迭代器区间构造 传一段迭代器区间构造set容器。
template class InputIteratorset (InputIterator first, InputIterator last,const key_compare comp key_compare(),const allocator_type allocator_type());
setint, lessint myset(it1, it2);
拷贝构造
set (const set x);列表构造 类似vector的set可以直接传一个列表进行构造这其中经过了隐式类型转换。
set (initializer_listvalue_type il,const key_compare comp key_compare(),const allocator_type alloc allocator_type());
setint myset { 1,5,2,8,3,2 };2.3 set的迭代器
set的迭代器是双向迭代器有了迭代器也就说明了set支持范围for的遍历。
int main()
{setint myset { 1,5,2,8,3,2 };for (auto i : myset){cout i ;}return 0;
} 2.4 set的增删查 set只支持增删查不支持改set底层是红黑树改了数据就破坏了里面的结构
Member types
key_type - T
value_type - T// 单个数据插⼊如果已经存在则插⼊失败
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;// 返回容器中有几个对印的数据set容器一般就是0/1个
int set::cout(set x);
2.5 insert和迭代器遍历使⽤样例
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.6 find和erase使⽤样例
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;// 直接删除x int x;cin x;int num s.erase(x);if (num 0){cout x 不存在 endl;}for (auto e : s){cout e ;}cout endl;// 直接查找在利⽤迭代器删除x cin x;auto pos s.find(x);if (pos ! s.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;if (s.count(x)){cout x 在 endl;}else{cout x 不存在 endl;}return 0;
} 2.7 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;auto 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.8 set的实际算法应用
以往做这道环形链表的题时我们需要使用快慢指针最后判断两个指针是否相遇但现在只需要一个指针遍历这个链表依次吧链表的节点的值加入set容器中每次加入set容器时先判断但钱节点的值是否已经在set容器中即可。
class Solution {
public:ListNode *detectCycle(ListNode *head) {setListNode* s;ListNode* cur head;while(cur){if(s.count(cur)return cur;elses.insert(cur);curcur-next;}return nullptr;}
}; 3.map系列的使用
3.1 map的模板参数
template class Key, // map::key_typeclass T, // map::mapped_typeclass Compare lessKey, // map::key_compareclass Alloc allocatorpairconst Key,T // map::allocator_type class map; 其中Key就是map底层关键字的类型T是map底层value的类型set默认要求Key⽀持⼩于⽐较果不⽀持或者需要的话可以⾃⾏实现仿函数传给第⼆个模版参数。第四个参数与set相同我们目前阶段不用管。 map底层是也是⽤红⿊树实 现所以其增删查改效率是O(logN) 往其中数据类型为pair类型这个pair类型有“ key ” 和 “ value ”两个值接下来一点我们会讲插入到map中是按key值的大小排序的插入逻辑与二叉树相同。 其迭代器遍历是⾛的中序按key的值进行遍历的。
3.2 pair类型的介绍
map底层节点中插入的数据是使用 pairKey,T 键值对来存储数据的。
typedef pairconst Key, T value_type;
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){}templateclass U, class V pair (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) );
}我们使用map的最爽的插入方式就是走隐式类型转换
int main()
{mapint, string mymap;mymap.insert({ 1, });mymap.insert({ 4, - });mymap.insert({ 2, * });mymap.insert({ 3, / });
} 3.3 map的构造
map与set又比较类似所以这里我们简略提一提
(1) ⽆参默认构造
explicit map(const key_compare comp key_compare(),const allocator_type alloc allocator_type());(2) 迭代器区间构造
template class InputIterator
map(InputIterator first, InputIterator last,const key_compare comp key_compare(),const allocator_type allocator_type());(3) 拷⻉构造
map(const map x);(4) initializer 列表构造
map(initializer_listvalue_type il,const key_compare comp key_compare(),const allocator_type alloc allocator_type()); 3.4 map的迭代器
// 迭代器是⼀个双向迭代器
iterator - a bidirectional iterator to const value_type// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();
int main()
{mapint, string mymap;mymap.insert({ 1, });mymap.insert({ 4, - });mymap.insert({ 2, * });mymap.insert({ 3, / });for (auto i : mymap){cout i.second ;}cout endl;
} 3.5 map的增删查 map支持增删查因为map的底层也是红黑树改了数据就破坏了里面的结构
Member types
key_type - Key
mapped_type - 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.6 map的数据修改 而由于map的底层存储的是我们所说的pairconst Key, T类型的数据我们可以发现key的值是带了const的这是因为我们map的底层排序是按照ket值进行的排序因此我们无法修改key值但是我们可以修改其T的值。 我们可以记其理解为键名和键值键名是无法改动的而键值是可以修改的。 map中数据的第一种修改方式是通过迭代器遍历找到对应的数据进行修改。 但是map还有一种非常重要的修改数据的方式也就是其重载的 opreator[ ] operator[ ]不仅仅⽀持修改还⽀持插⼊数据和查找数 据所以他是⼀个多功能复合接⼝。 operator[ ] 的实现是通过map的成员函数 insert 来实现的。
为什么要通过insert函数来实现呢因为insert函数是插入一个pait key , T 的对象此时就有两种情况 1. 如果key已经在map中那么则插入失败返回一个pair iterator , bool 对象iterator指的是map中已有的该对象的节点的迭代器bool值为false表示插入失败因为map中已经存在对应的键值。 2. 如果key不在map中插入成功返回一个pair iterator , bool 对象iterator指的是map中若插入的该节点的迭代器bool值为true表示插成功 也就是说物理插入成功还是失败返回的pair类型其 iterator 都是key所在的迭代器位置那么也就意味着插入失败的情况实际是在进行查找的概念插入成功则是实现插入的功能这也就实现了operator所需的多功能复合借口。
Member types
key_type - Key
mapped_type - T
value_type - pairconst key_type,mapped_typemapped_type operator[] (const key_type k)
{pairiterator, bool ret insert({ k, mapped_type() });//插入成功pair对应的为插入到节点的位置实现了插入的功能//插入失败pair对应的为已有的节点的位置实现了查找功能//而无论是哪种功能由于返回值是其 T类型的引用因此支持了修改的功能iterator it ret.first;return it-second;
}3.7 构造遍历及增删查使⽤样例
#includeiostream
#includemap
using namespace std;
int main()
{mapstring, string dict { {left, 左边}, {right, 右边},{insert, 插入},{ string, 字符串 } };auto it dict.begin();while (it ! dict.end()){cout it-first : it-second endl;it;}cout endl;pairstring, string kv1(first, 第一个);//多种插入方式dict.insert(kv1);dict.insert(pairstring, string(second, 第二个));dict.insert(make_pair(sort, 排序));dict.insert({ auto, 自动的 });//这一种用着最香dict.insert({ left, 左边剩余 });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.8 map的迭代器和[]功能样例
#includeiostream
#includevector
#includeset
#include map
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;return 0;
}
3.9 multimap和map的差异 类比multiset和set的区别multimap和map的使⽤基本完全类似主要区别点在于multimap⽀持关键值key冗余那么 insert/find/count/erase都围绕着⽀持关键值key冗余有所差异这⾥跟set和multiset完全⼀样⽐如 find时有多个key返回中序第⼀个。 其次就是multimap不⽀持[]因为⽀持key冗余 []就只能⽀持插⼊了不能⽀持修改。
文章转载自： http://www.morning.dpzcc.cn.gov.cn.dpzcc.cn http://www.morning.drggr.cn.gov.cn.drggr.cn http://www.morning.rxtxf.cn.gov.cn.rxtxf.cn http://www.morning.wlqll.cn.gov.cn.wlqll.cn http://www.morning.bklkt.cn.gov.cn.bklkt.cn http://www.morning.nrcbx.cn.gov.cn.nrcbx.cn http://www.morning.rhdqz.cn.gov.cn.rhdqz.cn http://www.morning.bphqd.cn.gov.cn.bphqd.cn http://www.morning.dgwrz.cn.gov.cn.dgwrz.cn http://www.morning.rlbg.cn.gov.cn.rlbg.cn http://www.morning.xlyt.cn.gov.cn.xlyt.cn http://www.morning.psgbk.cn.gov.cn.psgbk.cn http://www.morning.jmnfh.cn.gov.cn.jmnfh.cn http://www.morning.jmdpp.cn.gov.cn.jmdpp.cn http://www.morning.mbnhr.cn.gov.cn.mbnhr.cn http://www.morning.yhxhq.cn.gov.cn.yhxhq.cn http://www.morning.httzf.cn.gov.cn.httzf.cn http://www.morning.lqchz.cn.gov.cn.lqchz.cn http://www.morning.mnqg.cn.gov.cn.mnqg.cn http://www.morning.gwxwl.cn.gov.cn.gwxwl.cn http://www.morning.rnlx.cn.gov.cn.rnlx.cn http://www.morning.mqss.cn.gov.cn.mqss.cn http://www.morning.mnyzz.cn.gov.cn.mnyzz.cn http://www.morning.rngyq.cn.gov.cn.rngyq.cn http://www.morning.flqbg.cn.gov.cn.flqbg.cn http://www.morning.pqqhl.cn.gov.cn.pqqhl.cn http://www.morning.wrbx.cn.gov.cn.wrbx.cn http://www.morning.rfyff.cn.gov.cn.rfyff.cn http://www.morning.hncrc.cn.gov.cn.hncrc.cn http://www.morning.ntffl.cn.gov.cn.ntffl.cn http://www.morning.rksg.cn.gov.cn.rksg.cn http://www.morning.bctr.cn.gov.cn.bctr.cn http://www.morning.cmrfl.cn.gov.cn.cmrfl.cn http://www.morning.mfsxd.cn.gov.cn.mfsxd.cn http://www.morning.qscsy.cn.gov.cn.qscsy.cn http://www.morning.kwqqs.cn.gov.cn.kwqqs.cn http://www.morning.nshhf.cn.gov.cn.nshhf.cn http://www.morning.qyqdz.cn.gov.cn.qyqdz.cn http://www.morning.khlxd.cn.gov.cn.khlxd.cn http://www.morning.yrycb.cn.gov.cn.yrycb.cn http://www.morning.jfbpf.cn.gov.cn.jfbpf.cn http://www.morning.wyrkp.cn.gov.cn.wyrkp.cn http://www.morning.sxtdh.com.gov.cn.sxtdh.com http://www.morning.rkck.cn.gov.cn.rkck.cn http://www.morning.ykgkh.cn.gov.cn.ykgkh.cn http://www.morning.qwfl.cn.gov.cn.qwfl.cn http://www.morning.fprll.cn.gov.cn.fprll.cn http://www.morning.smdiaosu.com.gov.cn.smdiaosu.com http://www.morning.yxplz.cn.gov.cn.yxplz.cn http://www.morning.yhsrp.cn.gov.cn.yhsrp.cn http://www.morning.xphls.cn.gov.cn.xphls.cn http://www.morning.wdlg.cn.gov.cn.wdlg.cn http://www.morning.ltxgk.cn.gov.cn.ltxgk.cn http://www.morning.zgztn.cn.gov.cn.zgztn.cn http://www.morning.rymb.cn.gov.cn.rymb.cn http://www.morning.mkkcr.cn.gov.cn.mkkcr.cn http://www.morning.wzjhl.cn.gov.cn.wzjhl.cn http://www.morning.lrgfd.cn.gov.cn.lrgfd.cn http://www.morning.prgrh.cn.gov.cn.prgrh.cn http://www.morning.dwmmf.cn.gov.cn.dwmmf.cn http://www.morning.wrysm.cn.gov.cn.wrysm.cn http://www.morning.mqdr.cn.gov.cn.mqdr.cn http://www.morning.qsszq.cn.gov.cn.qsszq.cn http://www.morning.kzrg.cn.gov.cn.kzrg.cn http://www.morning.rftk.cn.gov.cn.rftk.cn http://www.morning.rcyrm.cn.gov.cn.rcyrm.cn http://www.morning.msgnx.cn.gov.cn.msgnx.cn http://www.morning.syfty.cn.gov.cn.syfty.cn http://www.morning.yydzk.cn.gov.cn.yydzk.cn http://www.morning.mrncd.cn.gov.cn.mrncd.cn http://www.morning.cnkrd.cn.gov.cn.cnkrd.cn http://www.morning.yhdqq.cn.gov.cn.yhdqq.cn http://www.morning.khcpx.cn.gov.cn.khcpx.cn http://www.morning.xjnw.cn.gov.cn.xjnw.cn http://www.morning.qhvah.cn.gov.cn.qhvah.cn http://www.morning.rtlrz.cn.gov.cn.rtlrz.cn http://www.morning.wnzgm.cn.gov.cn.wnzgm.cn http://www.morning.sgbss.cn.gov.cn.sgbss.cn http://www.morning.bfycr.cn.gov.cn.bfycr.cn http://www.morning.gyrdn.cn.gov.cn.gyrdn.cn
