== Quote from Andrei Alexandrescu (seewebsiteforem...@erdani.org)'s article > Michel Fortin wrote: > > On 2009-07-28 19:59:30 -0400, Andrei Alexandrescu > > <seewebsiteforem...@erdani.org> 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).
To be fair, distance is as fast as the iterator allows. If you pass a random access iterator it's O(1).