sequences

[ajb at spamcop.net]

G'day all.

Quoting ross at soi.city.ac.uk:

> I don't think
> default definitions are quite as useless as Chris suggests: often there
> is a most common default; in some other cases there is a choice, but
> you have a family of methods that will all decide the same way, so you
> can delegate to one member of the family.

Well spotted!

(Disclaimer: Mention of STL follows.  Potential Godwin's Law issues, so
proceed with caution.)

One thing which isn't often appreciated about the STL is that they key
thing which everything rests on is the iterator category.  The details
are unimportant, but the whole thing rests on what operations a specific
iterator supports.  The key features are:

    - Can the iterator be read from?
    - Can the iterator be written to?
    - Can you move it forwards (implies that it can be read from)?
    - Can you move it backwards (implies that you can move it forwards)?
    - Can you jump randomly (implies that it can be moved backwards)?

The key point is that choosing which algorithm is the most efficient for
some container can be determined from the iterator categories alone.

In principle, it shouldn't be too hard to identify families of
sequences/associations/collections all of which support a certain
efficient default, and to associate the family with the collection.

Cheers,
Andrew Bromage