2 * This module provides an `Array` type with deterministic memory usage not
3 * reliant on the GC, as an alternative to the built-in arrays.
5 * This module is a submodule of $(MREF std, container).
7 * Source: $(PHOBOSSRC std/container/array.d)
9 * Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
11 * License: Distributed under the Boost Software License, Version 1.0.
12 * (See accompanying file LICENSE_1_0.txt or copy at $(HTTP
13 * boost.org/LICENSE_1_0.txt)).
15 * Authors: $(HTTP erdani.com, Andrei Alexandrescu)
17 * $(SCRIPT inhibitQuickIndex = 1;)
19 module std.container.array;
21 import core.exception : RangeError;
22 import std.range.primitives;
25 public import std.container.util;
30 auto arr = Array!int(0, 2, 3);
32 assert(arr.front == 0);
33 assert(arr.back == 3);
37 assert(arr.length == 3);
38 assert(arr.capacity >= 1000);
41 arr.insertBefore(arr[1..$], 1);
42 assert(arr.front == 0);
43 assert(arr.length == 4);
46 assert(arr.back == 4);
47 assert(arr.length == 5);
57 import std.algorithm.comparison : equal;
58 auto arr = Array!int(1, 2, 3);
61 auto b = Array!int(11, 12, 13);
63 assert(arr.length == 6);
66 assert(arr[1 .. 3].equal([2, 3]));
69 arr.linearRemove(arr[1 .. 3]);
70 assert(arr[0 .. 2].equal([1, 11]));
73 /// `Array!bool` packs together values efficiently by allocating one bit per element
76 auto arr = Array!bool([true, true, false, true, false]);
77 assert(arr.length == 5);
80 private struct RangeT(A)
82 /* Workaround for https://issues.dlang.org/show_bug.cgi?id=13629
83 See also: http://forum.dlang.org/post/vbmwhzvawhnkoxrhbnyb@forum.dlang.org
86 private @property ref inout(A) _outer() inout { return _outer_[0]; }
88 private size_t _a, _b;
90 /* E is different from T when A is more restrictively qualified than T:
91 immutable(Array!int) => T == int, E = immutable(int) */
92 alias E = typeof(_outer_[0]._data._payload[0]);
94 private this(ref A data, size_t a, size_t b)
101 @property RangeT save()
106 @property bool empty() @safe pure nothrow const
111 @property size_t length() @safe pure nothrow const
115 alias opDollar = length;
117 @property ref inout(E) front() inout
119 assert(!empty, "Attempting to access the front of an empty Array");
122 @property ref inout(E) back() inout
124 assert(!empty, "Attempting to access the back of an empty Array");
125 return _outer[_b - 1];
128 void popFront() @safe @nogc pure nothrow
130 assert(!empty, "Attempting to popFront an empty Array");
134 void popBack() @safe @nogc pure nothrow
136 assert(!empty, "Attempting to popBack an empty Array");
140 static if (isMutable!A)
142 import std.algorithm.mutation : move;
146 assert(!empty, "Attempting to moveFront an empty Array");
147 assert(_a < _outer.length,
148 "Attempting to moveFront using an out of bounds low index on an Array");
149 return move(_outer._data._payload[_a]);
154 assert(!empty, "Attempting to moveBack an empty Array");
155 assert(_b - 1 < _outer.length,
156 "Attempting to moveBack using an out of bounds high index on an Array");
157 return move(_outer._data._payload[_b - 1]);
163 "Attempting to moveAt using an out of bounds index on an Array");
164 assert(_a + i < _outer.length,
165 "Cannot move past the end of the array");
166 return move(_outer._data._payload[_a + i]);
170 ref inout(E) opIndex(size_t i) inout
173 "Attempting to fetch using an out of bounds index on an Array");
174 return _outer[_a + i];
179 return typeof(return)(_outer, _a, _b);
182 RangeT opSlice(size_t i, size_t j)
184 assert(i <= j && _a + j <= _b,
185 "Attempting to slice using an out of bounds indices on an Array");
186 return typeof(return)(_outer, _a + i, _a + j);
189 RangeT!(const(A)) opSlice() const
191 return typeof(return)(_outer, _a, _b);
194 RangeT!(const(A)) opSlice(size_t i, size_t j) const
196 assert(i <= j && _a + j <= _b,
197 "Attempting to slice using an out of bounds indices on an Array");
198 return typeof(return)(_outer, _a + i, _a + j);
201 static if (isMutable!A)
203 void opSliceAssign(E value)
205 assert(_b <= _outer.length,
206 "Attempting to assign using an out of bounds indices on an Array");
207 _outer[_a .. _b] = value;
210 void opSliceAssign(E value, size_t i, size_t j)
213 "Attempting to slice assign using an out of bounds indices on an Array");
214 _outer[_a + i .. _a + j] = value;
217 void opSliceUnary(string op)()
218 if (op == "++" || op == "--")
220 assert(_b <= _outer.length,
221 "Attempting to slice using an out of bounds indices on an Array");
222 mixin(op~"_outer[_a .. _b];");
225 void opSliceUnary(string op)(size_t i, size_t j)
226 if (op == "++" || op == "--")
229 "Attempting to slice using an out of bounds indices on an Array");
230 mixin(op~"_outer[_a + i .. _a + j];");
233 void opSliceOpAssign(string op)(E value)
235 assert(_b <= _outer.length,
236 "Attempting to slice using an out of bounds indices on an Array");
237 mixin("_outer[_a .. _b] "~op~"= value;");
240 void opSliceOpAssign(string op)(E value, size_t i, size_t j)
243 "Attempting to slice using an out of bounds indices on an Array");
244 mixin("_outer[_a + i .. _a + j] "~op~"= value;");
250 * _Array type with deterministic control of memory. The memory allocated
251 * for the array is reclaimed as soon as possible; there is no reliance
252 * on the garbage collector. `Array` uses `malloc`, `realloc` and `free`
253 * for managing its own memory.
255 * This means that pointers to elements of an `Array` will become
256 * dangling as soon as the element is removed from the `Array`. On the other hand
257 * the memory allocated by an `Array` will be scanned by the GC and
258 * GC managed objects referenced from an `Array` will be kept alive.
262 * When using `Array` with range-based functions like those in `std.algorithm`,
263 * `Array` must be sliced to get a range (for example, use `array[].map!`
264 * instead of `array.map!`). The container itself is not a range.
267 if (!is(immutable T == immutable bool))
269 import core.memory : free = pureFree;
270 import std.internal.memory : enforceMalloc, enforceRealloc;
271 import core.stdc.string : memcpy, memmove, memset;
273 import core.memory : GC;
275 import std.exception : enforce;
276 import std.typecons : RefCounted, RefCountedAutoInitialize;
278 // This structure is not copyable.
279 private struct Payload
284 this(T[] p) { _capacity = p.length; _payload = p; }
286 // Destructor releases array memory
289 // Warning: destroy would destroy also class instances.
290 // The hasElaborateDestructor protects us here.
291 static if (hasElaborateDestructor!T)
292 foreach (ref e; _payload)
295 static if (hasIndirections!T)
296 GC.removeRange(_payload.ptr);
303 void opAssign(Payload rhs) @disable;
305 @property size_t length() const
307 return _payload.length;
310 @property void length(size_t newLength)
312 import std.algorithm.mutation : initializeAll;
314 if (length >= newLength)
317 static if (hasElaborateDestructor!T)
318 foreach (ref e; _payload.ptr[newLength .. _payload.length])
321 _payload = _payload.ptr[0 .. newLength];
324 immutable startEmplace = length;
326 initializeAll(_payload.ptr[startEmplace .. newLength]);
327 _payload = _payload.ptr[0 .. newLength];
330 @property size_t capacity() const
335 void reserve(size_t elements)
337 if (elements <= capacity) return;
338 static if (T.sizeof == 1)
344 import core.checkedint : mulu;
346 const sz = mulu(elements, T.sizeof, overflow);
348 assert(false, "Overflow");
350 static if (hasIndirections!T)
352 /* Because of the transactional nature of this
353 * relative to the garbage collector, ensure no
354 * threading bugs by using malloc/copy/free rather
357 immutable oldLength = length;
359 auto newPayloadPtr = cast(T*) enforceMalloc(sz);
360 auto newPayload = newPayloadPtr[0 .. oldLength];
362 // copy old data over to new array
363 memcpy(newPayload.ptr, _payload.ptr, T.sizeof * oldLength);
364 // Zero out unused capacity to prevent gc from seeing false pointers
365 memset(newPayload.ptr + oldLength,
367 (elements - oldLength) * T.sizeof);
368 GC.addRange(newPayload.ptr, sz);
369 GC.removeRange(_payload.ptr);
371 _payload = newPayload;
375 // These can't have pointers, so no need to zero unused region
376 auto newPayloadPtr = cast(T*) enforceRealloc(_payload.ptr, sz);
377 auto newPayload = newPayloadPtr[0 .. length];
378 _payload = newPayload;
380 _capacity = elements;
384 size_t insertBack(Elem)(Elem elem)
385 if (isImplicitlyConvertible!(Elem, T))
387 import core.lifetime : emplace;
388 assert(_capacity >= length);
389 if (_capacity == length)
391 import core.checkedint : addu;
394 immutable size_t newCapacity = addu(capacity, capacity / 2 + 1, overflow);
396 assert(false, "Overflow");
398 reserve(newCapacity);
400 assert(capacity > length && _payload.ptr,
401 "Failed to reserve memory");
402 emplace(_payload.ptr + _payload.length, elem);
403 _payload = _payload.ptr[0 .. _payload.length + 1];
407 // Insert a range of items
408 size_t insertBack(Range)(Range r)
409 if (isInputRange!Range && isImplicitlyConvertible!(ElementType!Range, T))
411 immutable size_t oldLength = length;
413 static if (hasLength!Range)
415 immutable size_t rLength = r.length;
416 reserve(oldLength + rLength);
426 static if (hasLength!Range)
427 assert(result == rLength, "insertBack: range might have changed length");
429 assert(length == oldLength + result,
430 "Failed to insertBack range");
435 private alias Data = RefCounted!(Payload, RefCountedAutoInitialize.no);
439 * Constructor taking a number of items.
441 this(U)(U[] values...)
442 if (isImplicitlyConvertible!(U, T))
444 import core.lifetime : emplace;
446 static if (T.sizeof == 1)
448 const nbytes = values.length;
452 import core.checkedint : mulu;
454 const nbytes = mulu(values.length, T.sizeof, overflow);
456 assert(false, "Overflow");
458 auto p = cast(T*) enforceMalloc(nbytes);
459 // Before it is added to the gc, initialize the newly allocated memory
460 foreach (i, e; values)
464 static if (hasIndirections!T)
467 GC.addRange(p, T.sizeof * values.length);
469 _data = Data(p[0 .. values.length]);
473 * Constructor taking an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
476 if (isInputRange!Range && isImplicitlyConvertible!(ElementType!Range, T) && !is(Range == T[]))
482 * Comparison for equality.
484 bool opEquals(const Array rhs) const
486 return opEquals(rhs);
490 bool opEquals(ref const Array rhs) const
492 if (empty) return rhs.empty;
493 if (rhs.empty) return false;
494 return _data._payload == rhs._data._payload;
498 * Defines the array's primary range, which is a random-access range.
500 * `ConstRange` is a variant with `const` elements.
501 * `ImmutableRange` is a variant with `immutable` elements.
503 alias Range = RangeT!Array;
506 alias ConstRange = RangeT!(const Array);
509 alias ImmutableRange = RangeT!(immutable Array);
512 * Duplicates the array. The elements themselves are not transitively
515 * Complexity: $(BIGOH length).
517 @property Array dup()
519 if (!_data.refCountedStore.isInitialized) return this;
520 return Array(_data._payload);
524 * Returns: `true` if and only if the array has no elements.
526 * Complexity: $(BIGOH 1)
528 @property bool empty() const
530 return !_data.refCountedStore.isInitialized || _data._payload.empty;
534 * Returns: The number of elements in the array.
536 * Complexity: $(BIGOH 1).
538 @property size_t length() const
540 return _data.refCountedStore.isInitialized ? _data._payload.length : 0;
544 size_t opDollar() const
550 * Returns: The maximum number of elements the array can store without
551 * reallocating memory and invalidating iterators upon insertion.
553 * Complexity: $(BIGOH 1)
555 @property size_t capacity()
557 return _data.refCountedStore.isInitialized ? _data._capacity : 0;
561 * Returns: the internal representation of the array.
563 * Complexity: $(BIGOH 1).
568 return _data._payload;
572 * Ensures sufficient capacity to accommodate `e` _elements.
573 * If `e < capacity`, this method does nothing.
575 * Postcondition: `capacity >= e`
577 * Note: If the capacity is increased, one should assume that all
578 * iterators to the elements are invalidated.
580 * Complexity: at most $(BIGOH length) if `e > capacity`, otherwise $(BIGOH 1).
582 void reserve(size_t elements)
584 if (!_data.refCountedStore.isInitialized)
586 if (!elements) return;
587 static if (T.sizeof == 1)
593 import core.checkedint : mulu;
595 const sz = mulu(elements, T.sizeof, overflow);
597 assert(false, "Overflow");
599 auto p = enforceMalloc(sz);
600 static if (hasIndirections!T)
602 // Zero out unused capacity to prevent gc from seeing false pointers
606 _data = Data(cast(T[]) p[0 .. 0]);
607 _data._capacity = elements;
611 _data.reserve(elements);
616 * Returns: A range that iterates over elements of the array in
619 * Complexity: $(BIGOH 1)
623 return typeof(return)(this, 0, length);
626 ConstRange opSlice() const
628 return typeof(return)(this, 0, length);
631 ImmutableRange opSlice() immutable
633 return typeof(return)(this, 0, length);
637 * Returns: A range that iterates over elements of the array from
638 * index `i` up to (excluding) index `j`.
640 * Precondition: `i <= j && j <= length`
642 * Complexity: $(BIGOH 1)
644 Range opSlice(size_t i, size_t j)
646 assert(i <= j && j <= length, "Invalid slice bounds");
647 return typeof(return)(this, i, j);
650 ConstRange opSlice(size_t i, size_t j) const
652 assert(i <= j && j <= length, "Invalid slice bounds");
653 return typeof(return)(this, i, j);
656 ImmutableRange opSlice(size_t i, size_t j) immutable
658 assert(i <= j && j <= length, "Invalid slice bounds");
659 return typeof(return)(this, i, j);
663 * Returns: The first element of the array.
665 * Precondition: `empty == false`
667 * Complexity: $(BIGOH 1)
669 @property ref inout(T) front() inout
671 assert(_data.refCountedStore.isInitialized,
672 "Cannot get front of empty range");
673 return _data._payload[0];
677 * Returns: The last element of the array.
679 * Precondition: `empty == false`
681 * Complexity: $(BIGOH 1)
683 @property ref inout(T) back() inout
685 assert(_data.refCountedStore.isInitialized,
686 "Cannot get back of empty range");
687 return _data._payload[$ - 1];
691 * Returns: The element or a reference to the element at the specified index.
693 * Precondition: `i < length`
695 * Complexity: $(BIGOH 1)
697 ref inout(T) opIndex(size_t i) inout
699 assert(_data.refCountedStore.isInitialized,
700 "Cannot index empty range");
701 return _data._payload[i];
705 * Slicing operators executing the specified operation on the entire slice.
707 * Precondition: `i < j && j < length`
709 * Complexity: $(BIGOH slice.length)
711 void opSliceAssign(T value)
713 if (!_data.refCountedStore.isInitialized) return;
714 _data._payload[] = value;
718 void opSliceAssign(T value, size_t i, size_t j)
720 auto slice = _data.refCountedStore.isInitialized ?
723 slice[i .. j] = value;
727 void opSliceUnary(string op)()
728 if (op == "++" || op == "--")
730 if (!_data.refCountedStore.isInitialized) return;
731 mixin(op~"_data._payload[];");
735 void opSliceUnary(string op)(size_t i, size_t j)
736 if (op == "++" || op == "--")
738 auto slice = _data.refCountedStore.isInitialized ? _data._payload : T[].init;
739 mixin(op~"slice[i .. j];");
743 void opSliceOpAssign(string op)(T value)
745 if (!_data.refCountedStore.isInitialized) return;
746 mixin("_data._payload[] "~op~"= value;");
750 void opSliceOpAssign(string op)(T value, size_t i, size_t j)
752 auto slice = _data.refCountedStore.isInitialized ? _data._payload : T[].init;
753 mixin("slice[i .. j] "~op~"= value;");
756 private enum hasSliceWithLength(T) = is(typeof({ T t = T.init; t[].length; }));
759 * Returns: A new array which is a concatenation of `this` and its argument.
762 * $(BIGOH length + m), where `m` is the number of elements in `stuff`.
764 Array opBinary(string op, Stuff)(Stuff stuff)
769 static if (hasLength!Stuff || isNarrowString!Stuff)
770 result.reserve(length + stuff.length);
771 else static if (hasSliceWithLength!Stuff)
772 result.reserve(length + stuff[].length);
773 else static if (isImplicitlyConvertible!(Stuff, T))
774 result.reserve(length + 1);
776 result.insertBack(this[]);
782 * Forwards to `insertBack`.
784 void opOpAssign(string op, Stuff)(auto ref Stuff stuff)
787 static if (is(typeof(stuff[])) && isImplicitlyConvertible!(typeof(stuff[0]), T))
798 * Removes all the elements from the array and releases allocated memory.
800 * Postcondition: `empty == true && capacity == 0`
802 * Complexity: $(BIGOH length)
810 * Sets the number of elements in the array to `newLength`. If `newLength`
811 * is greater than `length`, the new elements are added to the end of the
812 * array and initialized with `T.init`.
815 * Guaranteed $(BIGOH abs(length - newLength)) if `capacity >= newLength`.
816 * If `capacity < newLength` the worst case is $(BIGOH newLength).
818 * Postcondition: `length == newLength`
820 @property void length(size_t newLength)
822 _data.refCountedStore.ensureInitialized();
823 _data.length = newLength;
827 * Removes the last element from the array and returns it.
828 * Both stable and non-stable versions behave the same and guarantee
829 * that ranges iterating over the array are never invalidated.
831 * Precondition: `empty == false`
833 * Returns: The element removed.
835 * Complexity: $(BIGOH 1).
837 * Throws: `Exception` if the array is empty.
847 alias stableRemoveAny = removeAny;
850 * Inserts the specified elements at the back of the array. `stuff` can be
851 * a value convertible to `T` or a range of objects convertible to `T`.
853 * Returns: The number of elements inserted.
856 * $(BIGOH length + m) if reallocation takes place, otherwise $(BIGOH m),
857 * where `m` is the number of elements in `stuff`.
859 size_t insertBack(Stuff)(Stuff stuff)
860 if (isImplicitlyConvertible!(Stuff, T) ||
861 isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
863 _data.refCountedStore.ensureInitialized();
864 return _data.insertBack(stuff);
868 alias insert = insertBack;
871 * Removes the value from the back of the array. Both stable and non-stable
872 * versions behave the same and guarantee that ranges iterating over the
873 * array are never invalidated.
875 * Precondition: `empty == false`
877 * Complexity: $(BIGOH 1).
879 * Throws: `Exception` if the array is empty.
884 static if (hasElaborateDestructor!T)
885 .destroy(_data._payload[$ - 1]);
887 _data._payload = _data._payload[0 .. $ - 1];
891 alias stableRemoveBack = removeBack;
894 * Removes `howMany` values from the back of the array.
895 * Unlike the unparameterized versions above, these functions
896 * do not throw if they could not remove `howMany` elements. Instead,
897 * if `howMany > n`, all elements are removed. The returned value is
898 * the effective number of elements removed. Both stable and non-stable
899 * versions behave the same and guarantee that ranges iterating over
900 * the array are never invalidated.
902 * Returns: The number of elements removed.
904 * Complexity: $(BIGOH howMany).
906 size_t removeBack(size_t howMany)
908 if (howMany > length) howMany = length;
909 static if (hasElaborateDestructor!T)
910 foreach (ref e; _data._payload[$ - howMany .. $])
913 _data._payload = _data._payload[0 .. $ - howMany];
918 alias stableRemoveBack = removeBack;
921 * Inserts `stuff` before, after, or instead range `r`, which must
922 * be a valid range previously extracted from this array. `stuff`
923 * can be a value convertible to `T` or a range of objects convertible
924 * to `T`. Both stable and non-stable version behave the same and
925 * guarantee that ranges iterating over the array are never invalidated.
927 * Returns: The number of values inserted.
929 * Complexity: $(BIGOH length + m), where `m` is the length of `stuff`.
931 * Throws: `Exception` if `r` is not a range extracted from this array.
933 size_t insertBefore(Stuff)(Range r, Stuff stuff)
934 if (isImplicitlyConvertible!(Stuff, T))
936 import core.lifetime : emplace;
937 enforce(r._outer._data is _data && r._a <= length);
939 assert(_data.refCountedStore.isInitialized,
940 "Failed to allocate capacity to insertBefore");
941 // Move elements over by one slot
942 memmove(_data._payload.ptr + r._a + 1,
943 _data._payload.ptr + r._a,
944 T.sizeof * (length - r._a));
945 emplace(_data._payload.ptr + r._a, stuff);
946 _data._payload = _data._payload.ptr[0 .. _data._payload.length + 1];
951 size_t insertBefore(Stuff)(Range r, Stuff stuff)
952 if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
954 import core.lifetime : emplace;
955 enforce(r._outer._data is _data && r._a <= length);
956 static if (isForwardRange!Stuff)
958 // Can find the length in advance
959 auto extra = walkLength(stuff);
960 if (!extra) return 0;
961 reserve(length + extra);
962 assert(_data.refCountedStore.isInitialized,
963 "Failed to allocate capacity to insertBefore");
964 // Move elements over by extra slots
965 memmove(_data._payload.ptr + r._a + extra,
966 _data._payload.ptr + r._a,
967 T.sizeof * (length - r._a));
968 foreach (p; _data._payload.ptr + r._a ..
969 _data._payload.ptr + r._a + extra)
971 emplace(p, stuff.front);
975 _data._payload.ptr[0 .. _data._payload.length + extra];
980 import std.algorithm.mutation : bringToFront;
982 immutable offset = r._a;
983 enforce(offset <= length);
984 auto result = insertBack(stuff);
985 bringToFront(this[offset .. length - result],
986 this[length - result .. length]);
992 alias stableInsertBefore = insertBefore;
995 size_t insertAfter(Stuff)(Range r, Stuff stuff)
996 if (isImplicitlyConvertible!(Stuff, T) ||
997 isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
999 import std.algorithm.mutation : bringToFront;
1000 enforce(r._outer._data is _data);
1002 immutable offset = r._b;
1003 enforce(offset <= length);
1004 auto result = insertBack(stuff);
1005 bringToFront(this[offset .. length - result],
1006 this[length - result .. length]);
1011 size_t replace(Stuff)(Range r, Stuff stuff)
1012 if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
1014 enforce(r._outer._data is _data);
1016 for (; !stuff.empty; stuff.popFront())
1021 return result + insertBefore(r, stuff);
1023 r.front = stuff.front;
1027 // Remove remaining stuff in r
1033 size_t replace(Stuff)(Range r, Stuff stuff)
1034 if (isImplicitlyConvertible!(Stuff, T))
1036 enforce(r._outer._data is _data);
1039 insertBefore(r, stuff);
1051 * Removes all elements belonging to `r`, which must be a range
1052 * obtained originally from this array.
1054 * Returns: A range spanning the remaining elements in the array that
1055 * initially were right after `r`.
1057 * Complexity: $(BIGOH length)
1059 * Throws: `Exception` if `r` is not a valid range extracted from this array.
1061 Range linearRemove(Range r)
1063 import std.algorithm.mutation : copy;
1065 enforce(r._outer._data is _data);
1066 enforce(_data.refCountedStore.isInitialized);
1067 enforce(r._a <= r._b && r._b <= length);
1068 immutable offset1 = r._a;
1069 immutable offset2 = r._b;
1070 immutable tailLength = length - offset2;
1071 // Use copy here, not a[] = b[] because the ranges may overlap
1072 copy(this[offset2 .. length], this[offset1 .. offset1 + tailLength]);
1073 length = offset1 + tailLength;
1074 return this[length - tailLength .. length];
1088 assert(a.length == 10);
1089 assert(a.capacity >= a.length);
1094 struct Dumb { int x = 5; }
1097 assert(a.length == 10);
1098 assert(a.capacity >= a.length);
1099 immutable cap = a.capacity;
1103 assert(a.length == 5);
1104 // do not realloc if length decreases
1105 assert(a.capacity == cap);
1110 assert(a.length == 8);
1111 // do not realloc if capacity sufficient
1112 assert(a.capacity == cap);
1113 assert(Dumb.init.x == 5);
1115 assert(a[i].x == 10);
1116 foreach (i; 5 .. a.length)
1117 assert(a[i].x == Dumb.init.x);
1119 // realloc required, check if values properly copied
1122 assert(a.capacity >= 20);
1124 assert(a[i].x == 1);
1125 foreach (i; 8 .. a.length)
1126 assert(a[i].x == Dumb.init.x);
1128 // check if overlapping elements properly initialized
1131 assert(a[0].x == 1);
1132 foreach (e; a[1 .. $])
1133 assert(e.x == Dumb.init.x);
1138 Array!int a = Array!int(1, 2, 3);
1139 //a._data._refCountedDebug = true;
1141 assert(b == Array!int(1, 2, 3));
1143 assert(b == Array!int(42, 2, 3));
1144 assert(a == Array!int(1, 2, 3));
1149 auto a = Array!int(1, 2, 3);
1150 assert(a.length == 3);
1155 const Array!int a = [1, 2];
1158 assert(a.front == 1);
1159 assert(a.back == 2);
1161 static assert(!__traits(compiles, { a[0] = 1; }));
1162 static assert(!__traits(compiles, { a.front = 1; }));
1163 static assert(!__traits(compiles, { a.back = 1; }));
1176 // https://issues.dlang.org/show_bug.cgi?id=13621
1177 import std.container : Array, BinaryHeap;
1178 alias Heap = BinaryHeap!(Array!int);
1183 // https://issues.dlang.org/show_bug.cgi?id=18800
1184 static struct S { void* p; }
1193 assert(a.length == 0);
1195 assert(a.capacity >= 1000);
1196 auto p = a._data._payload.ptr;
1197 foreach (i; 0 .. 1000)
1201 assert(p == a._data._payload.ptr);
1206 auto a = Array!int(1, 2, 3);
1213 auto a = Array!int(1, 2, 3);
1214 auto b = Array!int(11, 12, 13);
1216 assert(c == Array!int(1, 2, 3, 11, 12, 13));
1217 assert(a ~ b[] == Array!int(1, 2, 3, 11, 12, 13));
1218 assert(a ~ [4,5] == Array!int(1,2,3,4,5));
1223 auto a = Array!int(1, 2, 3);
1224 auto b = Array!int(11, 12, 13);
1226 assert(a == Array!int(1, 2, 3, 11, 12, 13));
1231 auto a = Array!int(1, 2, 3, 4);
1232 assert(a.removeAny() == 4);
1233 assert(a == Array!int(1, 2, 3));
1238 auto a = Array!int(1, 2, 3, 4, 5);
1239 auto r = a[2 .. a.length];
1240 assert(a.insertBefore(r, 42) == 1);
1241 assert(a == Array!int(1, 2, 42, 3, 4, 5));
1243 assert(a.insertBefore(r, [8, 9]) == 2);
1244 assert(a == Array!int(1, 2, 8, 9, 42, 3, 4, 5));
1249 auto a = Array!int(0, 1, 2, 3, 4, 5, 6, 7, 8);
1250 a.linearRemove(a[4 .. 6]);
1251 assert(a == Array!int(0, 1, 2, 3, 6, 7, 8));
1254 // Give the Range object some testing.
1257 import std.algorithm.comparison : equal;
1258 import std.range : retro;
1259 auto a = Array!int(0, 1, 2, 3, 4, 5, 6)[];
1260 auto b = Array!int(6, 5, 4, 3, 2, 1, 0)[];
1261 alias A = typeof(a);
1263 static assert(isRandomAccessRange!A);
1264 static assert(hasSlicing!A);
1265 static assert(hasAssignableElements!A);
1266 static assert(hasMobileElements!A);
1268 assert(equal(retro(b), a));
1269 assert(a.length == 7);
1270 assert(equal(a[1 .. 4], [1, 2, 3]));
1273 // https://issues.dlang.org/show_bug.cgi?id=5920
1276 struct structBug5920
1279 uint* pDestructionMask;
1282 if (pDestructionMask)
1283 *pDestructionMask += 1 << order;
1287 alias S = structBug5920;
1290 auto arr = Array!S(cast(S[])[]);
1292 arr.insertBack(S(i, &dMask));
1293 // don't check dMask now as S may be copied multiple times (it's ok?)
1295 assert(arr.length == 8);
1298 assert(arr.length == 6); // make sure shrinking calls the d'tor
1299 assert(dMask == 0b1100_0000);
1301 assert(arr.length == 5); // make sure removeBack() calls the d'tor
1302 assert(dMask == 0b1110_0000);
1304 assert(arr.length == 2); // ditto
1305 assert(dMask == 0b1111_1100);
1307 assert(arr.length == 0); // make sure clear() calls the d'tor
1308 assert(dMask == 0b1111_1111);
1310 assert(dMask == 0b1111_1111); // make sure the d'tor is called once only.
1313 // Test for https://issues.dlang.org/show_bug.cgi?id=5792
1314 // (mainly just to check if this piece of code is compilable)
1317 auto a = Array!(int[])([[1,2],[3,4]]);
1319 assert(a.capacity >= 4);
1320 assert(a.length == 2);
1321 assert(a[0] == [1,2]);
1322 assert(a[1] == [3,4]);
1324 assert(a.capacity >= 16);
1325 assert(a.length == 2);
1326 assert(a[0] == [1,2]);
1327 assert(a[1] == [3,4]);
1330 // test replace!Stuff with range Stuff
1333 import std.algorithm.comparison : equal;
1334 auto a = Array!int([1, 42, 5]);
1335 a.replace(a[1 .. 2], [2, 3, 4]);
1336 assert(equal(a[], [1, 2, 3, 4, 5]));
1339 // test insertBefore and replace with empty Arrays
1342 import std.algorithm.comparison : equal;
1343 auto a = Array!int();
1344 a.insertBefore(a[], 1);
1345 assert(equal(a[], [1]));
1349 import std.algorithm.comparison : equal;
1350 auto a = Array!int();
1351 a.insertBefore(a[], [1, 2]);
1352 assert(equal(a[], [1, 2]));
1356 import std.algorithm.comparison : equal;
1357 auto a = Array!int();
1358 a.replace(a[], [1, 2]);
1359 assert(equal(a[], [1, 2]));
1363 import std.algorithm.comparison : equal;
1364 auto a = Array!int();
1366 assert(equal(a[], [1]));
1368 // make sure that Array instances refuse ranges that don't belong to them
1371 import std.exception : assertThrown;
1373 Array!int a = [1, 2, 3];
1375 assertThrown(a.insertBefore(r, 42));
1376 assertThrown(a.insertBefore(r, [42]));
1377 assertThrown(a.insertAfter(r, 42));
1378 assertThrown(a.replace(r, 42));
1379 assertThrown(a.replace(r, [42]));
1380 assertThrown(a.linearRemove(r));
1384 auto a = Array!int([1, 1]);
1385 a[1] = 0; //Check Array.opIndexAssign
1387 a[1] += 1; //Check Array.opIndexOpAssign
1390 //Check Array.opIndexUnary
1392 //a[0]++ //op++ doesn't return, so this shouldn't work, even with 5044 fixed
1394 assert(+a[0] == +2);
1395 assert(-a[0] == -2);
1396 assert(~a[0] == ~2);
1399 r[1] = 0; //Check Array.Range.opIndexAssign
1401 r[1] += 1; //Check Array.Range.opIndexOpAssign
1404 //Check Array.Range.opIndexUnary
1406 //r[0]++ //op++ doesn't return, so this shouldn't work, even with 5044 fixed
1408 assert(+r[0] == +3);
1409 assert(-r[0] == -3);
1410 assert(~r[0] == ~3);
1415 import std.algorithm.comparison : equal;
1417 //Test "array-wide" operations
1418 auto a = Array!int([0, 1, 2]); //Array
1420 assert(a[].equal([5, 6, 7]));
1422 assert(a[].equal([6, 7, 8]));
1424 assert(a[].equal([6, 35, 40]));
1426 assert(a[].equal([0, 0, 40]));
1429 auto a2 = Array!int.init;
1437 //Test "range-wide" operations
1438 auto r = Array!int([0, 1, 2])[]; //Array.Range
1440 assert(r.equal([5, 6, 7]));
1442 assert(r.equal([6, 7, 8]));
1444 assert(r.equal([6, 35, 40]));
1446 assert(r.equal([0, 0, 40]));
1449 auto r2 = Array!int.init[];
1464 this(this) { assert(i == 1337); }
1465 ~this() { assert(i == 1337); }
1473 // https://issues.dlang.org/show_bug.cgi?id=11459
1482 alias B = Array!(shared bool);
1485 // https://issues.dlang.org/show_bug.cgi?id=11884
1488 import std.algorithm.iteration : filter;
1489 auto a = Array!int([1, 2, 2].filter!"true"());
1492 // https://issues.dlang.org/show_bug.cgi?id=8282
1495 auto arr = new Array!int;
1498 // https://issues.dlang.org/show_bug.cgi?id=6998
1515 auto arr = Array!C(c);
1518 //Array should not have destroyed the class instance
1521 //Just to make sure the GC doesn't collect before the above test.
1522 assert(c.dummy == 1);
1525 //https://issues.dlang.org/show_bug.cgi?id=6998 (2)
1528 static class C {int i;}
1534 assert(c.i == 42); //fails
1539 static assert(is(Array!int.Range));
1540 static assert(is(Array!int.ConstRange));
1543 @system unittest // const/immutable Array and Ranges
1545 static void test(A, R, E, S)()
1550 assert(r.length == 0);
1551 static assert(is(typeof(r.front) == E));
1552 static assert(is(typeof(r.back) == E));
1553 static assert(is(typeof(r[0]) == E));
1554 static assert(is(typeof(r[]) == S));
1555 static assert(is(typeof(r[0 .. 0]) == S));
1558 alias A = Array!int;
1560 test!(A, A.Range, int, A.Range);
1561 test!(A, const A.Range, const int, A.ConstRange);
1563 test!(const A, A.ConstRange, const int, A.ConstRange);
1564 test!(const A, const A.ConstRange, const int, A.ConstRange);
1566 test!(immutable A, A.ImmutableRange, immutable int, A.ImmutableRange);
1567 test!(immutable A, const A.ImmutableRange, immutable int, A.ImmutableRange);
1568 test!(immutable A, immutable A.ImmutableRange, immutable int,
1573 @nogc @system unittest
1577 assert(ai.front == 1);
1580 assert(ai.capacity == 10);
1582 static immutable arr = [1, 2, 3];
1587 * typeof may give wrong result in case of classes defining `opCall` operator
1588 * https://issues.dlang.org/show_bug.cgi?id=20589
1590 * destructor std.container.array.Array!(MyClass).Array.~this is @system
1591 * so the unittest is @system too
1608 import std.algorithm.comparison : equal;
1609 auto a = Array!int([1,2,3,4,5]);
1610 assert(a.length == 5);
1612 assert(a.insertAfter(a[0 .. 5], [7, 8]) == 2);
1613 assert(equal(a[], [1,2,3,4,5,7,8]));
1615 assert(a.insertAfter(a[0 .. 5], 6) == 1);
1616 assert(equal(a[], [1,2,3,4,5,6,7,8]));
1620 ////////////////////////////////////////////////////////////////////////////////
1622 ////////////////////////////////////////////////////////////////////////////////
1625 * _Array specialized for `bool`. Packs together values efficiently by
1626 * allocating one bit per element.
1629 if (is(immutable T == immutable bool))
1631 import std.exception : enforce;
1632 import std.typecons : RefCounted, RefCountedAutoInitialize;
1634 static immutable uint bitsPerWord = size_t.sizeof * 8;
1635 private static struct Data
1637 Array!size_t.Payload _backend;
1640 private RefCounted!(Data, RefCountedAutoInitialize.no) _store;
1642 private @property ref size_t[] data()
1644 assert(_store.refCountedStore.isInitialized,
1645 "Cannot get data of uninitialized Array");
1646 return _store._backend._payload;
1650 * Defines the array's primary range.
1654 private Array _outer;
1655 private size_t _a, _b;
1656 /// Range primitives
1657 @property Range save()
1670 @property bool empty()
1672 return _a >= _b || _outer.length < _b;
1677 enforce(!empty, "Attempting to access the front of an empty Array");
1681 @property void front(bool value)
1683 enforce(!empty, "Attempting to set the front of an empty Array");
1689 enforce(!empty, "Attempting to move the front of an empty Array");
1690 return _outer.moveAt(_a);
1695 enforce(!empty, "Attempting to popFront an empty Array");
1701 enforce(!empty, "Attempting to access the back of an empty Array");
1702 return _outer[_b - 1];
1705 @property void back(bool value)
1707 enforce(!empty, "Attempting to set the back of an empty Array");
1708 _outer[_b - 1] = value;
1713 enforce(!empty, "Attempting to move the back of an empty Array");
1714 return _outer.moveAt(_b - 1);
1719 enforce(!empty, "Attempting to popBack an empty Array");
1725 return _outer[_a + i];
1728 void opIndexAssign(T value, size_t i)
1730 _outer[_a + i] = value;
1735 return _outer.moveAt(_a + i);
1738 @property size_t length() const
1740 assert(_a <= _b, "Invalid bounds");
1743 alias opDollar = length;
1745 Range opSlice(size_t low, size_t high)
1747 // Note: indexes start at 0, which is equivalent to _a
1749 low <= high && high <= (_b - _a),
1750 "Using out of bounds indexes on an Array"
1752 return Range(_outer, _a + low, _a + high);
1757 * Constructor taking a number of items.
1759 this(U)(U[] values...)
1760 if (isImplicitlyConvertible!(U, T))
1762 reserve(values.length);
1763 foreach (i, v; values)
1765 auto rem = i % bitsPerWord;
1768 // Fits within the current array
1771 data[$ - 1] |= (cast(size_t) 1 << rem);
1775 data[$ - 1] &= ~(cast(size_t) 1 << rem);
1780 // Need to add more data
1781 _store._backend.insertBack(v);
1784 _store._length = values.length;
1788 * Constructor taking an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
1790 this(Range)(Range r)
1791 if (isInputRange!Range && isImplicitlyConvertible!(ElementType!Range, T) && !is(Range == T[]))
1797 * Property returning `true` if and only if the array has
1800 * Complexity: $(BIGOH 1)
1802 @property bool empty()
1808 * Returns: A duplicate of the array.
1810 * Complexity: $(BIGOH length).
1812 @property Array dup()
1815 result.insertBack(this[]);
1820 * Returns the number of elements in the array.
1822 * Complexity: $(BIGOH 1).
1824 @property size_t length() const
1826 return _store.refCountedStore.isInitialized ? _store._length : 0;
1828 alias opDollar = length;
1831 * Returns: The maximum number of elements the array can store without
1832 * reallocating memory and invalidating iterators upon insertion.
1834 * Complexity: $(BIGOH 1).
1836 @property size_t capacity()
1838 return _store.refCountedStore.isInitialized
1839 ? cast(size_t) bitsPerWord * _store._backend.capacity
1844 * Ensures sufficient capacity to accommodate `e` _elements.
1845 * If `e < capacity`, this method does nothing.
1847 * Postcondition: `capacity >= e`
1849 * Note: If the capacity is increased, one should assume that all
1850 * iterators to the elements are invalidated.
1852 * Complexity: at most $(BIGOH length) if `e > capacity`, otherwise $(BIGOH 1).
1854 void reserve(size_t e)
1856 import std.conv : to;
1857 _store.refCountedStore.ensureInitialized();
1858 _store._backend.reserve(to!size_t((e + bitsPerWord - 1) / bitsPerWord));
1862 * Returns: A range that iterates over all elements of the array in forward order.
1864 * Complexity: $(BIGOH 1)
1868 return Range(this, 0, length);
1873 * Returns: A range that iterates the array between two specified positions.
1875 * Complexity: $(BIGOH 1)
1877 Range opSlice(size_t a, size_t b)
1879 enforce(a <= b && b <= length);
1880 return Range(this, a, b);
1884 * Returns: The first element of the array.
1886 * Precondition: `empty == false`
1888 * Complexity: $(BIGOH 1)
1890 * Throws: `Exception` if the array is empty.
1892 @property bool front()
1895 return data.ptr[0] & 1;
1899 @property void front(bool value)
1902 if (value) data.ptr[0] |= 1;
1903 else data.ptr[0] &= ~cast(size_t) 1;
1907 * Returns: The last element of the array.
1909 * Precondition: `empty == false`
1911 * Complexity: $(BIGOH 1)
1913 * Throws: `Exception` if the array is empty.
1915 @property bool back()
1918 return cast(bool)(data.back & (cast(size_t) 1 << ((_store._length - 1) % bitsPerWord)));
1922 @property void back(bool value)
1927 data.back |= (cast(size_t) 1 << ((_store._length - 1) % bitsPerWord));
1932 ~(cast(size_t) 1 << ((_store._length - 1) % bitsPerWord));
1937 * Indexing operators yielding or modifyng the value at the specified index.
1939 * Precondition: `i < length`
1941 * Complexity: $(BIGOH 1)
1943 bool opIndex(size_t i)
1945 auto div = cast(size_t) (i / bitsPerWord);
1946 auto rem = i % bitsPerWord;
1947 enforce(div < data.length);
1948 return cast(bool)(data.ptr[div] & (cast(size_t) 1 << rem));
1952 void opIndexAssign(bool value, size_t i)
1954 auto div = cast(size_t) (i / bitsPerWord);
1955 auto rem = i % bitsPerWord;
1956 enforce(div < data.length);
1957 if (value) data.ptr[div] |= (cast(size_t) 1 << rem);
1958 else data.ptr[div] &= ~(cast(size_t) 1 << rem);
1962 void opIndexOpAssign(string op)(bool value, size_t i)
1964 auto div = cast(size_t) (i / bitsPerWord);
1965 auto rem = i % bitsPerWord;
1966 enforce(div < data.length);
1967 auto oldValue = cast(bool) (data.ptr[div] & (cast(size_t) 1 << rem));
1969 auto newValue = mixin("oldValue "~op~" value");
1970 // Write back the value
1971 if (newValue != oldValue)
1973 if (newValue) data.ptr[div] |= (cast(size_t) 1 << rem);
1974 else data.ptr[div] &= ~(cast(size_t) 1 << rem);
1985 * Returns: A new array which is a concatenation of `this` and its argument.
1988 * $(BIGOH length + m), where `m` is the number of elements in `stuff`.
1990 Array!bool opBinary(string op, Stuff)(Stuff rhs)
1995 static if (hasLength!Stuff)
1996 result.reserve(length + rhs.length);
1997 else static if (is(typeof(rhs[])) && hasLength!(typeof(rhs[])))
1998 result.reserve(length + rhs[].length);
1999 else static if (isImplicitlyConvertible!(Stuff, bool))
2000 result.reserve(length + 1);
2002 result.insertBack(this[]);
2008 * Forwards to `insertBack`.
2010 Array!bool opOpAssign(string op, Stuff)(Stuff stuff)
2013 static if (is(typeof(stuff[]))) insertBack(stuff[]);
2014 else insertBack(stuff);
2019 * Removes all the elements from the array and releases allocated memory.
2021 * Postcondition: `empty == true && capacity == 0`
2023 * Complexity: $(BIGOH length)
2031 * Sets the number of elements in the array to `newLength`. If `newLength`
2032 * is greater than `length`, the new elements are added to the end of the
2033 * array and initialized with `false`.
2036 * Guaranteed $(BIGOH abs(length - newLength)) if `capacity >= newLength`.
2037 * If `capacity < newLength` the worst case is $(BIGOH newLength).
2039 * Postcondition: `length == newLength`
2041 @property void length(size_t newLength)
2043 import std.conv : to;
2044 _store.refCountedStore.ensureInitialized();
2045 auto newDataLength =
2046 to!size_t((newLength + bitsPerWord - 1) / bitsPerWord);
2047 _store._backend.length = newDataLength;
2048 _store._length = newLength;
2052 * Removes the last element from the array and returns it.
2053 * Both stable and non-stable versions behave the same and guarantee
2054 * that ranges iterating over the array are never invalidated.
2056 * Precondition: `empty == false`
2058 * Returns: The element removed.
2060 * Complexity: $(BIGOH 1).
2062 * Throws: `Exception` if the array is empty.
2072 alias stableRemoveAny = removeAny;
2075 * Inserts the specified elements at the back of the array. `stuff` can be
2076 * a value convertible to `bool` or a range of objects convertible to `bool`.
2078 * Returns: The number of elements inserted.
2081 * $(BIGOH length + m) if reallocation takes place, otherwise $(BIGOH m),
2082 * where `m` is the number of elements in `stuff`.
2084 size_t insertBack(Stuff)(Stuff stuff)
2085 if (is(Stuff : bool))
2087 _store.refCountedStore.ensureInitialized();
2088 auto rem = _store._length % bitsPerWord;
2091 // Fits within the current array
2094 data[$ - 1] |= (cast(size_t) 1 << rem);
2098 data[$ - 1] &= ~(cast(size_t) 1 << rem);
2103 // Need to add more data
2104 _store._backend.insertBack(stuff);
2111 size_t insertBack(Stuff)(Stuff stuff)
2112 if (isInputRange!Stuff && is(ElementType!Stuff : bool))
2115 static if (hasLength!Stuff)
2116 result = stuff.length;
2118 for (; !stuff.empty; stuff.popFront())
2120 insertBack(stuff.front);
2121 static if (!hasLength!Stuff) ++result;
2128 alias stableInsertBack = insertBack;
2131 alias insert = insertBack;
2134 alias stableInsert = insertBack;
2137 alias linearInsert = insertBack;
2140 alias stableLinearInsert = insertBack;
2143 * Removes the value from the back of the array. Both stable and non-stable
2144 * versions behave the same and guarantee that ranges iterating over the
2145 * array are never invalidated.
2147 * Precondition: `empty == false`
2149 * Complexity: $(BIGOH 1).
2151 * Throws: `Exception` if the array is empty.
2155 enforce(_store._length);
2156 if (_store._length % bitsPerWord)
2158 // Cool, just decrease the length
2163 // Reduce the allocated space
2165 _store._backend.length = _store._backend.length - 1;
2170 alias stableRemoveBack = removeBack;
2173 * Removes `howMany` values from the back of the array. Unlike the
2174 * unparameterized versions above, these functions do not throw if
2175 * they could not remove `howMany` elements. Instead, if `howMany > n`,
2176 * all elements are removed. The returned value is the effective number
2177 * of elements removed. Both stable and non-stable versions behave the same
2178 * and guarantee that ranges iterating over the array are never invalidated.
2180 * Returns: The number of elements removed.
2182 * Complexity: $(BIGOH howMany).
2184 size_t removeBack(size_t howMany)
2186 if (howMany >= length)
2193 length = length - howMany;
2199 alias stableRemoveBack = removeBack;
2202 * Inserts `stuff` before, after, or instead range `r`, which must
2203 * be a valid range previously extracted from this array. `stuff`
2204 * can be a value convertible to `bool` or a range of objects convertible
2205 * to `bool`. Both stable and non-stable version behave the same and
2206 * guarantee that ranges iterating over the array are never invalidated.
2208 * Returns: The number of values inserted.
2210 * Complexity: $(BIGOH length + m), where `m` is the length of `stuff`.
2212 size_t insertBefore(Stuff)(Range r, Stuff stuff)
2214 import std.algorithm.mutation : bringToFront;
2215 // TODO: make this faster, it moves one bit at a time
2216 immutable inserted = stableInsertBack(stuff);
2217 immutable tailLength = length - inserted;
2219 this[r._a .. tailLength],
2220 this[tailLength .. length]);
2225 alias stableInsertBefore = insertBefore;
2228 size_t insertAfter(Stuff)(Range r, Stuff stuff)
2229 if (isImplicitlyConvertible!(Stuff, T) ||
2230 isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
2232 import std.algorithm.mutation : bringToFront;
2233 // TODO: make this faster, it moves one bit at a time
2234 immutable inserted = stableInsertBack(stuff);
2235 immutable tailLength = length - inserted;
2237 this[r._b .. tailLength],
2238 this[tailLength .. length]);
2243 alias stableInsertAfter = insertAfter;
2246 size_t replace(Stuff)(Range r, Stuff stuff)
2247 if (is(Stuff : bool))
2258 // No room, must insert
2259 insertBefore(r, stuff);
2265 alias stableReplace = replace;
2268 * Removes all elements belonging to `r`, which must be a range
2269 * obtained originally from this array.
2271 * Returns: A range spanning the remaining elements in the array that
2272 * initially were right after `r`.
2274 * Complexity: $(BIGOH length)
2276 Range linearRemove(Range r)
2278 import std.algorithm.mutation : copy;
2279 copy(this[r._b .. length], this[r._a .. length]);
2280 length = length - r.length;
2281 return this[r._a .. length];
2287 import std.algorithm.comparison : equal;
2289 auto a = Array!bool([true, true, false, false, true, false]);
2290 assert(equal(a[], [true, true, false, false, true, false]));
2296 import std.algorithm.comparison : equal;
2297 import std.range : retro;
2298 bool[] arr = [true, true, false, false, true, false];
2300 auto a = Array!bool(retro(arr));
2301 assert(equal(a[], retro(arr)));
2312 auto arr = Array!bool([false, false, false, false]);
2313 assert(arr.front == false);
2314 assert(arr.back == false);
2315 assert(arr[1] == false);
2317 slice = arr[0 .. $];
2318 slice = slice[1 .. $];
2322 slice = slice[0 .. $]; // https://issues.dlang.org/show_bug.cgi?id=19171
2323 assert(slice.front == true);
2324 assert(slice.back == true);
2325 assert(slice[1] == true);
2326 assert(slice.moveFront == true);
2327 assert(slice.moveBack == true);
2328 assert(slice.moveAt(1) == true);
2331 // uncomparable values are valid values for an array
2332 // https://issues.dlang.org/show_bug.cgi?id=16331
2335 double[] values = [double.nan, double.nan];
2336 auto arr = Array!double(values);
2339 @nogc @system unittest
2341 auto a = Array!int(0, 1, 2);
2342 int[3] b = [3, 4, 5];
2343 short[3] ci = [0, 1, 0];
2344 auto c = Array!short(ci);
2345 assert(Array!int(0, 1, 2, 0, 1, 2) == a ~ a);
2346 assert(Array!int(0, 1, 2, 3, 4, 5) == a ~ b);
2347 assert(Array!int(0, 1, 2, 3) == a ~ 3);
2348 assert(Array!int(0, 1, 2, 0, 1, 0) == a ~ c);
2351 @nogc @system unittest
2353 auto a = Array!char('a', 'b');
2354 assert(Array!char("abc") == a ~ 'c');
2355 import std.utf : byCodeUnit;
2356 assert(Array!char("abcd") == a ~ "cd".byCodeUnit);
2359 @nogc @system unittest
2361 auto a = Array!dchar("ąćę"d);
2362 assert(Array!dchar("ąćęϢϖ"d) == a ~ "Ϣϖ"d);
2364 assert(Array!dchar("ąćęϢz"d) == a ~ x ~ 'z');
2371 a.insertBack(false);
2387 import std.conv : to;
2389 assert(a.length == 0);
2391 assert(a.length == 1, to!string(a.length));
2396 import std.conv : to;
2398 assert(a.capacity == 0);
2399 foreach (i; 0 .. 100)
2402 assert(a.capacity >= a.length, to!string(a.capacity));
2409 assert(a.capacity == 0);
2411 assert(a.capacity >= 15657);
2413 assert(a.capacity >= 15657);
2418 auto a = Array!bool([true, false, true, true]);
2419 assert(a[0 .. 2].length == 2);
2424 auto a = Array!bool([true, false, true, true]);
2425 assert(a[].length == 4);
2430 auto a = Array!bool([true, false, true, true]);
2438 auto a = Array!bool([true, false, true, true]);
2439 assert(a[].length == 4);
2444 auto a = Array!bool([true, false, true, true]);
2452 auto a = Array!bool([true, false, true, true]);
2453 assert(a[0] && !a[1]);
2460 import std.algorithm.comparison : equal;
2461 auto a = Array!bool([true, false, true, true]);
2462 auto b = Array!bool([true, true, false, true]);
2463 assert(equal((a ~ b)[],
2464 [true, false, true, true, true, true, false, true]));
2465 assert((a ~ [true, false])[].equal([true, false, true, true, true, false]));
2468 assert((c ~ false)[].equal([true, false]));
2472 import std.algorithm.comparison : equal;
2473 auto a = Array!bool([true, false, true, true]);
2474 auto b = Array!bool([false, true, false, true, true]);
2478 [true, false, true, true, false, true, false, true, true]));
2483 auto a = Array!bool([true, false, true, true]);
2485 assert(a.capacity == 0);
2492 assert(a.length == 1057);
2493 assert(a.capacity >= a.length);
2498 immutable cap = a.capacity;
2500 assert(a.length == 100);
2501 // do not realloc if length decreases
2502 assert(a.capacity == cap);
2509 assert(!a.removeAny());
2510 assert(a.length == 1056);
2520 for (int i = 0; i < 100; ++i)
2530 assert(a.removeBack(1000) == 1000);
2531 assert(a.length == 57);
2540 import std.conv : to;
2544 a._store.refCountedDebug = true;
2546 a.insertBefore(a[], true);
2547 assert(a.length == 1, to!string(a.length));
2548 a.insertBefore(a[], false);
2549 assert(a.length == 2, to!string(a.length));
2550 a.insertBefore(a[1 .. $], true);
2551 import std.algorithm.comparison : equal;
2552 assert(a[].equal([false, true, true]));
2555 // https://issues.dlang.org/show_bug.cgi?id=21555
2558 import std.algorithm.comparison : equal;
2560 size_t len = arr.insertBack([false, true]);
2564 // https://issues.dlang.org/show_bug.cgi?id=21556
2567 import std.algorithm.comparison : equal;
2569 a.insertBack([true, true, false, false, true]);
2570 assert(a.length == 5);
2572 assert(a.insertAfter(a[0 .. 5], [false, false]) == 2);
2573 assert(equal(a[], [true, true, false, false, true, false, false]));
2575 assert(a.insertAfter(a[0 .. 5], true) == 1);
2576 assert(equal(a[], [true, true, false, false, true, true, false, false]));
2581 import std.conv : to;
2584 a.insertAfter(a[0 .. 5], true);
2585 assert(a.length == 11, to!string(a.length));
2594 assert(arr[0] == [1, 2, 3]);
2599 V3[2] v = [[1, 2, 3], [4, 5, 6]];
2602 assert(arr[0] == [1, 2, 3]);
2603 assert(arr[1] == [4, 5, 6]);
2606 // Change of length reallocates without calling GC.
2607 // https://issues.dlang.org/show_bug.cgi?id=13642
2611 class ABC { void func() { int x = 5; } }
2614 // Length only allocates if capacity is too low.
2616 assert(arr.capacity == 4);
2624 foreach (ref b; arr) b = new ABC;
2631 Array!int arr = [1, 2, 4, 5];
2632 int[] data = arr.data();
2635 assert(arr[0] == 0);