LEWG, SG14: P0040R1
2016-01-10
Brent Friedman
fourthgeek@gmail.com
When implementing containers that do not rely on standard allocators it is often necessary to manage memory directly. This paper seeks to fill gaps in the standard library’s memory management utilities.
The function template destroy calls the destructor for specified elements.
The function template uninitialized_move performs move construction of elements over a range of memory, similar to uninitialized_copy. uninitialized_move_n is also provided.
The function template uninitialized_value_construct performs value-construction of objects over a range of memory.
The function template uninitialized_default_construct performs default-construction of objects over a range of memory.
Proposed names were approved by LEWG in Kona.
Discussion is underway with Eric Niebler regarding how these algorithms should interact with range-v3.
destroy first appeared in SGI’s Standard Template Library. It is not known by the author why this algorithm was not inherited into the C++ Standard Library in its initial stages.
It is not possible to implement the “no effects” policy for destroy or uninitialized_move* so they are specifically excluded from that rule. uninitialized_move does need to destroy elements in the output range if an exception is thrown, but the source range cannot be restored to its original state.
Some concern is raised about exception handling with respect to uninitialized_move. If a move-constructor throws, moved-from objects may be left in a poorly defined state. Given that algorithm move has no special support for this case, it is believed that throwing constructors for this algorithm can be treated similarly.
An additional algorithm, uninitialized_move_if_noexcept, could be considered as a resolution to this concern. Such an algorithm was found already implemented in libstdc++. Given that there is currently no range-based move_if_noexcept algorithm, such a solution is not considered here. It is however trivial to implement such an algorithm – simply forwarding to copy or move as appropriate.
During implementation research, it was found that libstdc++ implements a variation of uninitialized_move by combining move_iterator with uninitialized_copy. This approach has some benefit for purposes of wording as it may alleviate needing to provide careful wording for the exception handling behavior of these algorithms. Both wordings are provided as alternatives. Given that the uninitialized_move algorithms can be reconstructed simply by combining these two features, the author is willing to drop uninitialized_move and uninitialized_move_n from this proposal if their motivation is found insufficient.
A design decision must be made regarding the order of destruction in destroy. Should bidirectional iterators destroy objects in reverse order? We argue no, for the following reasons:
It is conceivable that always destroying in forward order would be seen as suprising behavior to some. However, this is at least a consistent behavior which can be accounted for once understood.
The following section describes existing implementations of these algorithms prevalent among major C++ implementations. Empty cells denote where no function corresponding to this proposal was found.
Implementations denoted with $ rely on an additional allocator object to do construction/destruction
| P0040 | Dinkumware | libstdcxx | libcxx | EASTL | folly (Facebook) |
| uninitialized_move | $_Uninitialized_move | $__uninitialized_move_a | uninitialized_move | moveToUninitialized | |
| uninitialized_move_n | |||||
| uninitialized_value_construct | $ _Uninit_def_fill_n (n-variant) | __uninitialized_default | $ see vector::__construct_at_end | uses uninitialized_fill | see Barrier::allocateControlBlock |
| uninitialized_default_construct | |||||
| destroy | $_Destroy_range | _Destroy | $ see vector::__destruct_at_end | destruct | see ~small_vector |
libstdc++ implements uninitialized moves by combining move_iterator with uninitialized_copy. Most implementations use a separate algorithm instead.
The disparity between default and value initialization is to be expected given that standard library containers consistently prefer value initialization for contained elements.
EASTL's use of uninitialized_fill to implement uninitialized_value_construct is suboptimal in that it requires constructing an additional object, moving it, and destroying it. uninitialized_value_construct and uninitializeed_default_construct can be used with non-movable types and may avoid unnecessary operations.
Make the following changes in [specialized.algorithm]:
Modify: In the algorithms uninitialized_copy and uninitialized_move, the template parameter InputIterator is required…
Modify: In the following algorithms other than destroy, uninitialized_move, and uninitialized_move_n, if an exception is thrown there are no effects.
Add: In the algorithms uninitialized_move and uninitialized_move_n, if an exception is thrown then this function has no effects on the range beginning at result.
Add:
template<class ForwardIterator>
void destroy(ForwardIterator begin, ForwardIterator end);
Effects:
typedef typename iterator_traits<ForwardIterator>::value_type __t;
while (begin != end)
{
begin->~__t();
++begin;
}
template <class InputIterator, class ForwardIterator>
ForwardIterator uninitialized_move(InputIterator first, InputIterator last, ForwardIterator result);
Effects:
for (; first != last; ++result, ++first)
::new (static_cast<void*>(addressof(*result)))
typename iterator_traits<ForwardIterator>::value_type(std::move(*first));
return result;
template <class InputIterator, class ForwardIterator>
ForwardIterator uninitialized_move_n(InputIterator first, size_t count, ForwardIterator result);
Effects:
for ( ; count>0; ++result, ++first, --count)
::new (static_cast<void*>(addressof(*result)))
typename iterator_traits<ForwardIterator>::value_type(std::move(*first));
return result;
template<class ForwardIterator>
ForwardIterator uninitialized_value_construct(ForwardIterator first, ForwardIterator last);
Effects:
for (; first != last; ++first)
::new (static_cast<void*>(addressof(*first)))
typename iterator_traits<ForwardIterator>::value_type();
return first;
template<class ForwardIterator>
ForwardIterator uninitialized_default_construct(ForwardIterator first, ForwardIterator last);
Effects:
for (; first != last; ++first)
::new (static_cast<void*>(addressof(*first)))
typename iterator_traits<ForwardIterator>::value_type;
return first;
An alternative definition and wording for uninitialized_move is provided as a possible wording simplification. By using move_iterator, we no longer have to tiptoe around the wording for exception handling.
Omit the Add: section above which refers to exceptions in uninitialized_move and uninitialized_move_n
template <class InputIterator, class ForwardIterator>
ForwardIterator uninitialized_move(InputIterator first, InputIterator last, ForwardIterator result);
Effects:
return uninitialized_copy( make_move_iterator(first), make_move_iterator(last), result);
template <class InputIterator, class ForwardIterator>
ForwardIterator uninitialized_move_n(InputIterator first, size_t count, ForwardIterator result);
Effects:
return uninitialized_copy_n( make_move_iterator(first), count, result);