STL源碼剖析 set相關算法

  • ?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 <set>template<class T>
struct display{void operator()(const T&x){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::multiset<int>S1(ia1,ia1+6);std::multiset<int>S2(ia2,ia2+7);std::for_each(S1.begin(),S1.end(),display<int>{});std::cout << "\n";std::for_each(S2.begin(),S2.end(),display<int>{});std::cout << "\n";std::multiset<int>::iterator first1 = S1.begin();std::multiset<int>::iterator last1 = S1.end();std::multiset<int>::iterator first2 = S2.begin();std::multiset<int>::iterator last2 = S2.end();std::cout << "Union of S1 and S2: ";std::set_union(first1,last1,first2,last2,std::ostream_iterator<int>(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_iterator<int>(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_iterator<int>(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_iterator<int>(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 容器內，m<=1?且 n<=1
  • ?set_union是一種穩定(stable) 操作，意思是輸入區間內的每個元素的相對 順序都不會改變。set_union有兩個版本，差別在于如何定義某個元素小于另一 個元素。第一版本使用operator<進行比較，第二版本采用仿函數comp進行比較。
// 并集，求存在于［first1, last1)或存在于［first2, last2)的所有元素
// 注意，set是一種sorted range<>這是以下算法的前提
// 版本一
template<class 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 <?1
  • set_inter section是一種穩定(stable)操作，意思是輸出區間內的每個元素的相對順序都和S1內的相對順序相同。它有兩個版本，差別在于如何定義某個元素小于另一個元素.第一版本使用operator進行比較，第二版本采用仿函數comp 進行比較。
// 并集，求存在于［first1, last1)且存在于［first2, last2)的所有元素
// 注意，set是一種sorted range 這是以下算法的前提
// 版本一
template<class 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 這是以下算法的前提
// 版本一
template<class 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 == *first1++first1;++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 這是以下算法的前提
// 版本一
template<class 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 == *first1++first1;++first2;}return std::copy(first1,last1,std::copy(first2,last2,result));}

?

?

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/446430.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/446430.shtml
英文地址，請注明出處：http://en.pswp.cn/news/446430.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

C++ 使用遞增的方式初始化 一個 vector

C++ 使用遞增的方式初始化 一個 vector

int countOdds(int low, int high) {int count 0;std::vector<int>temp{high-low1,0};int n low;std::generate(temp.begin(),temp.end(),[&]{return n;});for (auto x:temp) {std::cout << x;}} 使用Itoa std::iota int countOdds(int low, int high) {in…
閱讀更多...
Python學習4 列表基礎知識和常用函數

Python學習4 列表基礎知識和常用函數

列表 1.格式 2.增刪改查 列表下標&#xff1a; 0–n-1 -n-(-1) #對列表進行切片 #0-(n-1) #-n-(-1) list[dq,python,mm] print(list[0:2])#[0,2) print(list[-3:-2])#[-3,-2) #輸出 #[dq, python] #[dq]題目&#xff1a; 【1&#xff1a;4&#xff1a;2】:[1,4),步長為2 下…
閱讀更多...
Python學習5 元組基礎知識和常用函數

Python學習5 元組基礎知識和常用函數

元組概念 元組&#xff1a;a&#xff08;1&#xff0c;23&#xff09; 列表&#xff1a;a [1,23] 創建和訪問元組 Python 的元組與列表類似&#xff0c;不同之處在于tuple被創建后就不能對其進行修改&#xff0c;類似字符串。 元組與列表類似&#xff0c;也用整數來對它進行…
閱讀更多...
STL源碼剖析 仿函數

STL源碼剖析 仿函數

仿函數 也叫函數對象1&#xff0c;具有函數性質的對象&#xff1b;2&#xff0c;這種東西在調用者可以像函數一樣地被調用(調用)&#xff0c;在被調用者則以對象所定義的function call operator扮 演函數的實質角色。要將某種 “操作”當做算法的參數&#xff0c;唯一辦法就是先…
閱讀更多...
Python學習6 字典基礎知識和常用函數

Python學習6 字典基礎知識和常用函數

字典概念 字典是 Python 提供的一種常用的數據結構&#xff0c;它用于存放具有映射關系的數據。為了保存具有映射關系的數據&#xff0c;Python 提供了字典&#xff0c;字典相當于保存了兩組數據&#xff0c;其中一組數據是關鍵數據&#xff0c;被稱為 key&#xff1b;另一組數…
閱讀更多...
EndNote概述

EndNote概述

概述 EndNote 是SCI&#xff08;Thomson Scientific 公司&#xff09;的官方軟件&#xff0c;支持國際期刊的參考文獻格式有3776 種&#xff0c;寫作模板幾百種&#xff0c;涵蓋各個領域的雜志。簡單來說EndNote的功能就是替你管理文獻&#xff0c;一鍵插入固定格式的參考文獻…
閱讀更多...
Java web后端2 Servlet Maven HttpServlet ServletConfig ServletContext HTTP協議

Java web后端2 Servlet Maven HttpServlet ServletConfig ServletContext HTTP協議

創建項目 新建項目 Java Enterprise JDK1.8 Web Application Tomcat JAVA 默認 過程需要聯網 Maven的配置 IDEA內置Maven 修改本地倉庫位置&#xff0c;因為以后會越來越大 替換配置文件&#xff1a; 阿里云鏡像下載 Servlet基礎 1.動態Web資源開發 2.Servlet是使用J…
閱讀更多...
STL源碼剖析 配接器

STL源碼剖析 配接器

配接器(adapters)在 STL組件的靈活組合運用功能上&#xff0c;扮演著軸承、轉換器的角色。Adapter這個概念&#xff0c;事實上是一種設計模式(design pattern)。 Design Patterns)) 一書提到23個最普及的設計模式&#xff0c;其中對odopter樣式的定義如下&#xff1a;將 一個cl…
閱讀更多...
中科大 計算機網絡3 網絡邊緣Edge

中科大 計算機網絡3 網絡邊緣Edge

網絡結構 邊緣系統 網絡核心 接入網 方塊&#xff1a;邊緣系統(主機) 圓的&#xff1a;網絡核心&#xff0c;數據交換作用 連接邊緣系統和網絡核心的叫做接入網&#xff08;access&#xff09;&#xff0c;把邊緣的主機接入到網絡核心&#xff08;所以是分布式的&#xff09; …
閱讀更多...
STL源碼剖析 入門開始 STL概論與版本簡介

STL源碼剖析 入門開始 STL概論與版本簡介

源代碼之中時而會出現一些全局函數調用操作&#xff0c;尤其是定義于<stl_construct.h> 之中用于對象構造與析構的基本函數&#xff0c;以及定義于<stl_uninitialized.h>之 中 用 于 內 存 管 理 的 基 本 函 數 &#xff0c; 以及定義于<stl_algobase.h>之中…
閱讀更多...
中科大 計算機網絡4 網絡核心Core 分組交換 電路交換

中科大 計算機網絡4 網絡核心Core 分組交換 電路交換

網絡核心 電路交換&#xff08;線路交換&#xff09;&#xff1a;打電話之前&#xff0c;先建立一條鏈路&#xff08;物理&#xff09; 分組交換&#xff1a;存儲轉發的方式 電路交換&#xff08;線路交換&#xff09; 通過信令&#xff08;控制信息&#xff0c;如&#xf…
閱讀更多...
STL 源碼剖析 空間配置器

STL 源碼剖析 空間配置器

以STL的運用角度而言&#xff0c;空間配置器是最不需要介紹的東西&#xff0c;它總是隱藏在一切組件&#xff08;更具體地說是指容器&#xff0c;container&#xff09; 的背后但是STL的操作對象都存放在容器的內部&#xff0c;容器離不開內存空間的分配為什么不說allocator是內…
閱讀更多...
中科大 計算機網絡7 分組延遲 分組丟失 吞吐量

中科大 計算機網絡7 分組延遲 分組丟失 吞吐量

分組丟失和延遲的原因 隊列太長沒有意義&#xff0c;用戶需求 排隊&#xff1a;輸出能力<到來的分組&#xff0c;需要等待 四種分組延遲 節點處理延遲&#xff1a;確定的 排隊延遲&#xff1a;隨機&#xff0c;取決于網絡情況 一個比特的傳輸時間&#xff1a; R1Mbps …
閱讀更多...
STL源碼剖析 迭代器iterator的概念 和 traits編程技法

STL源碼剖析 迭代器iterator的概念 和 traits編程技法

iterator模式定義如下&#xff1a;提供一種方法&#xff0c;使之能夠依序巡訪某個 聚合物(容器)所含的各個元素&#xff0c;而又無需暴露該聚合物的內部表述方式.STL的中心思想在于&#xff1a;將數據容器(containers)和算法(algorithms)分開&#xff0c;彼此獨立設計&#xff…
閱讀更多...
中科大 計算機網絡11 應用層原理

中科大 計算機網絡11 應用層原理

應用層大綱 傳輸層向應用層提供的服務&#xff0c;形式是Socket API&#xff08;原語&#xff09; 一些網絡應用的例子 互聯網層次中&#xff0c;應用層協議最多 流媒體應用&#xff1a;直播 網絡核心最高的層次就是網絡層 應用進程通信方式 C/S&#xff1a; 客戶端&…
閱讀更多...
STL源碼剖析 序列式容器 vector 和 ilist

STL源碼剖析 序列式容器 vector 和 ilist

Vector list 單向鏈表 ilistlist的刪除操作&#xff0c;也只有指向被刪除元素的迭代器會失效&#xff0c;其他迭代器不會受到影響
閱讀更多...
中科大 計算機網絡5 接入網和物理媒體

中科大 計算機網絡5 接入網和物理媒體

接入網 接入網&#xff1a;把邊緣&#xff08;主機&#xff09;接入核心&#xff08;路由器&#xff0c;交換機&#xff09; 骨干網【連接主機和主機】和接入網中都有物理媒體 接入方式&#xff1a;有線和無線 帶寬共享/獨享 接入網&#xff1a;住宅接入modem modem調制解調…
閱讀更多...
STL源碼剖析 序列式容器 deque雙端隊列

STL源碼剖析 序列式容器 deque雙端隊列

相較于vector的內存拷貝&#xff0c;deque在內存不足時只需要進行內存的拼接操作即可&#xff0c;不需要重新配置、復制、釋放等操作&#xff0c;代價就是迭代器的架構不是一個普通的指針&#xff0c;比較復雜d e q u e 的迭代器 deque是分段連續空間。維持其“整體連續”假象…
閱讀更多...
中科大 計算機網絡6 Internet結構和ISP

中科大 計算機網絡6 Internet結構和ISP

互聯網的結構 端系統通過接入ISPs接入互聯網 n個ISP互相連接&#xff1a; IXP,Internet exchage point:互聯網接入點&#xff0c;互聯網交互點 ISP&#xff1a;互聯網服務提供商&#xff0c;提供接入&#xff0c;提供網絡【中國移動&#xff0c;中國電信】 ICP&#xff1a…
閱讀更多...
STL源碼剖析 Stack棧 queue隊列

STL源碼剖析 Stack棧 queue隊列

隨機迭代器用于隨機數據訪問&#xff0c;所以棧stack不具備此功能
閱讀更多...
最新文章

Copyright @ 2022~2023