On Tuesday, 9 June 2015 at 17:05:19 UTC, Andrei Alexandrescu
wrote:
[snip]
One would be a good pass of std.container, in particular (a) a
design review with the DbI glasses on; (b) better documentation
- sadly it seems to me so inadequate as to make containers
themselves unusable; (c) investigate use of UFCS -
std.container's design predates UFCS yet is a perfect fit for
it, and most likely other cool language improvements we've
added since.
[snip]
Containers without a doubt. They are so fundamental to my day to
day programming it's amazing that D has gone for so long without
a good set of them (dynamic arrays and associative arrays do go a
long way though).
I might as well share some thoughts on it.
Containers that should be in the standard library in order of
preference (from my C++ STL and Boost experience primarily):
1. vector/array
2. hash map
3. hash set
4. flat map
5. flat set
6. map
7. set
8. deque
9. stack
10. queue
11. linked list
12. hash multimap
13. hash multiset
14. flat multimap
15. flat multiset
16. multimap
17. multiset
18. priority queue
We already have Array for 1 but the interface needs improvement
(I seem to recall having trouble with mutating items during
iteration or something like that which caused me to go back to
dynamic arrays). I don't think I like that it's RefCounted
either. r-value references have made C++'s vector much more
pleasant to efficiently work with in C++. We also have map in the
form of RedBlackTree. I think you might be able to use
RedBlackTree for a set too but I haven't tried it. I think
RedBlackTree isn't a very good name though. It's long and is an
implementation detail.
We have hash maps in the form of the built-in associative arrays
but something that uses the allocators rather than GC is needed.
"Flat" refers to containers that are backed by sorted arrays
rather than something like a Red-Black Tree. Insertion speed
suffers but in practice, thanks to cache locality and move
semantics and fast contiguous memory copying, they are generally
much faster than the traditional map backed by something like a
red-black tree for the majority of operations. Andrei put them in
loki so I'm preaching to the choir here but for anyone that
doesn't know about their advantages here's an article:
http://lafstern.org/matt/col1.pdf and the Boost container
library's rationale:
http://www.boost.org/doc/libs/1_56_0/doc/html/container/non_standard_containers.html#container.non_standard_containers.flat_xxx
Chandler Carruth spent a lot of time talking about this stuff at
CppCon 2014 as well: https://www.youtube.com/watch?v=fHNmRkzxHWs
As far as more exotic containers go, I rather like
Boost.MultiIndex which lets you have a container with several
different characteristics (e.g., a single container where you can
look up based on name, based on id, based on insertion order,
based on lexicographic order of name, etc.). You basically design
the perfect container for your needs ("I need random access and
fast lookups and a sorted list and bidirectional lookups between
keys and values"). It's the swiss army knife of containers. I
don't need it often but when I do I love it. I believe someone
said they implemented it for D but I haven't looked into it.
Although less versatile, building multi-indexing into most
containers could prove useful too. Spitballing an example with
plenty of room for improvement:
struct A { string name; int id; }
Map!(A, ((a, b) => a.name < b.name),
((a, b) => a.id < b.id)) a_map;
a_map.insert(A("bob", 7));
assert(a_map.index!0["bob"].id == 7);
assert(a_map.index!1[7].name == "bob");
A trie would be nice to have even though I rarely use them.
Boost has a stable_vector as well which is basically just an
array that uses indirection to keep iterators valid through
insertions/deletions. I could see it being useful but I haven't
used it.
