unordered_mapの要素をコピーせずにアクセスすることはできますか？

Question

私は、非常にパフォーマンスを重視するアプリケーションを持っています。ここでは、unordered_mapに保持されている文字列のコピーを避けたいと考えています。私ができるようにしたいのは、この文字列をローカルの文字列変数と比較することです。

例えば、

unordered_map<string,string> X; 
string test = "def"; 
X["abc"] = test; 

//other operations here... 

string* map_entry = X.???; //some operation that doesn't make a copy of the string 

size_t map_entry_size = (*map_entry).size(); 

for (size_t i = 0; i < map_entry_size; ++i) 
{ 
if ((*map_entry)[i] != test[i]) 
    throw 1; 
} 

は、これは可能ですか、私はいつもそれを使用する前に、要素のコピーを作成する必要がありますか？

Answer 1

[]演算子はリファレンスまたは参照参照を返します。そのため、そこにはコピーがありません。イテレータはstd::pair<std::string, std::string>への参照を与えますので、そこにはコピーはありません。

std::string &map_entry = X["abc"]; // Reference to value, no copy 
std::string *map_entry = &X["abc"]; // If you need a pointer 

あなたが本当に&map["key"]か&iterator->second有効であることを、ポインタを必要とする場合。

パフォーマンスを探している場合、特にキーが非常に短い場合は、std::stringをキーとして回避するか、少なくとも注意してください。

は確かに順序付けられていないマップがstd::unordered_map<std::string, T>はほぼ同じ速整数キーを言う使用などで、そのさらにわずか両方もなりにもかかわらず、通常の配列（可能性が密な整数キーからということO(1)であるという理由だけだと思う​​いけませんO(1)）。

• 一時的にstd::stringにする必要があります。最悪の場合、これは動的メモリ割り当てです。小さな文字列の場合、標準ライブラリの実装では "小さな文字列の最適化"があるかもしれませんが、それでもコピーはあります。

  可能であれば、既存のstd::stringを使用したいと考えています。

• ハッシュ（デフォルトはstd::hashを使用）を計算し、文字列の長さがO(n)の文字列に対して計算する必要があります。

  std::stringは、そのハッシュをキャッシュする方法がないため、再利用（例：定数/静的）を避けることはできません。ただし、独自の文字列ラッパーを作成することもできます。ハッシュが衝突する可能性があるためunordered_mapエントリが見つからない場合

• は、それは、ちょうどすべてがより速くなるでそう実際には何も見つからない（文字列の長さで再びO(n)である場合、には、とにかく完全な文字列の比較を行う必要があります正しいことを見つけること）。整数または他の小さな固定サイズのキーを言う使用

なります（あなたの文字列が4つのまたは8バイトを言うよりも常に小さいことを知っている場合も考慮し、あなただけの「ヌルパディング」との整数であること作ることができます）ハッシュは数学の単純な部分であり、比較は単一の操作である。

高密度整数（たとえば、列挙型0〜16）を使用すると、配列と配列の索引付けを使用できるようになります。非常に高速です。