unordered_map::emplace in C++0x


S

Scott Meyers

I'm having another of those days where nothing makes sense, sigh.

C++0x's unordered_map supports emplacement via this member function
(from the FDIS):

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

Now, somehow emplace's implementation has to figure out which elements
of args correspond to the unordered_map's key and which to the mapped
data. That is, given an unordered_map<K, T> named "um" and a call to
emplace as follows,

um.emplace(foo, bar, baz, wuz, hmmm, er, ouch);

emplace has to figure out which of those arguments correspond to K and
which to T. How does it do that? The only description I can find of
what's supposed to happen is in table 103 of the FDIS, where I'm told
that, given an unordered_map of type X, a call of the form
um.emplace(args) has the following semantics. Note that in what
follows, T is the mapped type for the container (per 23.2.5/3):
Requires: T shall be
EmplaceConstructible into X
from args.
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.

If all the data in args is used to construct an object of type T, how
can emplace figure out what the key is supposed to be?

Thanks,

Scott
 
Ad

Advertisements

Z

ZMZ

I'm having another of those days where nothing makes sense, sigh.

C++0x's unordered_map supports emplacement via this member function
(from the FDIS):

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

Now, somehow emplace's implementation has to figure out which elements
of args correspond to the unordered_map's key and which to the mapped
data.  That is, given an unordered_map<K, T> named "um" and a call to
emplace as follows,

   um.emplace(foo, bar, baz, wuz, hmmm, er, ouch);

emplace has to figure out which of those arguments correspond to K and
which to T.  How does it do that?  The only description I can find of
what's supposed to happen is in table 103 of the FDIS, where I'm told
that, given an unordered_map of type X, a call of the form
um.emplace(args) has the following semantics.  Note that in what
follows, T is the mapped type for the container (per 23.2.5/3):


If all the data in args is used to construct an object of type T, how
can emplace figure out what the key is supposed to be?

Thanks,

Scott

I am not too sure but I happened to read on emplace proposals
recently.

From http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2680.pdf
, the author says,

"However, variadic templates provide no way of supplying two argument
lists (such a facility
would require a new syntax at the call site). But since the key_type
of a map is in practice much
less likely to require in-place construction, I believe that the
common (albeit asymmetrical) use N2642=08-0152 2 2008-05-19
case of a copy (or move) constructed key_type with an in-place
constructed mapped_type is
well worth supporting. "

So I guess the key is the first argument and being copied/moved, and
the value is in-place constructed?
 
M

Marc

Scott said:
I'm having another of those days where nothing makes sense, sigh.

C++0x's unordered_map supports emplacement via this member function
(from the FDIS):

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

Now, somehow emplace's implementation has to figure out which elements
of args correspond to the unordered_map's key and which to the mapped
data.

This is lwg issue 2006, which was classified as not-a-defect in
Batavia. I can't think of why such a decision was taken...

libstdc++ doesn't have this function yet, and libc++ implemented it as
explained in the first answer to your message, with the first argument
for the key and the others for the mapped type.
 
S

SG

C++0x's unordered_map supports emplacement via this member function
(from the FDIS):

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

Now, somehow emplace's implementation has to figure out which elements
of args correspond to the unordered_map's key and which to the mapped
data.

I don't think so. args is just forwarded to the value_type's
constructor. The value_type is a pair<const key_type, mapped_type>. To
see what we can pass as arguments to a map's emplace function we just
need to check what kind of constructors this value_type has. A pair
offers the following constructors:

- default constructor
- constructor taking two args that are forwarded
- conversion constructors from other pair types
- a piecewise_construct constructor
(taking three arguments, a dummy tag and two tuples)

The last one is interesting as it allows us to explicitly say which
arguments are used to construct the first member and which arguments
are used to construct the second. Example:

struct mykey {
...
mykey(int,int);
...
};

struct mymapped {
...
mymapped(int,double,string);
...
};

int main() {
using namespace std;
map<mykey,mymapped> themap;
themap.emplace(piecewise_construct,
forward_as_tuple(23,42),
forward_as_tuple(99,3.1415,"hello") );
}

where forward_as_tuple packs the arguments into "reference tuples"
while preserving their value category. That is, forward_as_tuple(99)
yields a tuple<int&&> and forward_as_tuple(some_int_variable) yields a
tuple<int&>. This function template used to be called "pack_arguments"
in earlier drafts.

In the emplace function template this is simply forwarded to the pair
constructor. No need to do anything special in the (unordered_)map
implementation.

Cheers!
SG
 
M

Marc

SG said:
I don't think so. args is just forwarded to the value_type's
constructor. The value_type is a pair<const key_type, mapped_type>. To
see what we can pass as arguments to a map's emplace function we just
need to check what kind of constructors this value_type has.

Then the text Scott quoted should at least be changed, replacing T
with value_type.
 
S

Scott Meyers

I don't think so. args is just forwarded to the value_type's
constructor.

Not according to table 103, at least not as I read it. If that's what's
supposed to happen (and it makes perfect sense that it would be), then
the semantics for the emplacement functions need to refer to creating an
object of type value_type, not T.
themap.emplace(piecewise_construct,
forward_as_tuple(23,42),
forward_as_tuple(99,3.1415,"hello") );
In the emplace function template this is simply forwarded to the pair
constructor.

Nifty, and thanks for the example, but this really emphasizes that the
semantics of emplace are to forward the arguments to the map's
value_type, not to T.

Scott
 
Ad

Advertisements

S

SG

Not according to table 103, at least not as I read it.

Right. I believe table 102 and 103 contain some errors in this regard.
It appears as if some references to T ought to be references to
value_type instead. Otherwise, I can't make much sense of these
tables. But I'm not 100% sure. I don't claim to be aware of the
intended behaviour. This is the interpretation of someone who has
almost no connection to the library working group.
Nifty, and thanks for the example, but this really emphasizes that the
semantics of emplace are to forward the arguments to the map's
value_type, not to T.

Let me stress that this is not an example I saw in some paper. I just
believe it's supposed to work like that.

Cheers!
Sebastian
 
Ad

Advertisements

P

Pablo Halpern

Right. I believe table 102 and 103 contain some errors in this regard.
It appears as if some references to T ought to be references to
value_type instead. Otherwise, I can't make much sense of these
tables. But I'm not 100% sure. I don't claim to be aware of the
intended behaviour. This is the interpretation of someone who has
almost no connection to the library working group.



Let me stress that this is not an example I saw in some paper. I just
believe it's supposed to work like that.

Your analysis and example are exactly right. I am both the inventor
of piecewise_construct and the author of LWG 2006 and I was present
when LWG 2006 was voted NAD in Batavia. It was decided that the
(inadvertent) change of the meaning of emplace from N2680 is actually
an improvement because it doesn't require special treatment for the
'first' member of pair. Your correctly shows how it is supposed to
work. A new issue is being opened to fix the editorial issue of
changing 'T' to 'value_type' in the description of emplace.

- Pablo
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top