私はcplusplus.comstd::mapで、引数としてイテレータを渡すことによってaの要素を削除する操作は定数時間であることを読みました。
私が間違っていない場合（そして私が間違っている場合は訂正してください）、イテレータは基本的にマップ内の要素へのポインタであり、++演算子は現在の要素の順序どおりの後続を返すだけです。std::map。
マップが赤黒木である場合、要素の削除（そのアドレスを使用）を対数時間操作にすべきではありませんが、定数時間でどのように削除するのでしょうか（メモリを浪費する代替手段がない限り） 。
手始めに、cplusplus.comから取得する情報には注意が必要です。サイトにいくつかのエラーがあることが知られています。
cppreference.comにアクセスすると、複雑さが一定時間で償却されていることがわかります。これはerase、個々の消去操作にO（1）よりも長い時間がかかる場合でも、n回の操作のシーケンスにはO（n）の時間がかかることを意味します。
赤/黒木からの挿入または削除に必要な時間は、次のように計算されることになります。各挿入または削除には、ノードの位置を見つけるのに時間O（log n）がかかりますが、その後、償却されたO（ 1）要素の挿入または削除を行います。つまり、赤黒木からノードを挿入または削除する作業は、後でツリーのバランスを取り直すために必要な作業ではなく、そのノードがどこに行くのかを把握するために必要な作業によって支配されます。その結果、すでに赤黒木へのポインタがあり、その要素を削除したい場合は、要素を削除するために償却されたO（1）作業を行うだけで済みます。個々の削除には少し時間がかかる場合がありますが（最大でO（log n））、n回の操作のストリーム全体で、実行される作業の合計は最大でO（n）です。
std::map標準では、赤/黒の木を使用する必要がないことに注意してください。この時間の複雑さを保証する別のタイプのデータ構造（たとえば、スプレーツリー、スケープゴートツリー、または決定論的スキップリスト）を使用することもできます。ただし、興味深いことに、すべての平衡二分探索木構造が償却されたO（1）削除をサポートできるわけではありません。たとえば、AVLツリーにはこの保証はありません。
お役に立てれば！
イテレータをマップに渡して要素を削除すると、 http： //www.cplusplus.com/reference/map/map/erase/に従って一定時間償却されます。
償却定数時間とは、「多くの操作を行う場合、操作ごとにかかる平均時間」を意味します。そのため、一定時間よりも時間がかかる操作もあるかもしれませんが、同じ操作を何度も行うと、一定に償却されます。