[2/2] Fix complexity of map insert_or_assign with a hint.

[Mordante]

Summary

In bug 38722 Mitsuru Kariya reported the map operations insert_or_assign with a hint violates the complexity requirement. The function no longer uses a lower_bound, which caused the wrong complexity.

This fixes bug 38722.

Benchmarked with:
Run on (4 X 3400 MHz CPU s)
CPU Caches:
  L1 Data 32K (x4)
  L1 Instruction 32K (x4)
  L2 Unified 256K (x4)
  L3 Unified 6144K (x1)


Timing before:
-----------------------------------------------------------------------------------------------
Benchmark                                                    Time             CPU   Iterations
-----------------------------------------------------------------------------------------------
BM_InsertAssignHint_MapSize=10_ExistingElement            6.99 ns         6.98 ns    121900000
BM_InsertAssignHint_MapSize=100_ExistingElement           14.4 ns         14.4 ns     48800000
BM_InsertAssignHint_MapSize=1000_ExistingElement          43.0 ns         43.0 ns     17000000
BM_InsertAssignHint_MapSize=10000_ExistingElement         56.5 ns         56.5 ns     11000000
BM_InsertAssignHint_MapSize=100000_ExistingElement         116 ns          116 ns      6000000
BM_InsertAssignHint_MapSize=1000000_ExistingElement        154 ns          154 ns      5000000
BM_InsertAssignHint_MapSize=10_NewElement                 28.4 ns         28.4 ns     24690000
BM_InsertAssignHint_MapSize=100_NewElement                72.4 ns         72.4 ns     12600000
BM_InsertAssignHint_MapSize=1000_NewElement               74.3 ns         74.3 ns      9000000
BM_InsertAssignHint_MapSize=10000_NewElement              92.4 ns         92.4 ns      7000000
BM_InsertAssignHint_MapSize=100000_NewElement              151 ns          151 ns      5000000
BM_InsertAssignHint_MapSize=1000000_NewElement             194 ns          194 ns      4000000

-----------------------------------------------------------------------------------------------
Benchmark                                                    Time             CPU   Iterations
-----------------------------------------------------------------------------------------------
BM_InsertAssignHint_MapSize=10_ExistingElement            6.96 ns         6.96 ns    123030000
BM_InsertAssignHint_MapSize=100_ExistingElement           14.5 ns         14.4 ns     48600000
BM_InsertAssignHint_MapSize=1000_ExistingElement          43.0 ns         43.0 ns     17000000
BM_InsertAssignHint_MapSize=10000_ExistingElement         56.7 ns         56.7 ns     11000000
BM_InsertAssignHint_MapSize=100000_ExistingElement         116 ns          116 ns      6000000
BM_InsertAssignHint_MapSize=1000000_ExistingElement        153 ns          153 ns      5000000
BM_InsertAssignHint_MapSize=10_NewElement                 28.6 ns         28.6 ns     24600000
BM_InsertAssignHint_MapSize=100_NewElement                76.2 ns         76.2 ns     12600000
BM_InsertAssignHint_MapSize=1000_NewElement               74.6 ns         74.6 ns      9000000
BM_InsertAssignHint_MapSize=10000_NewElement              92.4 ns         92.4 ns      7000000
BM_InsertAssignHint_MapSize=100000_NewElement              151 ns          151 ns      4000000
BM_InsertAssignHint_MapSize=1000000_NewElement             194 ns          194 ns      3000000

-----------------------------------------------------------------------------------------------
Benchmark                                                    Time             CPU   Iterations
-----------------------------------------------------------------------------------------------
BM_InsertAssignHint_MapSize=10_ExistingElement            6.96 ns         6.96 ns    122840000
BM_InsertAssignHint_MapSize=100_ExistingElement           14.5 ns         14.5 ns     49000000
BM_InsertAssignHint_MapSize=1000_ExistingElement          43.0 ns         43.0 ns     17000000
BM_InsertAssignHint_MapSize=10000_ExistingElement         56.4 ns         56.4 ns     11000000
BM_InsertAssignHint_MapSize=100000_ExistingElement         116 ns          116 ns      6000000
BM_InsertAssignHint_MapSize=1000000_ExistingElement        154 ns          154 ns      4000000
BM_InsertAssignHint_MapSize=10_NewElement                 28.3 ns         28.3 ns     24830000
BM_InsertAssignHint_MapSize=100_NewElement                76.1 ns         76.1 ns     12500000
BM_InsertAssignHint_MapSize=1000_NewElement               74.7 ns         74.7 ns      9000000
BM_InsertAssignHint_MapSize=10000_NewElement              92.8 ns         92.8 ns      7000000
BM_InsertAssignHint_MapSize=100000_NewElement              150 ns          150 ns      4000000
BM_InsertAssignHint_MapSize=1000000_NewElement             197 ns          197 ns      3000000

Timing after:
-----------------------------------------------------------------------------------------------
Benchmark                                                    Time             CPU   Iterations
-----------------------------------------------------------------------------------------------
BM_InsertAssignHint_MapSize=10_ExistingElement            4.30 ns         4.30 ns    167310000
BM_InsertAssignHint_MapSize=100_ExistingElement           8.18 ns         8.18 ns     85400000
BM_InsertAssignHint_MapSize=1000_ExistingElement          8.11 ns         8.11 ns     87000000
BM_InsertAssignHint_MapSize=10000_ExistingElement         8.11 ns         8.11 ns     87000000
BM_InsertAssignHint_MapSize=100000_ExistingElement        8.28 ns         8.28 ns     83000000
BM_InsertAssignHint_MapSize=1000000_ExistingElement       8.63 ns         8.62 ns     82000000
BM_InsertAssignHint_MapSize=10_NewElement                 23.5 ns         23.4 ns     30110000
BM_InsertAssignHint_MapSize=100_NewElement                63.2 ns         63.0 ns     10000000
BM_InsertAssignHint_MapSize=1000_NewElement               46.7 ns         46.6 ns     15000000
BM_InsertAssignHint_MapSize=10000_NewElement              41.8 ns         41.7 ns     13000000
BM_InsertAssignHint_MapSize=100000_NewElement             42.3 ns         42.1 ns     15000000
BM_InsertAssignHint_MapSize=1000000_NewElement            47.9 ns         47.7 ns     14000000

-----------------------------------------------------------------------------------------------
Benchmark                                                    Time             CPU   Iterations
-----------------------------------------------------------------------------------------------
BM_InsertAssignHint_MapSize=10_ExistingElement            4.30 ns         4.30 ns    167500000
BM_InsertAssignHint_MapSize=100_ExistingElement           8.39 ns         8.39 ns     84800000
BM_InsertAssignHint_MapSize=1000_ExistingElement          8.14 ns         8.15 ns     86000000
BM_InsertAssignHint_MapSize=10000_ExistingElement         8.12 ns         8.12 ns     87000000
BM_InsertAssignHint_MapSize=100000_ExistingElement        8.37 ns         8.37 ns     85000000
BM_InsertAssignHint_MapSize=1000000_ExistingElement       8.61 ns         8.61 ns     82000000
BM_InsertAssignHint_MapSize=10_NewElement                 23.4 ns         23.4 ns     29830000
BM_InsertAssignHint_MapSize=100_NewElement                66.8 ns         66.8 ns     10000000
BM_InsertAssignHint_MapSize=1000_NewElement               46.6 ns         46.6 ns     14000000
BM_InsertAssignHint_MapSize=10000_NewElement              41.3 ns         41.4 ns     14000000
BM_InsertAssignHint_MapSize=100000_NewElement             41.7 ns         41.7 ns     14000000
BM_InsertAssignHint_MapSize=1000000_NewElement            48.5 ns         48.5 ns     11000000

-----------------------------------------------------------------------------------------------
Benchmark                                                    Time             CPU   Iterations
-----------------------------------------------------------------------------------------------
BM_InsertAssignHint_MapSize=10_ExistingElement            4.27 ns         4.27 ns    166850000
BM_InsertAssignHint_MapSize=100_ExistingElement           8.53 ns         8.53 ns     85100000
BM_InsertAssignHint_MapSize=1000_ExistingElement          8.31 ns         8.31 ns     86000000
BM_InsertAssignHint_MapSize=10000_ExistingElement         8.17 ns         8.18 ns     86000000
BM_InsertAssignHint_MapSize=100000_ExistingElement        8.73 ns         8.73 ns     82000000
BM_InsertAssignHint_MapSize=1000000_ExistingElement       8.98 ns         8.98 ns     81000000
BM_InsertAssignHint_MapSize=10_NewElement                 24.6 ns         24.6 ns     29720000
BM_InsertAssignHint_MapSize=100_NewElement                71.9 ns         71.9 ns     10000000
BM_InsertAssignHint_MapSize=1000_NewElement               46.1 ns         46.1 ns     13000000
BM_InsertAssignHint_MapSize=10000_NewElement              41.7 ns         41.8 ns     14000000
BM_InsertAssignHint_MapSize=100000_NewElement             42.1 ns         42.1 ns     13000000
BM_InsertAssignHint_MapSize=1000000_NewElement            48.6 ns         48.6 ns     13000000

[mclow.lists]

You're going to need several tests here.

Hints that are correct.
Hints that are wrong.
Hints that are end() <-- All the tests we have pass end(), as far as I can tell.
See "test/std/containers/associative/map/map.modifiers/insert_node_type_hint.pass.cpp"

[Mordante]

It seems there already is a unit test "test/std/containers/associative/map/map.modifiers/insert_or_assign.pass.cpp". I'll add extra tests to this file.

[ldionne]

@Mordante Ping! I'm willing to look at this with added tests.

[Mordante]

Thanks for looking into these patches!

I thought I already had added the unit test, but seem I forgot to update the diff.

[Mordante]

Added unit tests as requested and rebased against master.

[ldionne]

libcxx/include/map

1285

I think it would be better if __emplace_hint_unique_key_args returned a pair of bool and iterator, like __emplace_unique_key_args does. We could then reuse it to implement this functionality. WDYT?

[Mordante]

I'll rebase the patch and then have a look at your suggestion.

[Mordante]

libcxx/include/map

1285

I think it could work something like:

auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(     
    __h.__i_, __k, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));           
  
if (!__inserted)                                                          
  __r->__get_value().second = _VSTD::forward<_Vp>(__v);              

return __r;

I'm not fond of using __k and moving it in the same function call, but try_emplace(key_type&& __k, _Args&&... __args) uses the same method for the key. Since it's safe here and I see no reason why it would become unsafe in the future I don't mind.

I like that this approach keeps the header file smaller so I'll test this approach further.

[ldionne]

libcxx/include/map

1285

Excellent. I like that it avoids code duplication, but I agree the move is a bit sneaky. Let's use that approach, though.

[Mordante]

Improves the code based on @ldionne's suggestion

• __emplace_hint_unique_key_args returns a pair
• insert_or_assign uses __emplace_hint_unique_key_args internally
• removes the now unused code from the initial patch
• removes unused #ifdefs for __emplace_hint_unique_key_args, they seem a copy paste and the code isn't used for C++03

[ldionne]

This looks really good, thanks! Just one comment about structured bindings, and I think we're good to go.

libcxx/include/map

1276

You can't use structured bindings here, this is supposed to work before C++17.

[Mordante]

libcxx/include/map

1276

I used the structured bindings since the code is ifdef'ed at line 1204 with #if _LIBCPP_STD_VER > 14 so I assumed it wasn't intended to be used prior to C++17. But no problem to use a pair.

[ldionne]

LGTM, please:

1. Reduce your commit message to get rid of the benchmark output
2. Run: for std in c++03 c++11 c++14 c++17 c++2a; do <build-dir>/bin/llvm-lit -sv libcxx/test/std/containers/associative/map --param std=$std; done to make sure it all works

And the commit. Yay!

libcxx/include/map

1276

Oh, my apologies. In that case that LGTM.

[Mordante]

Thanks for the review!

In D62779#2279968, @ldionne wrote:

LGTM, please:

2. Run: for std in c++03 c++11 c++14 c++17 c++2a; do <build-dir>/bin/llvm-lit -sv libcxx/test/std/containers/associative/map --param std=$std; done to make sure it all works

Thanks for this hint, clang tests al required C++ versions without overriding the std. It turns out the removed C++03 was required so I restored it before committing.

libcxx/include/__tree

#else
         _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value);
 #endif
 
 #ifndef _LIBCPP_CXX03_LANG
     template <class _Key, class ..._Args>
     pair<iterator, bool>
     __emplace_unique_key_args(_Key const&, _Args&&... __args);
     template <class _Key, class ..._Args>
-    iterator
+    pair<iterator, bool>
     __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...);
 
     template <class... _Args>
     pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
 
     template <class... _Args>
     iterator __emplace_hint_unique_impl(const_iterator __p, _Args&&... __args);
 
#ifndef _LIBCPP_CXX03_LANG
     template <class _First, class _Second>
     _LIBCPP_INLINE_VISIBILITY
     typename enable_if<
         __can_extract_map_key<_First, key_type, __container_value_type>::value,
         iterator
     >::type __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) {
         return __emplace_hint_unique_key_args(__p, __f,
                                               _VSTD::forward<_First>(__f),
-                                              _VSTD::forward<_Second>(__s));
+                                              _VSTD::forward<_Second>(__s)).first;
     }
 
     template <class... _Args>
     _LIBCPP_INLINE_VISIBILITY
     iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) {
         return __emplace_hint_unique_impl(__p, _VSTD::forward<_Args>(__args)...);
     }
 
     template <class _Pp>
     _LIBCPP_INLINE_VISIBILITY
     iterator
     __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) {
       return __emplace_hint_unique_impl(__p, _VSTD::forward<_Pp>(__x));
     }
 
     template <class _Pp>
     _LIBCPP_INLINE_VISIBILITY
     iterator
     __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) {
-      return __emplace_hint_unique_key_args(__p, __x, _VSTD::forward<_Pp>(__x));
+      return __emplace_hint_unique_key_args(__p, __x, _VSTD::forward<_Pp>(__x)).first;
     }
 
     template <class _Pp>
     _LIBCPP_INLINE_VISIBILITY
     iterator
     __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) {
-      return __emplace_hint_unique_key_args(__p, __x.first, _VSTD::forward<_Pp>(__x));
+      return __emplace_hint_unique_key_args(__p, __x.first, _VSTD::forward<_Pp>(__x)).first;
     }
 
 #else
     template <class _Key, class _Args>
     _LIBCPP_INLINE_VISIBILITY
     pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args& __args);
     template <class _Key, class _Args>
     _LIBCPP_INLINE_VISIBILITY
-    iterator __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&);
+    pair<iterator, bool> __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&);
 #endif
 
     _LIBCPP_INLINE_VISIBILITY
     pair<iterator, bool> __insert_unique(const __container_value_type& __v) {
         return __emplace_unique_key_args(_NodeTypes::__get_key(__v), __v);
     }
 
     _LIBCPP_INLINE_VISIBILITY
     iterator __insert_unique(const_iterator __p, const __container_value_type& __v) {
-        return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), __v);
+        return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), __v).first;
     }
 
 #ifdef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     iterator __insert_multi(const __container_value_type& __v);
     _LIBCPP_INLINE_VISIBILITY
     iterator __insert_multi(const_iterator __p, const __container_value_type& __v);
 #else
     _LIBCPP_INLINE_VISIBILITY
     pair<iterator, bool> __insert_unique(__container_value_type&& __v) {
         return __emplace_unique_key_args(_NodeTypes::__get_key(__v), _VSTD::move(__v));
     }
 
     _LIBCPP_INLINE_VISIBILITY
     iterator __insert_unique(const_iterator __p, __container_value_type&& __v) {
-        return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), _VSTD::move(__v));
+        return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), _VSTD::move(__v)).first;
     }
 
     template <class _Vp, class = typename enable_if<
             !is_same<typename __unconstref<_Vp>::type,
                      __container_value_type
             >::value
         >::type>
     _LIBCPP_INLINE_VISIBILITY

 #endif
         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
         __r = __h.release();
         __inserted = true;
     }
     return pair<iterator, bool>(iterator(__r), __inserted);
 }
 
-
 #ifndef _LIBCPP_CXX03_LANG
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key, class... _Args>
-typename __tree<_Tp, _Compare, _Allocator>::iterator
+pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args(
     const_iterator __p, _Key const& __k, _Args&&... __args)
 #else
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key, class _Args>
-typename __tree<_Tp, _Compare, _Allocator>::iterator
+pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args(
     const_iterator __p, _Key const& __k, _Args& __args)
 #endif
 {
     __parent_pointer __parent;
     __node_base_pointer __dummy;
     __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k);
     __node_pointer __r = static_cast<__node_pointer>(__child);
+    bool __inserted = false;
     if (__child == nullptr)
     {
 #ifndef _LIBCPP_CXX03_LANG
         __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
 #else
         __node_holder __h = __construct_node(__args);
 #endif
         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
         __r = __h.release();
+        __inserted = true;
     }
-    return iterator(__r);
+    return pair<iterator, bool>(iterator(__r), __inserted);
 }
 
-
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class ..._Args>
 typename __tree<_Tp, _Compare, _Allocator>::__node_holder
 __tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&& ...__args)
 {
     static_assert(!__is_tree_value_type<_Args...>::value,

libcxx/include/map

#if _LIBCPP_STD_VER > 14
 
     template <class... _Args>
         _LIBCPP_INLINE_VISIBILITY
         iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
     {
         return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
             _VSTD::piecewise_construct,
             _VSTD::forward_as_tuple(__k),
-            _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
+            _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)).first;
     }
 
     template <class... _Args>
         _LIBCPP_INLINE_VISIBILITY
         iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
     {
         return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
             _VSTD::piecewise_construct,
             _VSTD::forward_as_tuple(_VSTD::move(__k)),
-            _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
+            _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)).first;
     }
 
     template <class _Vp>
         _LIBCPP_INLINE_VISIBILITY
         pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
     {
         iterator __p = lower_bound(__k);
         if ( __p != end() && !key_comp()(__k, __p->first))
template <class _Vp>
         {
             __p->second = _VSTD::forward<_Vp>(__v);
             return _VSTD::make_pair(__p, false);
         }
         return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true);
     }
 
     template <class _Vp>
-        _LIBCPP_INLINE_VISIBILITY
-        iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v)
-     {
-        iterator __p = lower_bound(__k);
-        if ( __p != end() && !key_comp()(__k, __p->first))
-        {
-            __p->second = _VSTD::forward<_Vp>(__v);
-            return __p;
-        }
-        return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v));
-     }
+    _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator __h,
+                                                        const key_type& __k,
+                                                        _Vp&& __v) {
+      auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(
+          __h.__i_, __k, __k, _VSTD::forward<_Vp>(__v));
+
+      if (!__inserted)
+        __r->__get_value().second = _VSTD::forward<_Vp>(__v);
+
+      return __r;
 
     template <class _Vp>
-        _LIBCPP_INLINE_VISIBILITY
-        iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v)
-     {
-        iterator __p = lower_bound(__k);
-        if ( __p != end() && !key_comp()(__k, __p->first))
-        {
-            __p->second = _VSTD::forward<_Vp>(__v);
-            return __p;
-        }
-        return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
-     }
+    _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator __h,
+                                                        key_type&& __k,
+                                                        _Vp&& __v) {
+      auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(
+          __h.__i_, __k, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
+
+      if (!__inserted)
+        __r->__get_value().second = _VSTD::forward<_Vp>(__v);
+
+      return __r;
 
 #endif // _LIBCPP_STD_VER > 14
 
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(iterator __p)       {return __tree_.erase(__p.__i_);}
     _LIBCPP_INLINE_VISIBILITY

libcxx/test/std/containers/associative/map/map.modifiers/insert_or_assign.pass.cpp

int main(int, char**)
         assert(r->second.get() == 3);  // value
 
         Moveable mv2(5, 5.0);
         r = m.insert_or_assign(it, 3, std::move(mv2));
         assert(m.size() == 11);
         assert(mv2.moved());           // was moved from
         assert(r->first        == 3);  // key
         assert(r->second.get() == 5);  // value
+
+        // wrong hint: begin()
+        Moveable mv3(7, 7.0);
+        r = m.insert_or_assign(m.begin(), 4, std::move(mv3));
+        assert(m.size() == 11);
+        assert(mv3.moved());           // was moved from
+        assert(r->first        == 4);  // key
+        assert(r->second.get() == 7);  // value
+
+        Moveable mv4(9, 9.0);
+        r = m.insert_or_assign(m.begin(), 5, std::move(mv4));
+        assert(m.size() == 12);
+        assert(mv4.moved());           // was moved from
+        assert(r->first        == 5);  // key
+        assert(r->second.get() == 9);  // value
+
+        // wrong hint: end()
+        Moveable mv5(11, 11.0);
+        r = m.insert_or_assign(m.end(), 6, std::move(mv5));
+        assert(m.size() == 12);
+        assert(mv5.moved());           // was moved from
+        assert(r->first        == 6);  // key
+        assert(r->second.get() == 11); // value
+
+        Moveable mv6(13, 13.0);
+        r = m.insert_or_assign(m.end(), 7, std::move(mv6));
+        assert(m.size() == 13);
+        assert(mv6.moved());           // was moved from
+        assert(r->first        == 7);  // key
+        assert(r->second.get() == 13); // value
+
+        // wrong hint: third element
+        Moveable mv7(15, 15.0);
+        r = m.insert_or_assign(std::next(m.begin(), 2), 8, std::move(mv7));
+        assert(m.size() == 13);
+        assert(mv7.moved());           // was moved from
+        assert(r->first        == 8);  // key
+        assert(r->second.get() == 15); // value
+
+        Moveable mv8(17, 17.0);
+        r = m.insert_or_assign(std::next(m.begin(), 2), 9, std::move(mv8));
+        assert(m.size() == 14);
+        assert(mv8.moved());           // was moved from
+        assert(r->first        == 9);  // key
+        assert(r->second.get() == 17); // value
     }
     { // iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
         typedef std::map<Moveable, Moveable> M;
         M m;
         M::iterator r;
         for ( int i = 0; i < 20; i += 2 )
             m.emplace ( Moveable(i, (double) i), Moveable(i+1, (double) i+1));
         assert(m.size() == 10);
int main(int, char**)
         Moveable mvkey2(3, 3.0);
         Moveable mv2(5, 5.0);
         r = m.insert_or_assign(it, std::move(mvkey2), std::move(mv2));
         assert(m.size() == 11);
         assert(mv2.moved());           // was moved from
         assert(mvkey2.moved());        // was moved from
         assert(r->first.get()  == 3);  // key
         assert(r->second.get() == 5);  // value
+
+        // wrong hint: begin()
+        Moveable mvkey3(6, 6.0);
+        Moveable mv3(8, 8.0);
+        r = m.insert_or_assign(m.begin(), std::move(mvkey3), std::move(mv3));
+        assert(m.size() == 11);
+        assert(mv3.moved());           // was moved from
+        assert(!mvkey3.moved());       // was not moved from
+        assert(r->first == mvkey3);    // key
+        assert(r->second.get() == 8);  // value
+
+        Moveable mvkey4(7, 7.0);
+        Moveable mv4(9, 9.0);
+        r = m.insert_or_assign(m.begin(), std::move(mvkey4), std::move(mv4));
+        assert(m.size() == 12);
+        assert(mv4.moved());           // was moved from
+        assert(mvkey4.moved());        // was moved from
+        assert(r->first.get()  == 7);  // key
+        assert(r->second.get() == 9);  // value
+
+        // wrong hint: end()
+        Moveable mvkey5(8, 8.0);
+        Moveable mv5(10, 10.0);
+        r = m.insert_or_assign(m.end(), std::move(mvkey5), std::move(mv5));
+        assert(m.size() == 12);
+        assert(mv5.moved());           // was moved from
+        assert(!mvkey5.moved());       // was not moved from
+        assert(r->first == mvkey5);    // key
+        assert(r->second.get() == 10); // value
+
+        Moveable mvkey6(9, 9.0);
+        Moveable mv6(11, 11.0);
+        r = m.insert_or_assign(m.end(), std::move(mvkey6), std::move(mv6));
+        assert(m.size() == 13);
+        assert(mv6.moved());           // was moved from
+        assert(mvkey6.moved());        // was moved from
+        assert(r->first.get()  == 9);  // key
+        assert(r->second.get() == 11); // value
+
+        // wrong hint: third element
+        Moveable mvkey7(10, 10.0);
+        Moveable mv7(12, 12.0);
+        r = m.insert_or_assign(std::next(m.begin(), 2), std::move(mvkey7), std::move(mv7));
+        assert(m.size() == 13);
+        assert(mv7.moved());           // was moved from
+        assert(!mvkey7.moved());       // was not moved from
+        assert(r->first == mvkey7);    // key
+        assert(r->second.get() == 12); // value
+
+        Moveable mvkey8(11, 11.0);
+        Moveable mv8(13, 13.0);
+        r = m.insert_or_assign(std::next(m.begin(), 2), std::move(mvkey8), std::move(mv8));
+        assert(m.size() == 14);
+        assert(mv8.moved());           // was moved from
+        assert(mvkey8.moved());        // was moved from
+        assert(r->first.get()  == 11); // key
+        assert(r->second.get() == 13); // value
     }
 
   return 0;
 }