事前に私の質問を見てくれてありがとう。
私は次のことを尋ねる大学の課題の質問を完了しています：
std :: list <>、std :: map <>、std :: unordered_map <>のそれぞれについて、要素の挿入とルックアップの保証されたパフォーマンスを文書化して説明します。
リスト内の要素検索について説明するまで、私はこれのほとんどを行うのに問題はありませんでした。
Josuttisとhttp://www.cplusplus.comから情報を収集していますが、これに関する情報が見つからないようです。
できないから推測しますか？
その部分以外は問題なかったとおっしゃっていますlistので、その部分についてのみお答えします。
この質問に答えるにstd::listは、実装方法を理解する必要があります。いくつかのクイック検索が表示されます：
リストコンテナは、二重にリンクされたリストとして実装されます。
私がそれをどのように解釈するかから、保証されたパフォーマンスは、最悪の場合のランタイムの複雑さと同じことを意味します。
二重リンクリストでの要素ルックアップの場合、最悪のシナリオは、ルックアップしようとしているアイテムがリストに含まれていないことです。その場合、リスト内のすべてのアイテムを検索しているアイテムと比較する必要があります。したがって、この操作の最悪の場合の実行時の複雑さはO（n）です。ここnで、はリストのサイズです。
サポートされているものについてより正式なステートメントが必要な場合は、標準で次のように記述されています。std::lower_bound私たちができる最善の検索については、 （§25.4.3.1/ 3）のような二分探索を使用することです。
複雑さ：最大でlog 2（
last − first）+ O（1）の比較。
ただし、これは比較の数を示しているだけです。コンテナ内を移動するには、lower_boundを使用しstd::advanceます。私たちが見つけたstd::listについて（§23.3.5.1/ 1）：
リストは、双方向イテレータをサポートするシーケンスコンテナです[...]
std::advanceでは、双方向イテレータを提供するコレクションではどのように機能するのでしょうか。（§24.4.4/ 1）：
[...]入力、順方向、および双方向のイテレータの場合、++を使用して線形時間の実装を提供します。
したがって、リスト内の何かを（値または位置のいずれかで）見つけるために、対数の比較数を使用して、全体的に線形の複雑さを調べます。正直なところ、std::find（§25.2.5/ 2）の方がおそらく良いでしょう：
複雑さ：
last - first対応する述語のほとんどのアプリケーション。
ただし、2つのどちらを選択するかは、必ずしも完全に明白であるとは限りません。リストのトラバースは明らかに直線的です。std::findトラバーサルをstd::lower_bound最小限に抑え、比較を最小限に抑えます。比較がトラバーサルよりもはるかに高価な場合は、std::lower_boundおそらくより良い結果が得られます。比較がかなり安い場合std::findは、おそらくより良いでしょう。
http://www.cplusplus.com/reference/list/list/から
これらの他のシーケンスコンテナと比較したlistsおよびforward_listsの主な欠点は、それらの位置によって要素に直接アクセスできないことです。たとえば、リストの6番目の要素にアクセスするには、既知の位置（開始位置や終了位置など）からその位置まで反復する必要があります。これには、これらの間の距離で線形時間がかかります。また、各要素に関連付けられたリンク情報を保持するために追加のメモリを消費します（これは、小さなサイズの要素の大きなリストにとって重要な要素になる可能性があります）。
したがって、std :: list <>（要素の検索）を反復処理することは線形の複雑さです。また、インデックスで要素にアクセスすることはできません。
次のリファレンスを読むことをお勧めします 。標準コンテナの複雑さの保証は何ですか？
多くの標準コンテナの注文の複雑さのチャートがあり、回答の1つはSTLの複雑さの仕様にリンクしています。（http://www.sgi.com/tech/stl/complexity.html）
これはクラスプロジェクトであるため、回答のためにこれらのリファレンスを読むだけでなく、STLヘッダーで時間をかけて、アーキテクチャへのこれらのコンテナの実装の感触をつかむことをお勧めします。
STLは、真の専門家の知識を活用するための素晴らしい方法です...ただし、デューデリジェンスが与えられていない場合は、十分なことわざのロープになることもあります。