@Araq - fabulous. I think a B-Tree in the stdlib would be great.
@mratsim - I think you meant `collections.intsets` with a 't' which does _not_
yield items() in key order.
The built-in `set[up to int16]` type _does_ (implicitly) order its keys,
though. @cdome also did not mention how large the integers he needed to support
were, but he said "int" which I took to be the standard Nim `int` which is too
big for a `set[]`. Also, while the set `incl` operations of `set[int16]` are
unbeatable performance-wise, iterating over the set can be relatively slow if
the set is not populated -- e.g., if you do int16 and only have 10 unique
numbers, you still have to loop over 65536 entries to convert to a seq[int].
You can play around with this little program to see the various effects.
import sets, intsets, times, random, sequtils, algorithm
let trials = 10000
let numberRange = 1000 # 10000
let doPrint = false
randomize()
var Is = initIntSet()
let tI0 = epochTime()
for i in 1..trials: Is.incl(random(numberRange))
var Iss = toSeq(items(Is))
Iss.sort(cmp[int])
echo "IntSet time: ", epochTime() - tI0
if doPrint: echo Iss
var Hs = initSet[int]()
let tH0 = epochTime()
for i in 1..trials: Hs.incl(random(numberRange))
var Hss = toSeq(items(Hs))
Hss.sort(cmp[int])
echo "HashSet[int] time: ", epochTime() - tH0
if doPrint: echo Hss
var Ss: set[int16]
let tS0 = epochTime()
for i in 1..trials: Ss.incl(int16(random(numberRange)))
var Sss = toSeq(items(Ss))
echo "set[int] time: ", epochTime() - tS0
if doPrint: echo Sss
