GeezerVison is showing dlang.org — std.algorithm.mutation - D Programming Language
Library Reference
version 2.113.0
overview
Report a bug
If you spot a problem with this page, click here to create a GitHub issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page.
Requires a signed-in GitHub account. This works well for small changes.
If you'd like to make larger changes you may want to consider using
a local clone.
std.algorithm.mutation
This is a submodule of std.algorithm.
It contains generic mutation algorithms.
Cheat Sheet| Function Name | Description |
|---|
| bringToFront | If a = [1, 2, 3] and b = [4, 5, 6, 7],
bringToFront(a, b) leaves a = [4, 5, 6] and
b = [7, 1, 2, 3]. |
| copy | Copies a range to another. If
a = [1, 2, 3] and b = new int[5], then copy(a, b)
leaves b = [1, 2, 3, 0, 0] and returns b[3 .. $]. |
| fill | Fills a range with a pattern,
e.g., if a = new int[3], then fill(a, 4)
leaves a = [4, 4, 4] and fill(a, [3, 4]) leaves
a = [3, 4, 3]. |
| initializeAll | If a = [1.2, 3.4], then initializeAll(a) leaves
a = [double.init, double.init]. |
| move | move(a, b) moves a into b. move(a) reads a
destructively when necessary. |
| moveEmplace | Similar to move but assumes target is uninitialized. |
| moveAll | Moves all elements from one range to another. |
| moveEmplaceAll | Similar to moveAll but assumes all elements in target are uninitialized. |
| moveSome | Moves as many elements as possible from one range to another. |
| moveEmplaceSome | Similar to moveSome but assumes all elements in target are uninitialized. |
| remove | Removes elements from a range in-place, and returns the shortened
range. |
| reverse | If a = [1, 2, 3], reverse(a) changes it to [3, 2, 1]. |
| strip | Strips all leading and trailing elements equal to a value, or that
satisfy a predicate.
If a = [1, 1, 0, 1, 1], then strip(a, 1) and
strip!(e => e == 1)(a) returns [0]. |
| stripLeft | Strips all leading elements equal to a value, or that satisfy a
predicate. If a = [1, 1, 0, 1, 1], then stripLeft(a, 1) and
stripLeft!(e => e == 1)(a) returns [0, 1, 1]. |
| stripRight | Strips all trailing elements equal to a value, or that satisfy a
predicate.
If a = [1, 1, 0, 1, 1], then stripRight(a, 1) and
stripRight!(e => e == 1)(a) returns [1, 1, 0]. |
| swap | Swaps two values. |
| swapAt | Swaps two values by indices. |
| swapRanges | Swaps all elements of two ranges. |
| uninitializedFill | Fills a range (assumed uninitialized) with a value. |
size_t bringToFront(InputRange, ForwardRange)(InputRange front, ForwardRange back) if (isInputRange!InputRange && isForwardRange!ForwardRange);
bringToFront takes two ranges front and back, which may
be of different types. Considering the concatenation of front and
back one unified range, bringToFront rotates that unified
range such that all elements in back are brought to the beginning
of the unified range. The relative ordering of elements in front
and back, respectively, remains unchanged.
The bringToFront function treats strings at the code unit
level and it is not concerned with Unicode character integrity.
bringToFront is designed as a function for moving elements
in ranges, not as a string function.
Performs Ο(max(front.length, back.length)) evaluations of swap.
The bringToFront function can rotate elements in one buffer left or right, swap
buffers of equal length, and even move elements across disjoint
buffers of different types and different lengths.
Preconditions
Either front and back are disjoint, or back is
reachable from front and front is not reachable from back.
Returns: The number of elements brought to the front, i.e., the length of back.
Examples: The simplest use of bringToFront is for rotating elements in a
buffer. For example:
auto arr = [4, 5, 6, 7, 1, 2, 3];
auto p = bringToFront(arr[0 .. 4], arr[4 .. $]);
writeln(p); // arr.length - 4
writeln(arr); // [1, 2, 3, 4, 5, 6, 7]
Examples: The front range may actually "step over" the back
range. This is very useful with forward ranges that cannot compute
comfortably right-bounded subranges like arr[0 .. 4] above. In
the example below, r2 is a right subrange of r1.
import std.algorithm.comparison : equal;
import std.container : SList;
import std.range.primitives : popFrontN;
auto list = SList!(int)(4, 5, 6, 7, 1, 2, 3);
auto r1 = list[];
auto r2 = list[]; popFrontN(r2, 4);
assert(equal(r2, [ 1, 2, 3 ]));
bringToFront(r1, r2);
assert(equal(list[], [ 1, 2, 3, 4, 5, 6, 7 ]));
Examples: Elements can be swapped across ranges of different types:
import std.algorithm.comparison : equal;
import std.container : SList;
auto list = SList!(int)(4, 5, 6, 7);
auto vec = [ 1, 2, 3 ];
bringToFront(list[], vec);
assert(equal(list[], [ 1, 2, 3, 4 ]));
assert(equal(vec, [ 5, 6, 7 ]));
Examples: Unicode integrity is not preserved:
import std.string : representation;
auto ar = representation("a".dup);
auto br = representation("ç".dup);
bringToFront(ar, br);
auto a = cast(char[]) ar;
auto b = cast(char[]) br;
// Illegal UTF-8
writeln(a); // "\303"
// Illegal UTF-8
writeln(b); // "\247a"
TargetRange copy(SourceRange, TargetRange)(SourceRange source, TargetRange target) if (isInputRange!SourceRange && isOutputRange!(TargetRange, ElementType!SourceRange));
Copies the content of source into target and returns the
remaining (unfilled) part of target.
Preconditions
target shall have enough room to accommodate
the entirety of source.
Parameters: SourceRange source |
an input range |
TargetRange target |
an output range |
Returns: The unfilled part of target
Examples: int[] a = [ 1, 5 ];
int[] b = [ 9, 8 ];
int[] buf = new int[](a.length + b.length + 10);
auto rem = a.copy(buf); // copy a into buf
rem = b.copy(rem); // copy b into remainder of buf
writeln(buf[0 .. a.length + b.length]); // [1, 5, 9, 8]
assert(rem.length == 10); // unused slots in buf
Examples: As long as the target range elements support assignment from source
range elements, different types of ranges are accepted:
float[] src = [ 1.0f, 5 ];
double[] dest = new double[src.length];
src.copy(dest);
Examples: To copy at most n elements from a range, you may want to use
std.range.take:
import std.range;
int[] src = [ 1, 5, 8, 9, 10 ];
auto dest = new int[](3);
src.take(dest.length).copy(dest);
writeln(dest); // [1, 5, 8]
Examples: To copy just those elements from a range that satisfy a predicate,
use filter:
import std.algorithm.iteration : filter;
int[] src = [ 1, 5, 8, 9, 10, 1, 2, 0 ];
auto dest = new int[src.length];
auto rem = src
.filter!(a => (a & 1) == 1)
.copy(dest);
writeln(dest[0 .. $ - rem.length]); // [1, 5, 9, 1]
Examples: std.range.retro can be used to achieve behavior similar to
STL's copy_backward':
import std.algorithm, std.range;
int[] src = [1, 2, 4];
int[] dest = [0, 0, 0, 0, 0];
src.retro.copy(dest.retro);
writeln(dest); // [0, 0, 1, 2, 4]
void fill(Range, Value)(auto ref Range range, auto ref Value value) if (isInputRange!Range && is(typeof(range.front = value)) || isSomeChar!Value && is(typeof(range[] = value)));
void fill(InputRange, ForwardRange)(InputRange range, ForwardRange filler) if (isInputRange!InputRange && (isForwardRange!ForwardRange || isInputRange!ForwardRange && isInfinite!ForwardRange) && is(typeof(InputRange.init.front = ForwardRange.init.front)));
Assigns value to each element of input range range.
Alternatively, instead of using a single value to fill the range,
a filler forward range
can be provided. The length of filler and range do not need to match, but
filler must not be empty.
Parameters: Range range |
An
input range
that exposes references to its elements and has assignable
elements |
Value value |
Assigned to each element of range |
ForwardRange filler |
A
forward range
representing the fill pattern. |
Throws: If filler is empty.
Examples: int[] a = [ 1, 2, 3, 4 ];
fill(a, 5);
writeln(a); // [5, 5, 5, 5]
Examples: int[] a = [ 1, 2, 3, 4, 5 ];
int[] b = [ 8, 9 ];
fill(a, b);
writeln(a); // [8, 9, 8, 9, 8]
void initializeAll(Range)(Range range) if (isInputRange!Range && hasLvalueElements!Range && hasAssignableElements!Range && __traits(compiles, ()
{
static ElementType!Range _;
}
));
void initializeAll(Range)(Range range) if (is(Range == char[]) || is(Range == wchar[]));
Initializes all elements of range with their .init value.
Assumes that the elements of the range are uninitialized.
This function is unavailable if T is a struct and T.this() is annotated
with @disable.
Parameters: Range range |
An
input range
that exposes references to its elements and has assignable
elements |
Examples: import core.stdc.stdlib : malloc, free;
struct S
{
int a = 10;
}
auto s = (cast(S*) malloc(5 * S.sizeof))[0 .. 5];
initializeAll(s);
writeln(s); // [S(10), S(10), S(10), S(10), S(10)]
scope(exit) free(s.ptr);
void move(T)(ref T source, ref T target) if (__traits(compiles, target = T.init));
void move(T)(ref T source, ref T target) if (!__traits(compiles, imported!"std.traits".lvalueOf!T = T.init));
T move(T)(ref return scope T source);
Moves source into target, via a destructive copy when necessary.
If T is a struct with a destructor or postblit defined, source is reset
to its .init value after it is moved into target, otherwise it is
left unchanged.
Preconditions
If source has internal pointers that point to itself and doesn't define
opPostMove, it cannot be moved, and will trigger an assertion failure.
Parameters: T source |
Data to copy. |
T target |
Where to copy into. The destructor, if any, is invoked before the
copy is performed. |
Examples: For non-struct types, move just performs target = source:
Object obj1 = new Object;
Object obj2 = obj1;
Object obj3;
move(obj2, obj3);
assert(obj3 is obj1);
// obj2 unchanged
assert(obj2 is obj1);
Examples: // Structs without destructors are simply copied
struct S1
{
int a = 1;
int b = 2;
}
S1 s11 = { 10, 11 };
S1 s12;
move(s11, s12);
writeln(s12); // S1(10, 11)
writeln(s11); // s12
// But structs with destructors or postblits are reset to their .init value
// after copying to the target.
struct S2
{
int a = 1;
int b = 2;
~this() pure nothrow @safe @nogc { }
}
S2 s21 = { 3, 4 };
S2 s22;
move(s21, s22);
writeln(s21); // S2(1, 2)
writeln(s22); // S2(3, 4)
Examples: Non-copyable structs can still be moved:
struct S
{
int a = 1;
@disable this(this);
~this() pure nothrow @safe @nogc {}
}
S s1;
s1.a = 2;
S s2 = move(s1);
writeln(s1.a); // 1
writeln(s2.a); // 2
Examples: opPostMove will be called if defined:
struct S
{
int a;
void opPostMove(const ref S old)
{
writeln(a); // old.a
a++;
}
}
S s1;
s1.a = 41;
S s2 = move(s1);
writeln(s2.a); // 42
pure @system void moveEmplace(T)(ref T source, ref T target);
Similar to move but assumes target is uninitialized. This
is more efficient because source can be blitted over target
without destroying or initializing it first.
Parameters: T source |
value to be moved into target |
T target |
uninitialized value to be filled by source |
Examples: static struct Foo
{
pure nothrow @nogc:
this(int* ptr) { _ptr = ptr; }
~this() { if (_ptr) ++*_ptr; }
int* _ptr;
}
int val;
Foo foo1 = void; // uninitialized
auto foo2 = Foo(&val); // initialized
assert(foo2._ptr is &val);
// Using `move(foo2, foo1)` would have an undefined effect because it would destroy
// the uninitialized foo1.
// moveEmplace directly overwrites foo1 without destroying or initializing it first.
moveEmplace(foo2, foo1);
assert(foo1._ptr is &val);
assert(foo2._ptr is null);
writeln(val); // 0
InputRange2 moveAll(InputRange1, InputRange2)(InputRange1 src, InputRange2 tgt) if (isInputRange!InputRange1 && isInputRange!InputRange2 && is(typeof(move(src.front, tgt.front))));
Calls move(a, b) for each element a in src and the corresponding
element b in tgt, in increasing order.
Preconditions
walkLength(src) <= walkLength(tgt).
This precondition will be asserted. If you cannot ensure there is enough room in
tgt to accommodate all of src use moveSome instead.
Parameters: InputRange1 src |
An input range with
movable elements. |
InputRange2 tgt |
An input range with
elements that elements from src can be moved into. |
Returns: The leftover portion of tgt after all elements from src have
been moved.
Examples: int[3] a = [ 1, 2, 3 ];
int[5] b;
assert(moveAll(a[], b[]) is b[3 .. $]);
writeln(a[]); // b[0 .. 3]
int[3] cmp = [ 1, 2, 3 ];
writeln(a[]); // cmp[]
@system InputRange2 moveEmplaceAll(InputRange1, InputRange2)(InputRange1 src, InputRange2 tgt) if (isInputRange!InputRange1 && isInputRange!InputRange2 && is(typeof(moveEmplace(src.front, tgt.front))));
Similar to moveAll but assumes all elements in tgt are
uninitialized. Uses moveEmplace to move elements from
src over elements from tgt. Examples: static struct Foo
{
~this() pure nothrow @nogc { if (_ptr) ++*_ptr; }
int* _ptr;
}
int[3] refs = [0, 1, 2];
Foo[3] src = [Foo(&refs[0]), Foo(&refs[1]), Foo(&refs[2])];
Foo[5] dst = void;
auto tail = moveEmplaceAll(src[], dst[]); // move 3 value from src over dst
assert(tail.length == 2); // returns remaining uninitialized values
initializeAll(tail);
import std.algorithm.searching : all;
assert(src[].all!(e => e._ptr is null));
assert(dst[0 .. 3].all!(e => e._ptr !is null));
Tuple! (InputRange1, InputRange2) moveSome(InputRange1, InputRange2)(InputRange1 src, InputRange2 tgt) if (isInputRange!InputRange1 && isInputRange!InputRange2 && is(typeof(move(src.front, tgt.front))));
Calls move(a, b) for each element a in src and the corresponding
element b in tgt, in increasing order, stopping when either range has been
exhausted.
Parameters: InputRange1 src |
An input range with
movable elements. |
InputRange2 tgt |
An input range with
elements that elements from src can be moved into. |
Returns: The leftover portions of the two ranges after one or the other of the
ranges have been exhausted.
Examples: int[5] a = [ 1, 2, 3, 4, 5 ];
int[3] b;
assert(moveSome(a[], b[])[0] is a[3 .. $]);
writeln(a[0 .. 3]); // b
writeln(a); // [1, 2, 3, 4, 5]
@system Tuple! (InputRange1, InputRange2) moveEmplaceSome(InputRange1, InputRange2)(InputRange1 src, InputRange2 tgt) if (isInputRange!InputRange1 && isInputRange!InputRange2 && is(typeof(move(src.front, tgt.front))));
Same as moveSome but assumes all elements in tgt are
uninitialized. Uses moveEmplace to move elements from
src over elements from tgt. Examples: static struct Foo
{
~this() pure nothrow @nogc { if (_ptr) ++*_ptr; }
int* _ptr;
}
int[4] refs = [0, 1, 2, 3];
Foo[4] src = [Foo(&refs[0]), Foo(&refs[1]), Foo(&refs[2]), Foo(&refs[3])];
Foo[3] dst = void;
auto res = moveEmplaceSome(src[], dst[]);
writeln(res.length); // 2
import std.algorithm.searching : all;
assert(src[0 .. 3].all!(e => e._ptr is null));
assert(src[3]._ptr !is null);
assert(dst[].all!(e => e._ptr !is null));
Defines the swapping strategy for algorithms that need to swap
elements in a range (such as partition and sort). The strategy
concerns the swapping of elements that are not the core concern of the
algorithm. For example, consider an algorithm that sorts [ "abc",
"b", "aBc" ] according to toUpper(a) < toUpper(b). That
algorithm might choose to swap the two equivalent strings "abc"
and "aBc". That does not affect the sorting since both
["abc", "aBc", "b" ] and [ "aBc", "abc", "b" ] are valid
outcomes.
Some situations require that the algorithm must NOT ever change the
relative ordering of equivalent elements (in the example above, only
[ "abc", "aBc", "b" ] would be the correct result). Such
algorithms are called stable. If the ordering algorithm may swap
equivalent elements discretionarily, the ordering is called unstable.
Yet another class of algorithms may choose an intermediate tradeoff by
being stable only on a well-defined subrange of the range. There is no
established terminology for such behavior; this library calls it semistable.
Generally, the stable ordering strategy may be more costly in
time and/or space than the other two because it imposes additional
constraints. Similarly, semistable may be costlier than unstable. As (semi-)stability is not needed very often, the ordering
algorithms in this module parameterized by SwapStrategy all
choose SwapStrategy.unstable as the default. Examples: int[] a = [0, 1, 2, 3];
writeln(remove!(SwapStrategy.stable)(a, 1)); // [0, 2, 3]
a = [0, 1, 2, 3];
writeln(remove!(SwapStrategy.unstable)(a, 1)); // [0, 3, 2]
Examples: import std.algorithm.sorting : partition;
// Put stuff greater than 3 on the left
auto arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
writeln(partition!(a => a > 3, SwapStrategy.stable)(arr)); // [1, 2, 3]
writeln(arr); // [4, 5, 6, 7, 8, 9, 10, 1, 2, 3]
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
writeln(partition!(a => a > 3, SwapStrategy.semistable)(arr)); // [2, 3, 1]
writeln(arr); // [4, 5, 6, 7, 8, 9, 10, 2, 3, 1]
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
writeln(partition!(a => a > 3, SwapStrategy.unstable)(arr)); // [3, 2, 1]
writeln(arr); // [10, 9, 8, 4, 5, 6, 7, 3, 2, 1]
Allows freely swapping of elements as long as the output
satisfies the algorithm's requirements.
In algorithms partitioning ranges in two, preserve relative
ordering of elements only to the left of the partition point.
Preserve the relative ordering of elements to the largest
extent allowed by the algorithm's requirements.
Range remove(SwapStrategy s = SwapStrategy.stable, Range, Offset...)(Range range, Offset offset) if (Offset.length >= 1 && allSatisfy!(isValidIntegralTuple, Offset));
Range remove(SwapStrategy s = SwapStrategy.stable, Range, Offset...)(Range range, Offset offset) if (Offset.length >= 1 && !allSatisfy!(isValidIntegralTuple, Offset));
Eliminates elements at given offsets from range and returns the shortened
range.
For example, here is how to remove a single element from an array:
import std.algorithm.mutation;
string[] a = [ "a", "b", "c", "d" ];
a = a.remove(1); // remove element at offset 1
assert(a == [ "a", "c", "d"]);
Note that remove does not change the length of the original range directly;
instead, it returns the shortened range. If its return value is not assigned to
the original range, the original range will retain its original length, though
its contents will have changed:
import std.algorithm.mutation;
int[] a = [ 3, 5, 7, 8 ];
assert(remove(a, 1) == [ 3, 7, 8 ]);
assert(a == [ 3, 7, 8, 8 ]);
The element at offset 1 has been removed and the rest of the elements have
shifted up to fill its place, however, the original array remains of the same
length. This is because all functions in std.algorithm only change content, not topology. The value 8 is repeated because move was
invoked to rearrange elements, and on integers move simply copies the source
to the destination. To replace a with the effect of the removal, simply
assign the slice returned by remove to it, as shown in the first example.
Multiple indices can be passed into remove. In that case,
elements at the respective indices are all removed. The indices must
be passed in increasing order, otherwise an exception occurs.
import std.algorithm.mutation;
int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
assert(remove(a, 1, 3, 5) ==
[ 0, 2, 4, 6, 7, 8, 9, 10 ]);
Note that all indices refer to slots in the original array, not
in the array as it is being progressively shortened.
Tuples of two integral offsets can be supplied to remove a range of indices:
import std.algorithm.mutation, std.typecons;
int[] a = [ 3, 4, 5, 6, 7];
// remove elements at indices 1 and 2
assert(remove(a, tuple(1, 3)) == [ 3, 6, 7 ]);
The tuple passes in a range closed to the left and open to
the right (consistent with built-in slices), e.g. tuple(1, 3)
means indices 1 and 2 but not 3.
Finally, any combination of integral offsets and tuples composed of two integral
offsets can be passed in:
import std.algorithm.mutation, std.typecons;
int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
a = remove(a, 1, tuple(3, 5), 9);
assert(a == [ 0, 2, 5, 6, 7, 8, 10 ]);
In this case, the slots at positions 1, 3, 4, and 9 are removed from
the array.
If the need is to remove some elements in the range but the order of
the remaining elements does not have to be preserved, you may want to
pass SwapStrategy.unstable to remove.
import std.algorithm.mutation;
int[] a = [ 0, 1, 2, 3 ];
assert(remove!(SwapStrategy.unstable)(a, 1) == [ 0, 3, 2 ]);
In the case above, the element at slot 1 is removed, but replaced
with the last element of the range. Taking advantage of the relaxation
of the stability requirement, remove moved elements from the end
of the array over the slots to be removed. This way there is less data
movement to be done which improves the execution time of the function.
remove works on bidirectional ranges that have assignable
lvalue elements. The moving strategy is (listed from fastest to slowest):
- If s == SwapStrategy.unstable && isRandomAccessRange!Range &&
hasLength!Range && hasLvalueElements!Range, then elements are moved from the
end of the range into the slots to be filled. In this case, the absolute
minimum of moves is performed.
- Otherwise, if s ==
SwapStrategy.unstable && isBidirectionalRange!Range && hasLength!Range
&& hasLvalueElements!Range, then elements are still moved from the
end of the range, but time is spent on advancing between slots by repeated
calls to
range.popFront.
- Otherwise, elements are moved
incrementally towards the front of
range; a given element is never
moved several times, but more elements are moved than in the previous
cases.
Parameters: | s |
a SwapStrategy to determine if the original order needs to be preserved |
Range range |
a bidirectional range
with a length member |
Offset offset |
which element(s) to remove |
Returns: A range containing elements of range with 1 or more elements removed.
Examples: import std.typecons : tuple;
auto a = [ 0, 1, 2, 3, 4, 5 ];
writeln(remove!(SwapStrategy.stable)(a, 1)); // [0, 2, 3, 4, 5]
a = [ 0, 1, 2, 3, 4, 5 ];
writeln(remove!(SwapStrategy.stable)(a, 1, 3)); // [0, 2, 4, 5]
a = [ 0, 1, 2, 3, 4, 5 ];
writeln(remove!(SwapStrategy.stable)(a, 1, tuple(3, 6))); // [0, 2]
a = [ 0, 1, 2, 3, 4, 5 ];
writeln(remove!(SwapStrategy.unstable)(a, 1)); // [0, 5, 2, 3, 4]
a = [ 0, 1, 2, 3, 4, 5 ];
writeln(remove!(SwapStrategy.unstable)(a, tuple(1, 4))); // [0, 5, 4]
Examples: import std.typecons : tuple;
// Delete an index
writeln([4, 5, 6].remove(1)); // [4, 6]
// Delete multiple indices
writeln([4, 5, 6, 7, 8].remove(1, 3)); // [4, 6, 8]
// Use an indices range
writeln([4, 5, 6, 7, 8].remove(tuple(1, 3))); // [4, 7, 8]
// Use an indices range and individual indices
writeln([4, 5, 6, 7, 8].remove(0, tuple(1, 3), 4)); // [7]
Examples: SwapStrategy.unstable is faster, but doesn't guarantee the same order of the original array
writeln([5, 6, 7, 8].remove!(SwapStrategy.stable)(1)); // [5, 7, 8]
writeln([5, 6, 7, 8].remove!(SwapStrategy.unstable)(1)); // [5, 8, 7]
Range remove(alias pred, SwapStrategy s = SwapStrategy.stable, Range)(Range range);
Reduces the length of the
bidirectional range range by removing
elements that satisfy pred. If s = SwapStrategy.unstable,
elements are moved from the right end of the range over the elements
to eliminate. If s = SwapStrategy.stable (the default),
elements are moved progressively to front such that their relative
order is preserved. Returns the filtered range.
Parameters: Range range |
a bidirectional ranges with lvalue elements
or mutable character arrays |
Returns: the range with all of the elements where pred is true
removed
Examples: static immutable base = [1, 2, 3, 2, 4, 2, 5, 2];
int[] arr = base[].dup;
// using a string-based predicate
writeln(remove!("a == 2")(arr)); // [1, 3, 4, 5]
// The original array contents have been modified,
// so we need to reset it to its original state.
// The length is unmodified however.
arr[] = base[];
// using a lambda predicate
writeln(remove!(a => a == 2)(arr)); // [1, 3, 4, 5]
Range reverse(Range)(Range r) if (isBidirectionalRange!Range && (hasSwappableElements!Range || hasAssignableElements!Range && hasLength!Range && isRandomAccessRange!Range || isNarrowString!Range && isAssignable!(ElementType!Range)));
Reverses r in-place. Performs r.length / 2 evaluations of swap.
UTF sequences consisting of multiple code units are preserved properly.
Parameters: Range r |
a bidirectional range
with either swappable elements, a random access range with a length member,
or a narrow string |
Note
When passing a string with unicode modifiers on characters, such as \u0301,
this function will not properly keep the position of the modifier. For example,
reversing ba\u0301d ("bád") will result in d\u0301ab ("d́ab") instead of
da\u0301b ("dáb").
Examples: int[] arr = [ 1, 2, 3 ];
writeln(arr.reverse); // [3, 2, 1]
Examples: char[] arr = "hello\U00010143\u0100\U00010143".dup;
writeln(arr.reverse); // "\U00010143\u0100\U00010143olleh"
Range strip(Range, E)(Range range, E element) if (isBidirectionalRange!Range && is(typeof(range.front == element) : bool));
Range strip(alias pred, Range)(Range range) if (isBidirectionalRange!Range && is(typeof(pred(range.back)) : bool));
Range stripLeft(Range, E)(Range range, E element) if (isInputRange!Range && is(typeof(range.front == element) : bool));
Range stripLeft(alias pred, Range)(Range range) if (isInputRange!Range && is(typeof(pred(range.front)) : bool));
Range stripRight(Range, E)(Range range, E element) if (isBidirectionalRange!Range && is(typeof(range.back == element) : bool));
Range stripRight(alias pred, Range)(Range range) if (isBidirectionalRange!Range && is(typeof(pred(range.back)) : bool));
The strip group of functions allow stripping of either leading, trailing,
or both leading and trailing elements.
The stripLeft function will strip the front of the range,
the stripRight function will strip the back of the range,
while the strip function will strip both the front and back
of the range.
Note that the strip and stripRight functions require the range to
be a BidirectionalRange range.
All of these functions come in two varieties: one takes a target element,
where the range will be stripped as long as this element can be found.
The other takes a lambda predicate, where the range will be stripped as
long as the predicate returns true.
Returns: a Range with all of range except element at the start and end
Examples: Strip leading and trailing elements equal to the target element.
writeln(" foobar ".strip(' ')); // "foobar"
writeln("00223.444500".strip('0')); // "223.4445"
writeln("ëëêéüŗōpéêëë".strip('ë')); // "êéüŗōpéê"
writeln([1, 1, 0, 1, 1].strip(1)); // [0]
writeln([0.0, 0.01, 0.01, 0.0].strip(0).length); // 2
Examples: Strip leading and trailing elements while the predicate returns true.
writeln(" foobar ".strip!(a => a == ' ')()); // "foobar"
writeln("00223.444500".strip!(a => a == '0')()); // "223.4445"
writeln("ëëêéüŗōpéêëë".strip!(a => a == 'ë')()); // "êéüŗōpéê"
writeln([1, 1, 0, 1, 1].strip!(a => a == 1)()); // [0]
writeln([0.0, 0.01, 0.5, 0.6, 0.01, 0.0].strip!(a => a < 0.4)().length); // 2
Examples: Strip leading elements equal to the target element.
writeln(" foobar ".stripLeft(' ')); // "foobar "
writeln("00223.444500".stripLeft('0')); // "223.444500"
writeln("ůůűniçodêéé".stripLeft('ů')); // "űniçodêéé"
writeln([1, 1, 0, 1, 1].stripLeft(1)); // [0, 1, 1]
writeln([0.0, 0.01, 0.01, 0.0].stripLeft(0).length); // 3
Examples: Strip leading elements while the predicate returns true.
writeln(" foobar ".stripLeft!(a => a == ' ')()); // "foobar "
writeln("00223.444500".stripLeft!(a => a == '0')()); // "223.444500"
writeln("ůůűniçodêéé".stripLeft!(a => a == 'ů')()); // "űniçodêéé"
writeln([1, 1, 0, 1, 1].stripLeft!(a => a == 1)()); // [0, 1, 1]
writeln([0.0, 0.01, 0.10, 0.5, 0.6].stripLeft!(a => a < 0.4)().length); // 2
Examples: Strip trailing elements equal to the target element.
writeln(" foobar ".stripRight(' ')); // " foobar"
writeln("00223.444500".stripRight('0')); // "00223.4445"
writeln("ùniçodêéé".stripRight('é')); // "ùniçodê"
writeln([1, 1, 0, 1, 1].stripRight(1)); // [1, 1, 0]
writeln([0.0, 0.01, 0.01, 0.0].stripRight(0).length); // 3
Examples: Strip trailing elements while the predicate returns true.
writeln(" foobar ".stripRight!(a => a == ' ')()); // " foobar"
writeln("00223.444500".stripRight!(a => a == '0')()); // "00223.4445"
writeln("ùniçodêéé".stripRight!(a => a == 'é')()); // "ùniçodê"
writeln([1, 1, 0, 1, 1].stripRight!(a => a == 1)()); // [1, 1, 0]
writeln([0.0, 0.01, 0.10, 0.5, 0.6].stripRight!(a => a > 0.4)().length); // 3
void swap(T)(ref T lhs, ref T rhs) if (is(typeof(lhs.proxySwap(rhs))));
pure nothrow @nogc @trusted void swap(T)(ref T lhs, ref T rhs) if (isBlitAssignable!T && !is(typeof(lhs.proxySwap(rhs))));
Swaps lhs and rhs. The instances lhs and rhs are moved in
memory, without ever calling opAssign, nor any other function. T
need not be assignable at all to be swapped.
If lhs and rhs reference the same instance, then nothing is done.
lhs and rhs must be mutable. If T is a struct or union, then
its fields must also all be (recursively) mutable.
Parameters: T lhs |
Data to be swapped with rhs. |
T rhs |
Data to be swapped with lhs. |
Examples: // Swapping POD (plain old data) types:
int a = 42, b = 34;
swap(a, b);
assert(a == 34 && b == 42);
// Swapping structs with indirection:
static struct S { int x; char c; int[] y; }
S s1 = { 0, 'z', [ 1, 2 ] };
S s2 = { 42, 'a', [ 4, 6 ] };
swap(s1, s2);
writeln(s1.x); // 42
writeln(s1.c); // 'a'
writeln(s1.y); // [4, 6]
writeln(s2.x); // 0
writeln(s2.c); // 'z'
writeln(s2.y); // [1, 2]
// Immutables cannot be swapped:
immutable int imm1 = 1, imm2 = 2;
static assert(!__traits(compiles, swap(imm1, imm2)));
int c = imm1 + 0;
int d = imm2 + 0;
swap(c, d);
writeln(c); // 2
writeln(d); // 1
Examples: // Non-copyable types can still be swapped.
static struct NoCopy
{
this(this) { assert(0); }
int n;
string s;
}
NoCopy nc1, nc2;
nc1.n = 127; nc1.s = "abc";
nc2.n = 513; nc2.s = "uvwxyz";
swap(nc1, nc2);
assert(nc1.n == 513 && nc1.s == "uvwxyz");
assert(nc2.n == 127 && nc2.s == "abc");
swap(nc1, nc1);
swap(nc2, nc2);
assert(nc1.n == 513 && nc1.s == "uvwxyz");
assert(nc2.n == 127 && nc2.s == "abc");
// Types containing non-copyable fields can also be swapped.
static struct NoCopyHolder
{
NoCopy noCopy;
}
NoCopyHolder h1, h2;
h1.noCopy.n = 31; h1.noCopy.s = "abc";
h2.noCopy.n = 65; h2.noCopy.s = null;
swap(h1, h2);
assert(h1.noCopy.n == 65 && h1.noCopy.s == null);
assert(h2.noCopy.n == 31 && h2.noCopy.s == "abc");
swap(h1, h1);
swap(h2, h2);
assert(h1.noCopy.n == 65 && h1.noCopy.s == null);
assert(h2.noCopy.n == 31 && h2.noCopy.s == "abc");
// Const types cannot be swapped.
const NoCopy const1, const2;
assert(const1.n == 0 && const2.n == 0);
static assert(!__traits(compiles, swap(const1, const2)));
void swapAt(R)(auto ref R r, size_t i1, size_t i2);
Swaps two elements in-place of a range r,
specified by their indices i1 and i2.
Parameters: R r |
a range with swappable elements |
size_t i1 |
first index |
size_t i2 |
second index |
Examples: import std.algorithm.comparison : equal;
auto a = [1, 2, 3];
a.swapAt(1, 2);
assert(a.equal([1, 3, 2]));
Tuple! (InputRange1, InputRange2) swapRanges(InputRange1, InputRange2)(InputRange1 r1, InputRange2 r2) if (hasSwappableElements!InputRange1 && hasSwappableElements!InputRange2 && is(ElementType!InputRange1 == ElementType!InputRange2));
Swaps all elements of r1 with successive elements in r2.
Returns a tuple containing the remainder portions of r1 and r2 that were not swapped (one of them will be empty). The ranges may
be of different types but must have the same element type and support
swapping.
Returns: Tuple containing the remainder portions of r1 and r2 that were not swapped
Examples: import std.range : empty;
int[] a = [ 100, 101, 102, 103 ];
int[] b = [ 0, 1, 2, 3 ];
auto c = swapRanges(a[1 .. 3], b[2 .. 4]);
assert(c[0].empty && c[1].empty);
writeln(a); // [100, 2, 3, 103]
writeln(b); // [0, 1, 101, 102]
void uninitializedFill(Range, Value)(Range range, Value value) if (isInputRange!Range && hasLvalueElements!Range && is(typeof(range.front = value)));
Initializes each element of range with value.
Assumes that the elements of the range are uninitialized.
This is of interest for structs that
define copy constructors (for all other types, fill and
uninitializedFill are equivalent).
Parameters: Range range |
An
input range
that exposes references to its elements and has assignable
elements |
Value value |
Assigned to each element of range |
Examples: import core.stdc.stdlib : malloc, free;
auto s = (cast(int*) malloc(5 * int.sizeof))[0 .. 5];
uninitializedFill(s, 42);
writeln(s); // [42, 42, 42, 42, 42]
scope(exit) free(s.ptr);
|
