リストを検索する方法は簡単ですか？

Question

私はプログラムをより効率的に走らせようとしています。このリニアサーチを修正することは、スピードの面で大きな助けになると思いますが、これをバイナリ私はリストが必ずしも注文されていないと思うので、検索。最初の引数keyに基づいてリストを注文する方法はありますか？私は現在で働いて何

：

int* key_sequences::data(int key){ 
    for(it=myList.begin(); it!=myList.end(); ++it){ 
     if(it->first==key){ 
      return &(it->second[0]); 
     } 
    } 
    return nullptr; 
}; 

Answer 1

は、単にリンクリストでの検索はnは、リストのサイズであるO（n）と、です。

しかし、一部の実装では、開始時に1つ、中央に1つ、最後に1つの3つのリストポインタを使用するため、検索が始まると処理が高速化され、オンラインで検索できますこの。

しかし、私があなたであり、検索を高速化するのに面白かった場合は、別のデータ構造（ハッシュはstd::unordered_mapのような）を試してみるか、リストをソートします。