D (The Programming Language)/d2/Slicing

Lesson 9: Slicing and a Deeper Look into Dynamic Arrays

Slicing 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

import 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

What are Slices?

You 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

Notice 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

The .capacity Property

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

It 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

Remember 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

When 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

An 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

Let'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

You 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

• Steven Schveighoffer's article "D Slices" is an excellent resource if you want to learn more.