A. More conservative insert(auto&&) impl

achabense · achabense · commit 312c496ab22e · 2023-08-31T12:24:40.000+08:00
diff --git a/stl/inc/flat_set b/stl/inc/flat_set
@@ -472,16 +472,24 @@ private:
             const iterator _End   = end();
             const iterator _Where = lower_bound(_Val);
             if (_Where != _End && _Keys_equal(*_Where, _Val)) {
+                // NOTE: if contains(val), the _STL_ASSERT(find(key(val))!=end (==_Where)) cannot be done without
+                // potential side effect.
                 return pair{_Where, false};
             }
             if constexpr (is_same_v<remove_cvref_t<_Ty>, _Kty>) {
                 return pair{_Cont.emplace(_Where, _STD forward<_Ty>(_Val)), true};
             } else {
                 // for flat_set::insert(auto&&)
                 _STL_INTERNAL_STATIC_ASSERT(_Keylt_transparent && is_constructible_v<_Kty, _Ty>);
+                // NOTE: !contains(val).
                 _Kty _Keyval(_STD forward<_Ty>(_Val));
-                _STL_ASSERT(_Check_where(_Where, _Keyval), "The input type was not equivalent to key_type!");
-                return pair{_Cont.emplace(_Where, _STD move(_Keyval)), true};
+                _STL_ASSERT(!contains(_Keyval), "find(val)==end but find(key(val))!=end");
+                // NOTE: Not trusting the strict equivalence(so that lower_bound(val)==lower_bound(key(val))) of val and
+                // key(val), so reuse _Emplace_hint instead, with the hope that, if really strictly equivalent, then the
+                // _Emplace_hint will not pose extra lower_bound cost; if not, the key(val) will be inserted at the
+                // correct position.
+                return pair{_Emplace_hint(_Where, _STD move(_Keyval)),
+                    true /*guaranteed by the precondition and checked by the assertion*/};
             }
         }
     }
@@ -536,10 +544,18 @@ private:
                 return _Cont.emplace(_Where, _STD forward<_Ty>(_Val));
             } else {
                 // for flat_set::insert(hint,auto&&)
+                // NOTE: In the above code, the hint is used as the hint for seeking lower_bound. If val
+                // is strictly equivalent to key(val), then this also works as if treating as insertion position, so the
+                // _Emplace_hint will also not make extra lower_bound search.
+                //
+                // I cannot imagine how hint can be used or provided in a meaningful way if not strictly equivalent. At
+                // least one full lower_bound search is required either in deciding the ?contains(val) or
+                // lower_bound(key(val)), so the time complexity constraint cannot hold true. Anyway, using
+                // _Emplace_hint can at least guarantee that the key(val) will be inserted at the correct position.
                 _STL_INTERNAL_STATIC_ASSERT(_Keylt_transparent && is_constructible_v<_Kty, _Ty>);
                 _Kty _Keyval(_STD forward<_Ty>(_Val));
-                _STL_ASSERT(_Check_where(_Where, _Keyval), "The input type was not equivalent to key_type!");
-                return _Cont.emplace(_Where, _STD move(_Keyval));
+                _STL_ASSERT(!contains(_Keyval), "find(val)==end but find(key(val))!=end");
+                return _Emplace_hint(_Where, _STD move(_Keyval));
             }
         }
     }
