Version 3 (modified by Nietsnie, 16 years ago) |
---|
Collection Improvement Proposal
This page is intended to discuss and keep track of ideas on how to improve the collections and iterators on the current Tango collection package. The collection package is based on Doug Lea's collection package, which was released into the public domain in 1999, so it is substantially out of date.
Goals
- Allow iterators that can remove elements while iterating over the collection
- Allow bi-directional iterators when appropriate
- Allow saving iterators into the middle of collections (such as for later removal or traversal)
- Allow slicing
- Explore collection concepts from other languages and how we can benefit from using their ideas.
Modifiable iterators
At the very least, an iterator should be able to remove the last iterated element. I have modified the current tree to allow this (see #965), but with the current iterator design, no other modifications make sense. For example, iterators provide a remaining() method, but this could potentially be a O(n) operation if the underlying container was modified.
Bi-directional iterators
This should be possible with the current collections package for containers that support it.
Copying of iterators to use in later operations
The current model is focused on only having one iterator into a container at a time, but there can be reasons to have multiple iterators. One example is to allow later removal of elements after the first search has found them in O(1) time.
Allow slicing
The rest of D is based on slicing, why can't slicing be available for collections too?
Explore other language collection constructs
There are plenty of good collection implementions to look at:
- C#
- C++ STL
- Java (which was based on Doug Lea's I think)
- Others?
References
Ticket on allowing iterator removal: #965 Ticket on allowing null keys/values in Hash: #626
Discussion
Attachments
- Cache.d (5.0 kB) -
Example of generic functionality that could be added to collection. (As a Cache, but could also be added simply as a MRU/LRU or BoundedList?)
, added by darrylb on 03/05/08 20:54:11. - collection.tgz (20.4 kB) -
New implementation of Collections to consider (re-implements lots of collection, using more D-style than Java style)
, added by schveiguy on 03/18/08 20:58:35.