set、unordered_set、multiset是什么？以及它們之間的區(qū)別

首先，它們?nèi)齻€(gè)都是C++標(biāo)準(zhǔn)庫(kù)提供的關(guān)聯(lián)容器中的一種。只不過(guò)set、multiset容器是有序的，而unordered_set容器是無(wú)序的

• std::set 是 C++ 標(biāo)準(zhǔn)庫(kù)中的一個(gè)容器，其存儲(chǔ)的元素按設(shè)定的順序排列。它使用平衡二叉樹實(shí)現(xiàn)，允許通過(guò)元素值直接訪問元素。它還提供 log(n) 的快速搜索時(shí)間。

• std::unordered_set 是一個(gè)關(guān)聯(lián)容器，其存儲(chǔ)的元素沒有特定的順序，可以通過(guò)元素的值來(lái)訪問。它使用散列表實(shí)現(xiàn)，提供更好的訪問性能。

• std::multiset 與 std::set 類似，但是它允許重復(fù)。它不會(huì)嘗試保持自己的數(shù)據(jù)排序，而是依賴哈希表決定具體元素所在的位置。

使用set

C++中的Sets可以用作實(shí)施與算法相關(guān)的問題的有效工具。 它們有助于搜索，排序，刪除和插入元素等活動(dòng)。 這包括通過(guò)另一個(gè)值替換現(xiàn)有值，查找最小或最大元素等任務(wù)。

由于其平衡的樹結(jié)構(gòu)，集合結(jié)構(gòu)的時(shí)間復(fù)雜度總是至少為O(log n)，因此在處理頻繁更新的數(shù)據(jù)集時(shí)，這將是最佳選擇。

使用unordered_set

C++中的無(wú)序sets利用哈希表結(jié)構(gòu)存儲(chǔ)和組織元素。 它不保證排序，但仍可以使用集合中的某些操作，例如插入和刪除元素，以常量時(shí)間搜索元素以及查找兩個(gè)元素是否相等。

使用無(wú)序集時(shí)，由于不能保證存儲(chǔ)元素的排序，無(wú)法使用與sets相關(guān)的任何需要排序的操作。

在做leetcode上面的算法題時(shí)，如果不需要維持元素中的順序，使用unordered_set這種數(shù)據(jù)結(jié)構(gòu)比set這種數(shù)據(jù)結(jié)構(gòu)耗時(shí)要少。

使用multiset

Multisets是允許存儲(chǔ)重復(fù)元素的容器。 當(dāng)解決元素出現(xiàn)頻率很重要的問題時(shí)可以使用它，例如頻率分析。 在許多情況下，它可以提供額外的功能; 例如添加節(jié)點(diǎn)的發(fā)生率并更新發(fā)生率。

通?？梢允褂脕?lái)自set和unordered_set的所有操作，以及特定的multiset操作，例如以其關(guān)聯(lián)頻率刪除元素的能力。

set、unordered、multiset之間的通用操作。

因?yàn)樗麄兌际菍儆贑++中的關(guān)聯(lián)容器，所以說(shuō)他們都可以執(zhí)行一些同樣的操作，且函數(shù)名也是一樣的。

插入操作

c.insert(v) // 插入一個(gè)元素，v是對(duì)應(yīng)容器類型的一個(gè)元素。

c.insert(b,e) // b和e是一對(duì)迭代器，表示一個(gè)范圍，將這個(gè)范圍內(nèi)的所有元素添加到容器中。區(qū)間是左閉右開

c.insert(il) // 其中il是一個(gè)列表，將列表中的元素全部都添加進(jìn)容器中，如果是不允許重復(fù)的容器，則只添加沒有添加過(guò)的元素。

刪除操作

c.erase(k) // 從c中刪除每個(gè)關(guān)鍵字為k的元素。返回一個(gè)size_type值，指出刪除元素的數(shù)量。

訪問操作

c.find(k); // 返回一個(gè)迭代器，指向第一個(gè)關(guān)鍵字為k的元素，若k不在容器中，則返回尾后迭代器。

c.count(k); //返回關(guān)鍵字等于k的元素的數(shù)量。對(duì)于不允許重復(fù)關(guān)鍵字的容器，返回值永遠(yuǎn)是0或1。

在不需要計(jì)數(shù)的情況，查找一個(gè)元素，最好是用find()，如果還需要統(tǒng)計(jì)元素的數(shù)量，這個(gè)時(shí)候再去考慮用count()