<deque>: std::deque::insert performance

[AlexGuteniev]

Describe the bug
The DevCom-216960 reporter suggested that inserting to the middle of deque can be accomplished by inserting a move'd new first/last element to begin/end, and then moveing elements further, and finally emplacing the destination element to move'd-out place.

It is faster than using rotate.
It is still O(N), but it is expected to execute faster.

Reporter's code uses std::move by default, but for string-like classes it uses swap.

Reporter's code sample

#define ZForward(T, v) static_cast<decltype(std::forward<T>(v))>(v)
#define ZMove(v) ((decltype(std::move(v))) (v))


template<typename T>
struct is_string_like
{
	enum { value = false };
};


template<class _Elem, class _Traits, class _Alloc>
struct is_string_like<std::basic_string<_Elem, _Traits, _Alloc>>
{
	enum { value = true };
};


template<typename Deque, typename... T>
auto deque_insert(Deque& d, typename Deque::iterator itr, T&&... args)
{
	auto begin = d.begin();
	typename Deque::size_type _Off = itr - begin;
	auto size = d.size();
	if (_Off < size / 2)
	{
		if (_Off == 0)
			d.emplace_front(ZForward(T, args)...);
		else
		{
			d.emplace_front(ZMove(*begin));
			begin = d.begin();
			typename Deque::iterator itrFrom = begin + 1;
			typename Deque::pointer pFrom = NULL, pWrite = &*itrFrom, pFinal = &begin[_Off];
			for (; pWrite != pFinal;)
			{
				pFrom = &*++itrFrom;
#if _HAS_CXX17
				if constexpr(sizeof(char[is_string_like<Deque::value_type>::value+1])==2)
					pWrite->swap(*pFrom);
				else
#endif
					*pWrite = ZMove(*pFrom);
				count_1++;
				pWrite = pFrom;
			}
			*pWrite = Deque::value_type{ ZForward(T, args)... };
		}
	}
	else
	{
		if (_Off == size)
			d.emplace_back(ZForward(T, args)...);
		else
		{
			d.emplace_back(ZMove(d.back()));
			begin = d.begin();
			typename Deque::iterator itrFrom = d.end() - 2;
			typename Deque::pointer pFrom = NULL, pWrite = &*itrFrom, pFinal = &begin[_Off];
			for (; pWrite != pFinal;)
			{
				pFrom = &*--itrFrom;
#if _HAS_CXX17
				if constexpr(sizeof(char[is_string_like<Deque::value_type>::value + 1]) == 2)
					pWrite->swap(*pFrom);
				else
#endif
					*pWrite = ZMove(*pFrom);
				count_1++;
				pWrite = pFrom;
			}
			*pWrite = Deque::value_type{ ZForward(T, args)... };
		}
	}
	//return (d.begin() + _Off);
}

Additional context
This item was originally reprted on Developer Community as DevCom-216960 and is also tracked by Microsoft-internal VSO-586319 / AB#586319.

[frederick-vs-ja]

The current implementation using rotate seems non-conforming - rotate relies on ADL-swap, but the standard doesn't require Cpp17Swappable/Cpp17ValueSwappable for single-element insert/emplace.