<deque> : A deque<T> where T is move-only, when nested in vector, does not compile

[AlexGuteniev]

Describe the bug
A deque<T> where T is move-only, when nested in vector, does not compile.

Command-line test case

d:\Temp2>type repro.cpp
#include <deque>
#include <vector>

struct A
{
        A(const A&) = delete;
};
void f()
{
        std::vector<std::deque<A> > q;
        q.resize(4);
}
int main()
{
        f();
        return 0;
}

d:\Temp2>cl /EHsc repro.cpp
Microsoft (R) C/C++ Optimizing Compiler Version 19.27.29009.1 for x86
Copyright (C) Microsoft Corporation.  All rights reserved.

repro.cpp
C:\Program Files (x86)\Microsoft Visual Studio\2019\Preview\VC\Tools\MSVC\14.27.29009\include\xmemory(694): error C2280: 'A::A(const A &)': attempting to reference a deleted function
repro.cpp(6): note: see declaration of 'A::A'
repro.cpp(6): note: 'A::A(const A &)': function was explicitly deleted
C:\Program Files (x86)\Microsoft Visual Studio\2019\Preview\VC\Tools\MSVC\14.27.29009\include\deque(821): note: see reference to function template instantiation 'void std::_Default_allocator_traits<_Alloc>::construct<_Ty,const A&>(_Alloc &,_Objty *const ,const A &)' being compiled
        with
        [
            _Alloc=std::allocator<A>,
            _Ty=A,
            _Objty=A
        ]
C:\Program Files (x86)\Microsoft Visual Studio\2019\Preview\VC\Tools\MSVC\14.27.29009\include\deque(820): note: see reference to function template instantiation 'void std::_Default_allocator_traits<_Alloc>::construct<_Ty,const A&>(_Alloc &,_Objty *const ,const A &)' being compiled
        with
        [
            _Alloc=std::allocator<A>,
            _Ty=A,
            _Objty=A
        ]
C:\Program Files (x86)\Microsoft Visual Studio\2019\Preview\VC\Tools\MSVC\14.27.29009\include\deque(662): note: see reference to function template instantiation 'void std::deque<A,std::allocator<A>>::emplace_back<const A&>(const A &)' being compiled
C:\Program Files (x86)\Microsoft Visual Studio\2019\Preview\VC\Tools\MSVC\14.27.29009\include\deque(630): note: see reference to function template instantiation 'void std::deque<A,std::allocator<A>>::_Construct<std::_Deque_unchecked_const_iterator<std::_Deque_val<std::_Deque_simple_types<_Ty>>>>(_Iter,_Iter)' being compiled
        with
        [
            _Ty=A,
            _Iter=std::_Deque_unchecked_const_iterator<std::_Deque_val<std::_Deque_simple_types<A>>>
        ]
C:\Program Files (x86)\Microsoft Visual Studio\2019\Preview\VC\Tools\MSVC\14.27.29009\include\deque(630): note: see reference to function template instantiation 'void std::deque<A,std::allocator<A>>::_Construct<std::_Deque_unchecked_const_iterator<std::_Deque_val<std::_Deque_simple_types<_Ty>>>>(_Iter,_Iter)' being compiled
        with
        [
            _Ty=A,
            _Iter=std::_Deque_unchecked_const_iterator<std::_Deque_val<std::_Deque_simple_types<A>>>
        ]
C:\Program Files (x86)\Microsoft Visual Studio\2019\Preview\VC\Tools\MSVC\14.27.29009\include\deque(626): note: while compiling class template member function 'std::deque<A,std::allocator<A>>::deque(const std::deque<A,std::allocator<A>> &)'
C:\Program Files (x86)\Microsoft Visual Studio\2019\Preview\VC\Tools\MSVC\14.27.29009\include\xmemory(694): note: see reference to function template instantiation 'std::deque<A,std::allocator<A>>::deque(const std::deque<A,std::allocator<A>> &)' being compiled
C:\Program Files (x86)\Microsoft Visual Studio\2019\Preview\VC\Tools\MSVC\14.27.29009\include\vector(1695): note: see reference to class template instantiation 'std::deque<A,std::allocator<A>>' being compiled
C:\Program Files (x86)\Microsoft Visual Studio\2019\Preview\VC\Tools\MSVC\14.27.29009\include\vector(1685): note: while compiling class template member function 'void std::vector<std::deque<A,std::allocator<A>>,std::allocator<std::deque<A,std::allocator<A>>>>::_Tidy(void) noexcept'
C:\Program Files (x86)\Microsoft Visual Studio\2019\Preview\VC\Tools\MSVC\14.27.29009\include\vector(673): note: see reference to function template instantiation 'void std::vector<std::deque<A,std::allocator<A>>,std::allocator<std::deque<A,std::allocator<A>>>>::_Tidy(void) noexcept' being compiled
repro.cpp(10): note: see reference to class template instantiation 'std::vector<std::deque<A,std::allocator<A>>,std::allocator<std::deque<A,std::allocator<A>>>>' being compiled

Expected behavior
Should compile

STL version

Microsoft Visual Studio Professional 2019 Preview
Version 16.7.0 Preview 3.1

Additional context
Other repro:

#include <iostream>
#include <deque>
#include <vector>

struct Data {
	explicit Data(int const time) : m_Time(time) { } 
	Data(Data&& rhs) : m_Time(rhs.m_Time) { }
	Data& operator=(Data&& rhs) { m_Time = rhs.m_Time; return *this; } 
	~Data() { }
	Data& operator=(Data const& rhs) = delete; 
	Data(Data const& rhs) = delete; 
	int m_Time; 
};


struct Map1 {
	typedef std::deque<Data> ValType; // OK with vector

	Map1() : m_Data() { } ValType& operator[](int const key)
	{
		auto it = m_Data.begin();
		if (m_Data.end() == it)                  // OK if commented out
		{                                        // OK if commented out 
			m_Data.emplace_back(key, ValType()); // OK if commented out 
			it = m_Data.end() - 1;               // OK if commented out 
		}                                        // OK if commented out
		return it->second;
	}
	std::vector<std::pair<int const, ValType> > m_Data;
};

int main()
{ 
	Map1 xxxxx; auto& ee = xxxxx[0];
	ee.emplace_back(1);
}

Yet another repro:

#include <vector>
#include <deque>
class Key {
public:
 Key() = default;
 template <typename U>
 Key(U&& u) {}
};
struct MoveOnly {
 MoveOnly() = default;
 MoveOnly(const MoveOnly &) = delete;
 MoveOnly &operator=(const MoveOnly &) = delete;
 MoveOnly(MoveOnly &&) = default;
 MoveOnly &operator=(MoveOnly &&other) = default;
 ~MoveOnly() = default;
};
using Value = std::vector<MoveOnly>;
struct Pair {
 Pair() = default;
 Pair(const Pair&) = default;
 Pair(Pair&&) = default;
 Pair &operator=(const Pair&) = delete;
 Pair &operator=(Pair &&other) { return *this; }
 ~Pair() = default;
 const Key first = Key();
 Value second = Value();
};
int main() {
 std::vector<Pair> data;
 data.emplace_back();
 return 0;
}

Also tracked as:

• DevCom-33006 and VSO-399383/ AB#399383 ("Problem with nested deque")
• DevCom-536767 and VSO-851210/ AB#851210 ("Compilation failure in complex move-only case")

[StephanTLavavej]

I believe this is the "constrained copy constructor" problem. Technically, our implementation is conformant, but the result is a terrible user experience; see my explanation on reddit for the tale of misery.

While the root cause is the Standard's inability to constrain container copy/moves, our implementation's longstanding choice to dynamically allocate sentinel nodes (and proxies) makes this a more common problem with our STL than libstdc++ or libc++. My thinking on this has evolved somewhat over the years; while we certainly can't do anything for v19 due to ABI, for vNext we should probably consider each container independently:

• unordered_meow really shouldn't be backed by a doubly-linked list; it is required to be forward but not bidi, so it doesn't need sentinel nodes. We should be able to arrange its representation (including the bucket "map") to avoid allocating memory.
• deque's representation is well-known to be problematic (see <deque>: Needs a major performance overhaul #147) and always needing a proxy object seems undesirable.
• The ordered map/set family is required to be bidi, but it seems unlikely that people need to maintain ranges that persist after swapping/moving.
• list is the container where I continue to think that dynamically allocated sentinel nodes are a better choice, because list is such a terrible container for performance but such an excellent container for iterator stability. For it to not provide stability for end iterators, which even vector inherently provides, seems to compromise its reason for existence. Avoiding the problem discussed here is a benefit, though (and one which was not previously known).

[AlexGuteniev]

What is the problem with sentinel nodes that is solved by making them heap allocated? Is this the validity of end() iterator?

What if sentinel node will only have pointers from it, but not to it, instead the pointers would be nullptr. This takes special handling on insertion/deletion, but not on iteration, so may be acceptable. actually, no it requires handling on iteration too

[AlexGuteniev]

How about this, have two incarnations of sentinel node:

• a static sentinel node with both forward and backward pointers set as nullptr. This is used for iteration, this is the value of end() iterator, head/tail nodes have pointers to it
• a member by value sentinel node that is only used as starting point. It does not have pointers to it, only from it.

This way:

• iteration is done without extra operations
• insertion/deletion should do one conditional pointer replacement, this is not terribly inefficient
• end() iterator is still valid for moved container, because all end() iterators are equal

[CaseyCarter]

How about this, have two incarnations of sentinel node:

• a static sentinel node with both forward and backward pointers set as nullptr. This is used for iteration, this is the value of end() iterator, head/tail nodes have pointers to it

How would we implement decrement for this end iterator? Recall that list is bidirectional.

[AlexGuteniev]

I see, apparently there's no good solution without heap-allocated sentinel node.

Then what is the problem with moving? Can't sentinel nodes of source and destination of move be just swapped?

[CaseyCarter]

Then what is the problem with moving? Can't sentinel nodes of source and destination of move be just swapped?

For move assignments, yes, but for move constructions the newly-constructed container doesn't have a node to swap until it allocates one. Allocation means that move constructor cannot be noexcept. So when you put such a container inside a vector, reallocation uses copies instead of moves since the container appears to be both copyable and movable (copy constructors can't be constrained because of the allocator completeness requirements) but the move constructor isn't noexcept.

[AlexGuteniev]

The newly allocated node in move constructor may go to either new container or to the old one. Can null pointer go to the old one instead of valid sentinel? Old container is going to be re-assigned or deleted anyway.

Or, more generally, can it be allocated lazily?

[StephanTLavavej]

Lazy allocation isn't viable - end() must be noexcept.

A moved-from container must be in a "valid but unspecified state", supporting all preconditionless member function calls. end() is a preconditionless member function, so it must be callable on moved-from containers, and you must be able to get an iterator to a sentinel node (whether container-internal or dynamically-allocated) which is later decrementable to the back() element if an element is push_backed.

During the final years of C++0x as it was finalized into C++11, as a junior implementer (who hadn't attended any Committee meetings), I partially understood the relevant issues and argued on the mailing lists that moved-from objects should be allowed to have an "emptier than empty" state, where only certain member functions would be permitted (obviously destruction; assignment destination would be desirable, possibly assignment source and swap, etc.). I was unable to persuade anyone, and it probably wasn't a great idea, but I tried.