Personal note: This is a labor of love. While working on the D programming language I’ve been mulling on a new abstraction for iteration and algorithms, and after many false starts I was ready to admit I was unable to define a significantly improved design. But I was desperate to fix some of STL’s shortcomings, and often desperation causes inspiration; I finally stumbled upon an abstraction that was stupidly simple, dead obvious, and yet surprisingly powerful. A few months and a superset of STL later, ranges were ready for prime time. Compatible containers were soon to follow.
Abstract:
It is fair to say that containers and iterators have been with us ever since the early days of high-level languages. Fortran was all about arrays, and Lisp used lists simultaneously as containers and their iterators. Object oriented languages brought elaborate container hierarchies and nomenclatures on the table, and just as the GoF was about to make iterators famous, the STL added one more twist to the plot: iterators are not just for iteration - they are a veritable liaison between containers and algorithms.
But that’s so 1994. Has the matter been settled for good? A closer look reveals many holes in the dam. Tries cannot be expressed in the STL. Heaps are not really containers - iterating a heap is destructive. Bloom filters - highly useful structures for searching - defy any classification. And STL iterators have their issues, too. No operation on an STL iterator can be made reasonably safe. Composition is tenuous - you need to pass two iterators, not one, to get anything done. Pointer syntax and approximate pointer semantics have been a mixed blessing.
This talk casts a fresh look at containers and iterators. It draws from extensive experience with designing the standard library for the D programming language. D features a simple yet comprehensive approach to containers, and also ranges - an obvious-in-hindsight, how-in-the-world-has-nobody-thought-of-that-before approach to iteration and algorithms. As usual, the deity - be it divine or fallen - is in the details, which the talk has a fair amount of. Get ready to iterate through it.
October 15, 2010 at 10:52 am
I expect that a good portion of the attendees to this conference were at BoostCon 2009 when you discussed this matter. I’ll be interested in seeing how the idea has developed since then.
November 28, 2010 at 8:21 pm
[…] note: Following the C++ and Beyond seminar in October, I decided to replace the session “A Fresh Look at Containers and Iterators”. This is because the topic, albeit generous, has limited immediate applicability. Although the C++ […]