STL中集合的并、交、差 運算

• 聲明
• 集合的介紹
• • 模闆定義
• 并集運算
• • 模闆定義
  • 使用舉例
  • • int類型set使用舉例
    • 自定義類型set使用舉例
• 總結

聲明

• 今天一直在學習STL， 學習目錄參考的是C語言程式設計網， 内容主要參考的是這個網站。 我學習的流程是按照C語言程式設計網的目錄結構， 學到哪一個知識點就去www.cplusplus.com這個網站搜, 他網站自帶的搜尋不太好用， 我有時候會搜不到内容， 可以在必應搜尋中指定網站搜尋， 比如搜尋set就按照set site:www.cplusplus.com這種關鍵詞來搜尋。
• 主要是記錄下來供自己日後參考， 因為一段時間不用就忘了， 是以是按照自己容易了解的方式寫的， 不過任然希望各位可以指出錯誤和欠缺的地方， 共同進步。

集合的介紹

模闆定義

• 模闆(文檔連接配接)

  template < class T,                    // set::key_type/value_type
         class Compare = less<T>,        // set::key_compare/value_compare
         class Alloc = allocator<T>      // set::allocator_type
         > class set;
             

• 介紹

  集合作為一種容器， 它的特殊性在于它的值是獨一無二的（僅考慮set， 不考慮multiset）， 聯想高中學習的集合的3個性質， 無序性、确定性和互異性。在c++的集合中， 可以保證确定性和互異性， 但是沒有無序性， 在set中， 元素的存儲是有序的， 使用的比較方法就是上面模闆中的less<T>。

  集合的其他使用方法不做介紹了， 這裡僅介紹集合的3個運算方法， 并、交、差。在C++中分别是set_union(), set_intersection(), set_difference().下面重點介紹并集， 其它兩個基本一樣， 就換了個名字。

并集運算

模闆定義

• 并集有兩種使用方法，分别是(文檔連接配接)：

// 1
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union (InputIterator1 first1, InputIterator1 last1,
                         InputIterator2 first2, InputIterator2 last2,
                         OutputIterator result);
// 2
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator set_union (InputIterator1 first1, InputIterator1 last1,
                         InputIterator2 first2, InputIterator2 last2,
                         OutputIterator result, Compare comp);
           

• 比較函數 comp 可以不指定， 一般情況下使用第一種即可。但是當使用自定義類型是就需要進行制定了，這個下面再說。

使用舉例

int類型set使用舉例

• 由上面的模闆定義可以看出， set_union()接受5個或6個參數， 前兩個參數指出一個容器的開始和結束的位置， 接下來的兩個參數指出另一容器的開始和結束的位置， 第五個參數指出需要插入容器的疊代器， 第六個參數是一個比較函數， 在使用已經有比較函數的類型的時候， 可以沒有。
• 第五個參數可以通過insert_iterator擷取, 參考它的文檔,觀察其構造函數：

explicit insert_iterator (Container& x, typename Container::iterator i) : container(&x), iter(i) {}
           

知道該函數接受兩個參數， 第一個參數是一個容器， 第二個參數是一個疊代器。當然也可以使用下面這種方式擷取疊代器:

auto iter = std::insert(result, std::begin(result));
           

這個也是參考網站上示例的方式。

• 根據上面的分析， 可以寫出下面的代碼

#include <iostream>
#include <string>
#include <utility>    // for pair<> & make_pair<>()
#include <set>	
#include <algorithm>
#include <iterator>

using std::cout;
using std::endl;
using std::string;
using intSet = std::set<int>;

void setUnion()
{
	intSet first = { 5, 10, 15, 20, 25 };
	intSet second = { 6 ,11, 16, 21, 26, 5, 15 ,20 };
	cout << "第一個集合中的元素時：\n";
	for (auto it : first) { cout << it << " "; }cout << endl;
	cout << "第二個集合中的元素時：\n";
	for (auto it : second) { cout << it << " "; }cout << endl;

	intSet result;

	std::insert_iterator<intSet> it(result, result.begin());
	std::set_union(first.begin(), first.end(), second.begin(), second.end(), it);
	cout << "集合的并集是：" << endl;
	for (auto it : result) { cout << it << " "; }cout << endl;
}
           

自定義類型set使用舉例

• 我們先自定義一個簡單的類型

class People
	{
	public:
		People(const string& fname, const string& sname):m_firstname(fname), m_secondname(sname) {}
		People() = default;
		friend std::ostream& operator<<(std::ostream& out, const People& people);
		friend std::istream& operator>>(std::istream& in, People& people);    // 友善輸出
		
		// 将名字打包傳回, 友善下一個進行名字的比較函數， 那個函數沒有聲明為友元函數， 是以無法直接通路該類的私有變量
		// 此處切不可傳回引用， 隻能使用值傳回的方式， 否則會報錯
		std::pair<string, string> getName() const
		{
			pair<string, string> ret;
			ret = std::make_pair(m_firstname, m_secondname);
			return ret;
		}
		
	private:
		string m_firstname;
		string m_secondname;
	};

	std::ostream& operator<<(std::ostream& out, const People& people)
	{
		out << people.m_firstname << " " << people.m_secondname;
		return out;
	}

	std::istream& operator>>(std::istream& in, People& people)
	{
		in >> people.m_firstname >> people.m_secondname;
		return in;
	}
           

• 這個類有兩個私有變量， m_firstname, 和 m_secondname。可以在類中直接重載<運算符作為比較函數， 像下面的代碼所示， 如果在類内重載<運算符的話， 就不需要另外指定比較函數了。

bool operator<(const People& otherPeople) const 
	{
		return m_secondname < otherPeople.m_secondname || m_secondname == otherPeople.m_secondname && m_firstname < otherPeople.m_firstname;
	}
           

• 但是為了了解set_union()第六個參數的意義， 我采用在外部自定義一個比較函數的方式。如下所示：

struct peopleComp
	{
		bool operator()(const People& people1, const People& people2)
		{
			std::pair<string, string> lname;
			std::pair<string, string> rname;
			lname = people1.getName();
			rname = people2.getName();

			return lname.second < rname.second || lname.second == rname.second && lname.first < rname.first;
		}
	}pComp;
           

• 然後就可以使用下面的函數來進行集合的并集運算了

void setTest()
	{
		using peopleSet = std::set<People, peopleComp>;

		peopleSet first = { {"liu", "bei"}, {"guan", "yu"}, {"zhang", "fei"} };
		peopleSet second = { {"liu", "bei"}, {"cao", "cao"}, {"sun", "quan"} };

		peopleSet result;

		cout << "第一個集合中的元素是：\n";
		for (auto it : first) { cout << it << " "; }cout << endl;
		cout << "第二個集合中的元素是：\n";
		for (auto it : second) { cout << it << " "; }cout << endl;
		
		std::insert_iterator<peopleSet> it(result, result.begin());
		set_union(first.begin(), first.end(), second.begin(), second.end(), it, pComp);
		cout << "二者的并集是：\n";
		for (auto it : result) { cout << it << " "; }cout << endl;
	}
           

• 結果大概如下圖所示

  

總結

• 交集和差集的使用類似， 隻是換了個名字。上面就是我對如何使用并、交、差運算方法的總結。當然于我而言最重要的并不是會使用這三種運算的基本文法， 而是找到了一種學習STL基礎知識的方式。 于我而言， 最重要的兩個資源就是C語言中文網和www.cplusplus.com這兩個網站。 對于沒有太長時間嚼書， 想要在短時間内掌握STL基礎知識來說還是不錯的， C語言中文網提供學習架構，www.cplusplus.com提供學習内容和示例。當然當有了時間之後還是希望自己可以比較系統完全的學習一下STL的，不過更多的還是要在實踐中學習。