江门网站制作流程,一般哪些商家需要建设网站,wordpress百度百家模板,网站做任务 炸金花 #x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;C学习 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 上一篇博客#xff1a;【C】STL… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接C学习 长路漫漫浩浩万事皆有期待 上一篇博客【C】STL详解八—— priority_queue的使用及模拟实现仿函数 文章目录 关联式容器树形结构与哈希结构键值对setset的介绍set的定义方式set的使用 multisetmapmap的介绍map的定义方式map的插入map的查找map的删除map的[ ]运算符重载map的迭代器遍历map的其他成员函数 multimap总结 关联式容器
CSTL包含了序列式容器和关联式容器
序列式容器里面存储的是元素本身其底层为线性序列的数据结构。比如vectorlistdequeforward_list(C11)等。关联式容器里面存储的是key, value结构的键值对在数据检索时比序列式容器效率更高。比如set、map、unordered_set、unordered_map等。
注意 CSTL当中的stack、queue和priority_queue属于容器适配器它们默认使用的基础容器分别是deque、deque和vector。
树形结构与哈希结构
根据应用场景的不同CSTL总共实现了两种不同结构的关联式容器树型结构和哈希结构。
关联式容器 容器结构 底层实现
set、map、multiset、multimap 树型结构 平衡搜索树红黑树unordered_set、unordered_map、 哈希结构 哈希表
unordered_multiset、
unordered_multimap其中树型结构容器中的元素是一个有序的序列而哈希结构容器中的元素是一个无序的序列。
键值对
键值对是用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量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){}
};set
set的介绍
1.set是按照一定次序存储元素的容器使用set的迭代器遍历set中的元素可以得到有序序列。
2.set当中存储元素的value都是唯一的不可以重复因此可以使用set进行去重。
3.与map/multimap不同map/multimap中存储的是真正的键值对key, valueset中只放value但在底层实际存放的是由value, value构成的键值对因此在set容器中插入元素时只需要插入value即可不需要构造键值对。
4.set中的元素不能被修改因为set在底层是用二叉搜索树来实现的若是对二叉搜索树当中某个结点的值进行了修改那么这棵树将不再是二叉搜索树。
5.在内部set中的元素总是按照其内部比较对象所指示的特定严格弱排序准则进行排序。当不传入内部比较对象时set中的元素默认按照小于来比较。
6.set容器通过key访问单个元素的速度通常比unordered_set容器慢但set容器允许根据顺序对元素进行直接迭代。
7.set在底层是用平衡搜索树红黑树实现的所以在set当中查找某个元素的时间复杂度为logN。
set的定义方式
方式一 构造一个某类型的空容器。
setint s1; //构造int类型的空容器方式二 拷贝构造某类型set容器的复制品。
setint s2(s1); //拷贝构造int类型s1容器的复制品方式三 使用迭代器拷贝构造某一段内容。
string str(abcdef);
setchar s3(str.begin(), str.end()); //构造string对象某段区间的复制品方式四 构造一个某类型的空容器比较方式指定为大于。
set int, greaterint s4; //构造int类型的空容器比较方式指定为大于set的使用
set当中常用的成员函数如下
成员函数 功能
insert 插入指定元素
erase 删除指定元素
find 查找指定元素
size 获取容器中元素的个数
empty 判断容器是否为空
clear 清空容器
swap 交换两个容器中的数据
count 获取容器中指定元素值的元素个数set当中迭代器相关函数如下
成员函数 功能
begin 获取容器中第一个元素的正向迭代器
end 获取容器中最后一个元素下一个位置的正向迭代器
rbegin 获取容器中最后一个元素的反向迭代器
rend 获取容器中第一个元素前一个位置的反向迭代器使用示例
#include iostream
#include set
using namespace std;int main()
{setint s;//插入元素去重s.insert(1);s.insert(4);s.insert(3);s.insert(3);s.insert(2);s.insert(2);s.insert(3);//遍历容器方式一范围forfor (auto e : s){cout e ;}cout endl; //1 2 3 4//删除元素方式一s.erase(3);//删除元素方式二setint::iterator pos s.find(1); //查找值为1的元素if (pos ! s.end()){s.erase(pos);}//遍历容器方式二正向迭代器setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl; //2 4//容器中值为2的元素个数cout s.count(2) endl; //1//容器大小cout s.size() endl; //2//清空容器s.clear();//容器判空cout s.empty() endl; //1//交换两个容器的数据setint tmp{ 11, 22, 33, 44 };s.swap(tmp);//遍历容器方式三反向迭代器setint::reverse_iterator rit s.rbegin();while (rit ! s.rend()){cout *rit ;rit;}cout endl; //44 33 22 11return 0;
}multiset
multiset容器与set容器的底层实现一样都是平衡搜索树红黑树其次multiset容器和set容器所提供的成员函数的接口都是基本一致的这里就不再列举了multiset容器和set容器的唯一区别就是multiset允许键值冗余即multiset容器当中存储的元素是可以重复的。
#include iostream
#include set
using namespace std;int main()
{multisetint ms;//插入元素允许重复ms.insert(1);ms.insert(4);ms.insert(3);ms.insert(3);ms.insert(2);ms.insert(2);ms.insert(3);for (auto e : ms){cout e ;}cout endl; //1 2 2 3 3 3 4return 0;
}由于multiset容器允许键值冗余因此两个容器中成员函数find和count的意义也有所不同
find
成员函数find 功能
set对象 返回值为val的元素的迭代器
multiset对象 返回底层搜索树中序的第一个值为val的元素的迭代器count
成员函数count 功能
set对象 值为val的元素存在则返回1不存在则返回0find成员函数可代替
multiset对象 返回值为val的元素个数find成员函数不可代替map
map的介绍
1.map是关联式容器它按照特定的次序按照key来比较存储键值key和值value组成的元素使用map的迭代器遍历map中的元素可以得到有序序列。
2.在map中键值key通常用于排序和唯一地标识元素而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类型value_type绑定在一起并取别名为pair。
3.map容器中元素的键值key不能被修改但是元素的值value可以被修改因为map底层的二叉搜索树是根据每个元素的键值key进行构建的而不是值value。
4.在内部map中的元素总是按照键值key进行比较排序的。当不传入内部比较对象时map中元素的键值key默认按照小于来比较。
5.map容器通过键值key访问单个元素的速度通常比unordered_map容器慢但map容器允许根据顺序对元素进行直接迭代。
6.map容器支持下标访问符即在[]中放入key就可以找到与key对应的value。
7.map在底层是用平衡搜索树红黑树实现的所以在map当中查找某个元素的时间复杂度为logN。
map的定义方式
方式一 指定key和value的类型构造一个空容器。
mapint, double m1; //构造一个key为int类型value为double类型的空容器方式二 拷贝构造某同类型容器的复制品。
mapint, double m2(m1); //拷贝构造key为int类型value为double类型的m1容器的复制品方式三 使用迭代器拷贝构造某一段内容。
mapint, double m3(m2.begin(), m2.end()); //使用迭代器拷贝构造m2容器某段区间的复制品方式四 指定key和value的类型构造一个空容器key比较方式指定为大于。
mapint, double, greaterint m4; //构造一个key为int类型value为double类型的空容器key比较方式指定为大于map的插入
map的插入函数的函数原型如下
pairiterator,bool insert (const value_type val);insert函数的参数显示是value_type类型的实际上value_type就是pair类型的别名
typedef pairconst Key, T value_type;因此我们向map容器插入元素时需要用key和value构造一个pair对象然后再将pair对象作为参数传入insert函数。
方式一 构造匿名对象插入。
#include iostream
#include string
#include map
using namespace std;int main()
{mapint, string m;//方式一调用pair的构造函数构造一个匿名对象插入m.insert(pairint, string(2, two));m.insert(pairint, string(1, one));m.insert(pairint, string(3, three));for (auto e : m){cout e.first , e.second ;}cout endl; //1,one 2,two 3,threereturn 0;
}但是这种方式会使得我们的代码变得很长尤其是没有直接展开命名空间的情况下因此我们最常用的是方式二。
方式二 调用make_pair函数模板插入。 在库当中提供以下make_pair函数模板
template class T1, class T2
pairT1, T2 make_pair(T1 x, T2 y)
{return (pairT1, T2(x, y));
}我们只需向make_pair函数传入key和value该函数模板会根据传入参数类型进行自动隐式推导最终构造并返回一个对应的pair对象。
#include iostream
#include string
#include map
using namespace std;int main()
{mapint, string m;//方式二调用函数模板make_pair构造对象插入m.insert(make_pair(2, two));m.insert(make_pair(1, one));m.insert(make_pair(3, three));for (auto e : m){cout e.first , e.second ;}cout endl; //1,one 2,two 3,threereturn 0;
}insert函数的返回值 insert函数的返回值也是一个pair对象该pair对象中第一个成员的类型是map的迭代器类型第二个成员的类型的一个bool类型具体含义如下
若待插入元素的键值key在map当中不存在则insert函数插入成功并返回插入后元素的迭代器和true。 若待插入元素的键值key在map当中已经存在则insert函数插入失败并返回map当中键值为key的元素的迭代器和false。
map的查找
map的查找函数的函数原型如下
iterator find (const key_type k);map的查找函数是根据所给key值在map当中进行查找若找到了则返回对应元素的迭代器若未找到则返回容器中最后一个元素下一个位置的正向迭代器。
#include iostream
#include string
#include map
using namespace std;int main()
{mapint, string m;m.insert(make_pair(2, two));m.insert(make_pair(1, one));m.insert(make_pair(3, three));//获取key值为2的元素的迭代器mapint, string::iterator pos m.find(2);if (pos ! m.end()){cout pos-second endl; //two}return 0;
}map的删除
map的删除函数的函数原型如下
//删除函数1
size_type erase (const key_type k);
//删除函数2
void erase(iterator position);也就是说我们既可以根据key值删除指定元素也可以根据迭代器删除指定元素若是根据key值进行删除则返回实际删除的元素个数。
#include iostream
#include string
#include map
using namespace std;int main()
{mapint, string m;m.insert(make_pair(2, two));m.insert(make_pair(1, one));m.insert(make_pair(3, three));//方式一根据key值进行删除m.erase(3);//方式二根据迭代器进行删除mapint, string::iterator pos m.find(2);if (pos ! m.end()){m.erase(pos);}return 0;
}map的[ ]运算符重载
map的[ ]运算符重载函数的函数原型如下
mapped_type operator[] (const key_type k);[ ]运算符重载函数的参数就是一个key值而这个函数的返回值如下
(*((this-insert(make_pair(k, mapped_type()))).first)).second实际上[ ]运算符重载实现的逻辑实际上就是以下三个步骤 调用insert函数插入键值对。 拿出从insert函数获取到的迭代器。 返回该迭代器位置元素的值value。 对应分解代码如下
mapped_type operator[] (const key_type k)
{//1、调用insert函数插入键值对pairiterator, bool ret insert(make_pair(k, mapped_type()));//2、拿出从insert函数获取到的迭代器iterator it ret.first;//3、返回该迭代器位置元素的值valuereturn it-second;
}那么这个函数的价值体现在哪里呢我们来看看下面这段代码
#include iostream
#include string
#include map
using namespace std;int main()
{mapint, string m;m.insert(make_pair(2, two));m.insert(make_pair(1, one));m.insert(make_pair(3, three));m[2] sherry; //修改key值为2的元素的value为sherrym[6] six; //插入键值对6, sixfor (auto e : m){cout e.first , e.second ;}cout endl; //1,one 2,sherry 3,three 6,sixreturn 0;
}以代码中的m[2] sherry为例说明通过[ ]运算符重载函数的三个步骤后不管是调用insert函数插入的也好是容器当中本来就已经存在的也好反正无论如何map容器当中都已经有了一个key值为2的元素。而[ ]运算符重载函数的返回值就是这个key值为2的元素的value的引用因此我们对该函数的返回值做修改实际上就是对键值为2的元素的value做修改。
总结 如果k不在map中则先插入键值对k, V()然后返回该键值对中V对象的引用。 如果k已经在map中则返回键值为k的元素对应的V对象的引用。
map的迭代器遍历
map当中迭代器相关函数如下
成员函数 功能
begin 获取容器中第一个元素的正向迭代器
end 获取容器中最后一个元素下一个位置的正向迭代器
rbegin 获取容器中最后一个元素的反向迭代器
rend 获取容器中第一个元素前一个位置的反向迭代器遍历方式一 用正向迭代器进行遍历。
#include iostream
#include string
#include map
using namespace std;int main()
{mapint, string m;m.insert(make_pair(2, two));m.insert(make_pair(1, one));m.insert(make_pair(3, three));//用正向迭代器进行遍历mapint, string::iterator it m.begin();while (it ! m.end()){cout it-first , it-second ;it;}cout endl; //1,one 2,two 3,threereturn 0;
}遍历方式二 用反向迭代器进行遍历。
#include iostream
#include string
#include map
using namespace std;int main()
{mapint, string m;m.insert(make_pair(2, two));m.insert(make_pair(1, one));m.insert(make_pair(3, three));//用反向迭代器进行遍历mapint, string::reverse_iterator rit m.rbegin();while (rit ! m.rend()){cout rit-first , rit-second ;rit;}cout endl; //3,three 2,two 1,onereturn 0;
}遍历方式三 用范围for进行遍历。
#include iostream
#include string
#include map
using namespace std;int main()
{mapint, string m;m.insert(make_pair(2, two));m.insert(make_pair(1, one));m.insert(make_pair(3, three));//用范围for进行遍历for (auto e : m){cout e.first , e.second ;}cout endl; //1,one 2,two 3,threereturn 0;
}注意 编译器在编译时会自动将范围for替换为迭代器的形式因此支持了迭代器实际上就支持了范围for。
map的其他成员函数
除了上述成员函数外set当中还有如下几个常用的成员函数
成员函数 功能
size 获取容器中元素的个数
empty 判断容器是否为空
clear 清空容器
swap 交换两个容器中的数据
count 获取容器中指定key值的元素个数使用示例
#include iostream
#include string
#include map
using namespace std;int main()
{mapint, string m;m.insert(make_pair(2, two));m.insert(make_pair(1, one));m.insert(make_pair(3, three));//获取容器中元素的个数cout m.size() endl; //3//容器中key值为2的元素个数cout m.count(2) endl; //1//清空容器m.clear();//容器判空cout m.empty() endl; //1//交换两个容器中的数据mapint, string tmp;m.swap(tmp);return 0;
}multimap
multimap容器与map容器的底层实现一样也都是平衡搜索树红黑树其次multimap容器和map容器所提供的成员函数的接口都是基本一致的这里也就不再列举了multimap容器和map容器的区别与multiset容器和set容器的区别一样multimap允许键值冗余即multimap容器当中存储的元素是可以重复的。
#include iostream
#include string
#include map
using namespace std;int main()
{multimapint, string mm;//插入元素允许重复mm.insert(make_pair(2, two));mm.insert(make_pair(2, double));mm.insert(make_pair(1, one));mm.insert(make_pair(3, three));for (auto e : mm){cout e.first , e.second ;}cout endl; //1,one 2,two 2,double 3,threereturn 0;
}由于multimap容器允许键值冗余因此两个容器中成员函数find和count的意义也有所不同
find
成员函数find 功能
map对象 返回值为键值为key的元素的迭代器
multimap对象 返回底层搜索树中序的第一个键值为key的元素的迭代器count
成员函数count 功能
map对象 键值为key的元素存在则返回1不存在则返回0find成员函数可代替
multimap对象 返回键值为key的元素个数find成员函数不可代替其次由于multimap容器允许键值冗余调用[ ]运算符重载函数时应该返回键值为key的哪一个元素的value的引用存在歧义因此在multimap容器当中没有实现[ ]运算符重载函数。
总结
今天我们比较详细地学习了set、map、multiset、multimap的相关知识了解了一些有关的底层原理。接下来我们将用一棵红黑树封装出map和set。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
