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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 25.05.2024 18:57, Marcel Mueller wrote:

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Marcel Mueller writes:

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 28.05.2024 18:53, Bonita Montero wrote:

Am 25.05.2024 um 19:37 schrieb 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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 29.05.2024 12:47, Bonita Montero wrote:

Am 29.05.2024 um 10:11 schrieb Paavo Helde:

On 28.05.2024 18:53, Bonita Montero wrote:

Am 25.05.2024 um 19:37 schrieb 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));

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;

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()?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 05/25/24 10:41 AM, Bonita Montero wrote:

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.

--
Best regards,
Andrey

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 06/30/24 10:15 AM, Bonita Montero wrote:

Am 30.06.2024 um 18:47 schrieb Andrey Tarasevich:

On 05/25/24 10:41 AM, Bonita Montero wrote:

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.

--
Best regards,
Andrey

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Bonita Montero <Bonita.Montero@gmail.com> writes:

Am 30.06.2024 um 18:47 schrieb Andrey Tarasevich:

On 05/25/24 10:41 AM, Bonita Montero wrote:

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Marcel Mueller <news.5.maazl@spamgourmet.org> writes:

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 05/25/24 8:57 AM, Marcel Mueller wrote:

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

--
Best regards,
Andrey

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 06/30/24 2:49 PM, Bonita Montero wrote:

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.

--
Best regards,
Andrey

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Bonita Montero <Bonita.Montero@gmail.com> writes:

Am 30.06.2024 um 21:21 schrieb Stefan Große Pawig:

Bonita Montero <Bonita.Montero@gmail.com> writes:

Am 30.06.2024 um 18:47 schrieb Andrey Tarasevich:

On 05/25/24 10:41 AM, Bonita Montero wrote:

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Am 30.06.24 um 22:32 schrieb 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

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 07/07/24 4:17 AM, Bonita Montero wrote:

Am 01.07.2024 um 13:41 schrieb Bonita Montero:

Am 01.07.2024 um 03:29 schrieb Andrey Tarasevich:

On 06/30/24 2:49 PM, Bonita Montero wrote:

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.

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

--
Best regards,
Andrey

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)