如何识别一个网站是否做的好,私人免费网站怎么下载,热门传奇网页游戏排行榜,可以做同城活动的网站目录
一、关联式容器介绍
1.1概念
1.2键值对
1.3树形结构的关联式容器 1.3.1pair模板介绍
1.3.2make_pair的介绍
二、set的介绍和使用
2.1set介绍
2.2set使用 2.2.1构造
2.2.2容量
2.2.3修改
三、map的介绍和使用 3.1map介绍 3.2map使用 3.2.1构造
3.2.2容量
…目录
一、关联式容器介绍
1.1概念
1.2键值对
1.3树形结构的关联式容器 1.3.1pair模板介绍
1.3.2make_pair的介绍
二、set的介绍和使用
2.1set介绍
2.2set使用 2.2.1构造
2.2.2容量
2.2.3修改
三、map的介绍和使用 3.1map介绍 3.2map使用 3.2.1构造
3.2.2容量
3.2.3修改
四、multiset和multimap简单介绍使用 一、关联式容器介绍
1.1概念
我们之前学过的STL中的部分容器比如string、vector、list、deque等。这些都是序列式容器他们都是线性序列的数据结构里面存储的是元素本身。
关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key,value结构的键值对在数据检索时比序列式容器效率更高
1.2键值对
在搜索二叉树中的kv模型已经介绍过了键值对了它是用来表示具有一一对应关系的结构该结构中包含两个成员变量key和valuekey代表键值value表示与key对应的信息。比如建立英汉词典互译、统计value出现的次数
1.3树形结构的关联式容器 为了更好的管理数据STL设计了两种不同结构的管理式容器树形结构与哈希结构。树形结构的关联式容器主要有四种map、set、multimap、multiset。他们的底层采用都是平衡搜索树(即红黑树)来实现容器中的元素是有序的序列。那么接下来在学习他们的用法前先介绍一下pair以方便后续理解setmap使用。在下一章节将会模拟实现他们。 1.3.1pair模板介绍 pair有两个模板参数pair类中有两个元素firstsecond分别为T1T2类型。其中T1被typedef成first_type,T2被typedef成second_type。其中元素firstsecond可以修改。对于set虽然其key值不存在pair当中但有接口的返回值类型是pair类型。对于map其值key和value存放在pair中。
函数声明功能介绍 pair(); 构造空pair templateclass U, class V pair (const pairU,V pr); 拷贝构造 pair (const first_type a, const second_type b); 分别用两个值初始化pair即分别初始化pair中的first和second元素 pair operator (const pair pr); 通过对象进行赋值
例子
#include iostream
using namespace std;int main()
{pairint, int p(1, 2);//初始化paircout p.first p.second endl;pairint, int pp(p);//拷贝构造pp.first 3;pp.second 4;cout pp.first pp.second endl;pairint, int ret pp;//赋值ret.first 5;ret.second 6;cout ret.first ret.second endl;return 0;
}
输出结果 1.3.2make_pair的介绍 make_pair其实就是一个pair对象。其实现如下 根据其实现pairT1,T2(x,y) 构造了一个默认pair对象并返回也就是说make_pair(T1 x, T2 y) pairT1,T2(x,y) 。所以make_pair即一个pair对象采用make_pair的好处就是简短了一点。
例如
#include iostream
using namespace std;int main()
{pairint, int p(make_pairint,int(1,2));//make_pair即一个pair对象将该对象拷贝给pcout p.first p.second endl;return 0;
} 输出结果 go on~
二、set的介绍和使用
2.1set介绍 1.set是按照一定次序存储元素的容器C中是按中序遍历的。
2.在set中元素key与value是一一对应的且是唯一的。set中的key不能在容器中修改(元素总是const)但是可以插入和删除。因为修改元素就破坏了树的结构。
3.在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。元素的相对顺序是严格确定的。
4.set容器通过key访问单个元素的速度通常比unordered_set(哈希实现)容器慢但他们允许根据顺序对子集直接迭代。
5.set在底层是用红黑树实现的。
注意
1.与map/multimap不同map/multimap中存储的是真正的键值对key,value,set中只放value,但在底层实际存放的是由value,value构成的键值对。
2.set实际使用不需要构造键值对只需传value参数即可。
3.set中的元素不可以重复,所以在插入相同的元素时set会进行去重
4.使用set的迭代器遍历元素得到的是有序序列因为set底层是以中序的方式遍历
5.set中的元素默认按照小于来比较
6.set中查找某个元素时间复杂度为log N
7.红黑树依然是搜索二叉树只不过其实现二叉搜索树的方式不同优化了最初的二叉搜索树的缺点。 set的第一个参数存放元素的类型第二个参数表示set元素默认按照小于来比较第三个参数表示元素空间的管理方式这个先不做了解不影响我们的使用模拟实现。 2.2set使用 2.2.1构造
函数声明功能介绍 explicit set (const key_comparecompkey_compare(),const allocator_type alloc allocator_type()); 构造空set template class InputIteratorset (InputIterator first, InputIterator last,const key_compare comp key_compare(),const allocator_type alloc allocator_type()); 用[first,last)区间中的元素构造set set (const set x);拷贝构造
例子
#include iostream
#include set
using namespace std;int main()
{int arr[] { 2,34,6,6,56,8,321,9,4,88 };setint s(arr, arr sizeof(arr)/sizeof(arr[0]));//迭代器区间构造for (auto e : s){cout e ;}cout endl;setint s1(s);//拷贝构造for (auto e : s1){cout e ;}cout endl;return 0;
}
输出结果 2.2.2容量
函数声明功能介绍 bool empty() const; 检测set是否为空空返回true否则返回false size_type size() const; 返回set中有效元素的个数 size_type max_size() const; 返回set能够存储的最大容量
例子
#include iostream
#include set
using namespace std;int main()
{int arr[] { 2,34,6,6,56,8,321,9,4,88 };setint s(arr, arr sizeof(arr) / sizeof(arr[0]));//迭代器区间构造for (auto e : s){cout e ;}cout endl;cout boolalpha s.empty() endl;//bool值形式打印cout s.size() endl;cout s.max_size() endl;return 0;
}
输出结果 2.2.3修改
函数声明功能介绍pairiterator,bool insert(const value_type x)在set中插入元素x实际插入的是x,x构成的键值对如果插入成功返回该元素在set中的位置true,失败说明x在set中已经存在返回x在set中的位置falsevoid erase(iterator position)删除迭代器所指向position位置上的元素size_type erase(const key_type x)删除set中值为x的元素返回删除的元素的个数void erase(iterator first,iterator last)删除迭代器区间[first,last)中的元素void swap(set st)交换两个set中的元素void clear()将set中的元素清空iterator find(const key_type x) const返回set中值为x的元素的位置未找到返回end()size_type count(const key_type x) const返回set中值为x的元素个数因为set会去重所以要么返回1要么返回0 其中key_type 代表第一个模板参数类型即T
例子
#include iostream
#include set
using namespace std;int main()
{int arr[] { 2,34,6,6,8,9,4};setint s(arr, arr sizeof(arr) / sizeof(arr[0]));//迭代器区间构造setint::iterator it s.begin();while(it ! s.end()){cout *it ;it;}cout endl;it s.find(6);//返回元素的当前位置cout *it endl;cout s.count(6) endl;size_t num s.erase(6);cout num endl;s.erase(s.begin());//删除迭代器当前位置元素it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;s.erase(s.begin(), s.end());//删除迭代器区间中的元素return 0;
}
输出结果 三、map的介绍和使用 3.1map介绍 1.map是关联式容器存储由键值key和value组合的元素。key和value的组合元素跟set一样依然是按照key来进行比较排序。
2.在map中key和value是一一对应的即使类型不同。由于他们绑定在一起并为他们取名为pairkey,value所以对于map而言Key和value元素存放在pairconst key, T类模板当中。其typedef pairconst key, T value_type;
3.map中通过键值访问单个元素的速度通常比unordered_map(哈希实现遍历顺序是无序的)容器慢但map遍历顺序是有序的。
4.map支持下标访问通过key访问即在[]中放入key,就可以找到key对应的value。
5.map由红黑树实现。 第一个参数表示key的类型第二个参数表示value的类型。第三个参数表示map中的元素默认是按key来比较且按小于来比。第四个参数表示空间配置器。 3.2map使用 3.2.1构造
函数声明功能介绍 explicit map (const key_comparecompkey_compare(),const allocator_type alloc allocator_type()); 构造空map template class InputIteratormap (InputIterator first, InputIterator last,const key_compare comp key_compare(),const allocator_type alloc allocator_type()); 用[first,last)区间中的元素构造map map (const map x); 拷贝构造 map operator (const map x); map operator (initializer_listvalue_type il); 通过对象进行初始化。 通过初始化列表进行初始化C11的用法
例子
#include iostream
#include map
using namespace std;int main()
{mapstring, string mp { {apple,苹果}, {banana,香蕉}, {orange,橙子} };//初始化列表进行初始化每个元素都是pair类型for (auto e : mp)//访问map元素实则就是pair中的元素{cout e.first : e.second endl;}cout endl;mapstring, string mmp(mp.begin(), mp.end());//迭代器区间构造mapstring, string::iterator it mmp.begin();while (it ! mmp.end()){cout it-first : it-second endl;it;}cout endl;mapstring, string pm(mmp);//拷贝构造for (auto e : pm){cout e.first : e.second endl;}return 0;
} 输出结果
3.2.2容量
函数声明功能简介 bool empty() const; 检测map中元素是否为空是,返回true否返回false size_type size() const; 返回map中有效元素的个数 mapped_type operator[] (const key_type k); 返回key对应的value。(支持插入修改。若key不存在则插入value并返回。若存在修改value,并返回) mapped_type at (const key_type k);const mapped_type at (const key_type k) const; 返回key对应的value。(支持修改不支持插入。若key不存在抛异常。若存在修改value并返回) 其中mapped_type类型是第二个模板参数的类型即T。
例子
#include iostream
#include map
using namespace std;int main()
{mapstring, int mp { {one,1},{two,2},{three,3},{four,4} };cout boolalpha mp.empty() endl;cout mp.size() endl;cout mp[one]: mp[one] endl;//返回对应的valuecout mp[two]: mp[two] endl;cout mp[three]: mp[three] endl;cout mp[four]: mp[four] endl endl;mp[one] 5;//修改valuemp[two] 6;mp[three] 7;mp[four] 8;mp[nine] 9;//mp对象中没有nine,9。则表示新建key,插入9mp[ten] 10;cout mp[one]: mp[one] endl;//返回对应的valuecout mp[two]: mp[two] endl;cout mp[three]: mp[three] endl;cout mp[four]: mp[four] endl;cout mp[nine]: mp[nine] endl;cout mp[ten]: mp[ten] endl;return 0;
}
输出结果 3.2.3修改
函数声明功能介绍pairiterator,bool insert(const value_type x)在map中插入键值对x注意x是一个键值对即pair类型返回值也是键值对iterator代表新插入元素的位置bool代表插入成功 void erase(iterator position) size_type erase(const key_type x) void erase(iterator first,iterator last) 删除position位置上的元素 删除键值为x的元素 删除[first,last)区间中的元素 void swap(mapKey,T,Compare,Allocator mp)交换两个map中的元素void clear()将map中的元素清空 iterator find(const key_type x) const_iterator find(const key_type x) const 在map中插入key为x的元素找到返回该元素的位置的迭代器否则返回end() 在map中插入key为x的元素找到返回该元素的位置的const迭代器否则返回end() size_type count(const key_type x)返回key为x的键值在map中的个数注意map汇总key是唯一的因此该函数的返回值要么为0要么为1因此也可以用该函数来检测一个key是否在map中
对于operator[]重载实现实则是按如下 由于该长代码不好理解将上述进行拆写那么该重载的实现可以按以下方式 mapped_type operator[](const k key){//插入成功iterator指向的就是插入成功的位置该位置类型为pair类型。插入失败说明已经存在iterator指向的就是已经存在的位置。pairiterator, bool p this-insert(make_pair(k,mapped()));//p.first就是迭代器对象指向k,value所在位置p.first-second就是valuereturn p.first-second;}
接下来就对修改的操作进行演示
#include iostream
#include map
using namespace std;int main()
{mapstring, string mp;mp.insert(pairstring, string(insert, 插入));//将insert,插入插入map中用pair构造键值对//mp.insert(make_pair(insert,插入));//通过make_pair构造键值对mp.insert(make_pair(fruit, 水果));pairmapstring,string::iterator, bool p mp.insert(make_pair(fruit, 水果));//已经存在fruit,水果,返回falsecout boolalpha p.second endl;//通过operator[]向map中插入元素mp[apple] 苹果;//mp.at(peach) 桃子;//peach不存在会抛异常不会插入mapstring, string m;m.swap(mp);cout boolalpha mp.empty() endl;m.erase(apple);mapstring, string::iterator it m.find(apple);if (it ! m.end()){cout 苹果存在 endl;}else{cout 苹果不存在 endl;}cout m.count(peach) endl;return 0;
}输出结果 总结一下map 1.map中的元素是键值对由pair管理。 2.map中的key是唯一的。 3.默认按照小于的方式对key进行比较 4.map中的元素是按中序的方式打印的即有序的。 5.[]操作符可插入可修改。 四、multiset和multimap简单介绍使用 multiset和multimap跟set和map的使用一样。唯一功能不一样的是multiset和multimap中的key不去重正因为有了不去重的功能所以对于他们就没必要提供operator[]因为该接口是先判断是否已经存在key,是则返回key对应的value,可以进行对value修改而不是继续插入key否则是新插入key这就达到了去重的概念。所以他们不提供该接口而对于其他接口的用法和set、map是类似的。 multiset:
#include iostream
#include set
using namespace std;int main()
{string arr[] { apple,apple,banana,apple,orange,grape,peach };multisetstring s(arr, arr sizeof(arr)/sizeof(arr[0]));//不去重for (auto e : s){cout e endl;}return 0;
}
输出结果 multimap:
#include iostream
#include map
using namespace std;int main()
{multimapstring, string mlp { {apple,苹果},{apple,苹果},{orange,橙子},{peach,桃子},{grape,葡萄},{apple,苹果},{banana,香蕉} };for (auto e : mlp){cout e.first : e.second endl;}mlp.insert(make_pair(peach,桃子));mlp.erase(apple);//删除所有applemultimapstring, string::iterator it mlp.find(apple);if (it ! mlp.end()){cout apple is also exist endl;}else{cout apple is not exist endl;}return 0;
} 输出结果 对于他们的底层实现会在之后的章节进一步实现最后封装map和set
end~
