unordered_map::emplace in C++0x

Discussion in 'C++' started by Scott Meyers, Apr 29, 2011.

  1. Scott Meyers

    Scott Meyers Guest

    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
     
    Scott Meyers, Apr 29, 2011
    #1
    1. Advertising

  2. Scott Meyers

    ZMZ Guest

    On Apr 29, 1:38 pm, Scott Meyers <> wrote:
    > 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


    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?
     
    ZMZ, Apr 29, 2011
    #2
    1. Advertising

  3. Scott Meyers

    Marc Guest

    Scott Meyers wrote:

    > 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.
     
    Marc, Apr 29, 2011
    #3
  4. Scott Meyers

    SG Guest

    On 29 Apr., 07:38, Scott Meyers wrote:
    >
    > 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
     
    SG, Apr 29, 2011
    #4
  5. Scott Meyers

    Marc Guest

    SG wrote:
    > On 29 Apr., 07:38, Scott Meyers wrote:
    >> 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.


    Then the text Scott quoted should at least be changed, replacing T
    with value_type.
     
    Marc, Apr 29, 2011
    #5
  6. Scott Meyers

    Scott Meyers Guest

    On 4/29/2011 9:11 AM, SG wrote:
    > On 29 Apr., 07:38, Scott Meyers wrote:
    >>
    >> 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.


    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

    --
    * C++ and Beyond: Meyers, Sutter, & Alexandrescu, Aug 7-10 in Banff
    (http://cppandbeyond.com/)
     
    Scott Meyers, Apr 29, 2011
    #6
  7. Scott Meyers

    SG Guest

    On 29 Apr., 20:00, Scott Meyers wrote:
    > On 4/29/2011 9:11 AM, SG wrote:
    > > 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.


    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.

    > >       themap.emplace(piecewise_construct,
    > >         forward_as_tuple(23,42),
    > >         forward_as_tuple(99,3.1415,"hello") );

    >
    > 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
     
    SG, Apr 30, 2011
    #7
  8. On Apr 30, 6:27 am, SG <> wrote:
    > On 29 Apr., 20:00, Scott Meyers wrote:
    >
    > > On 4/29/2011 9:11 AM, SG wrote:
    > > > 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.

    >
    > 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.
    >
    > > >       themap.emplace(piecewise_construct,
    > > >         forward_as_tuple(23,42),
    > > >         forward_as_tuple(99,3.1415,"hello") );

    >
    > > 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.


    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
     
    Pablo Halpern, May 5, 2011
    #8
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Paulo Matos

    Template problem with unordered_map

    Paulo Matos, Aug 3, 2006, in forum: C++
    Replies:
    4
    Views:
    468
    Paulo Matos
    Aug 3, 2006
  2. Rares Vernica

    error with tr1 unordered_map iterator

    Rares Vernica, Feb 24, 2007, in forum: C++
    Replies:
    6
    Views:
    1,822
  3. abir
    Replies:
    6
    Views:
    884
    W Karas
    Jun 26, 2008
  4. abir
    Replies:
    3
    Views:
    1,158
  5. Brian

    Emplace question

    Brian, May 17, 2010, in forum: C++
    Replies:
    2
    Views:
    929
    Brian
    May 17, 2010
Loading...

Share This Page