Part 1 of N4279 - "Improved insertion interface for unique-key maps"

[mclow.lists]

Summary

N4279 added try_emplace and insert_or_assign to std::map and std::unordered_map.
This patch implements the changes to map.

[mclow.lists]

Changed a couple of moves to forwards, and made the tests better.
I have an analogous set of changes to <unordered_map>, but since they're almost completely the same, I figured that they would add noise w/o value to this,

[mclow.lists]

Updated the diff with the changes from LWG#2464

[mclow.lists]

include/map

1138

I think this should be __h, not __p, since __p == end()

1151

Same as #1138

[EricWF]

A couple of inline comments. More to come.

include/map

1098

What kind of terrible compiler provides an C++11-incomplete C++17 implementation? It would be nice if we could move away from using these macros in anything C++14 and beyond.

However I don't object if you think they are needed.

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

63

Same comment as above. Should we hide these C++17 failures for non-conforming compilers?

[EricWF]

LGTM modulo inline comments.

include/map

1138

I actually think you should leave this as is. __tree seems to properly handle the end iterator as a hint. __tree::__find_equal(hint, ...) assumes that if hint is end() then the value should be inserted just prior to hint.

You should be able to implement the the try_emplace(hint, ...) methods in terms of the normal try_emplace methods because we ignore the hint anyway.

test/std/containers/associative/map/map.modifiers/try.emplace.pass.cpp

70

Why not use try_emplace here as well?

73

For the sake of covering corner cases could we test every inserted value? This applies for insert_or_assign as well.

for (int i=0; i < 20; i += 2) {
  Movable mv1(i, (double)i);
  r = m.try_emplace(2, std::move(mv1));
  assert(m.size() == 10);
  assert(!r.second);                  // was not inserted
  assert(!mv1.moved());               // was not moved from
  assert(r.first->first == 2);        // key
}

80

We should test the cases where insertion happens at the front and at the back.

[mclow.lists]

test/std/containers/associative/map/map.modifiers/try.emplace.pass.cpp

73

This doesn't really buy us anything, because it won't look at the value (mv1) unless the key doesn't exist. So this code is not testing every inserted value.

I think that this is what you meant:

for (int i=0; i < 20; i += 2) {
  Movable mv1(i, (double)i);
  r = m.try_emplace(i, std::move(mv1));
  assert(m.size() == 10);
  assert(!r.second);                  // was not inserted
  assert(!mv1.moved());               // was not moved from
  assert(r.first->first == i);        // key
}

80

If you want; though the behavior that we're checking for here is "was this inserted?" and "was the value moved from?", which are dependent upon "Did the value exist in the map before", as opposed to the position in the map.

[mclow.lists]

Committed as r241539.

include/map

         void insert(InputIterator first, InputIterator last);
     void insert(initializer_list<value_type> il);
 
+    template <class... Args>
+        pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);          // C++17
+    template <class... Args>
+        pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);               // C++17
+    template <class... Args>
+        iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
+    template <class... Args>
+        iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);      // C++17
+    template <class M>
+        pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);            // C++17
+    template <class M>
+        pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);                 // C++17
+    template <class M>
+        iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);   // C++17
+    template <class M>
+        iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);        // C++17
+
     iterator  erase(const_iterator position);
     iterator  erase(iterator position); // C++14
     size_type erase(const key_type& k);

 
 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
+#if _LIBCPP_STD_VER > 14
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef _LIBCPP_HAS_NO_VARIADICS
+    template <class... _Args>
+        _LIBCPP_INLINE_VISIBILITY
+        pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
+    {
+        iterator __p = lower_bound(__k);
+        if ( __p != end() && !key_comp()(__k, __p->first))
+            return _VSTD::make_pair(__p, false);
+        else
+            return _VSTD::make_pair(
+                      emplace_hint(__p, 
+                        _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k), 
+                        _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)),
+                      true);
+    }
+
+    template <class... _Args>
+        _LIBCPP_INLINE_VISIBILITY
+        pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
+    {
+        iterator __p = lower_bound(__k);
+        if ( __p != end() && !key_comp()(__k, __p->first))
+            return _VSTD::make_pair(__p, false);
+        else
+            return _VSTD::make_pair(
+                      emplace_hint(__p, 
+                        _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)), 
+                        _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)),
+                      true);
+    }
+
+    template <class... _Args>
+        _LIBCPP_INLINE_VISIBILITY
+        iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
+    {
+        iterator __p = lower_bound(__k);
+        if ( __p != end() && !key_comp()(__k, __p->first))
+            return __p;
+        else
+            return emplace_hint(__p, 
+                      _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k), 
+                      _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
+    }
+
+    template <class... _Args>
+        _LIBCPP_INLINE_VISIBILITY
+        iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
+    {
+        iterator __p = lower_bound(__k);
+        if ( __p != end() && !key_comp()(__k, __p->first))
+            return __p;
+        else
+            return emplace_hint(__p, 
+                      _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)), 
+                      _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
+    }
+
+    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))
+        {
+            __p->second = _VSTD::forward<_Vp>(__v);
+            return _VSTD::make_pair(__p, false);
+        }
+        return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
+    }
+        
+    template <class _Vp>
+        _LIBCPP_INLINE_VISIBILITY
+        pair<iterator, bool> insert_or_assign(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 _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));
+     }
+
+    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));
+     }
+#endif
+#endif
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
     _LIBCPP_INLINE_VISIBILITY

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

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: c++03, c++11, c++14
+
+// <map>
+
+// class map
+
+// template <class M>
+//  pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);            // C++17
+// template <class M>
+//  pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);                 // C++17
+// template <class M>
+//  iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);   // C++17
+// template <class M>
+//  iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);        // C++17
+
+#include <__config>
+#include <map>
+#include <cassert>
+#include <tuple>
+
+#include <iostream>
+
+class Moveable
+{
+    Moveable(const Moveable&);
+    Moveable& operator=(const Moveable&);
+
+    int int_;
+    double double_;
+public:
+    Moveable() : int_(0), double_(0) {}
+    Moveable(int i, double d) : int_(i), double_(d) {}
+    Moveable(Moveable&& x)
+        : int_(x.int_), double_(x.double_)
+            {x.int_ = -1; x.double_ = -1;}
+    Moveable& operator=(Moveable&& x)
+        {int_ = x.int_; x.int_ = -1;
+         double_ = x.double_; x.double_ = -1;
+         return *this;
+        }
+
+    bool operator==(const Moveable& x) const
+        {return int_ == x.int_ && double_ == x.double_;}
+    bool operator<(const Moveable& x) const
+        {return int_ < x.int_ || (int_ == x.int_ && double_ < x.double_);}
+
+    int get() const {return int_;}
+    bool moved() const {return int_ == -1;}
+};
+
+
+int main()
+{
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef _LIBCPP_HAS_NO_VARIADICS
+
+    { // pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
+        typedef std::map<int, Moveable> M;
+        typedef std::pair<M::iterator, bool> R;
+        M m;
+        R r;
+        for ( int i = 0; i < 20; i += 2 )
+            m.emplace ( i, Moveable(i, (double) i));
+        assert(m.size() == 10);
+
+        Moveable mv1(3, 3.0);
+        r = m.insert_or_assign(2, std::move(mv1));
+        assert(m.size() == 10);
+        assert(!r.second);                  // was not inserted
+        assert(mv1.moved());                // was moved from
+        assert(r.first->first        == 2); // key
+        assert(r.first->second.get() == 3); // value
+
+        Moveable mv2(5, 5.0);
+        r = m.insert_or_assign(3, std::move(mv2));
+        assert(m.size() == 11);
+        assert(r.second);                   // was inserted
+        assert(mv2.moved());                // was moved from
+        assert(r.first->first        == 3); // key
+        assert(r.first->second.get() == 5); // value
+    }
+    { // pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
+        typedef std::map<Moveable, Moveable> M;
+        typedef std::pair<M::iterator, bool> R;
+        M m;
+        R 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);
+
+        Moveable mvkey1(2, 2.0);
+        Moveable mv1(4, 4.0);
+        r = m.insert_or_assign(std::move(mvkey1), std::move(mv1));
+        assert(m.size() == 10);
+        assert(!r.second);                  // was not inserted
+        assert(!mvkey1.moved());            // was not moved from
+        assert(mv1.moved());                // was moved from
+        assert(r.first->first == mvkey1);   // key
+        assert(r.first->second.get() == 4); // value
+
+        Moveable mvkey2(3, 3.0);
+        Moveable mv2(5, 5.0);
+        r = m.try_emplace(std::move(mvkey2), std::move(mv2));
+        assert(m.size() == 11);
+        assert(r.second);                   // was inserted
+        assert(mv2.moved());                // was moved from
+        assert(mvkey2.moved());             // was moved from
+        assert(r.first->first.get()  == 3); // key
+        assert(r.first->second.get() == 5); // value
+    }
+    { // iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
+        typedef std::map<int, Moveable> M;
+        M m;
+        M::iterator r;
+        for ( int i = 0; i < 20; i += 2 )
+            m.emplace ( i, Moveable(i, (double) i));
+        assert(m.size() == 10);
+        M::const_iterator it = m.find(2);
+
+        Moveable mv1(3, 3.0);
+        r = m.insert_or_assign(it, 2, std::move(mv1));
+        assert(m.size() == 10);
+        assert(mv1.moved());           // was moved from
+        assert(r->first        == 2);  // key
+        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
+    }
+    { // 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);
+        M::const_iterator it = std::next(m.cbegin());
+
+        Moveable mvkey1(2, 2.0);
+        Moveable mv1(4, 4.0);
+        r = m.insert_or_assign(it, std::move(mvkey1), std::move(mv1));
+        assert(m.size() == 10);
+        assert(mv1.moved());          // was moved from
+        assert(!mvkey1.moved());      // was not moved from
+        assert(r->first == mvkey1);   // key
+        assert(r->second.get() == 4); // value
+
+        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
+    }
+
+#endif  // _LIBCPP_HAS_NO_VARIADICS
+#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+}

test/std/containers/associative/map/map.modifiers/try.emplace.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: c++03, c++11, c++14
+
+// <map>
+
+// class map
+
+// template <class... Args>
+//  pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);          // C++17
+// template <class... Args>
+//  pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);               // C++17
+// template <class... Args>
+//  iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
+// template <class... Args>
+//  iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);      // C++17
+
+#include <__config>
+#include <map>
+#include <cassert>
+#include <tuple>
+
+class Moveable
+{
+    Moveable(const Moveable&);
+    Moveable& operator=(const Moveable&);
+
+    int int_;
+    double double_;
+public:
+    Moveable() : int_(0), double_(0) {}
+    Moveable(int i, double d) : int_(i), double_(d) {}
+    Moveable(Moveable&& x)
+        : int_(x.int_), double_(x.double_)
+            {x.int_ = -1; x.double_ = -1;}
+    Moveable& operator=(Moveable&& x)
+        {int_ = x.int_; x.int_ = -1;
+         double_ = x.double_; x.double_ = -1;
+         return *this;
+        }
+
+    bool operator==(const Moveable& x) const
+        {return int_ == x.int_ && double_ == x.double_;}
+    bool operator<(const Moveable& x) const
+        {return int_ < x.int_ || (int_ == x.int_ && double_ < x.double_);}
+
+    int get() const {return int_;}
+    bool moved() const {return int_ == -1;}
+};
+
+
+int main()
+{
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef _LIBCPP_HAS_NO_VARIADICS
+
+    { // pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
+        typedef std::map<int, Moveable> M;
+        typedef std::pair<M::iterator, bool> R;
+        M m;
+        R r;
+        for ( int i = 0; i < 20; i += 2 )
+            m.emplace ( i, Moveable(i, (double) i));
+        assert(m.size() == 10);
+
+        Moveable mv1(3, 3.0);
+        r = m.try_emplace(2, std::move(mv1));
+        assert(m.size() == 10);
+        assert(!r.second);                  // was not inserted
+        assert(!mv1.moved());               // was not moved from
+        assert(r.first->first == 2);        // key
+
+        r = m.try_emplace(3, std::move(mv1));
+        assert(m.size() == 11);
+        assert(r.second);                   // was inserted
+        assert(mv1.moved());                // was moved from
+        assert(r.first->first == 3);        // key
+        assert(r.first->second.get() == 3); // value
+    }
+
+    {  // pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); 
+        typedef std::map<Moveable, Moveable> M;
+        typedef std::pair<M::iterator, bool> R;
+        M m;
+        R 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);
+
+        Moveable mvkey1(2, 2.0);
+        Moveable mv1(4, 4.0);
+        r = m.try_emplace(std::move(mvkey1), std::move(mv1));
+        assert(m.size() == 10);
+        assert(!r.second);                 // was not inserted
+        assert(!mv1.moved());              // was not moved from
+        assert(!mvkey1.moved());           // was not moved from
+        assert(r.first->first == mvkey1);  // key
+
+        Moveable mvkey2(3, 3.0);
+        r = m.try_emplace(std::move(mvkey2), std::move(mv1));
+        assert(m.size() == 11);
+        assert(r.second);                   // was inserted
+        assert(mv1.moved());                // was moved from
+        assert(mvkey2.moved());             // was moved from
+        assert(r.first->first.get()  == 3); // key
+        assert(r.first->second.get() == 4); // value
+    }
+
+    {  // iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
+        typedef std::map<int, Moveable> M;
+        M m;
+        M::iterator r;
+        for ( int i = 0; i < 20; i += 2 )
+            m.emplace ( i, Moveable(i, (double) i));
+        assert(m.size() == 10);
+        Moveable mv1(3, 3.0);
+        M::const_iterator it = m.find(2);
+        
+        r = m.try_emplace(it, 2, std::move(mv1));
+        assert(m.size() == 10);
+        assert(!mv1.moved());         // was not moved from
+        assert(r->first == 2);        // key
+
+        r = m.try_emplace(it, 3, std::move(mv1));
+        assert(m.size() == 11);
+        assert(mv1.moved());          // was moved from
+        assert(r->first == 3);        // key
+        assert(r->second.get() == 3); // value
+    }
+
+    {  // iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
+        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);
+        M::const_iterator it = std::next(m.cbegin());
+
+        Moveable mvkey1(2, 2.0);
+        Moveable mv1(4, 4.0);
+        r = m.try_emplace(it, std::move(mvkey1), std::move(mv1));
+        assert(m.size() == 10);
+        assert(!mv1.moved());        // was not moved from
+        assert(!mvkey1.moved());     // was not moved from
+        assert(r->first == mvkey1);  // key
+
+        Moveable mvkey2(3, 3.0);
+        r = m.try_emplace(it, std::move(mvkey2), std::move(mv1));
+        assert(m.size() == 11);
+        assert(mv1.moved());          // was moved from
+        assert(mvkey2.moved());       // was moved from
+        assert(r->first.get()  == 3); // key
+        assert(r->second.get() == 4); // value
+    }
+
+#endif  // _LIBCPP_HAS_NO_VARIADICS
+#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+}