自己做网站怎么搜索,php网站开发教程 pdf,宝塔重装WordPress,怎么查百度搜索排名STL 一共提供了四种与set (集合)相关的算法#xff0c;分别是并集(union)、交集(intersection) 差集 (difference)、对称差集 (symmetricdifference所谓set,可细分为数学上的定义和STL的定义两种#xff0c;数学上的set允许元素重复而未经排序#xff0c;例 如 #x… STL 一共提供了四种与set (集合)相关的算法分别是并集(union)、交集(intersection) 差集 (difference)、对称差集 (symmetricdifference所谓set,可细分为数学上的定义和STL的定义两种数学上的set允许元素重复而未经排序例 如 1,1,4,6,3 , ST L 的定义(也就是set 容器见 5.3节) 则要求元素不得重复并且经过排序例如 1,3,4,6 。本节的四个算法所接受的set,必须是有序区间(sorted range), 元素值得重复出现。换句话说它们可以接受 STL的 set /multiset容器作为输入区间SGI STL 另外提供有 hash_set / hash_m ultiset 两种容器以 hashtable为底层机制(见5.8节、5.10节 )其内的元素并未呈现排序状态所以虽然名称之中也有set字样却不可以应用于本节的四个算法
#include iostream
#include algorithm
#include iterator
#include settemplateclass T
struct display{void operator()(const Tx){std::cout x ;}
};
int main(int argc,char* argv[]) {int ia1[] {1,3,5,7,9,11};int ia2[] {1,1,2,3,5,8,13};std::multisetintS1(ia1,ia16);std::multisetintS2(ia2,ia27);std::for_each(S1.begin(),S1.end(),displayint{});std::cout \n;std::for_each(S2.begin(),S2.end(),displayint{});std::cout \n;std::multisetint::iterator first1 S1.begin();std::multisetint::iterator last1 S1.end();std::multisetint::iterator first2 S2.begin();std::multisetint::iterator last2 S2.end();std::cout Union of S1 and S2: ;std::set_union(first1,last1,first2,last2,std::ostream_iteratorint(std::cout, ));std::cout \n;first1 S1.begin();first2 S2.begin();std::cout Intersection of S1 and S2: ;std::set_intersection(first1,last1,first2,last2,std::ostream_iteratorint(std::cout, ));std::cout \n;first1 S1.begin();first2 S2.begin();std::cout Difference of S1 and S2(S1 - S2): ;std::set_difference(first1,last1,first2,last2,std::ostream_iteratorint(std::cout, ));std::cout \n;first1 S1.begin();first2 S2.begin();std::cout Symmetric difference of S1 and S2: ;std::set_symmetric_difference(first1,last1,first2,last2,std::ostream_iteratorint(std::cout, ));std::cout \n;return 0;
}6.5.1 set_ union
算 法 set_union可 构 造 S1和S2之并集。也就是说它能构造出集合SI U S2,此集合内含S1 或 S2内的每一个元素。S1、S2及其并集都是以排序区间表示。返回值为一个迭代器指向输出区间的尾端由 于 S1和 S 2 内的每个元素都不需唯一因此如果某个值在S1 出 现 n 次在 S2出 现 m 次那么该值在输出区间中会出现max(m,n)次其中n 个来自 s1, 其余来自S2 在 STL set 容器内m1 且 n1 set_union是一种稳定(stable) 操作意思是输入区间内的每个元素的相对 顺序都不会改变。set_union有两个版本差别在于如何定义某个元素小于另一 个元素。第一版本使用operator进行比较第二版本采用仿函数comp进行比较。
// 并集求存在于first1, last1)或存在于first2, last2)的所有元素
// 注意set是一种sorted range这是以下算法的前提
// 版本一
templateclass InputIterator1,class InputIterator2,class OutputIterator
OutputIterator set_union(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2,OutputIterator result){// 当两个区间都尚未到达尾端时执行以下操作…while (first1 ! last1 first2 ! last2){// 在两区间内分别移动迭代器。首先将元素值较小者(假设为A 区)记录于目标区// 然后移动A 区迭代器使之前进同时间之另一个区迭代器不动。然后进行新一次// 的比大小、记录小值、迭代器移动…直到两区中有一区到达尾端。如果元素相等// 取 S1者记录于目标区并同时移动两个迭代器if (*first1 *first2){*result *first1;first1;} else if (*first2 *first1){*result *first2;first2;} else{//*first2 *first1*result *first1;first1;first2;}result;// 只要两区之中有一区到达尾端就结束上述的while循环// 以下将尚未到达尾端的区间的所有剩余元素拷贝到目的端// 此刻的 first1, last1)和 first2 , last2)之中有一个是空白区间return std::copy(first1,first2,std::copy(first2,first2,result));}
}6.5.2 set_intersection
算 法 set_intersection可 构 造 SI、S 2 之交集。也就是说它能构造出集 合 SI∩S2,此集合内同时出现于S 1 和 S 2 内的每一个元素。SI. S2及其交集都是以排序区间表示。返回值为一个迭代器指向输出区间的尾端。由 于 S1和 S 2 内的每个元素都不需唯一因此如果某个值在S1出 现 n 次在 S2出 现 m 次那么该值在输出区间中会出现min(m,n)次并且全部来自 S1.在 STL set 容器内m 1 且 n 1set_inter section是一种稳定(stable)操作意思是输出区间内的每个元素的相对顺序都和S1内的相对顺序相同。它有两个版本差别在于如何定义某个元素小于另一个元素.第一版本使用operator进行比较第二版本采用仿函数comp 进行比较。
// 并集求存在于first1, last1)且存在于first2, last2)的所有元素
// 注意set是一种sorted range 这是以下算法的前提
// 版本一
templateclass InputIterator1,class InputIterator2,class OutputIterator
OutputIterator set_union(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2,OutputIterator result){// 当两个区间都尚未到达尾端时执行以下操作…while (first1 ! last1 first2 ! last2){//在两区间内分别移动迭代器直到遇有元素值相同暂停将该值记录于目标区//再继续移动迭代器… 直到两区之中有一区到达尾端if (*first1 *first2){first1;} else if (*first2 *first1){first2;} else{//*first2 *first1*result *first1;first1;first2;result;}return result;}
} 6.5.3 set_difference
算 法 set_difference可构造SI S 2 之差集。也就是说它能构造出集合 S1 - S2,此集合内含“出现于S 1 但不出现于S2” 的每一个元素。SI. S2及其交集都是以排序区间表示。返回值为一个迭代器指向输出区间的尾端。由于S1和 S 2 内的每个元素都不需唯一因此如果某个值在S1 出现n 次 在 S2出现m 次那么该值在输出区间中会出现max(n-m,0)次并且全部来自S1 . 在 STL set 容器内m 1 且 n 1.set_difference 是一种稳定(stable)操作意思是输出区间内的每个元素 的相对顺序都和S1内的相对顺序相同。它有两个版本差别在于如何定义某个元素小于另一个元素。第一版本使用operator进行比较,第二版本采用仿函数comp进行比较。
// 差集求存在于first1, last1)且不存在于first2, last2)的所有元素
// 注意set是一种sorted range 这是以下算法的前提
// 版本一
templateclass InputIterator1,class InputIterator2,class OutputIterator
OutputIterator set_union(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2,OutputIterator result){// 当两个区间都尚未到达尾端时执行以下操作…while (first1 ! last1 first2 ! last2){// 在两区间内分别移动迭代器。当第一区间的元素等于第二区间的元素(表示此值// 同时存在于两区间)就让两区间同时前进当第一区间的元素大于第二区间的元素,// 就让第二区间前进有了这两种处理就保证当第一区间的元素小于第二区间的// 元素时第一区间的元素只存在于第一区间中不存在于第二区间于是将它// 记录于目标区if (*first1 *first2){*result *first1;first1;result;} else if (*first2 *first1){first2;} else{//*first2 *first1first1;first2;}return std::copy(first1,last1,result);}
} 6.5.4 set_ symmetric_difference
算 法 set_symmetric_difference可构造 SI.S2之对称差集。也就是说 它能构造出集合 (S1-S2) U (S2-S1), 此集合内含出现于S1但不出现于S2以及《出现于S2但不出现于S1的每一个元素。SI、S2及其交集都是以排序区间表示。返回值为一个迭代器指向输出区间的尾端.由于 S1和 S 2 内的每个元素都不需唯一因此如果某个值在S1出现 n 次, 在 S2 出 现 m 次 那么该值在输出区间中会出现ln-m|次 。如 果 n m , 输出 区间内的最后n - m 个 元素将由S 1 复制而来如 果 n m 则输出区间内的最后 m - n 个元素将由S 2 复制而来。在 STL s e t 容器内m 1 且 n 1。 set_ symmetric_difference是 一 种 稳 定 (stable) 操 作 意思是输入区间 内的元素相对顺序不会被改变。它有两个版本差别在于如何定义某个元素小于另一个元素。第一版本使用 operator 进行比较第二版本采用仿函数 comp
// 对称差集求存在于first1, last1)且不存在于first2, last2)的所有元素
// 以及存在于first2, last2)且不存在于first1, last1)的所有元素
// 注意上述定义只有在“元素值独一无二”的情况下才成立.如果将set 一般化
// 允许出现重复元素那么 set-symmetric-difference的定义应该是
// 如果某值在first1 last1) 出现n次在 first2 last2)出现m 次
// 那么它在result range中应该出现abs (n-m)次
// 注意set是一种sorted range 这是以下算法的前提
// 版本一
templateclass InputIterator1,class InputIterator2,class OutputIterator
OutputIterator set_union(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2,OutputIterator result){// 当两个区间都尚未到达尾端时执行以下操作…while (first1 ! last1 first2 ! last2){// 在两区间内分别移动迭代器。当两区间内的元素相等就让两区同时前进// 当两区间内的元素不等就记录较小值于目标区并令较小值所在区间前进if (*first1 *first2){*result *first1;first1;result;} else if (*first2 *first1){*result *first2;first2;result;} else{//*first2 *first1first1;first2;}return std::copy(first1,last1,std::copy(first2,last2,result));}
