I'm implementing my own vector based on post-2018 San Diego draft (N4791) and have some questions regarding implementing strong exception safety.
Here is some code:
template <typename T, typename Allocator>
void Vector<T, Allocator>::push_back(const T& value)
{
if (buffer_capacity == 0)
{
this->Allocate(this->GetSufficientCapacity(1));
}
if (buffer_size < buffer_capacity)
{
this->Construct(value);
return;
}
auto new_buffer = CreateNewBuffer(this->GetSufficientCapacity(
buffer_size + 1), allocator);
this->MoveAll(new_buffer);
try
{
new_buffer.Construct(value);
}
catch (...)
{
this->Rollback(new_buffer, std::end(new_buffer));
throw;
}
this->Commit(std::move(new_buffer));
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::Allocate(size_type new_capacity)
{
elements = std::allocator_traits<Allocator>::allocate(allocator,
new_capacity);
buffer_capacity = new_capacity;
}
template <typename T, typename Allocator> template <typename... Args>
void Vector<T, Allocator>::Construct(Args&&... args)
{
// TODO: std::to_address
std::allocator_traits<Allocator>::construct(allocator,
elements + buffer_size, std::forward<Args>(args)...);
++buffer_size;
}
template <typename T, typename Allocator>
Vector<T, Allocator> Vector<T, Allocator>::CreateNewBuffer(
size_type new_capacity, const Allocator& new_allocator)
{
Vector new_buffer{new_allocator};
new_buffer.Allocate(new_capacity);
return new_buffer;
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::Move(iterator first, iterator last, Vector& buffer)
{
if (std::is_nothrow_move_constructible_v<T> ||
!std::is_copy_constructible_v<T>)
{
std::move(first, last, std::back_inserter(buffer));
}
else
{
std::copy(first, last, std::back_inserter(buffer));
}
}
template <typename T, typename Allocator
void Vector<T, Allocator>::MoveAll(Vector& buffer)
{
Move(std::begin(*this), std::end(*this), buffer);
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::Rollback(Vector& other, iterator last) noexcept
{
if (!std::is_nothrow_move_constructible_v<T> &&
std::is_copy_constructible_v<T>)
{
return;
}
std::move(std::begin(other), last, std::begin(*this));
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::Commit(Vector&& other) noexcept
{
this->Deallocate();
elements = other.elements;
buffer_capacity = other.buffer_capacity;
buffer_size = other.buffer_size;
allocator = other.allocator;
other.elements = nullptr;
other.buffer_capacity = 0;
other.buffer_size = 0;
}
I see 2 problems with this code. I've tried to follow the std::move_if_noexcept logic, but what if the element is nothrow move constructible but allocator_traits::construct throws exception in, say, some logging code inside custom allocator? Then my MoveAll call will throw and produce only basic guarantee. Is this a defect in the standard? Should there be more strict wording on Allocator::construct?
And another one in Rollback. It really produces strong guarantee only if the moved elements are nothrow move assignable. Otherwise, again, only basic guarantee. Is this how it is supposed to be?
The range-based std::move/copy functions are not capable of providing a strong exception guarantee. In the event of an exception, you need an iterator to the last element that was successfully copied/moved, so that you can undo things properly. You have to do the copy/move manually (or write a specialized function to do so).
As for the particulars of your question, the standard does not really address what should happen if construct emits an exception which is not thrown from within the constructor of the object being construction. The intent of the standard (for reasons I will explain below) is probably that this circumstance should never happen. But I have yet to find any statement in the standard about this. So let's assume for a moment that this is intended to be possible.
In order for allocator-aware containers to be able to offer the strong-exception guarantee, construct at the very least must not throw after constructing the object. After all, you don't know what exception was thrown, so otherwise you would not be able to tell if the object was successfully constructed or not. That would make implementing the standard required behavior impossible. So let us assume that the user has not done something that makes implementation impossible.
Given this circumstance, you can write your code assuming that any exception emitted by construct means that the object was not constructed. If construct emits an exception despite being given arguments that would invoke a noexcept constructor, then you assume that the constructor was never called. And you write your code accordingly.
In the case of copying, you only need to delete any already-copied elements (in reverse order of course). The move case is a bit trickier, but still quite doable. You have to move-assign each successfully-moved object back into its original position.
The problem? vector<T>::*_back does not require that T be MoveAssignable. It only requires that T be MoveInsertable: that is, you can use an allocator to construct them in uninitialized memory. But you're not moving it into uninitialized memory; you need to move it to where a moved-from T already exists. So to preserve this requirement, you would need to destroy all of the Ts that were successfully moved-from and then MoveInsert them back into place.
But since MoveInsertion requires using construct, which as previously established might throw... oops. Indeed, this very thing is preciesely why vector's reallocation functions do not move unless the type is nothrow-moveable or is non-copyable (and if it's the latter case, you don't get the strong-exception guarantee).
So it seems pretty clear to me that any allocator's construct method is expected by the standard to only throw if the selected constructor throws. There's no other way to implement the required behavior in vector. But given that there is no explicit statement of this requirement, I would say that this is a defect in the standard. And it's not a new defect, since I looked through the C++17 standard rather than the working paper.
Apparently this has been the subject of an LWG issue since 2014, with solutions to it being... troublesome.