1 /**
2  * D header file for interaction with C++ std::vector.
3  *
4  * Copyright: Copyright (c) 2018 D Language Foundation
5  * License: Distributed under the
6  *      $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost Software License 1.0).
7  *    (See accompanying file LICENSE)
8  * Authors:   Guillaume Chatelet
9  *            Manu Evans
10  * Source:    $(DRUNTIMESRC core/stdcpp/vector.d)
11  */
12 
13 module core.stdcpp.vector;
14 
15 ///////////////////////////////////////////////////////////////////////////////
16 // std::vector declaration.
17 //
18 // Current caveats :
19 // - missing noexcept
20 // - nothrow @trusted @nogc for most functions depend on knowledge
21 //   of T's construction/destruction/assignment semantics
22 ///////////////////////////////////////////////////////////////////////////////
23 
24 import core.stdcpp.allocator;
25 
26 enum DefaultConstruct { value }
27 
28 /// Constructor argument for default construction
29 enum Default = DefaultConstruct();
30 
31 extern(C++, "std"):
32 
33 alias vector(T) = vector!(T, allocator!T);
34 extern(C++, class) struct vector(T, Alloc)
35 {
36     import core.lifetime : forward, move, core_emplace = emplace;
37 
38     static assert(!is(T == bool), "vector!bool not supported!");
39 extern(D):
40 
41     ///
42     alias size_type = size_t;
43     ///
44     alias difference_type = ptrdiff_t;
45     ///
46     alias value_type = T;
47     ///
48     alias allocator_type = Alloc;
49     ///
50     alias pointer = T*;
51     ///
52     alias const_pointer = const(T)*;
53 
54     /// MSVC allocates on default initialisation in debug, which can't be modelled by D `struct`
55     @disable this();
56 
57     ///
58     alias length = size;
59     ///
60     alias opDollar = length;
61 
62     ///
63     size_t[2] opSlice(size_t dim : 0)(size_t start, size_t end) const pure nothrow @safe @nogc { return [start, end]; }
64 
65     ///
66     ref inout(T) opIndex(size_t index) inout pure nothrow @safe @nogc       { return as_array[index]; }
67     ///
68     inout(T)[] opIndex(size_t[2] slice) inout pure nothrow @safe @nogc      { return as_array[slice[0] .. slice[1]]; }
69     ///
70     inout(T)[] opIndex() inout pure nothrow @safe @nogc                     { return as_array(); }
71 
72     ///
73     ref vector opAssign(U)(auto ref vector!(U, Alloc) s)                    { opAssign(s.as_array); return this; }
74     ///
75     ref vector opAssign(T[] array)
76     {
77         clear();
78         reserve(array.length);
79         insert(0, array);
80         return this;
81     }
82 
83     ///
84     void opIndexAssign()(auto ref T val, size_t index)                      { as_array[index] = val; }
85     ///
86     void opIndexAssign()(auto ref T val, size_t[2] slice)                   { as_array[slice[0] .. slice[1]] = val; }
87     ///
88     void opIndexAssign(T[] val, size_t[2] slice)                            { as_array[slice[0] .. slice[1]] = val[]; }
89     ///
90     void opIndexAssign()(auto ref T val)                                    { as_array[] = val; }
91     ///
92     void opIndexAssign(T[] val)                                             { as_array[] = val[]; }
93 
94     ///
95     void opIndexOpAssign(string op)(auto ref T val, size_t index)           { mixin("as_array[index] " ~ op ~ "= val;"); }
96     ///
97     void opIndexOpAssign(string op)(auto ref T val, size_t[2] slice)        { mixin("as_array[slice[0] .. slice[1]] " ~ op ~ "= val;"); }
98     ///
99     void opIndexOpAssign(string op)(T[] val, size_t[2] slice)               { mixin("as_array[slice[0] .. slice[1]] " ~ op ~ "= val[];"); }
100     ///
101     void opIndexOpAssign(string op)(auto ref T val)                         { mixin("as_array[] " ~ op ~ "= val;"); }
102     ///
103     void opIndexOpAssign(string op)(T[] val)                                { mixin("as_array[] " ~ op ~ "= val[];"); }
104 
105     ///
106     ref inout(T) front() inout pure nothrow @safe @nogc                     { return as_array[0]; }
107     ///
108     ref inout(T) back() inout pure nothrow @safe @nogc                      { return as_array[$-1]; }
109 
110     ///
111     ref vector opOpAssign(string op : "~")(auto ref T item)                 { push_back(forward!item); return this; }
112     ///
113     ref vector opOpAssign(string op : "~")(T[] array)                       { insert(length, array); return this; }
114 
115     ///
116     void append(T[] array)                                                  { insert(length, array); }
117 
118     /// Performs elementwise equality check.
119     bool opEquals(this This, That)(auto ref That rhs)
120     if (is(immutable That == immutable vector))                             { return as_array == rhs.as_array; }
121 
122     /// Performs lexicographical comparison.
123     static if (is(typeof((ref T a, ref T b) => a < b)))
124     int opCmp(this This, That)(auto ref That rhs)
125     if (is(immutable That == immutable vector))                             { return __cmp(as_array, rhs.as_array); }
126 
127     /// Hash to allow `vector`s to be used as keys for built-in associative arrays.
128     /// **The result will generally not be the same as C++ `std::hash<std::vector<T>>`.**
129     size_t toHash() const                                                   { return .hashOf(as_array); }
130 
131     // Modifiers
132     ///
133     void push_back(U)(auto ref U element)
134     {
135         emplace_back(forward!element);
136     }
137 
138     version (CppRuntime_Microsoft)
139     {
140         //----------------------------------------------------------------------------------
141         // Microsoft runtime
142         //----------------------------------------------------------------------------------
143 
144         ///
145         this(DefaultConstruct) @nogc                                        { _Alloc_proxy(); }
146         ///
147         this()(size_t count)
148         {
149             _Alloc_proxy();
150             _Buy(count);
151             scope(failure) _Tidy();
152             _Get_data()._Mylast = _Udefault(_Get_data()._Myfirst, count);
153         }
154         ///
155         this()(size_t count, auto ref T val)
156         {
157             _Alloc_proxy();
158             _Buy(count);
159             scope(failure) _Tidy();
160             _Get_data()._Mylast = _Ufill(_Get_data()._Myfirst, count, val);
161         }
162         ///
163         this()(T[] array)
164         {
165             _Alloc_proxy();
166             _Buy(array.length);
167             scope(failure) _Tidy();
168             _Get_data()._Mylast = _Utransfer!false(array.ptr, array.ptr + array.length, _Get_data()._Myfirst);
169         }
170         ///
171         this(this)
172         {
173             _Alloc_proxy();
174             pointer _First = _Get_data()._Myfirst;
175             pointer _Last = _Get_data()._Mylast;
176             _Buy(_Last - _First);
177             scope(failure) _Tidy();
178             _Get_data()._Mylast = _Utransfer!false(_First, _Last, _Get_data()._Myfirst);
179         }
180 
181         ///
182         ~this()                                                             { _Tidy(); }
183 
184         ///
185         ref inout(Alloc) get_allocator() inout pure nothrow @safe @nogc     { return _Getal(); }
186 
187         ///
188         size_type max_size() const pure nothrow @safe @nogc                 { return ((size_t.max / T.sizeof) - 1) / 2; } // HACK: clone the windows version precisely?
189 
190         ///
191         size_type size() const pure nothrow @safe @nogc                     { return _Get_data()._Mylast - _Get_data()._Myfirst; }
192         ///
193         size_type capacity() const pure nothrow @safe @nogc                 { return _Get_data()._Myend - _Get_data()._Myfirst; }
194         ///
195         bool empty() const pure nothrow @safe @nogc                         { return _Get_data()._Myfirst == _Get_data()._Mylast; }
196         ///
197         inout(T)* data() inout pure nothrow @safe @nogc                     { return _Get_data()._Myfirst; }
198         ///
199         inout(T)[] as_array() inout pure nothrow @trusted @nogc             { return _Get_data()._Myfirst[0 .. size()]; }
200         ///
201         ref inout(T) at(size_type i) inout pure nothrow @trusted @nogc      { return _Get_data()._Myfirst[0 .. size()][i]; }
202 
203         ///
204         ref T emplace_back(Args...)(auto ref Args args)
205         {
206             if (_Has_unused_capacity())
207                 return _Emplace_back_with_unused_capacity(forward!args);
208             return *_Emplace_reallocate(_Get_data()._Mylast, forward!args);
209         }
210 
211         ///
212         void reserve(const size_type newCapacity)
213         {
214             if (newCapacity > capacity())
215             {
216 //                if (newCapacity > max_size())
217 //                    _Xlength();
218                 _Reallocate_exactly(newCapacity);
219             }
220         }
221 
222         ///
223         void shrink_to_fit()
224         {
225             if (_Has_unused_capacity())
226             {
227                 if (empty())
228                     _Tidy();
229                 else
230                     _Reallocate_exactly(size());
231             }
232         }
233 
234         ///
235         void pop_back()
236         {
237             static if (_ITERATOR_DEBUG_LEVEL == 2)
238             {
239                 assert(!empty(), "vector empty before pop");
240                 _Orphan_range(_Get_data()._Mylast - 1, _Get_data()._Mylast);
241             }
242             destroy!false(_Get_data()._Mylast[-1]);
243             --_Get_data()._Mylast;
244         }
245 
246         ///
247         void clear()
248         {
249             _Base._Orphan_all();
250             _Destroy(_Get_data()._Myfirst, _Get_data()._Mylast);
251             _Get_data()._Mylast = _Get_data()._Myfirst;
252         }
253 
254         ///
255         void resize()(const size_type newsize)
256         {
257             static assert(is(typeof({static T i;})), T.stringof ~ ".this() is annotated with @disable.");
258             _Resize(newsize, (pointer _Dest, size_type _Count) => _Udefault(_Dest, _Count));
259         }
260 
261         ///
262         void resize()(const size_type newsize, auto ref T val)
263         {
264             _Resize(newsize, (pointer _Dest, size_type _Count) => _Ufill(_Dest, _Count, forward!val));
265         }
266 
267         void emplace(Args...)(size_t offset, auto ref Args args)
268         {
269             pointer _Whereptr = _Get_data()._Myfirst + offset;
270             pointer _Oldlast = _Get_data()._Mylast;
271             if (_Has_unused_capacity())
272             {
273                 if (_Whereptr == _Oldlast)
274                     _Emplace_back_with_unused_capacity(forward!args);
275                 else
276                 {
277                     T _Obj = T(forward!args);
278                     static if (_ITERATOR_DEBUG_LEVEL == 2)
279                         _Orphan_range(_Whereptr, _Oldlast);
280                     move(_Oldlast[-1], *_Oldlast);
281                     ++_Get_data()._Mylast;
282                     _Move_backward_unchecked(_Whereptr, _Oldlast - 1, _Oldlast);
283                     move(_Obj, *_Whereptr);
284                 }
285                 return;
286             }
287             _Emplace_reallocate(_Whereptr, forward!args);
288         }
289 
290         ///
291         void insert(size_t offset, T[] array)
292         {
293             pointer _Where = _Get_data()._Myfirst + offset;
294             pointer _First = array.ptr;
295             pointer _Last = _First + array.length;
296 
297             const size_type _Count = array.length;
298             const size_type _Whereoff = offset;
299             const bool _One_at_back = _Count == 1 && _Get_data()._Myfirst + _Whereoff == _Get_data()._Mylast;
300 
301             if (_Count == 0)
302             {
303                 // nothing to do, avoid invalidating iterators
304             }
305             else if (_Count > _Unused_capacity())
306             {   // reallocate
307                 const size_type _Oldsize = size();
308 
309 //                if (_Count > max_size() - _Oldsize)
310 //                    _Xlength();
311 
312                 const size_type _Newsize = _Oldsize + _Count;
313                 const size_type _Newcapacity = _Calculate_growth(_Newsize);
314 
315                 pointer _Newvec = _Getal().allocate(_Newcapacity);
316                 pointer _Constructed_last = _Newvec + _Whereoff + _Count;
317                 pointer _Constructed_first = _Constructed_last;
318 
319                 try
320                 {
321                     _Utransfer!false(_First, _Last, _Newvec + _Whereoff);
322                     _Constructed_first = _Newvec + _Whereoff;
323 
324                     if (_One_at_back)
325                     {
326                         _Utransfer!(true, true)(_Get_data()._Myfirst, _Get_data()._Mylast, _Newvec);
327                     }
328                     else
329                     {
330                         _Utransfer!true(_Get_data()._Myfirst, _Where, _Newvec);
331                         _Constructed_first = _Newvec;
332                         _Utransfer!true(_Where, _Get_data()._Mylast, _Newvec + _Whereoff + _Count);
333                     }
334                 }
335                 catch (Throwable e)
336                 {
337                     _Destroy(_Constructed_first, _Constructed_last);
338                     _Getal().deallocate(_Newvec, _Newcapacity);
339                     throw e;
340                 }
341 
342                 _Change_array(_Newvec, _Newsize, _Newcapacity);
343             }
344             else
345             {   // Attempt to provide the strong guarantee for EmplaceConstructible failure.
346                 // If we encounter copy/move construction/assignment failure, provide the basic guarantee.
347                 // (For one-at-back, this provides the strong guarantee.)
348 
349                 pointer _Oldlast = _Get_data()._Mylast;
350                 const size_type _Affected_elements = cast(size_type)(_Oldlast - _Where);
351 
352                 if (_Count < _Affected_elements)
353                 {    // some affected elements must be assigned
354                     _Get_data()._Mylast = _Utransfer!true(_Oldlast - _Count, _Oldlast, _Oldlast);
355                     _Move_backward_unchecked(_Where, _Oldlast - _Count, _Oldlast);
356                     _Destroy(_Where, _Where + _Count);
357 
358                     try
359                     {
360                         _Utransfer!false(_First, _Last, _Where);
361                     }
362                     catch (Throwable e)
363                     {
364                         // glue the broken pieces back together
365                         try
366                         {
367                             _Utransfer!true(_Where + _Count, _Where + 2 * _Count, _Where);
368                         }
369                         catch (Throwable e)
370                         {
371                             // vaporize the detached piece
372                             static if (_ITERATOR_DEBUG_LEVEL == 2)
373                                 _Orphan_range(_Where, _Oldlast);
374                             _Destroy(_Where + _Count, _Get_data()._Mylast);
375                             _Get_data()._Mylast = _Where;
376                             throw e;
377                         }
378 
379                         _Move_unchecked(_Where + 2 * _Count, _Get_data()._Mylast, _Where + _Count);
380                         _Destroy(_Oldlast, _Get_data()._Mylast);
381                         _Get_data()._Mylast = _Oldlast;
382                         throw e;
383                     }
384                 }
385                 else
386                 {   // affected elements don't overlap before/after
387                     pointer _Relocated = _Where + _Count;
388                     _Get_data()._Mylast = _Utransfer!true(_Where, _Oldlast, _Relocated);
389                     _Destroy(_Where, _Oldlast);
390 
391                     try
392                     {
393                         _Utransfer!false(_First, _Last, _Where);
394                     }
395                     catch (Throwable e)
396                     {
397                         // glue the broken pieces back together
398                         try
399                         {
400                             _Utransfer!true(_Relocated, _Get_data()._Mylast, _Where);
401                         }
402                         catch (Throwable e)
403                         {
404                             // vaporize the detached piece
405                             static if (_ITERATOR_DEBUG_LEVEL == 2)
406                                 _Orphan_range(_Where, _Oldlast);
407                             _Destroy(_Relocated, _Get_data()._Mylast);
408                             _Get_data()._Mylast = _Where;
409                             throw e;
410                         }
411 
412                         _Destroy(_Relocated, _Get_data()._Mylast);
413                         _Get_data()._Mylast = _Oldlast;
414                         throw e;
415                     }
416                 }
417                 static if (_ITERATOR_DEBUG_LEVEL == 2)
418                     _Orphan_range(_Where, _Oldlast);
419             }
420         }
421 
422     private:
423         import core.stdcpp.xutility : MSVCLinkDirectives;
424 
425         // Make sure the object files wont link against mismatching objects
426         mixin MSVCLinkDirectives!true;
427 
428         pragma(inline, true)
429         {
430             ref inout(_Base.Alloc) _Getal() inout pure nothrow @safe @nogc       { return _Base._Mypair._Myval1; }
431             ref inout(_Base.ValTy) _Get_data() inout pure nothrow @safe @nogc    { return _Base._Mypair._Myval2; }
432         }
433 
434         void _Alloc_proxy() @nogc
435         {
436             static if (_ITERATOR_DEBUG_LEVEL > 0)
437                 _Base._Alloc_proxy();
438         }
439 
440         void _AssignAllocator(ref const(allocator_type) al) nothrow @nogc
441         {
442             static if (_Base._Mypair._HasFirst)
443                 _Getal() = al;
444         }
445 
446         bool _Buy(size_type _Newcapacity) @trusted @nogc
447         {
448             _Get_data()._Myfirst = null;
449             _Get_data()._Mylast = null;
450             _Get_data()._Myend = null;
451 
452             if (_Newcapacity == 0)
453                 return false;
454 
455             // TODO: how to handle this in D? kinda like a range exception...
456 //            if (_Newcapacity > max_size())
457 //                _Xlength();
458 
459             _Get_data()._Myfirst = _Getal().allocate(_Newcapacity);
460             _Get_data()._Mylast = _Get_data()._Myfirst;
461             _Get_data()._Myend = _Get_data()._Myfirst + _Newcapacity;
462 
463             return true;
464         }
465 
466         static void _Destroy(pointer _First, pointer _Last)
467         {
468             for (; _First != _Last; ++_First)
469                 destroy!false(*_First);
470         }
471 
472         void _Tidy()
473         {
474             _Base._Orphan_all();
475             if (_Get_data()._Myfirst)
476             {
477                 _Destroy(_Get_data()._Myfirst, _Get_data()._Mylast);
478                 _Getal().deallocate(_Get_data()._Myfirst, capacity());
479                 _Get_data()._Myfirst = null;
480                 _Get_data()._Mylast = null;
481                 _Get_data()._Myend = null;
482             }
483         }
484 
485         size_type _Unused_capacity() const pure nothrow @safe @nogc
486         {
487             return _Get_data()._Myend - _Get_data()._Mylast;
488         }
489 
490         bool _Has_unused_capacity() const pure nothrow @safe @nogc
491         {
492             return _Get_data()._Myend != _Get_data()._Mylast;
493         }
494 
495         ref T _Emplace_back_with_unused_capacity(Args...)(auto ref Args args)
496         {
497             core_emplace(_Get_data()._Mylast, forward!args);
498             static if (_ITERATOR_DEBUG_LEVEL == 2)
499                 _Orphan_range(_Get_data()._Mylast, _Get_data()._Mylast);
500             return *_Get_data()._Mylast++;
501         }
502 
503         pointer _Emplace_reallocate(_Valty...)(pointer _Whereptr, auto ref _Valty _Val)
504         {
505             const size_type _Whereoff = _Whereptr - _Get_data()._Myfirst;
506             const size_type _Oldsize = size();
507 
508             // TODO: what should we do in D? kinda like a range overflow?
509 //            if (_Oldsize == max_size())
510 //                _Xlength();
511 
512             const size_type _Newsize = _Oldsize + 1;
513             const size_type _Newcapacity = _Calculate_growth(_Newsize);
514 
515             pointer _Newvec = _Getal().allocate(_Newcapacity);
516             pointer _Constructed_last = _Newvec + _Whereoff + 1;
517             pointer _Constructed_first = _Constructed_last;
518 
519             try
520             {
521                 core_emplace(_Newvec + _Whereoff, forward!_Val);
522                 _Constructed_first = _Newvec + _Whereoff;
523                 if (_Whereptr == _Get_data()._Mylast)
524                     _Utransfer!(true, true)(_Get_data()._Myfirst, _Get_data()._Mylast, _Newvec);
525                 else
526                 {
527                     _Utransfer!true(_Get_data()._Myfirst, _Whereptr, _Newvec);
528                     _Constructed_first = _Newvec;
529                     _Utransfer!true(_Whereptr, _Get_data()._Mylast, _Newvec + _Whereoff + 1);
530                 }
531             }
532             catch (Throwable e)
533             {
534                 _Destroy(_Constructed_first, _Constructed_last);
535                 _Getal().deallocate(_Newvec, _Newcapacity);
536                 throw e;
537             }
538 
539             _Change_array(_Newvec, _Newsize, _Newcapacity);
540             return _Get_data()._Myfirst + _Whereoff;
541         }
542 
543         void _Resize(_Lambda)(const size_type _Newsize, _Lambda _Udefault_or_fill)
544         {
545             const size_type _Oldsize = size();
546             const size_type _Oldcapacity = capacity();
547 
548             if (_Newsize > _Oldcapacity)
549             {
550 //                if (_Newsize > max_size())
551 //                    _Xlength();
552 
553                 const size_type _Newcapacity = _Calculate_growth(_Newsize);
554 
555                 pointer _Newvec = _Getal().allocate(_Newcapacity);
556                 pointer _Appended_first = _Newvec + _Oldsize;
557                 pointer _Appended_last = _Appended_first;
558 
559                 try
560                 {
561                     _Appended_last = _Udefault_or_fill(_Appended_first, _Newsize - _Oldsize);
562                     _Utransfer!(true, true)(_Get_data()._Myfirst, _Get_data()._Mylast, _Newvec);
563                 }
564                 catch (Throwable e)
565                 {
566                     _Destroy(_Appended_first, _Appended_last);
567                     _Getal().deallocate(_Newvec, _Newcapacity);
568                     throw e;
569                 }
570                 _Change_array(_Newvec, _Newsize, _Newcapacity);
571             }
572             else if (_Newsize > _Oldsize)
573             {
574                 pointer _Oldlast = _Get_data()._Mylast;
575                 _Get_data()._Mylast = _Udefault_or_fill(_Oldlast, _Newsize - _Oldsize);
576                 static if (_ITERATOR_DEBUG_LEVEL == 2)
577                     _Orphan_range(_Oldlast, _Oldlast);
578             }
579             else if (_Newsize == _Oldsize)
580             {
581                 // nothing to do, avoid invalidating iterators
582             }
583             else
584             {
585                 pointer _Newlast = _Get_data()._Myfirst + _Newsize;
586                 static if (_ITERATOR_DEBUG_LEVEL == 2)
587                     _Orphan_range(_Newlast, _Get_data()._Mylast);
588                 _Destroy(_Newlast, _Get_data()._Mylast);
589                 _Get_data()._Mylast = _Newlast;
590             }
591         }
592 
593         void _Reallocate_exactly(const size_type _Newcapacity)
594         {
595             import core.lifetime : moveEmplace;
596 
597             const size_type _Size = size();
598             pointer _Newvec = _Getal().allocate(_Newcapacity);
599 
600             try
601             {
602                 for (size_t i = _Size; i > 0; )
603                 {
604                     --i;
605                     moveEmplace(_Get_data()._Myfirst[i], _Newvec[i]);
606                 }
607             }
608             catch (Throwable e)
609             {
610                 _Getal().deallocate(_Newvec, _Newcapacity);
611                 throw e;
612             }
613 
614             _Change_array(_Newvec, _Size, _Newcapacity);
615         }
616 
617         void _Change_array(pointer _Newvec, const size_type _Newsize, const size_type _Newcapacity)
618         {
619             _Base._Orphan_all();
620 
621             if (_Get_data()._Myfirst != null)
622             {
623                 _Destroy(_Get_data()._Myfirst, _Get_data()._Mylast);
624                 _Getal().deallocate(_Get_data()._Myfirst, capacity());
625             }
626 
627             _Get_data()._Myfirst = _Newvec;
628             _Get_data()._Mylast = _Newvec + _Newsize;
629             _Get_data()._Myend = _Newvec + _Newcapacity;
630         }
631 
632         size_type _Calculate_growth(const size_type _Newsize) const pure nothrow @nogc @safe
633         {
634             const size_type _Oldcapacity = capacity();
635             if (_Oldcapacity > max_size() - _Oldcapacity/2)
636                 return _Newsize;
637             const size_type _Geometric = _Oldcapacity + _Oldcapacity/2;
638             if (_Geometric < _Newsize)
639                 return _Newsize;
640             return _Geometric;
641         }
642 
643         struct _Uninitialized_backout
644         {
645             this() @disable;
646             this(pointer _Dest)
647             {
648                 _First = _Dest;
649                 _Last = _Dest;
650             }
651             ~this()
652             {
653                 _Destroy(_First, _Last);
654             }
655             void _Emplace_back(Args...)(auto ref Args args)
656             {
657                 core_emplace(_Last, forward!args);
658                 ++_Last;
659             }
660             pointer _Release()
661             {
662                 _First = _Last;
663                 return _Last;
664             }
665         private:
666             pointer _First;
667             pointer _Last;
668         }
669         pointer _Utransfer(bool _move, bool _ifNothrow = false)(pointer _First, pointer _Last, pointer _Dest)
670         {
671             // TODO: if copy/move are trivial, then we can memcpy/memmove
672             auto _Backout = _Uninitialized_backout(_Dest);
673             for (; _First != _Last; ++_First)
674             {
675                 static if (_move && (!_ifNothrow || true)) // isNothrow!T (move in D is always nothrow! ...until opPostMove)
676                     _Backout._Emplace_back(move(*_First));
677                 else
678                     _Backout._Emplace_back(*_First);
679             }
680             return _Backout._Release();
681         }
682         pointer _Ufill()(pointer _Dest, size_t _Count, auto ref T val)
683         {
684             // TODO: if T.sizeof == 1 and no elaborate constructor, fast-path to memset
685             // TODO: if copy ctor/postblit are nothrow, just range assign
686             auto _Backout = _Uninitialized_backout(_Dest);
687             for (; 0 < _Count; --_Count)
688                 _Backout._Emplace_back(val);
689             return _Backout._Release();
690         }
691         pointer _Udefault()(pointer _Dest, size_t _Count)
692         {
693             // TODO: if zero init, then fast-path to zeromem
694             auto _Backout = _Uninitialized_backout(_Dest);
695             for (; 0 < _Count; --_Count)
696                 _Backout._Emplace_back();
697             return _Backout._Release();
698         }
699         pointer _Move_unchecked(pointer _First, pointer _Last, pointer _Dest)
700         {
701             // TODO: can `memmove` if conditions are right...
702             for (; _First != _Last; ++_Dest, ++_First)
703                 move(*_First, *_Dest);
704             return _Dest;
705         }
706         pointer _Move_backward_unchecked(pointer _First, pointer _Last, pointer _Dest)
707         {
708             while (_First != _Last)
709                 move(*--_Last, *--_Dest);
710             return _Dest;
711         }
712 
713         static if (_ITERATOR_DEBUG_LEVEL == 2)
714         {
715             void _Orphan_range(pointer _First, pointer _Last) const @nogc
716             {
717                 import core.stdcpp.xutility : _Lockit, _LOCK_DEBUG;
718 
719                 alias const_iterator = _Base.const_iterator;
720                 auto _Lock = _Lockit(_LOCK_DEBUG);
721 
722                 const_iterator** _Pnext = cast(const_iterator**)_Get_data()._Base._Getpfirst();
723                 if (!_Pnext)
724                     return;
725 
726                 while (*_Pnext)
727                 {
728                     if ((*_Pnext)._Ptr < _First || _Last < (*_Pnext)._Ptr)
729                     {
730                         _Pnext = cast(const_iterator**)(*_Pnext)._Base._Getpnext();
731                     }
732                     else
733                     {
734                         (*_Pnext)._Base._Clrcont();
735                         *_Pnext = *cast(const_iterator**)(*_Pnext)._Base._Getpnext();
736                     }
737                 }
738             }
739         }
740 
741         _Vector_alloc!(_Vec_base_types!(T, Alloc)) _Base;
742     }
743     else version (None)
744     {
745         size_type size() const pure nothrow @safe @nogc                     { return 0; }
746         size_type capacity() const pure nothrow @safe @nogc                 { return 0; }
747         bool empty() const pure nothrow @safe @nogc                         { return true; }
748 
749         inout(T)* data() inout pure nothrow @safe @nogc                     { return null; }
750         inout(T)[] as_array() inout pure nothrow @trusted @nogc             { return null; }
751         ref inout(T) at(size_type i) inout pure nothrow @trusted @nogc      { data()[0]; }
752     }
753     else
754     {
755         static assert(false, "C++ runtime not supported");
756     }
757 }
758 
759 
760 // platform detail
761 private:
762 version (CppRuntime_Microsoft)
763 {
764     import core.stdcpp.xutility : _ITERATOR_DEBUG_LEVEL;
765 
766     extern (C++, struct) struct _Vec_base_types(_Ty, _Alloc0)
767     {
768         alias Ty = _Ty;
769         alias Alloc = _Alloc0;
770     }
771 
772     extern (C++, class) struct _Vector_alloc(_Alloc_types)
773     {
774         import core.stdcpp.xutility : _Compressed_pair;
775     extern(D):
776     @nogc:
777 
778         alias Ty = _Alloc_types.Ty;
779         alias Alloc = _Alloc_types.Alloc;
780         alias ValTy = _Vector_val!Ty;
781 
782         void _Orphan_all() nothrow @safe
783         {
784             static if (is(typeof(ValTy._Base)))
785                 _Mypair._Myval2._Base._Orphan_all();
786         }
787 
788         static if (_ITERATOR_DEBUG_LEVEL != 0)
789         {
790             import core.stdcpp.xutility : _Container_proxy;
791 
792             alias const_iterator = _Vector_const_iterator!(ValTy);
793 
794             ~this()
795             {
796                 _Free_proxy();
797             }
798 
799             void _Alloc_proxy() @trusted
800             {
801                 import core.lifetime : emplace;
802 
803                 alias _Alproxy = Alloc.rebind!_Container_proxy;
804                 _Alproxy _Proxy_allocator = _Alproxy(_Mypair._Myval1);
805                 _Mypair._Myval2._Base._Myproxy = _Proxy_allocator.allocate(1);
806                 emplace(_Mypair._Myval2._Base._Myproxy);
807                 _Mypair._Myval2._Base._Myproxy._Mycont = &_Mypair._Myval2._Base;
808             }
809             void _Free_proxy()
810             {
811                 alias _Alproxy = Alloc.rebind!_Container_proxy;
812                 _Alproxy _Proxy_allocator = _Alproxy(_Mypair._Myval1);
813                 _Orphan_all();
814                 destroy!false(_Mypair._Myval2._Base._Myproxy);
815                 _Proxy_allocator.deallocate(_Mypair._Myval2._Base._Myproxy, 1);
816                 _Mypair._Myval2._Base._Myproxy = null;
817             }
818         }
819 
820         _Compressed_pair!(Alloc, ValTy) _Mypair;
821     }
822 
823     extern (C++, class) struct _Vector_val(T)
824     {
825         import core.stdcpp.xutility : _Container_base;
826         import core.stdcpp.type_traits : is_empty;
827 
828         alias pointer = T*;
829 
830         static if (!is_empty!_Container_base.value)
831             _Container_base _Base;
832 
833         pointer _Myfirst;   // pointer to beginning of array
834         pointer _Mylast;    // pointer to current end of sequence
835         pointer _Myend;     // pointer to end of array
836     }
837 
838     static if (_ITERATOR_DEBUG_LEVEL > 0)
839     {
840         extern (C++, class) struct _Vector_const_iterator(_Myvec)
841         {
842             import core.stdcpp.xutility : _Iterator_base;
843             import core.stdcpp.type_traits : is_empty;
844 
845             static if (!is_empty!_Iterator_base.value)
846                 _Iterator_base _Base;
847             _Myvec.pointer _Ptr;
848         }
849     }
850 }