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