C++進(jìn)階：詳細(xì)講解容器set與map（pair、multiset、multimap）

上次介紹了搜索二叉樹：C++進(jìn)階：二叉搜索樹介紹、模擬實(shí)現(xiàn)（遞歸迭代兩版本）及其應(yīng)用

為了介紹后面的AVLTree和紅黑樹，我們要進(jìn)行一些鋪墊，就是set與map的介紹啦

1.關(guān)聯(lián)式容器與序列式容器

關(guān)聯(lián)式容器和序列式容器是 C++ 中兩種不同的容器類型

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

   • 關(guān)聯(lián)式容器主要包括 std::set, std::map, std::multiset, std::multimap 等。
   • 這些容器是基于鍵值對(duì)(<key, value>結(jié)構(gòu))的概念，通過鍵==（key）來(lái)唯一標(biāo)識(shí)元素==。
   • 關(guān)聯(lián)式容器內(nèi)部使用二叉搜索樹（通常是紅黑樹）或類似的數(shù)據(jù)結(jié)構(gòu)，以保持元素的有序性。
   • 插入、刪除、查找等操作的平均時(shí)間復(fù)雜度是 O(log n)。

2. 序列式容器:

   • 序列式容器包括 std::vector, std::list, std::deque, std::array 等。
   • 這些容器是基于線性結(jié)構(gòu)的，元素在容器中的位置是由插入的順序決定的。
   • 插入、刪除、查找等操作的平均時(shí)間復(fù)雜度因容器類型而異，但在最差情況下，可能達(dá)到 O(n)。

2.C++中的鍵值對(duì)——pair

在C++中，鍵值對(duì)是一種數(shù)據(jù)結(jié)構(gòu)，通常用于表示關(guān)聯(lián)關(guān)系

鍵值對(duì)由兩部分組成：鍵（Key）和值（Value）。這種結(jié)構(gòu)允許通過鍵來(lái)檢索和關(guān)聯(lián)對(duì)應(yīng)的值，key代表鍵值，value表示與key對(duì)應(yīng)的信息

2.1pair定義

std::pair 是C++標(biāo)準(zhǔn)庫(kù)中提供的一個(gè)簡(jiǎn)單的鍵值對(duì)實(shí)現(xiàn)。它包含在 <utility> 頭文件中。一個(gè) std::pair 有兩個(gè)公有成員：first 和 second，分別表示鍵和值==（first<= =>key ; second<= =>value）==

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

template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;
	T1 first;
	T2 second;

	pair() //構(gòu)造函數(shù)
	: first(T1()), second(T2())
	{}

	pair(const T1& a, const T2& b) //拷貝構(gòu)造
	: first(a), second(b)
	{}
};

2.2pair的對(duì)象創(chuàng)建與訪問

文檔中的構(gòu)造函數(shù)的介紹：

1. 默認(rèn)構(gòu)造函數(shù)：

• pair();
• 默認(rèn)構(gòu)造函數(shù)創(chuàng)建一個(gè)空的 std::pair 對(duì)象，不包含任何值。

2. 拷貝構(gòu)造函數(shù)：

• template<class U, class V> pair (const pair<U,V>& pr);
• 拷貝構(gòu)造函數(shù)用于從另一個(gè) std::pair 對(duì)象 pr 中復(fù)制鍵值對(duì)來(lái)構(gòu)造一個(gè)新的 std::pair 對(duì)象。

3. 初始化構(gòu)造函數(shù)：

• pair (const first_type& a, const second_type& b);
• 初始化構(gòu)造函數(shù)接受兩個(gè)參數(shù) a 和 b，分別用于初始化 std::pair 對(duì)象的 first 和 second 成員變量。

void test_pair()
{
	pair<int, char> p1;//空參
	pair<int, char> p2(2, '2');

	pair<int, char> p3(p2);//拷貝構(gòu)造

	cout << p1.first << " " << p1.second << endl;;
	cout << p2.first << " " << p2.second << endl;
	cout << p3.first << " " << p3.second << endl;
}

int main()
{
	test_pair();
	return 0;
}

2.3make_pair() 函數(shù)和使用{} -簡(jiǎn)化創(chuàng)建過程

void test_pair2()
{
	auto p4 = make_pair(2, 'c');//使用make_pair

	pair<int, char> p5 = { 3,'d' };//c++11后，使用{ }

	cout << p4.first << " " << p4.second << endl;
	cout << p5.first << " " << p5.second << endl;
}

int main()
{
	test_pair2();
	return 0;
}

我們能使用{}（初始化列表），是因?yàn)椋?mark>構(gòu)造函數(shù)匹配。如果使用花括號(hào)進(jìn)行初始化，編譯器會(huì)嘗試匹配合適的構(gòu)造函數(shù)。對(duì)于 pair，存在接受兩個(gè)參數(shù)的構(gòu)造函數(shù)，因此可以通過初始化列表直接構(gòu)造鍵值對(duì)

3. set容器

1. set是按照一定次序存儲(chǔ)元素的容器

2. 在set中，元素的value也標(biāo)識(shí)它(value就是key，類型為T)，并且每個(gè)value必須是唯一的。set中的元素不能在容器中修改(元素總是const)，但是可以從容器中插入或刪除它們。

3. 在內(nèi)部，set中的元素總是按照其內(nèi)部比較對(duì)象(類型比較)所指示的特定嚴(yán)格弱排序準(zhǔn)則進(jìn)行排序。

4. set容器通過key訪問單個(gè)元素的速度通常比unordered_set容器慢，但它們?cè)试S根據(jù)順序?qū)ψ蛹M(jìn)行直接迭代。

5. set在底層是用二叉搜索樹(紅黑樹)實(shí)現(xiàn)的

3.1Constructs構(gòu)造函數(shù)

void test_set1()
{
	set<int> s1;

	vector<int> v = { 1,2,3,4,5 };
	set<int> s2(v.begin(), v.end());//利用迭代區(qū)間

	set<int> s3 = s2;//拷貝構(gòu)造
	for (auto e : s1)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : s2)
	{
		cout << e << " ";
	}
	cout << endl;	
	for (auto e : s3)
	{
		cout << e << " ";
	}
	cout << endl;
}

int main()
{
	test_set1();
	return 0;
}

3.2Iterator 迭代器

3.3 插入、刪除、查找、count

3.3.1 insert（）插入

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

• 插入元素到 set 中。
• 如果插入成功，返回一個(gè)迭代器指向插入的位置和 true。
• 如果元素已經(jīng)存在，返回一個(gè)迭代器指向已存在的元素和 false。

• 返回一個(gè) pair 對(duì)象，包含插入的迭代器和插入是否成功的標(biāo)志。

3.3.2 erase（） 刪除

3.3.3 find（）查找

find 函數(shù)用于在 set 中查找指定鍵值的元素，并返回指向該元素的迭代器。如果元素不存在，則返回 end()。

3.3.4 count（）函數(shù)

聲明：size_type count (const key_type& k) const;

count 函數(shù)用于統(tǒng)計(jì) set 中與指定鍵值相等的元素個(gè)數(shù)。由于 set 中元素的鍵值是唯一的，因此該函數(shù)的返回值要么是 0（元素不存在），要么是 1（元素存在）。

void test_set2()
{
	// 排序+去重
	set<int> s;
	s.insert(5);
	s.insert(1);
	s.insert(6);
	s.insert(3);
	s.insert(5);
	s.insert(1);

	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	set<int>::iterator pos = s.find(5);//找到5就刪除
	if (pos != s.end())
	{
		cout << "找到了" << endl;
		s.erase(pos);
	}

	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	if (s.count(1))
	{
		cout << "1在" << endl;
	}
	else
	{
		cout << "1不在" << endl;
	}
}

int main()
{
	test_set2();
	return 0;
}

4.容器 multiset

1. multiset是按照特定順序存儲(chǔ)元素的容器，其中元素是可以重復(fù)的。

2. 在multiset中，元素的value也會(huì)識(shí)別它(因?yàn)閙ultiset中本身存儲(chǔ)的就是<value, value>組成的鍵值對(duì)，因此value本身就是key，key就是value，類型為T). multiset元素的值不能在容器中進(jìn)行修改(因?yàn)樵乜偸莄onst的)，但可以從容器中插入或刪除。

3. 在內(nèi)部，multiset中的元素總是按照其內(nèi)部比較規(guī)則(類型比較)所指示的特定嚴(yán)格弱排序準(zhǔn)則進(jìn)行排序。

4. multiset容器通過key訪問單個(gè)元素的速度通常比unordered_multiset容器慢，但當(dāng)使用迭代器遍歷時(shí)會(huì)得到一個(gè)有序序列。

5. multiset底層結(jié)構(gòu)為二叉搜索樹(紅黑樹)

注意：

1. multiset中再底層中存儲(chǔ)的是<value, value>的鍵值對(duì)

2. mtltiset的插入接口中只需要插入即可

3. 與set的區(qū)別是，multiset中的元素可以重復(fù)，set是中value是唯一的

4. 使用迭代器對(duì)multiset中的元素進(jìn)行遍歷，可以得到有序的序列

5. multiset中的元素不能修改

6. 在multiset中找某個(gè)元素，時(shí)間復(fù)雜度為$O(lo{g}_{2}N)$

7. multiset的作用：可以對(duì)元素進(jìn)行排序

multiset 是 C++ 標(biāo)準(zhǔn)庫(kù)中的關(guān)聯(lián)式容器之一，屬于有序容器。與 set 不同的是，multiset 允許鍵值重復(fù)，即可以包含相同鍵值的多個(gè)元素。

• 允許重復(fù)鍵值： multiset 允許容器中存在相同的鍵值，因此可以包含多個(gè)相同鍵值的元素。

• 有序性： 與 set 類似，multiset 也維護(hù)元素的有序性，根據(jù)鍵值進(jìn)行排序。

• 當(dāng)需要允許鍵值重復(fù)，并且希望保持元素有序時(shí)，可以選擇使用 multiset。

5.map 容器

1. map是關(guān)聯(lián)容器，它按照特定的次序(按照key來(lái)比較)存儲(chǔ)由鍵值key和值value組合而成的元素。

2. 在map中，鍵值key通常用于排序和惟一地標(biāo)識(shí)元素，而值value中存儲(chǔ)與此鍵值key關(guān)聯(lián)的內(nèi)容。鍵值key和值value的類型可能不同，并且在map的內(nèi)部，key與value通過成員類型value_type綁定在一起，為其取別名稱為pair:

3. 在內(nèi)部，map中的元素總是按照鍵值key進(jìn)行比較排序的。

4. map中通過鍵值訪問單個(gè)元素的速度通常比unordered_map容器慢，但map允許根據(jù)順序?qū)υ剡M(jìn)行直接迭代(即對(duì)map中的元素進(jìn)行迭代時(shí)，可以得到一個(gè)有序的序列)。

5. map支持下標(biāo)訪問符，即在[]中放入key，就可以找到與key對(duì)應(yīng)的value。

6. map通常被實(shí)現(xiàn)為二叉搜索樹(更準(zhǔn)確的說(shuō)：平衡二叉搜索樹(紅黑樹))。

5.1map 模板參數(shù)說(shuō)明

key: 鍵值對(duì)中key的類型

T： 鍵值對(duì)中value的類型

Compare: 比較器的類型，map中的元素是按照key來(lái)比較的，缺省情況下按照小于來(lái)比較，一般情況下(內(nèi)置類型元素)該參數(shù)不需要傳遞，如果無(wú)法比較時(shí)(自定義類型)，需要用戶自己顯式傳遞比較規(guī)則(一般情況下按照函數(shù)指針或者仿函數(shù)來(lái)傳遞)

Alloc：通過空間配置器來(lái)申請(qǐng)底層空間，不需要用戶傳遞，除非用戶不想使用標(biāo)準(zhǔn)庫(kù)提供的空間配置器

5.2 對(duì)象的創(chuàng)建

void testmap1()
{
	map<string, string> m1;//空的
	map<string, string> m2(m1);//拷貝構(gòu)造
}

5.3 迭代器，insert，find ，[]重載

5.3.1 迭代器

下面是關(guān)于 multiset 中成員函數(shù) begin(), end(), cbegin(), cend(), rbegin(), rend(), crbegin(), 和 crend() 的函數(shù)聲明和功能介紹：

5.3.2 insert() 函數(shù)

void testmap2()
{
	map<string, string> m1;//空的
	
	m1.insert(pair<string, string>("sort", "排序"));//匿名對(duì)象
	m1.insert(make_pair("apple", "蘋果"));//使用make_pair函數(shù)
	m1.insert({ "apple", "蘋果" });// C++11 多參數(shù)隱式類型轉(zhuǎn)換(構(gòu)造函數(shù)支持)
}

5.3.3 find() 函數(shù)

在 map 中，find 函數(shù)用于查找指定鍵的元素，并返回指向該元素的迭代器。如果找到了指定的鍵，則返回指向該鍵值對(duì)的迭代器；如果未找到，則返回指向 map 末尾的迭代器。

5.3.4 []

1. 讀取元素：當(dāng)使用 [] 運(yùn)算符時(shí)

   • 如果指定的鍵存在于 map 中，則返回與該鍵關(guān)聯(lián)的值
   • 如果不存在，則會(huì)插入一個(gè)新的鍵值對(duì)，鍵為指定的鍵，值為默認(rèn)構(gòu)造的對(duì)應(yīng)值類型的默認(rèn)值，并返回該默認(rèn)值的引用

2. 插入元素：當(dāng)使用 [] 運(yùn)算符向 map 中插入元素時(shí)

   • 如果指定的鍵不存在，則會(huì)創(chuàng)建一個(gè)新的鍵值對(duì)，鍵為指定的鍵，值為指定的值，并返回該值的引用
   • 如果鍵已經(jīng)存在，則直接返回對(duì)應(yīng)的值的引用。

void testmap3()
{
	map<string, string> m1;//空的

	m1.insert(pair<string, string>("sort", "排序"));//匿名對(duì)象
	m1.insert(make_pair("apple", "蘋果"));//使用make_pair函數(shù)
	m1.insert({ "left", "左邊" });// C++11 多參數(shù)隱式類型轉(zhuǎn)換(構(gòu)造函數(shù)支持)
	for (auto& kv : m1)
	{
		cout << kv.first << ":" << kv.second << " ";
	}
	cout << endl;

	m1["right"];//這是插入一個(gè)right（key）
	m1["apple"] = "青蘋果";//這里是進(jìn)行修改

	for (auto& kv : m1)
	{
		cout << kv.first << ":" << kv.second << " ";
	}
	cout << endl;
}

int main()
{
	testmap3();
	return 0;
}

6.容器 multimap

1. multiset是按照特定順序存儲(chǔ)元素的容器，其中元素是可以重復(fù)的

2. 在multiset中，元素的value也會(huì)識(shí)別它(因?yàn)閙ultiset中本身存儲(chǔ)的就是<value, value>組成的鍵值對(duì)，因此value本身就是key，key就是value，類型為T). multiset元素的值不能在容器中進(jìn)行修改(因?yàn)樵乜偸莄onst的)，但可以從容器中插入或刪除。

3. 在內(nèi)部，multiset中的元素總是按照其內(nèi)部比較規(guī)則(類型比較)所指示的特定嚴(yán)格弱排序準(zhǔn)則進(jìn)行排序。

4. multiset容器通過key訪問單個(gè)元素的速度通常比unordered_multiset容器慢，但當(dāng)使用迭代器遍歷時(shí)會(huì)得到一個(gè)有序序列。

5. multiset底層結(jié)構(gòu)為二叉搜索樹(紅黑樹)

注意

1. multiset中再底層中存儲(chǔ)的是<value, value>的鍵值對(duì)

2. mtltiset的插入接口中只需要插入即可

3. 與set的區(qū)別是，multiset中的元素可以重復(fù)，set是中value是唯一的

4. 使用迭代器對(duì)multiset中的元素進(jìn)行遍歷，可以得到有序的序列

5. multiset中的元素不能修改

6. 在multiset中找某個(gè)元素，時(shí)間復(fù)雜度為$O(lo{g}_{2}N)$

7. multiset的作用：可以對(duì)元素進(jìn)行排序

這次就到這里啦?。?！感謝大家支持?。?！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-848430.html

到了這里，關(guān)于C++進(jìn)階：詳細(xì)講解容器set與map（pair、multiset、multimap）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！