Re: [boost] Concepts talk on Google Video

From: Michael Marcin (mike_at_[hidden])
Date: 2007-03-13 12:46:12

Douglas Gregor wrote:
> On Tue, 2007-03-13 at 03:07 -0500, Michael Marcin wrote:
>> I'm not too familiar with the upcoming standard proposals.  After this 
>> talk I feel I could go and reimplement most of my template libraries 
>> with concepts fairly easily.  So kudos to you.
> 
> Thanks! (from *us*; lots of people are involved in concepts)
> 
>> One thing that is central to the STL that I might have missed from this 
>> talk is complexity guarantees.  Is there a way to promise STL's big O 
>> complexity guarantees with concepts?
> 
> No, there isn't. We haven't really seen a good way to describe
> complexity. Even if we did, it's unclear how useful it would be except
> as documentation. We couldn't verify the complexity (except in very
> simple cases), and it's unlikely to help in program testing or
> optimization.
> 

Actually thinking on it some more I think my main worry isn't a problem. 
  Lets say I have an iterator class that has an operator + convenience 
function that just internally does a slow O(n) loop of operator ++'s. 
Now IIUC having operator + alone isn't enough to make it choose a 
RandomAccessIterator overload over an InputIterator overload because I 
didn't specialize the concept map for this type, right?

Another note, I'm probably in the minority but many of the platforms I 
work on don't have FPU's and thus we use fixed point math.  In the 
current STL and many libraries we have to specialize methods that claim 
to require floating point types.  It feels to me like we are lying by 
specifying floating point traits for fixed point types. Perhaps the 
concept you referred to a in an early post of Floating could be a 
refinement of a concept for types with sub integral precision so that 
fixed point types can meet the requirements of most things floating 
point types can without lying.

Thanks,

Michael Marcin