オブジェクトの宣言のパフォーマンス

Question

私はある種の大学の征服でコーディングしていて、以下のようなループでマップを宣言したときに何かに気づきました。

for (int i = 0; i < n; i++)
{
    map<int, bool> hashMap;
    //...
}

以下よりも時間がかかります：

map<int, bool> hashMap;
for (int i = 0; i < n; i++)
{
    hashMap.clear();
    //...
}

それで、ループ内でオブジェクトを宣言すると、単に再初期化するよりもパフォーマンスが低下するのはなぜだろうと思っていました。

Answer 1

コードの最初のバージョンでは、のコンストラクタとデストラクタは回hashMapと呼ばnれますが、2番目のバージョンでは1回だけ呼び出されます。

自然な問題は、新しいmapオブジェクトを破棄して構築することと、同じオブジェクトをクリアして再利用することとでは、なぜ著しく異なるのかということです。これはmap、使用されている実装の実際のコードを調べることによってのみ明確に答えることができるため、以下はもっともらしい推測です。

std::map通常使用して実装され赤黒木を、それが使用する赤黒木の実装に共通であるセンチネル、NIL-葉のノードを例えば参照赤黒木でセンチネルリンパ節の利益？。この歩哨は、ツリーが構築されるたびに割り当てられ、破壊されると解放される必要があります。対照的に、clear'を実行するとmap、代わりにツリーが空になりますが、関連する内部オブジェクトが再利用されます。

このような実装の実際の例として、Microsoftの_Treeコンストラクターは適切な名前のを呼び出します_Alloc_sentinel_and_proxy();。それらmapはから派生しているため_Tree、これはmapオブジェクトが構築されるたびに呼び出されます。