Michel Fortin wrote:
On 2009-07-28 19:59:30 -0400, Andrei Alexandrescu
<[email protected]> said:
The way Phobos does things is the following:
a) You must define .empty which completes in O(1).
b) If you can define .length with O(1), define it, otherwise don't.
Then Phobos defines walkLength() on a best-effort basis which is
guaranteed to finish in O(n) but may finish faster. It uses .length if
defined, or else it just iterates the range to exhaustion.
This looks like a good approach. I'm just not too thrilled by the name
"walkLength". But perhaps I'm the only one.
STL defines distance() but people tend to forget it's O(n). So I chose a
name that makes it rather obvious it's O(n).
Andrei
