[boost] Re: [Formal review] Collection Traits library

From: David Abrahams (dave_at_[hidden])
Date: 2004-05-07 11:13:52

"Thorsten Ottosen" <nesotto_at_[hidden]> writes:

> "Peter Dimov" <pdimov_at_[hidden]> wrote in message news:00f601c43438$67a5ab60$1d00a8c0_at_pdimov2...
> | Thorsten Ottosen wrote:
> | > "Peter Dimov" <pdimov_at_[hidden]> wrote in message
> | > news:003b01c4337c$83b49df0$1d00a8c0_at_pdimov2...
> | >> Thorsten Ottosen wrote:
> | > [snip]
>
> | >> Range is begin(), end();
> | >
> | > So you want size() and empty() to be removed from the Range Traits?
> |
> | I just omitted them for brevity, but since you ask, size() is essential
> | since it can be O(1) when distance( begin(), end() ) is O(N), but it seems
> | to me that empty() is always begin() == end(), so it can be removed.
> | (begin() and end() should be O(1).)
>
> hm...empty() is O(N) for strings if implemented as end() - begin(), but
> O(1) currently.

What kind of string doesn't have random-access iterators? Or are you
talking about C-strings which would have an O(N) end() function?

I am leery of performance discontinuities like O(N) for end(char
const*).  Maybe it just shouldn't be provided (or something).

-- 
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com