I've been trying to contribute to statrs recently, and one of the issues I've been running into is that I'm trying to have an iterator that returns items in sorted order without cloning the underlying data. I'm working this PR if you wanted to take a look at my code so far. I looked up this problem and found this StackOverflow post about this topic from years ago but, frankly, I don't believe it. Assuming you're iterating from a vector, mutating the underlying vector is akin to keeping state on the order of the vector. Why cant that happen in a separate data structure? Is there a more efficient way to represent ordinality other than a vector? Creating an iterator is simply tracking traversal through that structure, which I think could be done using a bloom filter to track which indices have not been traversed yet. That just leaves the traversal algorithm itself. What information would an iterator need to know to make the best decision? Could I adapt a sorting algorithm to be an iterator?
I'm asking a lot of questions because I'm a statistics guys, not an algorithms guy. Any starting point or input is much appreciated!
You would have to either mutate the original vector or clone it, yes. If you really want to iterate through an immutable Vec with only constant memory usage, then you probably can't get around O(n^2) runtime, but maybe there is some time-memory-tradeoff where a small memory usage can get some time reduction.