std：排序vs插入std :: set

我正在讀cin的一些線段。每條線段都由一個起點和終點表示。 2D。 X和Y.std：排序vs插入std :: set

輸入未排序。它是隨機的。（更新：但我需要他們的排序條件爲X，然後再由Y）

我可以在所有段閱讀，把它們存儲在一個向量，然後調用的std ::排序。另一方面，我可以創建一個空的std :: set並在它到達時插入每個段。該集將自動保持排序順序。哪兩種方法更有效率？

更新：輸入（段數）的總大小是事先知道的。

來源

2013-03-26 Agnel Kurian

@larsmans感謝您的糾正。從酒吧發佈信息。 ;） – 2013-03-26 13:22:38

你爲什麼不試試呢？真實世界的表現數據>「互聯網上的一些人告訴我的」 – jalf 2013-03-26 13:24:05

@jalf我認爲這是一個普遍接受的答案，這是一個老問題。另外，在做出決定之前，我應該嘗試多少個不同的輸入集？ – 2013-03-26 13:38:45

你應該測量兩種方法的表現予以肯定，但它是一個安全的賭注假設std::sort上std::vector是方式不是插入到std::set由於當地的影響和大常量躲在樹快插入算法。而且，隨後的查找和迭代將會更快。

（然而，std::set更適合用於支撐的混合系列的插入和缺失/查找/迭代。在向量維持秩序是昂貴的，因爲每個插入將就平均線性時間。）

來源

2013-03-26 13:19:24

哦，真的嗎？那爲什麼呢？ – 2013-03-26 13:19:47

它取決於什麼？ – 2013-03-26 13:20:07

@LightnessRacesinOrbit：插入樹中的常量非常高（認爲在紅黑樹中重新平衡）與優化排序中的常量相比。 – 2013-03-26 13:22:56

使用容器它具有適合您需求的適當語義。效率通常會自動從該選擇開始。

如果然後你遇到性能瓶頸，做一些基準測試。

來源

2013-03-26 13:20:29

我的需求是，我應該能夠從左到右遍歷輸入。如果兩個輸入具有相同的x，則較小的y勝。 – 2013-03-26 13:26:52

+1：語義第一，表現第二。 – 2013-03-26 13:55:44

@AgnelKurian如果您的數據沒有固有的順序，請使用一組。這是一個擠進一個袋子的東西。作爲一種令人愉悅的副作用，您可以在迭代時獲得字典（或任何您需要的）排序，所以如果您希望在最後使用它，那麼也很方便。 – 2013-03-26 14:05:42

它確實不依賴，但它肯定std::set是用於隨機插入和刪除。在這種情況下，你只能插入。去std::vector。另外，也許更重要的是，如果事先知道有多少片段，則只需分配一次矢量，每次大小加倍時都不會重新分配內存。

來源

2013-03-26 13:27:24

作爲一個很好的經驗規則，嚴格的擔保提供，性能越差，你會得到。

插入到std::set保證序列在每次插入後被排序。

插入到std::vector，並呼籲std::sort一次畢竟插入已經完成保證了順序排序一旦上了vector所有操作已經完成。它不需要在所有中間插入過程中對矢量進行排序。

甲std::vector也表現出更好的空間局部性，且需要更少的內存分配。所以我將承擔vector方法要快，但是如果性能對你很重要，那麼它很重要，足以成爲測量。

如果你不在乎什麼來衡量你的情況更快爲您數據集與您應用您代碼，那麼你不在乎這是更快。

來源

2013-03-26 13:56:05 jalf

std：排序vs插入std :: set

回答

相關問題