STLの検索速度

[ぬっち]

お世話になっています。

タイトルとは質問内容が多少違ってしまうかもしれませんが、一番合うだろうと思われるものにしました。
リソースの管理クラスを作っていて、その実装方法でSTLのmapを使用することを考えました。
ところが、mapの検索にO(logN)かかり、その代替案としてのvectorがあり、この場合は検索にO(1)であるが、削除の仕方によっては削除していない要素にアクセスできないとのことです。
このことをネットで調べてみたところ、
http://www.c3.club.kyutech.ac.jp/gamewi ... ontent_1_9
のようなサイトがあり、検索速度について触れられていました。
ところが、最後の「そこで描画するオブジェクトに～」で始まる1段落がどういうことを言っているのかよくわかりませんでした。
ここのサイトの掲示板はスパム（？）で機能していないようでしたのでこちらで質問させていただくことにしました。

この段落はどのようなことを言っているのでしょうか？
リソースのポインタ自体を返して、それを用いて描画するということでしょうか？
mapでO(1)の検索速度で行えるということがいまいちよくわからなかったです。

私自身この問題についてよくわかっていませんので、場違いな質問でしたらすいません。

よろしくお願いします。

[MNS]

描画するオブジェクトを毎回検索して取得するよりは、
描画するオブジェクトを記録するポインタを作っておいて、
それに描画するオブジェクトのアドレスを記録して使うほうが速いという意味です。

つまり、

void Render()
{
myMap.find("Car")->second.Render(); //O(logN)
}

よりは、

Object* p_obj = &myMap.find("Car")->second;
void Render()
{
p_obj->Render(); //O(1)
}

とするほうが速いということです。

[ぬっち]

MNSさん返信ありがとうございました。

なるほど、最初に描画対象のポインタを保持しておくということですね。
コート付きのわかりやすい返答ありがとうございます。