Complexity nomenclature

[tn via Digitalmars-d]

On Friday, 4 December 2015 at 03:37:10 UTC, Andrei Alexandrescu 
wrote:
> On 12/3/15 10:29 PM, Jack Stouffer wrote:
>> On Friday, 4 December 2015 at 02:21:12 UTC, Andrei 
>> Alexandrescu wrote:
>>> On 12/03/2015 09:10 PM, Idan Arye wrote:
>>>> The complexities of the operations is a property of the data 
>>>> structure
>>>> being used. If each collection type will have it's own set 
>>>> of method
>>>> names based on the complexity of operations on it, we won't 
>>>> be able to
>>>> have templated functions that operate on any kind of 
>>>> collection(or at
>>>> the very least, these functions will be really tedious to 
>>>> code).
>>>
>>> Your premise is right but you reach the negation of the 
>>> correct
>>> conclusion. -- Andrei
>>
>> How so? If a singly linked list and a doubly linked list have 
>> two
>> different method names for the same operation, then they 
>> cannot be
>> easily templated.
>
> Took me a while to figure. There's a hierarchy of operations, 
> e.g. if a collection implements insert, it automatically 
> implements linearInsert. And so on. The collections framework 
> provides these defaults, so client code that needs quick insert 
> uses insert, whereas code that's fine with a linear upper bound 
> uses linearInsert and captures both.

"I just want to insert an element. I don't care how long it 
takes. Why do I need to specify that it should be linear?"

In my opinion, there should be "constantInsert", "linearInsert", 
etc. for those who care about the complexity, and "insert" should 
be always available.