RE: [DUG]: iterators, deques etc

Paul Heinz Tue, 08 Oct 2002 15:28:35 -0700

Tracey asked:

we are learning about the c++ Builder STL at poly... a question was asked of me if Delphi has similar.

Does it?

Does Delphi have iterators and deques and queues??? I cant find them in the help.

The 'T' in STL stands for Templates and no, unfortunately Delphi doesn't have language support for them as yet. It may finally acquire them as MS Research is working on adding support for Generics (aka Templates) to .NET so to keep Delphi for Win32 and Kylix in sync with the coming Delphi for .NET, Borland _might_ implement a work-a-like.

Even then, I don't know if .NET generics will ever get as 'sophisticated' as C++ with partial instantiation and specialisation support plus function templates which STL depends on for it's coolness.

I wrote an external Macro preprocessor for Delphi so you can manually instantiate (i.e. expand a template) a template unit for a Linked List of <type> or Red Black Tree of <type> without having to hand code it. The templates are 'normal' Delphi units with some additional metacomments for the macros and a macro token pasting operator (the '|' token) - which is the same as ## in C. It's been quite useful for me (which is why I wrote it :-) but it's not as convenient as having template instantiation built right into the language.

By way of example, here's a sample snippet of a template:

-- snip --

unit tDList;

{
Doubly Linked List Class Template

{
Template Params

ItemType: 'Type of Item' = Pointer;
TypePrefix: 'Type Prefix' = u;
FreeItem(Item): 'Code for FreeItem' = FreeMem(Item);
}

{.DEFINE DEBUG}

interface

uses
Classes;

type
P|TypePrefix|DListNode = ^T|TypePrefix|DListNode;

T|TypePrefix|DList = class
private
    FOwnsItems: Boolean;
    FCount: Integer;
    FFirst: P|TypePrefix|DListNode;
    FLast: P|TypePrefix|DListNode;
protected
    function GetItem(Node: P|TypePrefix|DListNode): ItemType;
    procedure SetItem(Node: P|TypePrefix|DListNode; Item: ItemType);
{$IFDEF DEBUG}
    procedure Invariant; virtual;
{$ENDIF}
public
    constructor Create(OwnsItems: Boolean);
    destructor Destroy; override;
    procedure Clear;
    function Delete(Node: P|TypePrefix|DListNode): P|TypePrefix|DListNode;
    function Insert(Node: P|TypePrefix|DListNode; Item: ItemType): P|TypePrefix|DListNode;
    function Append(Item: ItemType): P|TypePrefix|DListNode;
    procedure Exchange(Node1, Node2: P|TypePrefix|DListNode);
    function Prior(Node: P|TypePrefix|DListNode): P|TypePrefix|DListNode;
    function Next(Node: P|TypePrefix|DListNode): P|TypePrefix|DListNode;
    function IndexOf(Node: P|TypePrefix|DListNode): Integer;
    function SeekIndex(Index: Integer): P|TypePrefix|DListNode;
    procedure Assign(List: T|TypePrefix|DList);
    procedure Reorder(List: TList);

-- snip --

If anyone on the Delphi list wants a copy of the template/macro processor and a sample template, drop me an email and I'll send you a copy.

Writing stack, queue and deque class templates would not be hard. You can take an existing implementation and turn it into a generic template with a search and replace (that's how I created my template units).

Iterators is a bit trickier since they are intended to work alongside function templates (as opposed to class temaplates) to support generic algorithms. I suppose you could use a combination of Delphi interfaces for the algorithms and class templates which produce adapters to support the interface.

Still, that would still require a virtual method call which would defeat the whole point of function templates. Hrmm... I wonder if it would be possible to support function templates and interators in my template processor. I'll have to cogitate on that one for a while...

As an aside, C++'s template infrastructure is actually Turing complete (and I just thought it was over-complicated :-) and you can effectively write rather 'interesting' templates in it that 'expand' to effectively evaluate values and produce code at compile time. This technique was first discovered and exploited in a scientific matrix numerics library called Blitz++ which uses this technique to produce optimised inline matrix handling code which rivals (and sometimes beats) hand-tuned C and Fortran!

Template metaprogramming is not for the faint hearted though - nor is it necessarily 'fast' to execute since you're co-opting the compilers template machinery but in scientific computing, the importantance of the speed of the resultant executable dwarfs the somwehat slower compile time.

TTFN,

Paul.

RE: [DUG]: iterators, deques etc

Reply via email to