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

更新時間：2022年02月24日 09:20:25 作者：小倪同學(xué) -_-

本文主要介紹了C++中map和set的簡介及使用詳解，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

關(guān)聯(lián)式容器

關(guān)聯(lián)式容器包括序列式容器和關(guān)聯(lián)式容器

序列式容器： 底層為線性序列的數(shù)據(jù)結(jié)構(gòu)，里面存儲的是元素本身，包含vector、list、deque、forward_list(C++11)等。
關(guān)聯(lián)式容器： 里面存儲的是<key, value>結(jié)構(gòu)的鍵值對，在數(shù)據(jù)檢索時比序列式容器效率更高，包含set、map、unordered_set、unordered_map等。

注意： stack、queue和priority_queue屬于容器適配器

鍵值對

用來表示具有一一對應(yīng)關(guān)系的一種結(jié)構(gòu)，該結(jié)構(gòu)中一般只包含兩個成員變量key和value，key代表鍵值，value表示與key對應(yīng)的信息。

現(xiàn)在要建立一個英漢互譯的字典，那該字典中必然有英文單詞與其對應(yīng)的中文含義，而且，英文單詞與其中文含義是一一對應(yīng)的關(guān)系，即通過該應(yīng)該單詞，在詞典中就可以找到與其對應(yīng)的中文含義。

SGI-STL中關(guān)于鍵值對的定義：

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)，但是可以從容器中插入或刪除它們。
在內(nèi)部，set中的元素總是按照其內(nèi)部比較對象(類型比較)所指示的特定嚴(yán)格弱排序準(zhǔn)則進行排序。
set容器通過key訪問單個元素的速度通常比unordered_set容器慢，但它們允許根據(jù)順序?qū)ψ蛹M行直接迭代。
set在底層是用二叉搜索樹(紅黑樹)實現(xiàn)的。

注意：

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

set的使用

set的模板參數(shù)列表

在這里插入圖片描述

T: set中存放元素的類型，實際在底層存儲<value, value>的鍵值對。
Compare：set中元素默認(rèn)按照小于來比較
Alloc：set中元素空間的管理方式，使用STL提供的空間配置器管理

set的構(gòu)造

函數(shù)聲明	功能介紹
set (const Compare& comp = Compare(), const Allocator& =Allocator());	構(gòu)造空的set
set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() );	用[first, last)區(qū)間中的元素構(gòu)造set
set ( const set<Key,Compare,Allocator>& x);	set的拷貝構(gòu)造

set中常用的成員函數(shù)

成員函數(shù)	功能
insert	插入元素
erase	刪除元素
find	查找元素
size	獲取容器中元素的個數(shù)
clear	清空容器
empty	判空
swap	交換兩個容器中的數(shù)據(jù)
count	獲取某個元素的個數(shù)

使用示例

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;
	//交換兩個容器的數(shù)據(jù)
	set<int> tmp{ 10, 20, 30, 40 };
	s.swap(tmp);
	//容器中值為2的元素個數(shù)
	cout << s.count(2) << endl;

	cout << endl;
}

運行結(jié)果如下

在這里插入圖片描述

set中迭代器相關(guān)函數(shù)

成員函數(shù)	功能
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; 
}

運行結(jié)果如下

在這里插入圖片描述

multiset

multiset和set的區(qū)別是multiset允許數(shù)據(jù)冗余，即multiset中允許存在數(shù)據(jù)相同的元素，而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;
}

運行結(jié)果如下

在這里插入圖片描述

兩個容器中成員函數(shù)find意義也有區(qū)別：

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

map

map的介紹

map是關(guān)聯(lián)容器，它按照特定的次序(按照key來比較)存儲由鍵值key和值value組合而成的元素。
在map中，鍵值key通常用于排序和惟一地標(biāo)識元素，而值value中存儲與此鍵值key關(guān)聯(lián)的內(nèi)容。鍵值key和值value的類型可能不同，并且在map的內(nèi)部，key與value通過成員類型value_type綁定在一起，為其取別名稱為pair。
在內(nèi)部，map中的元素總是按照鍵值key進行比較排序的。
map中通過鍵值訪問單個元素的速度通常比unordered_map容器慢，但map允許根據(jù)順序?qū)υ剡M行直接迭代(即對map中的元素進行迭代時，可以得到一個有序的序列)。
map支持下標(biāo)訪問符，即在[]中放入key，就可以找到與key對應(yīng)的value。
map通常被實現(xiàn)為二叉搜索樹(更準(zhǔn)確的說：平衡二叉搜索樹(紅黑樹))。

map的使用

map的模板參數(shù)說明

在這里插入圖片描述

key: 鍵值對中key的類型
T：鍵值對中value的類型
Compare: 比較器的類型，map中的元素是按照key來比較的，缺省情況下按照小于來比較，一般情況下(內(nèi)置類型元素)該參數(shù)不需要傳遞，如果無法比較時(自定義類型)，需要用戶自己顯式傳遞比較規(guī)則(一般情況下按照函數(shù)指針或者仿函數(shù)來傳遞)
Alloc：通過空間配置器來申請底層空間，不需要用戶傳遞，除非用戶不想使用標(biāo)準(zhǔn)庫提供的空間配置器

map構(gòu)造

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

map的插入

插入函數(shù)原型

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

這里的value_type是pair的重命名

typedef pair<const Key, T> value_type;

方式一： 構(gòu)造匿名對象插入。

int main()
{
	map<int, string> m;
	// 構(gòu)造一個匿名對象插入
	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;
}

運行結(jié)果如下

在這里插入圖片描述

方式二： 調(diào)用make_pair函數(shù)模板

make_pair函數(shù)模板如下

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

make_pair可以根據(jù)傳入?yún)?shù)類型自行推導(dǎo)模板類型

上述代碼可改為

int main()
{
	map<int, string> m;
	// 構(gòu)造一個匿名對象插入
	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;
}

運行結(jié)果相同

在這里插入圖片描述

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

bool類型的作用如下

若待插入元素的鍵值key在map當(dāng)中不存在，則insert函數(shù)插入成功，并返回插入后元素的迭代器和true。
若待插入元素的鍵值key在map當(dāng)中已經(jīng)存在，則insert函數(shù)插入失敗，并返回map當(dāng)中鍵值為key的元素的迭代器和false。

map的[ ]運算符重載

函數(shù)原型：

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

函數(shù)的返回值如下：

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

乍一看很是復(fù)雜，把括號分清后便明朗許多

在這里插入圖片描述

原代碼可分解為

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

應(yīng)用場景：

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;
}

運行結(jié)果

在這里插入圖片描述

map其他常用成員函數(shù)

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

使用示例

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"));
	//根據(jù)key值進行刪除
	m.erase(3);
	//根據(jù)迭代器進行刪除
	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; 
	}
	//獲取容器中元素的個數(shù)
	cout << m.size() << endl; 
	//容器中key值為2的元素個數(shù)
	cout << m.count(2) << endl; 
	//清空容器
	m.clear();
	//容器判空
	cout << m.empty() << endl;
	//交換兩個容器中的數(shù)據(jù)
	map<int, string> tmp;
	m.swap(tmp);
	
	return 0;
}

在這里插入圖片描述

map的迭代器相關(guān)函數(shù)

成員函數(shù)	功能
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容器的區(qū)別與multiset容器和set容器的區(qū)別一樣，multimap允許鍵值冗余，即multimap容器當(dāng)中存儲的元素是可以重復(fù)的。

int main()
{
	multimap<int, string> mt;
	//插入元素（允許重復(fù)）
	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;
}

在這里插入圖片描述