std::map::emplace useful in any way?

[Marcel Mueller]

The emplace functions generally allows to construct container objects
directly at the target location. But std::map expects a value type of
std::pair<const Key, T>. Now the implementation of emplace needs to
instantiate the value type just to get the key to find the insert
location. This cannot happen at the target location, isn't it?

I know, this has been solved in C++17 by try_emplace. I just wonder what
was the idea of this function.


Marcel

[Paavo Helde]

Post by Marcel Mueller
The emplace functions generally allows to construct container objects
directly at the target location. But std::map expects a value type of
std::pair<const Key, T>. Now the implementation of emplace needs to
instantiate the value type just to get the key to find the insert
location. This cannot happen at the target location, isn't it?
I know, this has been solved in C++17 by try_emplace. I just wonder what
was the idea of this function.

Most probably it was done just for symmetry with other containers.

The cppreference site also gives an example which uses
std::piecewise_construct to emulate try_emplace, so it looks like it is
actually possible to use emplace for a real in-place construction,
albeit in a pretty convoluted way.

[Bonita Montero]

Post by Paavo Helde
The cppreference site also gives an example which uses
std::piecewise_construct to emulate try_emplace, so it looks like it
is actually possible to use emplace for a real in-place construction,
albeit in a pretty convoluted way.

And this really works ? The key-value pair has still to be built
from the two forwarding tuples.

[Paavo Helde]

Post by Bonita Montero

Post by Paavo Helde
The cppreference site also gives an example which uses
std::piecewise_construct to emulate try_emplace, so it looks like it
is actually possible to use emplace for a real in-place construction,
albeit in a pretty convoluted way.

And this really works ? The key-value pair has still to be built
from the two forwarding tuples.

Seems so. To be honest I am not sure I fully understand what it does,
this is just a slightly modified example from the cppreference site:

#include <iostream>
#include <tuple>
#include <utility>
#include <map>
#include <string>

struct Foo
{
Foo() {
std::cout << "Constructed a Foo\n";
std::cout << "Constructing at address: " << this << "\n";
}

Foo(int, float) {
std::cout << "Constructed a Foo from an int and a float\n";
std::cout << "Constructing at address: " << this << "\n";
}

void Report() const {
std::cout << "Reporting from address : " << this << "\n";
}
};

int main() {
std::map<std::string, Foo> m;

m.emplace(std::piecewise_construct,
std::forward_as_tuple("foo"),
std::forward_as_tuple(10, 3.14f));

m["foo"].Report();
}

OUTPUT:

Constructed a Foo from an int and a float
Constructing at address: 00000216F1C43F48
Reporting from address : 00000216F1C43F48

[Bonita Montero]

Post by Paavo Helde

Post by Bonita Montero

Post by Paavo Helde
The cppreference site also gives an example which uses
std::piecewise_construct to emulate try_emplace, so it looks like it
is actually possible to use emplace for a real in-place construction,
albeit in a pretty convoluted way.

And this really works ? The key-value pair has still to be built
from the two forwarding tuples.

Seems so. To be honest I am not sure I fully understand what it does,
#include <iostream>
#include <tuple>
#include <utility>
#include <map>
#include <string>
struct Foo
{
    Foo() {
        std::cout << "Constructed a Foo\n";
        std::cout << "Constructing at address: " << this << "\n";
    }
    Foo(int, float) {
        std::cout << "Constructed a Foo from an int and a float\n";
        std::cout << "Constructing at address: " << this << "\n";
    }
    void Report() const {
        std::cout << "Reporting from address : " << this << "\n";
    }
};
int main() {
    std::map<std::string, Foo> m;
    m.emplace(std::piecewise_construct,
        std::forward_as_tuple("foo"),
        std::forward_as_tuple(10, 3.14f));

The issue would be that the string constructed from your "foo" would
be consumed if the insertion fails. You're not forwarding a string
object which is used otherwise if insertion fails.

Take this:

#include <iostream>
#include <map>

using namespace std;

int main()
{
map<string, string> map;
auto doIt = [&]( bool tryInsert, char const *what )
{
cout << what << endl;
string
key( "hello"sv ),
value( "world"sv );
if( !tryInsert )
map.emplace( piecewise_construct, forward_as_tuple( move( key ) ),
forward_as_tuple( move( value ) ) );
else
map.try_emplace( move( key ), move( value ) );
cout << "\tkey: " << key << endl;
cout << "\tvalue: " << key << endl;
};
doIt( false, "before:" );
doIt( false, "after insertion:" );
map.clear();
cout << endl;
doIt( true, "before / try:" );
doIt( true, "after insertion / try:" );
}

Post by Paavo Helde
    m["foo"].Report();
}
Constructed a Foo from an int and a float
Constructing at address: 00000216F1C43F48
Reporting from address : 00000216F1C43F48

[Paavo Helde]

Post by Bonita Montero

Post by Paavo Helde

Post by Bonita Montero

Post by Paavo Helde
The cppreference site also gives an example which uses
std::piecewise_construct to emulate try_emplace, so it looks like it
is actually possible to use emplace for a real in-place
construction, albeit in a pretty convoluted way.

And this really works ? The key-value pair has still to be built
from the two forwarding tuples.

Seems so. To be honest I am not sure I fully understand what it does,
#include <iostream>
#include <tuple>
#include <utility>
#include <map>
#include <string>
struct Foo
{
     Foo() {
         std::cout << "Constructed a Foo\n";
         std::cout << "Constructing at address: " << this << "\n";
     }
     Foo(int, float) {
         std::cout << "Constructed a Foo from an int and a float\n";
         std::cout << "Constructing at address: " << this << "\n";
     }
     void Report() const {
         std::cout << "Reporting from address : " << this << "\n";
     }
};
int main() {
     std::map<std::string, Foo> m;
     m.emplace(std::piecewise_construct,
         std::forward_as_tuple("foo"),
         std::forward_as_tuple(10, 3.14f));

The issue would be that the string constructed from your "foo" would
be consumed if the insertion fails. You're not forwarding a string
object which is used otherwise if insertion fails.
#include <iostream>
#include <map>
using namespace std;
int main()
{
    map<string, string> map;
    auto doIt = [&]( bool tryInsert, char const *what )
    {
        cout << what << endl;
        string
            key( "hello"sv ),
            value( "world"sv );
        if( !tryInsert )
            map.emplace( piecewise_construct, forward_as_tuple( move(
key ) ), forward_as_tuple( move( value ) ) );
        else
            map.try_emplace( move( key ), move( value ) );
        cout << "\tkey: " << key << endl;
        cout << "\tvalue: " << key << endl;

I see you are focusing on another aspect of try_emplace(). Indeed,
try_emplace() is documented to leave any rvalue reference parameters
unchanged if insertion does not happen, which seems to be not possible
with emplace().

However, I do not like that the code uses values after std::move() has
been called on them. Maybe define a synonym like move_if_needed()?

[Bonita Montero]

Post by Paavo Helde
I see you are focusing on another aspect of try_emplace(). Indeed,
try_emplace() is documented to leave any rvalue reference parameters
unchanged if insertion does not happen, which seems to be not possible
with emplace().

Therefore it isn't possible to emulate try_emplace with that as you
mentioned. I just wanted to demonstrate that with as less code as
possible.

[Chris M. Thomasson]

Post by Bonita Montero

Post by Paavo Helde
I see you are focusing on another aspect of try_emplace(). Indeed,
try_emplace() is documented to leave any rvalue reference parameters
unchanged if insertion does not happen, which seems to be not possible
with emplace().

Therefore it isn't possible to emulate try_emplace with that as you
mentioned. I just wanted to demonstrate that with as less code as
possible.

thanks.

[Bonita Montero]

Post by Chris M. Thomasson

Post by Bonita Montero

Post by Paavo Helde
I see you are focusing on another aspect of try_emplace(). Indeed,
try_emplace() is documented to leave any rvalue reference parameters
unchanged if insertion does not happen, which seems to be not
possible with emplace().

Therefore it isn't possible to emulate try_emplace with that as you
mentioned. I just wanted to demonstrate that with as less code as
possible.

thanks.

❤

[Bonita Montero]

Post by Marcel Mueller
The emplace functions generally allows to construct container objects
directly at the target location. But std::map expects a value type of
std::pair<const Key, T>. Now the implementation of emplace needs to
instantiate the value type just to get the key to find the insert
location. This cannot happen at the target location, isn't it?
I know, this has been solved in C++17 by try_emplace. I just wonder
what was the idea of this function.
Marcel

You can find() your key and if it doesn't exist you emplace() the
new node.

[Andrey Tarasevich]

Post by Bonita Montero
You can find() your key and if it doesn't exist you emplace() the
new node.

Which is completely unacceptable, since it will perform key search
twice. This is a huge problem, which the interface of all associative
containers is designed to avoid. If your code performs redundant
searches, you are using the container incorrectly.

[Bonita Montero]

Post by Bonita Montero
You can find() your key and if it doesn't exist you emplace() the
new node.

Which is completely unacceptable, ...

Depends on your constraints. Before C++17 there was no other solution
for that and you had to accept that.

[Andrey Tarasevich]

Post by Bonita Montero

Post by Bonita Montero
You can find() your key and if it doesn't exist you emplace() the
new node.

Which is completely unacceptable, ...

Depends on your constraints. Before C++17 there was no other solution
for that and you had to accept that.

It depends on what problem you are referring to. In C++98 you could
still work around both the "redundant search" problem and "unnecessary
construction of the pair" problem by performing insertions through
`std::map<>::operator[]`. Although in order to make it work efficiently
you'd also have to ensure that the `mapped_type` default construction is
lightweight and detectable

Map map; // `Map` is `std::map<whatever>`
...
Map::mapped_type &data = map[key];
if (`data` has just been constructed)
{
// Build the new element in `data`
}

This is inelegant in a sense that you have to make the `mapped_type`
default-constructible and also force the default-construction behavior
to obey the demands of the above pattern. But it worked.

[Stefan Große Pawig]

Post by Bonita Montero

Post by Bonita Montero
You can find() your key and if it doesn't exist you emplace() the
new node.

Which is completely unacceptable, ...

Depends on your constraints. Before C++17 there was no other solution
for that and you had to accept that.

What about using lower_bound() and emplace_hint() instead? That is
available since C++11.

And while C++98 does not have emplace_hint(), the insert() overload that
takes an iterator as first argument can be used.

Stefan

[Bonita Montero]

Post by Stefan Große Pawig

Post by Bonita Montero

Post by Bonita Montero
You can find() your key and if it doesn't exist you emplace() the
new node.

Which is completely unacceptable, ...

Depends on your constraints. Before C++17 there was no other solution
for that and you had to accept that.

What about using lower_bound() and emplace_hint() instead? That is
available since C++11.

lower_bound() needs a random-access iterator since it does a binary
search.

Post by Stefan Große Pawig
And while C++98 does not have emplace_hint(), the insert() overload that
takes an iterator as first argument can be used.
Stefan

[Andrey Tarasevich]

Post by Bonita Montero

Post by Stefan Große Pawig
What about using lower_bound() and emplace_hint() instead? That is
available since C++11.

lower_bound() needs a random-access iterator since it does a binary
search.

That's actually one of those curious spots in the standard library: it
doesn't needs a random-access iterator. It needs a forward iterator.

I presume I simply uses `std::distance` and `std::advance` to manipulate
the iterators, thus paying a pretty penny for "simulating" random-access
through forward iterators, but that's just the way it is.

[Bonita Montero]

Post by Andrey Tarasevich

Post by Bonita Montero

Post by Stefan Große Pawig
What about using lower_bound() and emplace_hint() instead? That is
available since C++11.

lower_bound() needs a random-access iterator since it does a binary
search.

That's actually one of those curious spots in the standard library: it
doesn't needs a random-access iterator. It needs a forward iterator.

Interesting, but the algorithm for MSVC is still binary partitioning.
Internally a sth. like find_first_if would make more sense. But I think
most developers would be intelligent enough to use find_first_if their-
selfes.

[Bonita Montero]

Post by Bonita Montero

Post by Andrey Tarasevich

Post by Bonita Montero

Post by Stefan Große Pawig
What about using lower_bound() and emplace_hint() instead? That is
available since C++11.

lower_bound() needs a random-access iterator since it does a binary
search.

That's actually one of those curious spots in the standard library: it
doesn't needs a random-access iterator. It needs a forward iterator.

Interesting, but the algorithm for MSVC is still binary partitioning.
Internally a sth. like find_first_if would make more sense. But I think
most developers would be intelligent enough to use find_first_if their-
selfes.

I checked the source and found that the MSVC-code simply uses distance()
and advance(), and both are specialized for non random-access iterators.

[Andrey Tarasevich]

Post by Bonita Montero

Post by Bonita Montero

Post by Bonita Montero

Post by Stefan Große Pawig
What about using lower_bound() and emplace_hint() instead? That is
available since C++11.

lower_bound() needs a random-access iterator since it does a binary
search.

it doesn't needs a random-access iterator. It needs a forward iterator.

Interesting, but the algorithm for MSVC is still binary partitioning.
Internally a sth. like find_first_if would make more sense. But I think
most developers would be intelligent enough to use find_first_if their-
selfes.

I checked the source and found that the MSVC-code simply uses distance()
and advance(), and both are specialized for non random-access iterators.

This approach, when random-access is emulated through sequential access
(seemingly unnecessarily), is present in other places of the library and
not only in MSVC's implementation

https://stackoverflow.com/questions/40622430/stdlistsort-why-the-sudden-switch-to-top-down-strategy

[Bonita Montero]

Post by Andrey Tarasevich
This approach, when random-access is emulated through sequential access
(seemingly unnecessarily), is present in other places of the library and
not only in MSVC's implementation ...

And I'm pretty sure they take the same way like MSVC.

[Stefan Große Pawig]

Post by Bonita Montero

Post by Stefan Große Pawig

Post by Bonita Montero

Post by Bonita Montero
You can find() your key and if it doesn't exist you emplace() the
new node.

Which is completely unacceptable, ...

Depends on your constraints. Before C++17 there was no other solution
for that and you had to accept that.

What about using lower_bound() and emplace_hint() instead? That is
available since C++11.

lower_bound() needs a random-access iterator since it does a binary
search.

I had std::map::lower_bound() in mind.

Stefan

[Sam]

Post by Marcel Mueller
The emplace functions generally allows to construct container objects
directly at the target location. But std::map expects a value type of
std::pair<const Key, T>. Now the implementation of emplace needs to
instantiate the value type just to get the key to find the insert
location. This cannot happen at the target location, isn't it?
I know, this has been solved in C++17 by try_emplace. I just wonder what
was the idea of this function.

With a converting constructor for either the key or the value one could
squeeze some lemon juice fairly easily out of std::map::emplace and avoid an
occasional copy. But to make more lemonade one will then have to write a
short, ugly novel using std::piecewise_construct, however that'll still
generate unwanted copies.

std::map::try_emplace was just an attempt to avoid some of that gobbledygook
and the copies, for the most common use cases. But, it should be possible to
do anything with emplace that can be done with try_emplace. It just requires
more sweat and tears, and maybe an extra copy. If the key and value
constructors' arguments are simple types you might get lucky and avoid the
extra copies from emplace().

[Stefan Große Pawig]

Post by Marcel Mueller
The emplace functions generally allows to construct container objects
directly at the target location. But std::map expects a value type of
std::pair<const Key, T>. Now the implementation of emplace needs to
instantiate the value type just to get the key to find the insert
location. This cannot happen at the target location, isn't it?
I know, this has been solved in C++17 by try_emplace. I just wonder what
was the idea of this function.

While the value type may be instantiated and immediately destroyed when
it turns out that an element with the same key already exists, emplace()
still allows you to insert values that are neither copyable nor moveable.

Stefan

[Andrey Tarasevich]

Post by Marcel Mueller
The emplace functions generally allows to construct container objects
directly at the target location. But std::map expects a value type of
std::pair<const Key, T>. Now the implementation of emplace needs to
instantiate the value type just to get the key to find the insert
location. This cannot happen at the target location, isn't it?

Yes, it sorta-kinda can happen "at target location", If I correctly
understand what you mean by "target location".

In mainstream implementations `emplace` does not really construct a some
local `value_type t` object. Instead, it immediately allocates and
constructs out of the supplied arguments a _node_ object. This node
object is what the `std::map` is literally built of and, of course, that
node object contains a `value_type` object inside.

If the key is not present in the map, the node object is immediately
_attached_ directly into to the map. Otherwise, it is destroyed and
deallocated. In other words, that node object is the "target location".

So, yes, there is an "optimistic" construction of a `value_type` object
(which might prove to be a waste), but there's no subsequent
copying/moving from that `value_type` object to the "target location".
The `value_type` object is created as part of the "target location" from
the very beginning.

This approach is what permits usage of `emplace` for insertion of
non-copyable/non-movable objects into the map through
`std::piecewise_construct` (which is likely what Stefan refers to in his
comment).

[Marcel Mueller]

Post by Andrey Tarasevich
In mainstream implementations `emplace` does not really construct a some
local `value_type t` object. Instead, it immediately allocates and
constructs out of the supplied arguments a _node_ object. This node
object is what the `std::map` is literally built of and, of course, that
node object contains a `value_type` object inside.

[...]> This approach is what permits usage of `emplace` for insertion of

Post by Andrey Tarasevich
non-copyable/non-movable objects into the map through
`std::piecewise_construct` (which is likely what Stefan refers to in his
comment).

Indeed. That is the point.


Marcel