Rust

I haven't looked at the code, so my two cents may be irrelevant, but it sounds like you could define a structure that borrows the vector, keeps a separate vector of indices into borrowed vector, and has a current element index.

struct SortFacadeIterator<'a, T: Ord> {
    data: &'a Vec<T>,
    indices: Vec<usize>,
    position: usize,
}

Then in new you would need to sort the original vector but instead of mutating it you would store indices of a resulting sorted elements from the original, i.e. when passed ["b", "a", "c"] you would create index storage of [1, 0, 2]. After that you can iterate both ways, returning an element by index:

impl<'a, T: Ord> SortFacadeIterator<'a, T> {
    fn current(&self) -> &T {
        self.data[self.indices[self.position]]
    }
}

I think, maybe sorting a vector could be done by enumerating original vector and sort_by a value, also I'm not sure you need a full ordering, but I don't remember what a sort expects

Maybe a heap data structure is what you're looking for. Depending on the usecase you might have to first turn an unsorted Vec into a heap (runtime in O(n), which is still faster than fully sorting it), at that point you can both insert new elements and remove the minimum element within a time in O(log n).

First, let's start by looking at the Iterator trait. It has one method (well, two, but one relevant one):

fn next(&mut self) -> Option<Self::Item>

If the last item the iterator returns is your minimum value, you need to run the iterator all the way to the end to find and return that value.

If you do this, in order to return any other value the iterator returned, you needed to buffer it somewhere. You cannot traverse an iterator in reverse. This means that in order to properly sort an iterator, you need to collect the entire iterator into a buffer to first check whether the last value it returned was the minimum and thus should be the first value in the sorted iterator.

If you have access to a backing buffer or can iterate in reverse, other options become available. You don't need to buffer again because you can access previous elements which are stored somewhere else.

Iterators in the traditional sense represent streams of data that may or may not have a backing buffer, though. For example, repeat(1) is an infinite length iterator. Sorting an infinite length iterator would be computationally impossible, of course.

Not sure what you're asking. If it's about sorting without moving values of big structs around, maybe something like this?