C++中map和set的簡介及使用詳解

2022-02-24 10:00:05

關聯式容器

關聯式容器包括序列式容器和關聯式容器

序列式容器： 底層為線性序列的資料結構，裡面儲存的是元素本身，包含vector、list、deque、forward_list(C++11)等。
關聯式容器： 裡面儲存的是<key, value>結構的鍵值對，在資料檢索時比序列式容器效率更高，包含set、map、unordered_set、unordered_map等。

注意： stack、queue和priority_queue屬於容器介面卡

鍵值對

用來表示具有一一對應關係的一種結構，該結構中一般只包含兩個成員變數key和value，key代表鍵值，value表示與key對應的資訊。

現在要建立一個英漢互譯的字典，那該字典中必然有英文單詞與其對應的中文含義，而且，英文單詞與其中文含義是一一對應的關係，即通過該應該單詞，在詞典中就可以找到與其對應的中文含義。

SGI-STL中關於鍵值對的定義：

template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;
	T1 first;
	T2 second;
	pair() : first(T1()), second(T2())
	{}
	pair(const T1& a, const T2& b) : first(a), second(b)
	{}
};

set

set的介紹

set是按照一定次序儲存元素的容器。
在set中，元素的value必須是唯一的。set中的元素不能在容器中修改(元素總是const)，但是可以從容器中插入或刪除它們。
在內部，set中的元素總是按照其內部比較物件(型別比較)所指示的特定嚴格弱排序準則進行排序。
set容器通過key存取單個元素的速度通常比unordered_set容器慢，但它們允許根據順序對子集進行直接迭代。
set在底層是用二元搜尋樹(紅黑樹)實現的。

注意：

與map/multimap不同，map/multimap中儲存的是真正的鍵值對<key, value>，set中只放value，但在底層實際存放的是由<value, value>構成的鍵值對。
set中插入元素時，只需要插入value即可，不需要構造鍵值對。
set中的元素不可以重複(因此可以使用set進行去重)。
使用set的迭代器遍歷set中的元素，可以得到有序序列
set中的元素預設按照小於來比較
set中查詢某個元素，時間複雜度為：logN

set的使用

set的模板參數列

T: set中存放元素的型別，實際在底層儲存<value, value>的鍵值對。
Compare：set中元素預設按照小於來比較
Alloc：set中元素空間的管理方式，使用STL提供的空間設定器管理

set的構造

函數宣告	功能介紹
set (const Compare& comp = Compare(), const Allocator& =Allocator());	構造空的set
set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() );	用[first, last)區間中的元素構造set
set ( const set<Key,Compare,Allocator>& x);	set的拷貝構造

set中常用的成員函數

成員函數	功能
insert	插入元素
erase	刪除元素
find	查詢元素
size	獲取容器中元素的個數
clear	清空容器
empty	判空
swap	交換兩個容器中的資料
count	獲取某個元素的個數

使用範例

int main()
{
	set<int> s;
	//插入元素(自動去重）
	s.insert(1);
	s.insert(4);
	s.insert(3);
	s.insert(3);
	s.insert(2);
	s.insert(2);
	s.insert(3);
	//遍歷容器
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	//查詢元素
	set<int>::iterator pos = s.find(3);
	//刪除元素
	s.erase(pos);// 刪除元素3
	s.erase(4);
	//容器大小
	cout << s.size() << endl;
	//清空容器
	s.clear();
	//容器判空
	cout << s.empty() << endl;
	//交換兩個容器的資料
	set<int> tmp{ 10, 20, 30, 40 };
	s.swap(tmp);
	//容器中值為2的元素個數
	cout << s.count(2) << endl;

	cout << endl;
}

執行結果如下

set中迭代器相關函數

成員函數	功能
begin	返回set中起始位置元素的迭代器
end	返回set中最後一個元素後面的迭代器
rbegin	返回set第一個元素的反向迭代器
rend	返回set最後一個元素下一個位置的反向迭代器

使用範例

void test_set()
{
	set<int> s;
	//插入元素
	s.insert(1);
	s.insert(4);
	s.insert(3);
	s.insert(3);
	s.insert(2);
	s.insert(2);
	s.insert(3);
	//遍歷容器（正向迭代器）
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	//反向迭代器
	set<int>::reverse_iterator rit = s.rbegin();
	while (rit != s.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	cout << endl; 
}

執行結果如下

multiset

multiset和set的區別是multiset允許資料冗餘，即multiset中允許存在資料相同的元素，而set不能。

void test_set()
{
	set<int> s;
	s.insert(1);
	s.insert(3);
	s.insert(4);
	s.insert(2);	
	s.insert(2);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	multiset<int> ms;
	ms.insert(1);
	ms.insert(3);
	ms.insert(4);
	ms.insert(2);
	ms.insert(2);
	for (auto e : ms)
	{
		cout << e << " ";
	}
	cout << endl;
}

執行結果如下

兩個容器中成員函數find意義也有區別：

set中的find是返回值為val的迭代器，而multiset中的find是返回第一個值為val的迭代器。

map

map的介紹

map是關聯容器，它按照特定的次序(按照key來比較)儲存由鍵值key和值value組合而成的元素。
在map中，鍵值key通常用於排序和惟一地標識元素，而值value中儲存與此鍵值key關聯的內容。鍵值key和值value的型別可能不同，並且在map的內部，key與value通過成員型別value_type繫結在一起，為其取別名稱為pair。
在內部，map中的元素總是按照鍵值key進行比較排序的。
map中通過鍵值存取單個元素的速度通常比unordered_map容器慢，但map允許根據順序對元素進行直接迭代(即對map中的元素進行迭代時，可以得到一個有序的序列)。
map支援下標存取符，即在[]中放入key，就可以找到與key對應的value。
map通常被實現為二元搜尋樹(更準確的說：平衡二元搜尋樹(紅黑樹))。

map的使用

map的模板引數說明

key: 鍵值對中key的型別
T：鍵值對中value的型別
Compare: 比較器的型別，map中的元素是按照key來比較的，預設情況下按照小於來比較，一般情況下(內建型別元素)該引數不需要傳遞，如果無法比較時(自定義型別)，需要使用者自己顯式傳遞比較規則(一般情況下按照函數指標或者仿函數來傳遞)
Alloc：通過空間設定器來申請底層空間，不需要使用者傳遞，除非使用者不想使用標準庫提供的空間設定器

map構造

void test_map()
{
	map<int, double> m1; //構造一個key為int型別，value為double型別的空容器
	map<int, double> m2(m1); //拷貝構造
	map<int, double> m3(m2.begin(), m2.end()); //利用迭代器拷貝構造
	map<int, double, greater<int>> m4; //按int降序排序
}

map的插入

插入函數原型

pair<iterator,bool> insert (const value_type& val);

這裡的value_type是pair的重新命名

typedef pair<const Key, T> value_type;

方式一： 構造匿名物件插入。

int main()
{
	map<int, string> m;
	// 構造一個匿名物件插入
	m.insert(pair<int, string>(2, "two"));
	m.insert(pair<int, string>(1, "one"));
	m.insert(pair<int, string>(3, "three"));
	for (auto e : m)
	{
		cout << e.first << "-" << e.second << endl;
	}
	cout << endl;
	return 0;
}

執行結果如下

方式二： 呼叫make_pair函數模板

make_pair函數模板如下

template <class T1, class T2>
pair<T1, T2> make_pair(T1 x, T2 y)
{
	return (pair<T1, T2>(x, y));
}

make_pair可以根據傳入引數型別自行推導模板型別

上述程式碼可改為

int main()
{
	map<int, string> m;
	// 構造一個匿名物件插入
	m.insert(make_pair(2, "two"));
	m.insert(make_pair(1, "one"));
	m.insert(make_pair(3, "three"));
	for (auto e : m)
	{
		cout << e.first << "-" << e.second << endl;
	}
	cout << endl;
	return 0;
}

執行結果相同

insert的返回值也是一個pair物件，pair中第一個成員型別是插入的map的迭代器型別，第二個成員型別是bool型別

bool型別的作用如下

若待插入元素的鍵值key在map當中不存在，則insert函數插入成功，並返回插入後元素的迭代器和true。
若待插入元素的鍵值key在map當中已經存在，則insert函數插入失敗，並返回map當中鍵值為key的元素的迭代器和false。

map的[ ]運運算元過載

函數原型：

mapped_type& operator[] (const key_type& k);

函數的返回值如下：

(*((this->insert(make_pair(k, mapped_type()))).first)).second

乍一看很是複雜，把括號分清後便明朗許多

原始碼可分解為

mapped_type& operator[] (const key_type& k)
{
	//呼叫insert函數插入鍵值對
	pair<iterator, bool> ret = insert(make_pair(k, mapped_type()));
	//拿出從insert函數獲返回的迭代器
	iterator it = ret.first;
	//返回該迭代器位置元素的值value
	return it->second;
}

應用場景：

void test_map1()
{
	string str[] = { "sort", "sort", "tree", "insert", "sort", "tree", "sort", "test", "sort" };
	map<string, int> countMap;
	for (auto& e : str)
	{
		countMap[e]++;
	}

	for (auto& e : countMap)
	{
		cout << e.first << "-" << e.second << endl;
	}
	cout << endl;
}

執行結果

map其他常用成員函數

成員函數	功能
void erase ( iterator position )	利用迭代器刪除元素
size_type erase ( const key_type& x )	刪除鍵值為x的元素
void erase ( iterator first,iterator last )	刪除[first, last)區間中的元素
iterator find ( const key_type& x)	找到返回該元素的位置的迭代器，否則返回end
size	獲取容器中元素的個數
empty	判空
clear	清空容器
swap	交換兩個容器中的資料
count	獲取某個元素的個數

使用範例

int main()
{
	map<int, string> m;
	m.insert(make_pair(2, "two"));
	m.insert(make_pair(1, "one"));
	m.insert(make_pair(3, "three"));
	m.insert(make_pair(4, "four"));
	//根據key值進行刪除
	m.erase(3);
	//根據迭代器進行刪除
	map<int, string>::iterator pos = m.find(4);
	if (pos != m.end())
	{
		m.erase(pos);
	}
	// 獲取元素為2的迭代器
	pos = m.find(2);
	if (pos != m.end())
	{
		cout << pos->first<<"-"<<pos->second << endl; 
	}
	//獲取容器中元素的個數
	cout << m.size() << endl; 
	//容器中key值為2的元素個數
	cout << m.count(2) << endl; 
	//清空容器
	m.clear();
	//容器判空
	cout << m.empty() << endl;
	//交換兩個容器中的資料
	map<int, string> tmp;
	m.swap(tmp);
	
	return 0;
}

map的迭代器相關函數

成員函數	功能
begin	返回map中起始位置元素的迭代器
end	返回map中最後一個元素後面的迭代器
rbegin	返回map第一個元素的反向迭代器
rend	返回map最後一個元素下一個位置的反向迭代器

操作演示

int main()
{
	map<int, string> m;
	m.insert(make_pair(2, "two"));
	m.insert(make_pair(1, "one"));
	m.insert(make_pair(3, "three"));
	// 正向迭代器遍歷
	map<int, string>::iterator it = m.begin();
	while (it != m.end())
	{
		cout << it->first << "-" << it->second << endl;
		it++;
	}
	cout << endl;
	// 反向迭代器遍歷
	map<int, string>::reverse_iterator it2 = m.rbegin();
	while (it2 != m.rend())
	{
		cout << it2->first << "-" << it2->second << endl;
		it2++;
	}
	cout << endl;
	return 0;
}

multiset

multimap容器和map容器的區別與multiset容器和set容器的區別一樣，multimap允許鍵值冗餘，即multimap容器當中儲存的元素是可以重複的。

int main()
{
	multimap<int, string> mt;
	//插入元素（允許重複）
	mt.insert(make_pair(2, "two"));
	mt.insert(make_pair(2, "two"));
	mt.insert(make_pair(1, "one"));
	mt.insert(make_pair(3, "three"));
	for (auto e : mt)
	{
		cout << e.first << "-" << e.second << endl;
	}
	cout << endl; 
	return 0;
}