Should node construction in map::emplace not be deferred until after the collision check?

[Tomalak Geret'kal]

Reference: http://stackoverflow.com/q/20328242/560648

Considering the following:

#include <memory>

#include <utility>

#include <map>

#include <iostream>

#include <cassert>

int main()

{

    typedef std::unique_ptr<int> T;

    T x(new int(1)), y(new int(2));

    

    std::map<int, T> m;

    

    m.emplace(1, std::move(x));

    auto it = m.emplace(1, std::move(y));

    

    assert(!it.second);

    std::cout << y.get() << '\n';

}

The result is "0"; that is, y has been moved into the container even though this occurred during an "emplace" operation that ultimately resulted in no modification to the container (since key 1 already existed).

Table 102 says about emplace:

Effects: Inserts a T object t constructed with std::forward<Args>(args)... if and only if there is no element in the container with key equivalent to the key of t.

So, I would not have expected this move. I would have expected the argument to be untouched since there is already an element in the container with key equivalent to the key of t. But, instead, GCC 4.8.0, clang v3.2 and MSVS 2012 all result in y becoming null.

• Is this the intent of the passage? Or wouldn't be clearer if the node construction only occurred if destined for insertion? Then the moved-from object would remain intact and untouched when no insertion is performed.
  
• Yes or no, could the passage be disambiguated to define whether or not the construction happens in this scenario, as well as defining whether the insertion happens?
  

Thanks,

Tom

 

[Howard Hinnant]

I believe this is covered by 17.6.4.9 Function arguments [res.on.arguments]/p1/b3:

> • If a function argument binds to an rvalue reference parameter, the implementation may assume that this parameter is a unique reference to this argument.

If one looks at this from the implementor's point of view:

template <class... Args>
pair<iterator, bool> emplace(Args&&... args);

To discover if the key already exists, one is going to have to construct a key from zero or more of the args... One does not know before hand which pair constructor args... is going to resolve to. There are pair constructors taking 0, 1, 2 or 3 arguments that could be the right match. I find it unsurprising that every single implementation has constructed the entire pair from args... prior to searching the tree for the existence of pair.first.

Howard

[Tomalak Geret'kal]

On Monday, December 2, 2013 5:08:40 PM UTC, Howard Hinnant wrote:

I believe this is covered by 17.6.4.9 Function arguments [res.on.arguments]/p1/b3:

> • If a function argument binds to an rvalue reference parameter, the implementation may assume that this parameter is a unique reference to this argument.

If one looks at this from the implementor's point of view:

    template <class... Args>
        pair<iterator, bool> emplace(Args&&... args);

To discover if the key already exists, one is going to have to construct a key from zero or more of the args...  One does not know before hand which pair constructor args... is going to resolve to.  There are pair constructors taking 0, 1, 2 or 3 arguments that could be the right match.  I find it unsurprising that every single implementation has constructed the entire pair from args... prior to searching the tree for the existence of pair.first.

Howard

A very good point. I would still expect that the key could be examined as a reference of some kind in order to achieve this, rather than requiring value initialisation* from it.

Otherwise, would you agree that the passage I quoted might remove the "and only if" and append "; otherwise, no insertion is performed (though construction may be)", in order to make this clearer?

* (May or may not be the correct term in this context)

Tom

[Howard Hinnant]

On Dec 2, 2013, at 12:13 PM, Tomalak Geret'kal <tom...@gmail.com> wrote:

> Otherwise, would you agree that the passage I quoted might remove the "and only if" and append "; otherwise, no insertion is performed (though construction may be)", in order to make this clearer?

No objections from me.

Howard

[xavi]

I filed a bug report to libc++ some time ago about something similar: http://llvm.org/bugs/show_bug.cgi?id=12999

My complain was more about efficiency that things being moved away, but I guess it's related. In my case, libstdc++ had the expected behaviour. 

2013/12/2 Tomalak Geret'kal <tom...@gmail.com>

--
 
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussio...@isocpp.org.
To post to this group, send email to std-dis...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-discussion/.

[Howard Hinnant]

On Dec 2, 2013, at 12:42 PM, xavi <gra...@gmail.com> wrote:

> I filed a bug report to libc++ some time ago about something similar: http://llvm.org/bugs/show_bug.cgi?id=12999
> My complain was more about efficiency that things being moved away, but I guess it's related. In my case, libstdc++ had the expected behaviour.

<nod> In this case it is quite fixable, because it is clear what the key is (you don't have to construct anything to discover what the key is). Indeed the libc++ bug disappears if the argument is an lvalue.

Howard

[David Krauss]

See discussion from two weeks ago: https://groups.google.com/a/isocpp.org/forum/#!search/inserting$20rvalue/std-proposals/uzdJImp2wAE/0ghNsBVYayAJ

The same issue exists in insert() , but there's less of an excuse because the argument is likely to be an rvalue reference to value_type pair.