std::map の iterator insert (iterator position, const value_type& val); (with hint) はどうなっているの？？

#質問概要

std::map のwith hint の insert()であるiterator insert (iterator position, const value_type& val); はどうやって与えられたヒント(iterator position)が適当なヒントかどうかを判断しているんでしょうか？？
各種ライブラリではどのようなロジックでこの関数が実装されているか知りたいです！
自分でライブラリのソースコードを見てみようと思ったのですが、難解でわかりませんでした。。。。。

#質問詳細
このリファレンスによると、C++98 において上記のinsert()については、

Hint for the position where the element can be inserted.
C++98
The function optimizes its insertion time if position points to the element that will precede the inserted element.
Notice that this is just a hint and does not force the new element to be inserted at that position within the map container (the elements in a map always follow a specific order depending on their key).
Member types iterator and const_iterator are defined in map as bidirectional iterator types that point to

とあります。

つまり、map の平衡二分木の条件を満たすような挿入なら、新しい要素を挿入位置のヒントを表すイテレータpositionのすぐ前に挿入する。そうじゃなかったらO(log N)で最適な挿入場所を探索して挿入。ってことだと解釈してます。
↑
（そもそもこの理解あってる？？）

とすると、正直にやろうとしたら、ヒントとして与えられたposition の前に新要素を挿入することが適当かどうか判断する作業が毎度必要ですよね

結局、root まで登りながら平衡が保たれているかの判断をしないといけないため、O(log N)の計算量が必要になります。

なので計算量を抑えられるというこの関数の効用がなくなってしまいますよね？

ライブラリでは、与えられたposition が適切なヒントかどうかをどうやって判断しているのでしょうか。

よろしくお願いします！！！！m（＿　＿）m

もし質問がわかりにくかったら修正依頼を出していただけたらもっと詳しく書きます！！

行動規範の内容に同意します

回答1件

ベストアンサー

あまりアルゴリズムに詳しくないのでcpprefjpを読んだ範囲で。

平衡二分探索木を登りながら判定していくわけですが、一つ木を登るだけで判定が終わればそのとき最適位置だったこととなり、償却時間で処理できるのではないでしょうか・・・？

https://cpprefjp.github.io/reference/map/map/insert.html

(3), (4) : 一般に対数時間だが、指定された新たな要素が position が指す要素の直前に挿入された場合は償却定数時間。（ただし、備考も参照）

(3), (4) : C++03 までの仕様では、計算量が償却定数時間となる条件は、「position が指す要素の後ろに挿入された場合」となっているが、主要な実装はC++03時点から position が指す前に挿入する場合に償却定数時間となっていた。これは、position の後ろでは、適切な位置が先頭の場合に指定する方法がないこと、vector::insert の場合、position の前に挿入されること、STL のオリジナルである HP 社の実装が position の前に挿入する場合に償却定数時間であったことなどによる。

投稿2021/02/19 12:21