D (The Programming Language)/d2/Slicing
Lesson 9: Slicing and a Deeper Look into Dynamic Arrays
editSlicing in D is one of the language's most powerful and useful aspects. This lesson is really more of a continuation of the last lesson - you will also get a deeper look into how D's arrays work.
Introductory Code
editimport std.stdio;
void writeln_middle(string msg)
{
writeln(msg[1 .. $ - 1]);
}
void main()
{
int[] a = [1,3,5,6];
a[0..2] = [6,5];
writeln(a); // [6, 5, 5, 6]
a[0..$] = [0,0,0,0];
writeln(a); // [0, 0, 0, 0]
a = a[0 .. 3];
writeln(a); // [0, 0, 0]
a ~= [3,5];
writeln(a); // [0, 0, 0, 3, 5]
int[] b;
b.length = 2;
b = a[0 .. $];
writeln(b.length); // 5
b[0] = 10;
writeln(b); // [10, 0, 0, 3, 5]
writeln(a); // [10, 0, 0, 3, 5]
writeln_middle("Phobos"); // hobo
writeln_middle("Phobos rocks");
}
Concepts
editWhat are Slices?
editYou can take slices of arrays in D with this syntax:
arr[start_index .. end_index]
The element at end_index
is not included in the slice.
Remember that dynamic arrays are just structures with a pointer to the first element and a length value. Taking a slice of a dynamic array simply creates a new one of those pointer structures that points to the elements of that same array.
string a = "the entire part of the array";
string b = a[11 .. $]; // b = "part of the array"
// b points to the last 17 elements of a
// If you modify individual elements of b, a will also
// change since they point to the same underlying array!
Three Ways to Do the Same Thing
editNotice that the $
is automatically replaced with the length of the array being sliced from. The following three lines are equivalent and both create slices of the entirety of an array arr
.
char[] a = arr[0 .. $];
char[] a = arr[0 .. arr.length];
char[] a = arr[]; // shorthand for the above
A Visual Representation
editThe .capacity
Property
edit
All dynamic arrays in D have a .capacity
property. It is the maximum number of elements that can be appended to that array without having to move the array somewhere else (reallocation).
int[] a = [1,2,3,45];
writeln("Ptr: ", a.ptr);
writeln("Capacity: ", a.capacity);
a.length = a.capacity; // the array reaches maximum length
writeln("Ptr: ", a.ptr, "\nCapacity: ", a.capacity); // Still the same
a ~= 1; // array has exceeded its capacity
// it has either been moved to a spot in memory with more space
// or the memory space has been extended
// if the former is true, then a.ptr is changed.
writeln("Capacity: ", a.capacity); // Increased
Maximizing Efficiency by Only Reallocating When Necessary
editIt is good for efficiency to make sure that appending and concatenation do not cause too many reallocations because it is an expensive procedure to reallocate a dynamic array. The following code may reallocate up to 5 times:
int[] a = [];
a ~= new int[10];
a ~= [1,2,3,4,5,6,7,8,9];
a ~= a;
a ~= new int[20];
a ~= new int[30];
Make sure that the array capacity
is big enough at the beginning to allow for efficient non-reallocating array appends and concatenations later if performance is a concern.
You can't modify the .capacity
property. You are only allowed to either modify the length, or use the reserve
function.
int[] a = [1,2,3,45];
a.reserve(10); // if a's capacity is more than 10, nothing is done
// else a is reallocated so that it has a capacity of at least 10
When Passed to Functions
editRemember that D's arrays are passed to functions by value. When static arrays are passed, the entire array is copied. When a dynamic array is passed, only that structure with the pointer to the underlying array and the length is copied - the underlying array is not copied.
import std.stdio;
int[] a = [1,2,3];
void function1(int[] arr)
{
assert(arr.ptr == a.ptr); // They are the same
// But the arr is not the same as a
// If arr's .length is modified, a is unchanged.
// both arr and a's .ptr refer to the same underlying array
// so if you wrote: arr[0] = 0;
// both arr and a would show the change, because they are both
// references to the same array.
// what if you forced arr to reallocate?
arr.length = 200; // most likely will reallocate
// now arr and a refer to different arrays
// a refers to the original one, but
// arr refers to the array that's reallocated to a new spot
arr[0] = 0;
writeln(arr[0]); // 0
writeln(a[0]); // 1
}
void main()
{
function1(a);
}
As you can see, there are a few possibilities if you pass a dynamic array to a function that looks like this:
void f(int[] arr)
{
arr.length = arr.length + 10;
arr[0] += 10;
}
- First possibility: the array's capacity was large enough to accommodate the resizing, so no reallocation occurred. The original underlying array's first element was modified.
- Second possibility: the array's capacity was not large enough to accommodate the resizing, but D's memory management was able to extend the memory space without copying the entire array. The original underlying array's first element was modified.
- Third possibility: the array's capacity was not large enough to accommodate the resizing. D's memory management had to reallocate the underlying array into a completely new space in memory. The original underlying array's first element was not modified.
What if you want to make sure that the following works?
int[] a = [0,0,0];
f(a);
assert(a[0] == 10);
Simply change the function f
so that dynamic arrays are passed by reference:
void f(ref int[] arr)
{
arr.length = arr.length + 10;
arr[0] += 10;
}
Appending to Slices
editWhen you take a slice of a dynamic array, and then append to that slice, whether the slice is reallocated depends on where the slice ends. If the slice ends in the middle of the data from the original array, then appending to that slice would cause a reallocation.
int[] a = [1,2,3,4];
auto b = a[1 .. 3];
writeln(b.capacity); // 0
// b cannot possibly be appended
// without overwriting elements of a
// therefore, its capacity is 0
// any append would cause reallocation
Lets say you took a slice of a dynamic array, and that slice ends at where the dynamic array ends. What if you appended to the dynamic array so that the slice no longer ends at where the dynamic array's data ends?
int[] a = [1,2,3,4];
writeln(a.capacity); // 7
auto b = a[1 .. 4];
writeln(b.capacity); // 6
a ~= 5; // whoops!
// now the slice b does *not* end at the end of a
writeln(a.capacity); // 7
writeln(b.capacity); // 0
The .capacity
property of a slice does indeed depend on other references to the same data.
Assignment-To-Slices
editAn Assignment-To-Slice looks like this:
a[0 .. 10] = b
You are assigning b
to a slice of a
You have actually seen Assignment-to-Slices in the last two lessons, even before you learned about slices. Remember this?
int[] a = [1,2,3];
a[] = 3;
Remember that a[]
is shorthand for a[0 .. $]
When you assign a int[]
slice to a single int
value, that int
value is assigned to all the elements within that slice.
An Assignment-To-Slice always causes data to be copied.
int[4] a = [0,0,0,0];
int[] b = new int[4];
b[] = a; // Assigning an array to a slice
// this guarantees array-copying
a[0] = 10000;
writeln(b[0]); // still 0
Beware! Whenever you use Assignment-To-Slice, the left and right sides' .length
values must match! If not, there will be a runtime error!
int[] a = new int[1];
a[] = [4,4,4,4]; // Runtime error!
You also must make sure that the left and right slices do not overlap.
int[] s = [1,2,3,4,5];
s[0 .. 3] = s[1 .. 4]; // Runtime error! Overlapping Array Copy
Vector Operations
editLet's say you wanted to double each and every integer element of an array. Using D's vector operation syntax, you can write any of these:
int[] a = [1,2,3,4];
a[] = a[] * 2; // each element in the slice is multiplied by 2
a[0 .. $] = a[0 .. $] * 2; // more explicit
a[] *= 2 // same thing
Likewise, if you wanted to perform this operation: [1, 2, 3, 4] (int[] a) + [3, 1, 3, 1] (int[] b) = [4, 3, 6, 5] You would write this:
int[] a = [1, 2, 3, 4];
int[] b = [3, 1, 3, 1];
a[] += b[]; // same as a[] = a[] + b[];
Just like for Assignment-To-Slice, you have to make sure the left and right sides of vector operations have matching lengths, and that the slices do not overlap. If you fail to follow that rule, the result is undefined (There would be neither a runtime error nor a compile-time error).
Defining Array Properties
editYou can define your own array properties by writing functions in which the first argument is an array.
void foo(int[] a, int b)
{
// do stuff
}
void eggs(int[] a)
{
// do stuff
}
void main()
{
int[] a;
foo(a, 1);
a.foo(1); // means the same thing
eggs(a);
a.eggs; // you can omit the parentheses
// (only when there are no arguments)
}
Tips
edit- Steven Schveighoffer's article "D Slices" is an excellent resource if you want to learn more.