emplace pair

[Christopher J. Pisz]

If I understand emplace correctly, rather than make an object and pass
it to emplace, I pass the arguments to the object's constructor and it
is "created in place", saving a copy construction.

This works handy for vector<T> myVector; by calling
myVector.emplace_back with T's constructor arguments.

However, when I use unordered_map<int, T> and call emplace, it seems I
need to pass the arguments to the pair, one of which is going to be T(),
so I am still making an extra copy of T...

Is there some way around that?

[Alf P. Steinbach]

When you control the wrapper's code (here that would be the pair class'
code) then you can use Boost in-place factories.

See <url:
http://www.boost.org/doc/libs/1_61_0/libs/optional/doc/html/boost_optional/tutorial/in_place_factories.html>.

I don't like that solution: it feels unclean, what with a `void*`
involved, and just in general. But it's a solution for a general class
of cases. Which does not include your case; just worth being aware of.

• • •

Otherwise you can use indirection.

David Wheeler: “All problems in computer science can be solved by
another level of indirection”.

Essentially that means using pointers as your value type, and dynamic
allocation.

Uh oh… “Dynamic allocation”?!? That's going to take one heck of a
performance hit, won't it?

Well no, not if it's done right for this particular case. Because your
container is clearly the /owner/ of those value objects. And that means
that ordinary slow-as-molasses inefficient raw C++ dynamic allocation
can be replaced with super-fast dedicated dynamic allocation.

It can be done in many different ways.

The idea that popped up from my association circuits as “the” way to do
that is to use a sequence `std::vector`s as storage, and a free-list to
manage individual items. When all allocated storage has been used,
create a new vector of double size as the last one. The doubling
strategy (which is similar to a vector's internal buffer management)
means that the number of raw dynamic allocations will only be O(log n)
in the number of items managed by the allocator.

Example, showing only the allocation idea, with debugging / clarifying
clog statements:


#include <utility> // std::move
#include <vector> // std::vector
#include <stack> // std::stack
#include <stddef.h> // ptrdiff_t
#include <type_traits> // std::(aligned_storage)

#include <iostream>
using std::clog;

namespace my {
using std::aligned_union_t;
using std::move;
using std::stack;
using std::vector;

using Size = ptrdiff_t;

struct Node
{
Node* next;
};

auto unlinked( Node*& p )
-> Node*
{
Node* result = p;
p = p->next;
return result;
}

// This class is just to be sure that no vector is ever /copied/,
because that
// could invalidate pointers and references to items in its buffer.
template< class Item >
struct Non_copyable_vector
{
vector<Item> v;

Non_copyable_vector() {}

Non_copyable_vector( Non_copyable_vector const& ) = delete;

Non_copyable_vector( Non_copyable_vector&& other )
: v( move( other.v ) ) // vector guarantees ptr validity
after move.
{} // (which is why it can't use fast
`realloc`)
};

namespace tag {
template< class Item >
struct Storage_ptr_ { Item* value; };

struct Do_nothing {};
};

template< class Item >
class Fixed_size_allocator
{
private:
using Item_storage_bytes = aligned_union_t< 0, Item, Node >;
static_assert( alignof( Item_storage_bytes ) >= alignof( Item
), "!" );
static_assert( alignof( Item_storage_bytes ) >= alignof( Node
), "!" );

struct Item_storage
{
Item_storage_bytes bytes;
Item_storage( tag::Do_nothing ) {} // Fast do-nothing
construction.
};
static_assert( alignof( Item_storage ) >= alignof(
Item_storage_bytes ), "!" );

using Storage = stack< Non_copyable_vector< Item_storage > >;

Storage storage_;
Node* first_free_ = nullptr;

public:
auto allocate()
-> tag::Storage_ptr_<Item> // Points to uninitialized
storage.
{
if( first_free_ )
{
clog << "| using first free\n";
return { reinterpret_cast<Item*>( unlinked( first_free_
) ) };
}

if( storage_.top().v.size() == storage_.top().v.capacity() )
{
Size const new_capacity = 2*storage_.top().v.size();
clog << "| adding new vector with capacity " <<
new_capacity << "\n";
storage_.push( {} );
storage_.top().v.reserve( new_capacity ); // Raw
allocation.
}

vector<Item_storage>& v = storage_.top().v;
v.emplace_back( tag::Do_nothing{} ); // Hopefully
this is fast.
clog << "| using vector item " << &v.back() << "\n";
return {reinterpret_cast<Item*>( &v.back() )};
}

Fixed_size_allocator()
{
storage_.push( {} );
storage_.top().v.reserve( 1 ); // Or some higher
initial capacity.
}
};
} // namespace my

template< class Item >
auto operator new( size_t const size, my::Fixed_size_allocator<Item>& a )
-> void*
{ return a.allocate().value; }

#include <iostream>
using namespace std;
auto main()
-> int
{
using namespace my;

Fixed_size_allocator<int> fsa;
vector<int*> v;
for( int i = 0; i < 10; ++i )
{
cout << i << endl;
v.push_back( new( fsa ) int{ i } );
}
for( int* const p : v )
{
cout << *p << " ";
}
cout << endl;
}


I suggest you just wrap your container (of key->pointer pairs) together
with a Fixed_size_allocater, in a suitable little wrapper class.

To destroy non-POD items you can call the destructor of the item, then
if necessary deallocate its storage (add it to the free list).


Cheers & hth., + maybe a little challence :),

- Alf

[Alf P. Steinbach]

On 14-Mar-17 3:46 PM, Alf P. Steinbach wrote:
> : v( move( other.v ) ) // vector guarantees ptr validity
> after move.
> {} // (which is why it can't use fast
> `realloc`)

The first is correct but the second, the “which is why”, was typed
automatically by my fingers, without consulting me!

The `realloc` problem is more subtle.


Cheers!,

- Alf

[Frank Tetzel]

There's C++17's try_emplace, if you have a very recent compiler.

It only constructs T and the pair if an insertion happens.

[Christopher Pisz]

Is there anything wrong with the use of std::piecewise_construct and std::forward_as_tuple?

#include <iostream>
#include <vector>
#include <unordered_map>

//----------------------------------------------------------------------------------------
class SomeClass
{
public:
SomeClass(int x, double y)
:
m_x(x)
, m_y(y)
{
std::cout << " Constructor " << std::endl;
}

SomeClass(const SomeClass & rhs)
:
m_x(rhs.m_x)
, m_y(rhs.m_y)
{
std::cout << " Copy Constructor " << std::endl;
}

SomeClass(SomeClass && rhs)
:
m_x(rhs.m_x)
, m_y(rhs.m_y)
{
std::cout << " Move Constructor " << std::endl;
}

private:

int m_x;
double m_y;
};

//----------------------------------------------------------------------------------------
int main(int argc, char ** argv)
{
std::vector<SomeClass> myVector;
// The arguments for SomeClass' constructor are used and no temporary is created
myVector.emplace_back(1, 2.0);

std::unordered_map<int, SomeClass> myMap;
// I see no way to get around creating the temporary SomeClass to pass as an argument
// myMap.emplace(1, 1, 2.0); // Gives error as it tries to pass 3 args to std::pair
myMap.emplace(1, SomeClass(1, 2.0));

myMap.emplace(std::piecewise_construct, std::forward_as_tuple(2), std::forward_as_tuple(4, 4.0));



return 0;
}

[Alf P. Steinbach]

On 15-Mar-17 8:41 PM, Christopher Pisz wrote:
> On Monday, March 13, 2017 at 11:00:53 PM UTC-5, Christopher J. Pisz
> wrote:
>> If I understand emplace correctly, rather than make an object and
>> pass it to emplace, I pass the arguments to the object's
>> constructor and it is "created in place", saving a copy
>> construction.
>>
>> This works handy for vector<T> myVector; by calling
>> myVector.emplace_back with T's constructor arguments.
>>
>> However, when I use unordered_map<int, T> and call emplace, it
>> seems I need to pass the arguments to the pair, one of which is
>> going to be T(), so I am still making an extra copy of T...
>>
>> Is there some way around that?
>
>
> Is there anything wrong with the use of std::piecewise_construct and
> std::forward_as_tuple?

No, it looks OK.

I never used it, it didn't even enter my mind that std::pair had such
support, or I would have suggested it rather than an elaborate (albeit
more generally applicable) workaround.


Cheers!, & thanks for that pointer,

- Alf

[Chris Vine]

On Wed, 15 Mar 2017 12:41:29 -0700 (PDT)
Christopher Pisz <christo...@gmail.com> wrote:
[snip]

> int main(int argc, char ** argv)
> {
> std::vector<SomeClass> myVector;
> // The arguments for SomeClass' constructor are used and no temporary is created myVector.emplace_back(1, 2.0);
>
> std::unordered_map<int, SomeClass> myMap;
> // I see no way to get around creating the temporary SomeClass to pass as an argument
> // myMap.emplace(1, 1, 2.0); // Gives error as it tries to pass 3 args

> // to std::pair myMap.emplace(1, SomeClass(1, 2.0));

>
> myMap.emplace(std::piecewise_construct,
> std::forward_as_tuple(2),
> std::forward_as_tuple(4, 4.0));
>
> return 0;
> }

Yes, this is the exact use case that the std::piecewise_construct
overload for the std::pair constructor was intended to serve in
C++11/14.

C++17 will apparently make this unintuitive (and probably nearly
unknown) overload unnecessary by providing a new std::map::try_emplace()
method. It would apparently allow your original proposal as follows:

myMap.try_emplace(1, 1, 2.0);

See §23.4.4.4/4 of N4640 for further information. If your compiler
supports it, try the -std=c++1z or -std=c++17 option.