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);
vector(T,Alloc)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:
version(CppRuntime_Microsoft)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 }
851