std :: set和std :: vector有什麼區別？

我正在學習STL。我讀了關於set容器。我有問題，當你想使用set？看完description of set看起來好像沒用，因爲我們可以用vector來代替它。你能說vector vs set容器的優點和成本。謝謝std :: set和std :: vector有什麼區別？

來源

2011-12-31 ashim

既然你讀了關於集，也讀地圖。然後再試一次！ – 2011-12-31 06:34:15

[請謹慎選擇容器]（https://docs.google.com/open?id=0B_ZAqgwpqtF4MjQ5NmNlM2ItNTQxNS00MmEyLWFiODctNDk4YTY5MDRlYzQz） – 2011-12-31 07:00:59

@NicolBolas我編輯了鏈接。你讓我做了一些額外的工作，但：D – 2011-12-31 07:01:56

A set已訂購。根據您提供的仿函數，它是保證保持特定的順序。無論您添加或刪除哪些元素（除非添加副本，這在set中都不允許），它將始終是有序的。

A vector正好和只有您明確給它的順序。 vector中的項目是你放置它們的地方。如果你把它們弄亂了，那麼它們就失靈了。你現在需要sort這個容器把它們放回來。

無可否認，set具有相對有限的用途。通過適當的紀律，人們可以將物品插入vector並保持訂購。但是，如果您不斷插入和移除容器中的物品，vector會遇到很多問題。它會做很多複製/移動元素等等，因爲它實際上只是一個數組。

將項目插入vector所需的時間與已在vector中的項目數成比例。將物品插入到set所需的時間與物品數量的log₂成正比。如果項目的數量很大，那是巨大的差異。 log 2（100,000）是〜16;這是一個重大的速度提升。去除也是一樣。

但是，如果您在初始化時一次完成所有插入操作，則沒有問題。您可以將所有內容插入到vector中，對其進行排序（支付一次該價格），然後使用標準算法對vectors進行排序以查找元素並遍歷排序列表。雖然迭代set的元素並不是很慢，但迭代vector會更快。

所以有些情況下排序的vector擊敗set。話雖如此，除非你知道這是必要的，否則你真的不應該爲這種優化而付出代價。所以使用set，除非你有你正在寫的系統的經驗（因此知道你需要這種性能），或者掌握分析數據，告訴你需要一個vector而不是set。

來源

2011-12-31 06:49:04

但是不是'set'僅僅是一個實現細節？從數學上講，一套沒有秩序。 – 2011-12-31 10:33:28

+29

@PaulManta：'std :: set'不是由數學定義的;它由C++規範定義。規範說明它是有序的。 – 2011-12-31 18:03:57

@NicolBolas：爲什麼「插入一個項目到一個向量所花費的時間與已經在向量中的項目數量成正比」。？ - 你的意思是始終使用insert（），而不是在最後插入？你不能只使用push_back（）並將它添加到O（1）中嗎？特別是因爲用戶控制了排序。 – 2012-10-13 03:26:03

他們是不同的東西：你決定如何排序向量，你也可以把許多平等的東西放入向量，只要你願意。集合按照該集合的內部規則進行排序（您可以設置規則，但集合將處理排序），並且不能將多個相同的項目放入集合中。

當然，您可以保持獨特項目的矢量，但是當您執行面向集合的操作時，性能會受到很大影響。例如，假設您有一組10000個項目和一個包含10000個不同無序項目的向量。現在假設您需要檢查值X是否在集合中的值（或向量中的值）之間。當X不在這些項目中時，搜索矢量的速度會慢100倍。在計算設置的聯合和交叉點時，您會看到類似的性能差異。總之，集合和向量有不同的目的。您可以使用矢量而不是集合，但需要更多工作，並且可能會嚴重影響性能。

來源

2011-12-31 06:34:55 dasblinkenlight

+1的唯一性。我無法相信其他人不會指出這一點。恥辱！唯一性是主要的好處。並且不要貶低它，但即使它在理論上可能會更慢一些，但即使隨便使用'erase' /'emplace'.ften也會導致我使用'[unordered_] set'，儘管通常在速度爲no的設置部分關心，我只擔心以後幾乎無法讀取代碼！例如我想確保一個物品放在容器中，但只有一次;編寫'set.emplace（it）'而不是'if（vec.find（it）！= vec.end（））{vec.emplace（it）}'（更多的用於'erase'！） – 2016-02-14 04:44:03

根據一個集合比一個向量（O（log（n））vs O（n））搜索一個項目更快。要根據矢量搜索項目，需要迭代矢量中的所有項目，但該組使用紅黑樹來優化搜索，只有少數項目會被查找以找到匹配項。

該集合是有序的，這意味着您只能按順序或顛倒的順序從最小的一個迭代到最大的一個。

但是矢量是無序的，你可以通過插入順序來移動它。

來源

2011-12-31 06:39:18

不正確。你可以在'std :: vector'上做'std :: binary_search'，它做對數的比較。 – Arlen 2011-12-31 10:17:01

+25

但是，二進制搜索僅在矢量排序後纔有效。 – rsaxvc 2012-01-02 06:07:29

形式cpluplus.com 組：

集是存儲以下特定順序獨特元件的容器。

所以該組是有序的和物品被唯一地表示

而VECT：

載體是表示可以在大小改變陣列序列的容器。

所以向量的順序填寫它，並可以保存多個相同的物品

喜歡設置：

項目按照指定的順序（在矢量中執行此操作需要專門對矢量進行排序）。

喜歡矢量：

，如果你想在解析相同的順序，你將他們推
（假設你不處理矢量順序）

來源

2016-05-11 13:30:06

std :: set和std :: vector有什麼區別？

回答

相關問題