STL 之 初識set multiset（map multimap）

一：起因

（1）：set的含義是集合，它是一個有序的容器，裡面的元素都是排序好的，支援插入，删除，查找等操作，就 像一個集合一樣。所有的操作的都是嚴格在logn時間之内完成，效率非常高，具體實作采用了紅黑樹的平衡二叉樹的資料結構。

set和multiset的差別是：set插入的元素不能相同，但是multiset可以相同。

建立 multiset<ss> base; 删除：如果删除元素a,那麼在定義的比較關系下和a相等的所有元素都會被删除

base.count( a )：set能傳回0或者1，multiset是有多少個傳回多少個．

（2）：Set和multiset都是引用<set>頭檔案,複雜度都是logn；Set中的元素可以是任意類型的，但是由于需要排序，是以元素必須有一個序，即大小的比較關系，比如 整數可以用＜比較．

（3）set 和 multiset的對比

（4）set 和 multiset 在STL中的定義

template<class _Kty,
    class _Pr = less<_Kty>,
    class _Alloc = allocator<_Kty> >
class set
//需要包含頭檔案：#include <set> ;   set和multiset都是定義在std空間裡的類模闆
template<class _Kty,
	class _Pr = less<_Kty>,
	class _Alloc = allocator<_Kty> >
class multiset
           

注意： 第二個參數用來定義排序準則。預設準則less是一個仿函數

（5）自定義仿函數（或者應用系統提供的less<> 和 greater<> 等template模闆函數）

struct compare{
bool operator ()(string s1,string s2){
return s1>s2;
}///自定義一個仿函數
};
           

二：代碼介紹

（1）代碼詳解

#include<iostream>
#include<set>// multiset 和 set
using namespace std;
typedef struct
{
	int a;
	char s;
}newtype;
struct compare// 注意，這裡沒有括号 (),自定義比較函數
{
	bool operator()(const newtype &a,const newtype &b) const
	{
	    if(a.s==b.s)
            return a.a < b.a;
		return a.s < b.s;
	}
};// 注意分号
bool fncomp(const newtype &a,const newtype &b);
set<newtype,compare> element;
multiset<newtype,compare> eles;
int main()
{
	newtype a,b,c,d;
	a.a = 1,a.s = 'a';
	b.a = 1,b.s = 'b';
	c.a = 4,c.s = 'c';
	d.a = 3,d.s = 'c';
	element.insert(b);
	element.insert(a);
	element.insert(c);
	element.insert(d);
	element.insert(a);
	set<newtype,compare>::iterator it;
	for(it=element.begin();it!=element.end();it++)
	{
		cout << (*it).a << " ";
	}
	cout << endl;
	for(it=element.begin();it!=element.end();it++)
	{
		cout << (*it).s << " ";
	}
	cout << endl;
	// multiset
	eles.insert(a);
	eles.insert(b);
	eles.insert(c);
	eles.insert(d);
	eles.insert(a);
	set<newtype,compare>::iterator m_it;
	for(m_it=eles.begin();m_it!=eles.end();m_it++)
	{
		cout << (*m_it).a << " ";
	}
	cout << endl;
	for(m_it=eles.begin();m_it!=eles.end();m_it++)
	{
		cout << (*m_it).s << " ";
	}
	cout << endl;
	// 函數指針的應用與multiset，
	bool (*fn_pt)(const newtype&,const newtype&) = fncomp;
	multiset<newtype,bool (*)(const newtype&,const newtype&)> eles2(fn_pt);
	//multiset<newtype,fncomp> eles2;

	eles2.insert(a);
	eles2.insert(c);
	eles2.insert(d);
	eles2.insert(a);
	set<newtype,bool (*)(const newtype&,const newtype&)>::iterator m_it2;// 函數指針的應用
	//set<newtype,fncomp>::iterator m_it2;

	for(m_it2=eles2.begin();m_it2!=eles2.end();m_it2++)
	{
		cout << (*m_it2).a << " ";
	}
	cout << endl;
	for(m_it2=eles2.begin();m_it2!=eles2.end();m_it2++)
	{
		cout << (*m_it2).s << " ";
	}
	cout << endl;
	return 0;
}

bool fncomp(const newtype &a,const newtype &b)
{
    if(a.s==b.s)
            return a.a < b.a;
    return a.s < b.s;
}
           

三：map和multimap

（1）對比簡介

|->名稱----->map

|->個性

|      |------> ①map與set的最大差別在于map是一種特殊的set，它的所有元素都是pair<key,value>

|      |------> ②map最大的特性在于map提供了下标subscript操作的能力，你可以向數組一樣操作  |      |              map[key]來引用相應的值。這個除了友善以外同樣也是問題的根源。

|      |------> ③幾乎所有針對map的操作都是基于key的。比如，排序就是通過比較key來進行的。

|      |------> ④對于set成立的操作在map中基本上都成立

|

|->陷阱

|      |------> ①如果你采用了這樣的語句erase(pos)——其中的pos是個iterator，那麼最好不要在 |    |        對該pos最任何操作，應為erase(pos)已經将這個pos删除了，此後任何關于pos的操作|    |        都視為定義的。這種情況要是發生在for循環中，for(pos=.begin(),pos!=.end         |      |           (),pos++)就能解決問題了。

|      |------> ②假設代碼中有這樣的語句，cout<<map[key],按理這是沒有問題的，但是如果你的 |      |            key在map中原本是不存在的，那麼這句代碼會“自作聰明”的幫你在map中将上一個  |    |         該key的value為default的元素，這恐怕不是件好事。

|      |------> ③map[key]=value的操作要比insert(value)的方式慢。

|

|->說明------>multimap的操作與map大緻一樣，不同在于multimap允許有相同的key在容器中存在。

|

|->Type----->class

|->Include---><map>

|->Define---->map<key,value,optional compare ,optional>

|->Sub

|->Fun

       |------>map和set基本具有相同的操作。

       |------> 不同的是map的insert(elem)不再傳回一個pair而是一個pos的iterator。

（2）map和multimap的差別

以multimap <string, string>authors,為例子，key是作者，值是書名，這種類型允許一個作者寫多本書，而map一個作者隻能寫一本書。map是一種特殊的set

（3）map（set）的基本操作函數：

C++ Maps是一種關聯式容器，包含“關鍵字/值”對

begin() 傳回指向map頭部的疊代器

clear(） 删除所有元素

count() 傳回指定元素出現的次數

empty() 如果map為空則傳回true

end() 傳回指向map末尾的疊代器

equal_range() 傳回特殊條目的疊代器對

erase() 删除一個元素

find() 查找一個元素

get_allocator() 傳回map的配置器

insert() 插入元素

key_comp() 傳回比較元素key的函數

lower_bound() 傳回鍵值>=給定元素的第一個位置

max_size() 傳回可以容納的最大元素個數

rbegin() 傳回一個指向map尾部的逆向疊代器

rend() 傳回一個指向map頭部的逆向疊代器

size() 傳回map中元素的個數

swap() 交換兩個map

upper_bound() 傳回鍵值>給定元素的第一個位置

value_comp() 傳回比較元素value的函數

(4)map 和 multimap的注意事項（三種插入資料的方法）

 Map<int, string> mapStudent;

第一種：用insert函數插入pair資料 （比較這種的方法） ——    mapStudent.insert(pair<int, string>(1, “student_one”)); ；

第二種：用insert函數插入value_type資料 —— mapStudent.insert(map<int, string>::value_type (1, “student_one”)); ；

第三種：用數組方式插入資料（最常用的方法）   ——  mapStudent[1] = “student_one”;  ；

注意：multimap好像不能用 第三種方式，隻能insert方式（大家可以試一試，若有錯誤，歡迎指正）；

三種插入方式，是有所不同的，前兩種是一樣的效果，不能覆寫原有的資料，如：mapStudent.insert(map<int, string>::value_type (1, “student_one”));  mapStudent.insert(map<int, string>::value_type (1, “student_one_new”)); ,第二條資料是不能夠插入的；

而第三種：用數組方式插入資料，可以覆寫原來的資料。

（5) 詳解 map 的成員函數 請看 http://www.cnblogs.com/mattins/p/3531362.html

（6）map的删除方法 —— 這裡要用到erase函數，它有三個重載了的函數（其實map中的成員函數，基本上都重載了三種方法），下面在例子中詳細說明它們的用法

// 第一種： 如果要删除1,用疊代器删除
    map<int, string>::iterator iter;
    iter = mapStudent.find(1);
    mapStudent.erase(iter);
    // 第二種：如果要删除1，用關鍵字删除
    int n = mapStudent.erase(1);//如果删除了會傳回1，否則傳回0
    // 第三種：用疊代器，成片的删除，一下代碼把整個map清空
    mapStudent.earse(mapStudent.begin(), mapStudent.end());
           

  注意：成片删除也是STL的特性，删除區間是一個前閉後開的集合