【C++】关于 std::set | 您所在的位置:网站首页 › intersection函数python输出顺序 › 【C++】关于 std::set |
C++ STL 提供求交集的函数 set_intersection( ) 、求集合差的函数 set_difference( ) 和合并两个集合的函数 set_union( ) 。以 set_intersection( ) 为例,分析两端程序并简单记录其用法: nums1:1,2,2,1 nums2:2,2 #include // set_intersection #include // insert_iterator vector intersection(vector& nums1, vector& nums2) { vector res; set cod1(nums1.begin(),nums1.end()); set cod2(nums2.begin(),nums2.end()); std::set_intersection(cod1.begin(),cod1.end(),cod2.begin(),cod2.end(),insert_iterator(res,res.begin())); return res; // res:2 } vector intersect(vector& nums1, vector& nums2) { vector res; std::sort(nums1.begin(),nums1.end()); std::sort(nums2.begin(),nums2.end()); std::set_intersection(nums1.begin(),nums1.end(),nums2.begin(),nums2.end(),insert_iterator(res,res.begin())); return res; // res:2,2 }首先传递的容器必须是排序的,set 容器中元素默认是排序的,而 vector 需要调用 sort 函数进行排序。其次 set_intersection( )中最后存放交集的容器的容量必须要足够大到能放下所有的元素,即函数只执行复制,不是插入!但是模板 insert_iterator 可以将复制转换为插入,可以解决该问题。 set_intersection( ) 不是 set 的方法,而是一个通用函数,而 set 函数必须要满足这些算法!使用 set 时,可以自动忽略重复的元素,而使用 vector 时可以保留重复的元素,即保留了‘个数’这一信息。 该函数的时间复杂度为线性复杂度,其实现为: template OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) { while (first1!=last1 && first2!=last2) { if (*first1 |
CopyRight 2018-2019 实验室设备网 版权所有 |