[boost] [Range] Expected complexity constraints

From: David Abrahams (dave_at_[hidden])
Date: 2006-05-08 08:19:28

I note that the range library still supports the following:

  * treating null-terminated strings as Ranges where the complexity of
    end(s) is O(N)

  * treating pairs of non-random-access iterators as Ranges where the
    complexity of size(p) is O(N)

In my view both of these would ideally be eliminated.  The argument
for the latter is slightly weaker because of prcedent in the std,
although the LWG is considering removing it.

Possible alternatives distinguish the ranges that actually give the
expected complexity:

  a. Provide separate concepts for O1EndRange and O1SizeRange

  b. Provide traits to detect has_o1_end and has_o1_size

Probably you'd want to do both.

By the way, you can get back O(1) for end(s) where s is a
null-terminated string if you allow the end iterator to have a
different type from the begin iterator... but those ranges don't play
well with the standard algorithms.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com