Why is D missing container classes?

Question

I'm used to C++ STL containers. D has arrays, associative arrays, and strings, but where is the rest? I know about std.container, but as far as I can tell it only has one container, the red-black tree, which I could use if I needed something similar to std::set. But, what if I need a list? Am I supposed to use an array instead?

std::vector -> array

std::deque -> ?

std::queue -> ?

std::stack -> ? maybe array and std.container functions ?

std::priority_queue -> BinaryHeap

std::list -> ?

std::set -> std.container RedBlackTree

std::multiset -> ?

std::unordered_set -> ?

std::map -> associative arrays

std::multimap -> ?

std::unordered_map -> ?

Are there any plans to support any of the missing?

Answer 1

I believe that the main holdup for getting more containers into std.container is that Andrei Alexandrescu has been sorting out how best to deal with custom allocators, and he wants to do that before implementing all of the sundry container types, because otherwise it's going to require a lot of code changes once he does.

In the interim, you have the built-in arrays and associative arrays, and std.container contains Array (which is essentially std::vector), SList (which is a singly-linked list), RedBlackTree (which can be used for any type of set or map which uses a tree - which is what the STL's various set and map types do), and BinaryHeap.

So, there's no question that the situation needs to be improved (and it will), but I don't know how soon. Eventually, std.container should have container types which correspond to all of the STL container types.

Answer 2

Containers are a todo in terms of library development in D, but noone's gotten a comprehensive container library into Phobos because noone agrees on what the design should be, and everyone who contributes to the standard library (which has been growing very rapidly) has found more interesting things to work on.

std::vector -> array as you say

std::dequeue, std::queue: We don't have one yet, unfortunately.

std::stack: This can be trivially implemented on top of SList or an array.

std::set: This can be trivially implemented on top of either RedBlackTree.

std::multiset: I think RedBlackTree can be set to allow duplicates.

std::unordered_set: This can be trivially implemented on top of the builtin associative array. To implement it on top of the builtin AA, use byte[0][SomeType].

std::map: Can be trivially implemented on top of RedBlackTree.

std::multimap: You can probably use associative arrays of arrays for this.

std__unordered_map: Use builtin associative arrays.