my colleague created a custom hiearchical hash map structure three layers deep with an alternate data structure for fallback. this data structure always maintained sorted order and could be iterated through at any time in order. i think its purpose was part of a realtime image processing tool for cheating at online gambling (this was like 16 years ago). after the third collision, it would start as array in fallback and manually maintain sort after each operation within the same colliding hash. but eventually it would change from array to red-black tree based on a heuristic for when a large enough array would become more expensive to maintain than a red-black tree (his hash map, my red-black tree because at the time std::map and his own red-black tree implementations were both slower than mine). my red-black tree also had built-in internal memory management either as fixed size or non-fixed similar to ideal deque. that experience alone seems like it would make an always-sorted optimized data structure a worthy candidate to 1st party inclusion in any sufficiently complex programming language that includes a standard library as a part of its standard specification.
its the same like double double or quad double, when i originally ported QD from C into C++ / C# and had to maintain it myself (I think it has its own lightweight C++ wrapper now which they added years later).
http://crd-legacy.lbl.gov/~dhbailey/mpdist/
for lower level data structures there is something lost for their implementation as 3rd party versus 1st party. core data structures should be played close to the chest, and have a bigger benefit to being 1st party versus a higher level 3rd party library like a UI framework.
a high quality always-sorted data structure if 3rd party can eventually be adopted as an optional part of the standard similar to how c++ technical reports sometimes start as optional components in current versions of the standard and are eventually rolled into a future version of the standard as a requirement.
i am glad any compatible implementation exists 3rd party or not but i've been burned enough by 3rd party low level data structures that i am confident ease of use, adoption, and finding and fixing bugs may be an order of magnitude easier if such a thing were a 1st party component.
also i already have my own custom implementation of self-balancing red-black trees which is another reason i am less interested in a 3rd party solution. i've brought this up several years ago in the apple dev forums before swift went open source and got basically the same reaction, except last time there was not even a good 3rd party solution.
i think my original threads are gone since the apple dev forums revamp in 2015, so these links probably don't work (a quick try seems to fail though i might have to be logged in first)
my original red-black balanced binary tree code is here (2003 self-extracting zip as exe) but i've rewritten it at least twice since then (this is before i started using source control). so the code linked here is total crap but i thought i would put my money where my mouth is. i'll have to dig in my backup drive or dropbox for newer versions including the swift port i did and had linked to in the apple dev forum threads back in 2015 and had given away the ip to use as an example for a native implementation (i was between jobs at the time so could give away my code).
http://robert.seattleholograms.com/Robert_Aldridge.exe
ah i checked in dropbox i had a version that was heavy on C interop i don't remember if the native swift version ever worked. this may have been a work-in-progress swift version. i was still figuring out the subtleties between swift's struct and class. copy-on-write may not have been well understood at the time. early 2015.
right the community owes me nothing. i understand that. though i am also talking about the 30+ year history of objective c and slightly shorter history of objective c++ never rolling in an always-sorted optimized data structure. the history of the issue is not just with swift. sorry if i come off so negative i've been waiting almost as long for a similar data type to be added to native java i still don't think it exists. c# i think has SortedList though i'm not sure that data structure is optimized internally.
c++ might be unique in that it tackles so many data types natively even the ones that are either inefficient or difficult to implement. stp::map is great though my favorite is std::deque since a perfectly implemented deque is effectively constant cost for nearly all operations including the cost of underlying memory management if you fudge the bit depth as a constant factor and then drop it out (though a properly abstracted list data type could internally use deque). some of the pushback may also be that swift prefers to not expose underlying data types but only what is at the higher level. it makes sense to have a few highly-abstracted high level data types though i think it would be a mistake to not also expose some of the inner data types directly for specialized use.
i am grateful for all the responses even the negative ones thank you.
ps off topic: i'm also waiting for apple's custom a series gpus to add native double precision support (i can't deal with single precision). the hard ai push for half precision support in gpu is not helping my cause (it practically mocks me). i am an evangelist for double double and quad double. though unless i am pushing for ieee quad double support in swift this is unrelated.
