STL地圖插件效率：[]對插入

有地圖插入的方式有兩種：STL地圖插件效率：[]對插入

m[key] = val;

或者

m.insert(make_pair(key, val));

我的問題是，其運算速度更快？人們通常會說第一個比較慢，因爲STL標準最初'插入'一個默認元素，如果'key'不存在於map中，然後將'val'賦給默認元素。

但我沒有看到第二種方式更好，因爲'make_pair'。 make_pair實際上是一個方便的方式，與pair<T1, T2>(key, val)進行比較。無論如何，他們都做了兩個任務，一個是將'key'分配給'pair.first'，另外兩個是將'val'分配給'pair.second'。配對完成後，map插入由'pair.second'初始化的元素。

所以第一種方式是1「default construct of typeof(val)」 2.分配第二種方式是1分配2「copy construct of typeof(val)」

來源

2011-04-17 DerekFOol

另請參閱：http://stackoverflow.com/q/1594631/78845 – Johnsyweb 2011-04-17 07:44:13

兩個完成不同的事情。

m[key] = val;

將插入一個新的鍵值對，如果key已經不存在，或者它會覆蓋映射到key如果它已經存在的舊值。

m.insert(make_pair(key, val));

只會插入一對，如果key不存在，它絕不會覆蓋舊值。所以，根據你想要完成的選擇。
對於什麼更有效的問題：配置文件。：P可能是我說的第一種方式。這個任務（aka copy）就是這種情況，所以唯一的區別在於施工。正如我們都知道並且應該實施的那樣，默認的建設應該基本上是無效的，因此非常有效。副本就是 - 副本。所以在方法一中我們得到一個「禁用」和一個副本，在方法二中我們得到兩個副本。
編輯：最後，請相信你的分析能告訴你什麼。我的分析就像@Matthieu在他的評論中提到的那樣，但那是我的猜測。 :)

以後，我們的C++ 0x的到來，並在第二路雙副本將化爲烏有，因爲該貨幣對可以簡單地搬到現在。所以最後，我認爲它回到了我的第一點：用正確的方式來完成你想要做的事情。

來源

2011-04-17 07:39:50 Xeo

+1用於從語義選擇而非性能。我認爲，分析有點不合適。第一種方式應該比較慢（通過默認構造），因爲在這兩種情況下鍵和值都被複制。 – 2011-04-17 10:48:44

@Matthieu：恩，真夠的。我會編輯一下，但會讓我的分析保持。這再次表明，分析將真正告訴你什麼更快。 – Xeo 2011-04-17 10:52:14

'std :: map <> :: operator []'不默認 - 初始化值，它_value-initializes_ values，因此像'std :: map > :: operator []'可能會非常浪費。 – ildjarn 2012-05-02 21:06:52

在用大量的存儲器，這代碼輕負載系統：

#include <map> 
#include <iostream> 
#include <ctime> 
#include <string> 

using namespace std; 

typedef map <unsigned int,string> MapType; 
const unsigned int NINSERTS = 1000000; 

int main() { 
    MapType m1; 
    string s = "foobar"; 
    clock_t t = clock(); 
    for (unsigned int i = 0; i < NINSERTS; i++) { 
     m1[i] = s; 
    } 
    cout << clock() - t << endl; 
    MapType m2; 
    t = clock(); 
    for (unsigned int i = 0; i < NINSERTS; i++) { 
     m2.insert(make_pair(i, s)); 
    } 
    cout << clock() - t << endl; 
}

生產：

1547 
1453

或相似的值上重複運行。所以插入是（在這種情況下）稍微快一點。

來源

2011-04-17 09:48:46

我們必須通過提及相關性能取決於所複製對象的類型（大小）來改進分析。

我做了一個類似的實驗（以NBT）與（int - >集）的地圖。我知道這是一件可怕的事情，但是，對於這種情況來說也是說明性的。在這個例子中，「值」是一組整數，其中有20個元素。

我執行[] = Vs的一百萬次迭代。插入操作並執行RDTSC/iter-count。

[] = set | 10731個週期

insert（make_pair <>）| 26100個週期

它顯示了由於複製而增加的罰分的大小。當然，CPP11（move ctor's）會改變圖片。

來源

2014-11-20 21:33:19 KalyanS

表現明智我認爲他們大體上是相同的一般。對於包含大對象的地圖可能會有一些例外情況，在這種情況下，您應該使用[]或者可能會創建比'insert'更少的臨時對象的emplace。有關詳細信息，請參閱討論here。

但是，如果在插入運算符上使用「提示」功能，則可以在特殊情況下獲得性能提升。所以，從here看着選項2：

iterator insert (const_iterator position, const value_type& val);

「插入」操作可以降低到一定的時間（從數（n））的，如果你給一個很好的提示（通常情況下，如果你知道你正在添加東西在你的地圖的後面）。

來源

2015-04-22 18:37:48

我對它的看法：值得提醒的是，地圖是一個平衡的二叉樹，大部分的修改和檢查都需要O（logN）。

確實取決於您嘗試解決的問題。

1）如果你只是想插入值，知道它現在還沒有，則[]會做兩件事情：一）檢查項目是否有或沒有二）如果它不存在將創建一對並做什麼插入（ O（logN））的雙重工作，所以我會使用插入。如果你不確定它是否存在或不存在，那麼a）如果你通過做類似if（map.find（item）== mp.end幾行上面的某處，然後使用插入，因爲雙重工作[]會執行b）如果你沒有檢查，那麼它取決於，原因插入不會修改值，如果它在那裏，[]會，否則他們等於

來源

2017-03-15 01:24:39

STL地圖插件效率：[]對插入

回答

相關問題