In-place construction in container

[helios]

I have a class D that implements various deserialization functions. Suppose there's a class T that implements a constructor that accepts a reference to a D. Now suppose there's a vector/set/list of Ts. Is there any way to populate the container without involving temporary copies of T?

[JLBorges]

Standard containers support construction in situ with emplace functions.
For instance: http://en.cppreference.com/w/cpp/container/vector/emplace_back

[helios]

Great, thanks.

[helios]

One more thing: Is the order of construction of key and value for std::map and std::unordered_map defined?

[JLBorges]

#include <map>
#include <string>
#include <utility>

int main()
{
    struct A { int i ; std::string str ; A( int i, const std::string& str ) : i(i), str(str) {} };

    std::map< std::pair< int, std::string>, A > map ;

    map.emplace( std::make_pair( 1, "abcd" ) /* key */ , A{ 3, "efghi" } /* mapped value */  ) ; // move key, move mapped value

    map.emplace( std::piecewise_construct, // tag: http://en.cppreference.com/w/cpp/utility/piecewise_construct_t
                 std::forward_as_tuple( 3, "jkl" ), // piecewise-construct key in situ
                 std::forward_as_tuple( 10, "mnopqrst" ) ) ; // piecewise-construct mapped value in situ
}

[helios]

Err... I don't see how that answers my question. I read that reference page already, it doesn't say anything about the order of construction of the key and value.

[JLBorges]

The value_type of a map is std::pair< const key_type, mapped_type > ;

std::pair<> is defined as:

namespace std 
{
    template <class T1, class T2> struct pair 
   {
       // ...
       T1 first;
       T2 second;
        // .... 
    };
    // ...
}

Non-static data members are initialised in the order they were declared in the class definition.

Note: it is important to understand that that the order of the mem-initializers in the member initializer list of a constructor is not relevant in determining the order of initialisation of non-static member objects.

std::pair<>::first is initialised before std::pair<>::second as per order of declaration; const key is initialised before the mapped value.

[helios]

Are you saying that std::map<T1, T2> behaves (ignoring performance) as though it contained an array of std::pair<T1, T2>? I wasn't aware of this.

Note: it is important to understand that that the order of the mem-initializers in the member initializer list of a constructor is not relevant in determining the order of initialisation of non-static member objects.

Of course. I don't think I implied otherwise.

[JLBorges]

> std::map<T1, T2> behaves (ignoring performance) as though it contained an array of std::pair<T1, T2>?

std::map<> is typically implemented as a red-black tree.
(with each node in the tree containing a key-value pair std::pair< const key_type, mapped_type >).

It is an ordered associative container; its iterators iterate over a sorted sequence of key-value pairs. Performance is the best that is possible for an ordered associative container - lookup, removal, and insertion operations have logarithmic complexity.

[MiiNiPaa]

Also you can look at map as std::set<std::pair<key, value>, comp> with comparator which ignores .second in contained elements.

[helios]

Yes, I'm aware of all of that, but I asked about the order of construction of the key and value in a map, and you replied with the order of construction of first and second in std::pair, which to my knowledge are not related.

Maybe the question wasn't asked clearly enough.
Given T1 and T2 that have the same properties as T in the OP, if I have an std::map<T1, T2> m and I call m.emplace(std::pair<D &, D &>(d, d)), is a library implementation allowed to call T1::T1(D &) and T2::T2(D &) in any order, or is the order defined?

[JLBorges]

> is a library implementation allowed to call T1::T1(D &) and T2::T2(D &) in any order, or is the order defined?

The order is defined by the rules of C++.
Non-static data members are initialised in the order they were declared in the class definition.

Repeat: the value_type of a map is std::pair< const key_type, mapped_type > ;
Repeat: emplace() constructs the value_type of the container in situ.
Repeat: When a std::pair<> is constructed, member first is constructed before member second

[MiiNiPaa]

For in-place initialization order is defined, as arguments are used to directly initialize pair elements inside node and member initialization order is defined.

For move emplacing, elements are used to initialize pair elements. Oorder of move/copy constructors call is defined, but order of temporary variables creation (if you are passing temporary variables) is unspecified as with any function argument evaluation.

[helios]

Repeat: emplace() constructs the value_type of the container in situ.

Ah, this was the bit of info that was missing. Don't put "repeat" when it's the first time you've said it.

Thanks to both.

[JLBorges]

> Don't put "repeat" when it's the first time you've said it.

Standard containers support construction in situ with emplace functions.
http://www.cplusplus.com/forum/general/172808/#msg858924

That was the first time.

Or were you under the delusion that a standard container holds a sequence of something other than its value_type?

[helios]

No, that wasn't the first time, since you made no mention of value_type.
Yes, I assumed value_type was merely what iterators returned, and that containers could hold their data in something else.

[LB]

helios wrote:

Yes, I assumed value_type was merely what iterators returned, and that containers could hold their data in something else.

How would that work when modifying by reference? C++ doesn't have proxy type support yet.

[helios]

That's why it's an assumption. I never needed to think about it until now.

[JLBorges]

typename my_allocator<T>::reference can be a proxy type.

The only container in the standard library which has a proxy reference is std::vector<bool>.
However, it does not meet the standard container or standard sequence container requirements.