順序付けされていないマップ<string、ベクトル<string>>でfind（）を使用すると、C++の順序付きマップと同じ時間がかかります

Question

文字列とベクトルの配列の順序が揃っていません（un_map<string,vector<string> >）。 find関数を使用して、特定の文字列を検索しながら：

find((un_map[A].begin(),un_map[A].end(),field)==un_map[A].end()) 

順不同マップの検索機能を実行する際に、マップを命じたことは同じことをしています。なぜ誰かが説明することができますか？私が知る限り、順序付けされていないマップは、ハッシングのために順序付けされたマップよりもはるかに高速でなければなりません。 find関数を最適化したい。助けてください

Answer 1

std::findは、イテレータのインクリメントだけを使用して、すべてのコンテナに標準的な反復を使用して検索しています。ですから、ここでの複雑さはO（n）です。

コンテナに基づいて要素を高速化するには、コンテナのメソッドfindに電話する必要があります。

std::unordered_map::find O（1）の検索の複雑さを指しているので、ハッシングを使用しています。

std::map::find検索の複雑さは、バイナリ検索を使用しているため、O（log（n））です。