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 }