On Saturday, 28 December 2013 at 16:35:41 UTC, Jakob Ovrum wrote:
I have *no* idea where you got this idea from. D and its standard library follows in the footsteps of STL when it comes to the algorithmic complexity of primitives
STL is not great, has never been great, and probably will never be great. Cool idea, bad execution for the language it was implemented in. So they had to change C++ to support i better! :-P
How much time does a committee need to agree on a hash-table implementation? Or should I say decades? STL is so designed-by-a-committee that it hurts. It is not a shining star! Not at all.
STL is ok for early prototyping with C++11, but if you care about performance you roll your own.
an important tenet from *at least* the early days of D2. A few examples include std.container's maximum complexity requirement for primitives (including `length`) and the existence of
Single linked lists is very useful for situations where you want lists that are mostly empty or short, but where you do not want to impose an upperbound. O(N) on length() does not matter much in many real-world scenarios.
What you want is a (mild) warning if you use a templated algorithm and that algorithm use a O(N) primitive where it is invisible to the library user. A warning you should be able to suppress (basically telling the compiler "trust me, this is deliberate").
std.range.walkLength. A recent example of enforcement includes the rejection of adding binary `in` functionality for non-associative arrays.
Why is that? If your non-associative array on average is of length 3-4 then it might outperform an associative array.
Just like insertion sort will outperform other sorts for mostly-sorted arrays where the elements are offset by jitter (so they are 3-4 elements out-of-place). O(N*N) can easily beat O(N) if the dataset is a good fit. If not, everybody would use radix-sort and nobody would even consider quicksort.
Worst case analysis assuming unbounded arbitrary input is only of theoretical interest, in the real world you care about the average cost over the dataset you actually run the algorithm on. Unless you write hard realtime systems (life-support, weapon systems, etc).
You could say this about any restriction in the type system. (`@obsolete`? Did you mean `deprecated`?)
(sure, or "@forbid" or "@notimplemented" etc)
