杭州哪个网站建设最好,苏州网站建设案例,小公司使用的网站开发,wordpress为用户添加积分关于set和map的接口函数部分#xff0c;只重点介绍一些相较于别的容器有特殊地方的接口#xff0c;set和map的接口可以触类旁通。
一、概念
#xff08;一#xff09;、关联式容器 关联式容器存储的元素是一个个的键值对key,value。通过键#xff08;key#x… 关于set和map的接口函数部分只重点介绍一些相较于别的容器有特殊地方的接口set和map的接口可以触类旁通。
一、概念
一、关联式容器 关联式容器存储的元素是一个个的键值对key,value。通过键key可以快速索引到其对应的value值。关联容器可以快速查找、读取或者删除所存储的元素同时该类型的容器插入元素的效率比序列容器如vector高。
二、键值对 键值对用来表示具有一一对应关系的一种结构该结构中只包含两个成员变量key和valuekey代表键值value表示与key对应的信息可以通过键值key快速索引到其对应的信息value。比如说英汉词典查询单词的中文释义就需要通过英文单词快速索引到中文释义这里的键key是英文单词key的类型为stringkey对应的信息value是中文释义value的类型也为string这样英文单词和中文释义就构成了一个string,string的键值对。 键值对可以用pair类来表示pair是C的STL提供的一个类。pair - C Reference (cplusplus.com)https://legacy.cplusplus.com/reference/utility/pair/ pair存储了公有的两个成员变量一个叫做first一个叫做second可以在外部访问这两个成员变量的类型通过用户指定。我们可以用pair的first存储键key用second存储key对应的信息value。 三、关联式容器的结构 根据应用场景的不同STL总共实现了两种不同结构的关联式容器树型结构与哈希结构。树型结构的关联式容器主要有四种map、set、multimap、multiset。这四种容器的共同点是使用平衡二叉搜索树(红黑树)作为其底层结果容器中的元素是一个有序的序列迭代器遍历得到的是一个有序的序列。
二、set和multiset
一set
set - C Reference (cplusplus.com)https://legacy.cplusplus.com/reference/set/set/
set的简介 模板类型 template class T, // set::key_type/value_type class Compare lessT, // set::key_compare/value_compare class Alloc allocatorT // set::allocator_type Tset存储的元素类型。 Compare仿函数用于提供元素之间的比较方法。 Alloc空间配置器 1、set是按照特定次序存储的没有重复元素的容器。 2、在set中一个元素value就对应其本身的值(value本身就是键key类型为T)并且每个元素在set中必须是不能重复的。set中元素的值在容器中不能被再次修改(元素的类型总是const类型)但是可以从容器中插入或删除。 3、在内部set中的元素总是按照其内部比较对象(类型为Compare)所指示的特定严格弱排序标准进行排序。 4、set容器在通过key访问单个元素时通常比unordered_set容器慢但set迭代到的序列是有序的。 5、set通常以平衡二叉搜索树的形式实现。 set的接口
1、插入insert 对于set的insert第一个single element和第三个range版本的插入最常用而中间的第二个with hint版本不是很常用这个接口并不是在指定位置插入而是在插入时提供一个接近最终插入的位置的迭代器对插入元素时的效率进行优化但这种优化效果并不总是显著的因为用户提示不好则会忽略用户的提示从头开始搜索插入位置进行插入且红黑树的平衡性会影响搜索提示时的效率。 注意到第一个single element版本的insert的返回值不是指向新插入位置的迭代器而是pairiterator,bool类型。因为set中的元素都是唯一的set不允许插入已经存在的元素若插入的元素存在时则插入失败将返回一个pairiterator,bool的对象其first成员为指向set中现有元素位置的迭代器second成员bool值为false表示插入失败若插入的元素不存在其first成员为指向新插入元素位置的迭代器second成员bool值为true表示插入成功。 代码例子
#include iostream
#include set
using namespace std;int main()
{setint s;int arr[] { 2,3,5,6,7,1,2,0,5};//将arr的元素依次插入到s中for (auto e : arr){auto ret s.insert(e);if (ret.second false)//插入失败{cout *(ret.first) 已存在插入失败。 endl;}}//打印s的元素for (auto e : s){cout e ;}return 0;
}
运行结果 2已存在插入失败。 5已存在插入失败。 0 1 2 3 5 6 7 2、查找并计数count 这个函数的功能是在容器中搜索与val相等的元素并返回匹配次数。因为每个元素在set中都是唯一的所以返回值只能为0和1。如果只想查找某个元素在不在set容器内可以考虑不使用find函数而使用count函数如果返回值为1那么存在为0则不存在。 代码例子
int main()
{setint s;int arr[] {1,2,3,4,5,6,7,8,9,10};for (auto e : arr){s.insert(e);}//查找某个值在不在s中int x;//方法1使用find函数cin x;auto it s.find(x);if (it ! s.end())cout *it 存在! endl;elsecout x 不存在 endl;cout endl;//方法2使用count函数cin x;if (s.count(x))cout x 存在 endl;elsecout x 不存在 endl;return 0;
}
3、lower_bound和upper_bound
lower_bound得到下界 指定一个值x返回一个迭代器该迭代器指向容器中的第一个满足条件的元素条件是该元素大于或等于x。如果使用默认比较类型 less 实例化 set 类则该函数将返回一个迭代器该迭代器指向的值不小于x。 upper_bound得到上界 指定一个值y返回一个迭代器该迭代器指向容器中的第一个满足条件的元素条件是该元素大于y。如果使用默认比较类型 less 实例化 set 类则该函数将返回一个迭代器该迭代器指向的值大于y。 通过上面两个函数可以获得到两个迭代器当x y 时这两个迭代器维护一个区间区间范围是[x,y)左闭右开可以用于删除指定范围的子序列。
代码例子
int main()
{std::setint myset;std::setint::iterator itlow, itup;for (int i 1; i 10; i) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90//删除区间位于 [25,65) 的元素 itlow myset.lower_bound(25); //找到第一个大于等于25的元素这里是30itup myset.upper_bound(65); //找到第一个大于65的元素这里是70 //删除对应迭代器区间的元素[itlow,itup)myset.erase(itlow, itup); // 10 20 70 80 90std::cout myset contains:;for (std::setint::iterator it myset.begin(); it ! myset.end(); it)std::cout *it;std::cout \n;return 0;
}
运行结果 myset contains: 10 20 70 80 90 4、equal_range 功能指定一个值val返回一对迭代器该迭代器维护着一段区间该区间内的元素的值都为相同为val。由于set的元素是唯一的所以该区间内最多只能有一个元素。若val值不存在两个迭代器都指向位于val之后的第一个元素。
代码例子
int main()
{std::setint myset;for (int i 1; i 5; i) myset.insert(i * 10); // myset: 10 20 30 40 50std::pairstd::setint::const_iterator, std::setint::const_iterator ret;ret myset.equal_range(30);std::cout the lower bound points to: *ret.first \n;std::cout the upper bound points to: *ret.second \n;return 0;
}
运行结果 the lower bound points to: 30 the upper bound points to: 40 二multiset
multiset - C Reference (cplusplus.com)https://legacy.cplusplus.com/reference/set/multiset/ multiset功能和set相似但是multiset允许元素有冗余可以存储多个相同的元素而set里的每个元素都是唯一的。这里直接介绍multiset和set使用上的不同。
1、insert 因为multise允许有重复的数据所以用insert插入数据时不会存在插入失败的情况其返回值不是pairiterator,bool类型而直接就是iterator类型。
2、erase 如果通过erase删除值为value的元素那么在容器中所有与value相等的元素都会被删除。
代码例子
int main()
{multisetint myMultiset;int arr[] { 10,10,20,20,20,30,40,50,60 };for (auto e : arr){myMultiset.insert(e);}for (auto e : myMultiset){cout e ;}cout endl;cout 删除20 endl;myMultiset.erase(20);for (auto e : myMultiset){cout e ;}return 0;
}
运行结果 10 10 20 20 20 30 40 50 60 删除20 10 10 30 40 50 60 3、count 由于元素在multise中不再唯一count的返回值是大于等于0的。
int main()
{multisetint myMultiset;int arr[] { 10,10,20,20,20,30,40,50,60 };for (auto e : arr){myMultiset.insert(e);}for (auto e : myMultiset){cout e ;}cout endl;cout 20出现了 myMultiset.count(20) 次 endl;return 0;
}
运行结果 10 10 20 20 20 30 40 50 60 20出现了3次 4、lower_bound和upper_bound 功能和上面介绍的set的lower_bound和upper_bound一样不过lower_bound和upper_bound在multiset用得更多一些。
代码例子
int main()
{multisetint myMultiset;int arr[] { 10,10,20,20,20,30,40,50,60,60,60,70,80,90,100};//插入数据for (auto e : arr){myMultiset.insert(e);}//打印for (auto e : myMultiset){cout e ;}cout endl;//删除区间位于 [25,65) 的元素 auto itlow myMultiset.lower_bound(25); //找到第一个大于等于25的元素这里是30auto itup myMultiset.upper_bound(65); //找到第一个大于65的元素这里是70 myMultiset.erase(itlow, itup);for (auto e : myMultiset){cout e ;}return 0;
}
运行结果 10 10 20 20 20 30 40 50 60 60 60 70 80 90 100 10 10 20 20 20 70 80 90 100 5、equal_range 功能和上面介绍的set的equal_range一样不过equal_range在multiset用得更多一些可以得到一个迭代器区间该区间内的元素都和指定key相同。
代码例子
int main()
{multisetint myMultiset;int arr[] { 10,10,20,20,20,30,40,50,60,60,60,70,80,90,100 };//插入数据for (auto e : arr){myMultiset.insert(e);}//打印for (auto e : myMultiset){cout e ;}cout endl;//得到重复元素60的迭代器区间pairmultisetint::iterator, multisetint::iterator ret myMultiset.equal_range(60);//删除myMultiset.erase(ret.first, ret.second);//打印for (auto e : myMultiset){cout e ;}cout endl;return 0;
}
运行结果 10 10 20 20 20 30 40 50 60 60 60 70 80 90 100 10 10 20 20 20 30 40 50 70 80 90 100 三、map和multimap
一map
map - C Reference (cplusplus.com)https://legacy.cplusplus.com/reference/map/map/
map的简介 模板类型 template class Key, // map::key_type class T, // map::mapped_type class Compare lessKey, // map::key_compare class Alloc allocatorpairconst Key,T // map::allocator_type key键key的类型。 T映射值value的类型。 Compare: 比较器的类型map中的元素是按照key来比较的缺省情况下按照小于来比较一般情况下(内置类型元素)该参数不需要传递如果无法比较时(自定义类型)需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递) Alloc空间配置器 1、map是一种关联容器用于存储由键key和映射值value组合而成的元素,按照特定顺序存储。 2、在map中键值通常用于对元素进行排序和唯一标识而映射值存储与此键相关的内容。键和映射值的类型可以不同键和映射值在成员中用一个value_type类型的变量组合在一起value_type是将两者组合在一起的pair类型:typedef pairconst Key, T value_type; 3、在内部映射中的元素总是按照其内部比较对象(类型为Compare)所指示的特定严格弱排序标准的键进行排序。 4、map容器在通过键key访问单个元素时通常比unordered_map容器慢但map迭代到的序列是有序的。 5、map中的映射值value可以使用括号操作符((operator[])通过对应的键key直接访问到。 6、map通常以二叉搜索树的形式实现。 map的接口
1、插入insert map存储的元素类型是pairK,V类型插入元素时需要传入pairK,V类型的对象进行插入。
插入例子
void test1()
{//英汉词典mapstring, string dict;//插入方法1:实例化pair对象插入pairstring, string kv1(abandon, v.放弃);dict.insert(kv1);//插入方法2:构造函数生成匿名对象dict.insert(pairstring, string(ability, n. 能力 才能));//插入方法3使用make_pair函数返回pair类型变量dict.insert(make_pair(able, a. 能够有能力的));//插入方法4多参数构造函数的类型转换pairstring, string kv2 { abnormal, a. 不正常的 };dict.insert(kv2);dict.insert({ abnormal, a. 不正常的 });//插入方法5: 初始化列表initializer_list 多参数构造函数的类型转换initializer_listpairconst string, string l { {aboard,ad.在船、飞机上} ,{abolish,v.废除},{about,ad. 大约到处四处} };dict.insert(l);dict.insert({ {aboard,ad.在船、飞机上} ,{abolish,v.废除},{about,ad. 大约到处四处} });//打印词库for (auto e : dict){cout e.first - e.second endl;}
}void test2()
{//插入方法5: 初始化列表initializer_list 多参数构造函数的类型转换//一步到位//英汉词典mapstring, string dict { {abandon, v.放弃},{ability, n. 能力 才能},{abnormal, a. 不正常的},{aboard,ad.在船、飞机上},{abolish,v.废除},{about,ad. 大约到处四处}};//打印词库for (auto e : dict){cout e.first - e.second endl;}
}int main()
{test1();cout endl;test2();return 0;
}
运行结果 abandon - v.放弃 ability - n. 能力 才能 able - a. 能够有能力的 abnormal - a. 不正常的 aboard - ad.在船、飞机上 abolish - v.废除 about - ad. 大约到处四处 abandon - v.放弃 ability - n. 能力 才能 abnormal - a. 不正常的 aboard - ad.在船、飞机上 abolish - v.废除 about - ad. 大约到处四处 2、下标访问operator[]和at 功能使map可以像数组通过下标访问到数据一样通过对应的键key访问到其对应映射的值value。 如果key与容器中元素的键匹配则该函数将返回对其映射值的引用。 如果key与容器中任何元素的键不匹配则该函数将插入一个该键的新元素并返回对其映射值的引用。请注意 本操作会让容器大小增加 1即使没有为该元素分配映射值来初始化该新元素会在构造时使用映射值类型的默认构造进行初始化 功能和operator[]功能类似通过键key访问其映射值返回key对应的映射值的引用。但是如果键key不存在则会抛异常。 代码例子 int main()
{//统计选民的投票次数string arr[] { 张三,李四,张三,李四,王某,王某,李四,李四,王某 };//键名字 映射值投票次数mapstring, int count;//计数for (auto e : arr){//通过名字索引对应的投票次数并加一代表投票次数加一//如果该名字不在count里则用该名字作为key新插入一个元素其映射值使用的是int内置类型的默认构造其值为0count[e]; }//打印选民和对应的投票次数for (auto e : count){cout e.first - e.second endl;}return 0;
} 运行结果 李四 - 4 王某 - 3 张三 - 2 3、其他接口 map的count、lower_bound、upper_bound以及equal_range的功能和set的是一样的其功能在set部分已经着重介绍过了这里不再赘述。
二、multimap multimap和map功能类似这里也不再赘述。需要注意的是multimap允许元素冗余容器中可以存在多个相同key的元素并且multimap中没有重载operator[]和at操作因为multimap中可以有多个相同的key对应不同的映射值使用operator[]的话返回值的类型应该是一个引用映射值的数组这样的话会使内存更加复杂化如果需要得到所有相同key的元素可以通过equal_range得到这个集合的迭代器区间这样更加简洁。
