Containers

[pbackus]

Phobos v3 should have a library of generic, general-purpose containers, suitable for as many use-cases as can be reasonably supported. Most D programmers should not have to look for containers outside the standard library.

Desired Features

• Should include a broad selection commonly-used data structures (dynamic array, hash table, binary tree, linked list, etc.).
• Should work with generic algorithms via the range interface.
• Individual container elements should be addressable by index/key/"cursor".
• Containers should have value semantics.
• Should be usable in as many kinds of D code as possible. In particular:
  • Should work in @safe, @nogc, and nothrow code.
  • Should work in BetterC code (possibly with a reduced feature set).

Current Status

Phobos's current container library is the std.container package.

It has several shortcomings:

• The selection of data structures is not as broad as it could be. Some possible additions:
  • Hash table
  • Ring buffer
  • Multidimensional array
  • B-tree
  • TODO: any more?
• Many common operations (e.g., inserting or removing an element in the middle of an array) are extremely cumbersome because they are done with ranges rather than an index or cursor.
  • The concept of a container's "primary range" makes this especially awkward, because it requires users to know which algorithms return a range of the same type they are given, and which ones return a new range type. Normally, ranges are structurally typed, and it is not necessary to know a range's concrete type.
• Containers have reference semantics, which makes inclusion of containers with unique ownership of elements (e.g., UniquePtr!T) impossible without introducing inconsistency.

Examples In Other Languages

• Java's Collections Framework
• C++'s containers library
• Rust's std::collections module

Related Topics

• @safe Allocators
• Ranges (TODO: link discussion when posted)

[crazymonkyyy]

TODO: what are users asking for that's missing?

off the top of my head for me:

circularBuffer - array that has no allocation, and no overflowing by trading off correctness
nullablesArray - elements are assoated with bools and can be set to null which will filter it from being used, allowing for random deletion without grabbing a linked list, while keeping order and references sane-ish
2dArray - 2d slicing, width and height can be defined to match use
lookaheadBuffer - often i'll use .array for random access of strings where I just need to know "is that a '\n'", a inline data struct that knows how to grab from a range, and use opIndex to give small slices

[pbackus]

Ring buffer and multidimensional array are both pretty common; I'll add them to the list.

The other two, I've never heard of before. Do you know of any examples of them in other languages or libraries?

[crazymonkyyy]

I use this rn (foreach doesnt work with ref, should be smarter about inserting)

struct nullablearray(T,int N){
	T[N] data;
	bool[N] nulls=true;
	alias THIS=typeof(this);
	enum N_=N;
	ref opIndex(size_t i){
		return data[i];
	}
	auto opSlice(){
		struct filter{
			THIS* parent;
			size_t index;
			bool empty=false;
			auto front()=> tuple!(size_t,T)(index,(*parent)[index]);
			void popFront(){
				loop:
					index++;
					if(index==N){empty=true; return;}
					if((*parent).nulls[index]){ goto loop;}
			}
		}
		auto o=filter(&this,0);
		if(nulls[0]){o.popFront;}
		return o;
	}
	void opIndexAssign(T value,size_t i){
		data[i]=value;
		nulls[i]=false;
	}
	void opIndexAssign(typeof(null),size_t i){
		nulls[i]=true;
	}
	void opOpAssign(string s:"~")(T v){
		foreach(i,b;nulls){
			if(b){
				this[i]=v;
				return;
			}
		}
	}
}
unittest{
	import std;
	nullablearray!(int,10) foo;
	foo.nulls.writeln;
	foo[0]=3;
	foo[4]=5;
	foo[8]=0;
	foo.nulls.writeln;
	foreach(i,e;foo[]){
		e.writeln;
	}
	"----".writeln;
	foo[4]=null;
	foreach(i,e;foo[]){
		e.writeln;
	}
	foo.nulls.writeln;
	foo~=2;
	foo~=7;
	foo.nulls.writeln;
	foreach(i,e;foo[]){
		e.writeln;
	}
}

I know ive seen it as a "pattern" but injected in a game object struct as "isAlive"/"isActive", the inverse of a "dirty" flag

https://gameprogrammingpatterns.com/dirty-flag.html

---

lookaheadBuffer should probably be a circularbuffer + (forward) range => range with random access

I know ive tried to do it sometimes but .array is easier even if its obviously very slow

[crazymonkyyy]

ndarrays

I'm unsure how many people go higher then, 3 or even 4d; while yes d can do it; is it going to be better then making 2d as good as possible

When I made that 4d chess demo I used 2d arrays of 2d arrays, as thats how I actually think of even something that complex, i'd consider making 2d arrays, and maybe seeing if people actually want a managed 3d array

[LightBender]

I would like to see the following containers:

1. Key-Value Pairs (sometimes call Dictionary)
2. Stack (hopefully "concurrent" safe)
3. Queue (hopefully "concurrent" safe)

Another one that I would like to see that has been more controversial is what C# calls a List type, where you can arbitrarily Add/Remove from any location.

[crazymonkyyy]

If the formal acedimia ones are added; I think the most important one is Set, even if its just a wrapper for void[T]

[pbackus]

The first 3 are all abstract data types that can be implemented with multiple data structures. I agree that data structures implementing these ADTs should be included; please suggest any you think are missing.

It looks like C#'s List<T> is implemented using an array data structure, so we should be able to cover that by giving our Array container methods for inserting and removing elements at arbitrary locations (insertAt/removeAt). (Technically std.container.array already supports this, but it's a pain to use.)

[pbackus]

@crazymonkyyy It looks like the most common data structures used to implement sets are hash tables and binary trees.

Probably worth asking, should we just provide data structure implementations, or should we also have wrappers that implement a particular ADT on top of a data structure? Several languages do this—e.g., Java and Rust both have a HashSet container that's basically a wrapper around HashMap.

[crazymonkyyy]

Id straight up just use aa's and a 10 line struct

I'm stilling waiting to see if the style guide and culture is shifting towards simplicity, this may be a good litmus test, set's should reuse something else, and be mostly about having good opOverloads; if the design by community and saftyphila win I will expect 500 line monsterousity like the old nullable

[kassane]

Allocators (TODO: link discussion when posted)

If it is the case that there are no implicit allocations, it would be interesting to try to highlight std.experimental.allocator and use it explicitly when necessary in some containers.
A reference for this is Zig. However, D has certain RAII advantages that could be better suited to it, which Zig doesn't have.

Some References

• zig: std.Ring Buffer
• Zig HashMap (alloc/noalloc)
  Zig-Stdlib doc in #Types section have all containers.
• Polymorphic allocators

[pbackus]

Allocators are a good idea, although std.experimental.allocator probably needs a v2 upgrade first. See #11.

[ichordev]

• Multidimensional array

Why can't multidimensional arrays be created by nesting the existing std.container.array type?

import std.container.array;
import std.stdio;

void main(){
	auto x = Array!(Array!uint)(Array!uint(10, 11, 12), Array!uint(20, 21, 22));
	writeln(x[0][2]);
}

[PetarKirov]

https://github.com/libmir/mir-algorithm is much better from efficiency and ease of use point of view (uses multi-dimensional opIndex and opSlice)

[Moth-Tolias]

I would love to see a c++ ordered_map equivalent.

[apbryan]

What value does a "Hash table" provide over an associative array?

If we're passing in an allocator to the container, I think it makes sense to:

1. Only do so at compile time (how do you deallocate older data if you've changed the allocator at runtime?)
2. Default to the GC allocator