Complexity nomenclature

[Andrei Alexandrescu via Digitalmars-d]

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.

Another way to look at it: in STL container-independent code is near 
impossible because different containers use the same signature for 
operations that are different (either wrt iterator invalidation or 
complexity). My design avoids that by giving distinct operations 
distinct names.


Andrei