Repository navigation
VecDeque has no sort_by method (should possibly have one to match Vec).聽#27322
Description
I just came across a use case for this while working on a visit order for the UI graph in conrod - its absence took me by surprise 馃樃
Is there a particular reason this hasn't been implemented yet? Or has it just not popped up yet (pun intended)?
Activity
tamird commentedon Jul 27, 2015
How come either method has to be inherent? Seems like this could be a trait that requires
sortand providessort_by.abonander commentedon Oct 28, 2015
sortandsort_byare methods provided by[T]. Since the sorting algorithm requires2 * nextra space, I don't see a too much problem with copying the data from the disjoint slices into one allocation to sort and then putting it back in-order. It's mostly just a question of semantics.retep998 commentedon Oct 30, 2015
Wouldn't it have to be
sort_bywhich is required andsorthave a default implementation?I'd prefer if
VecDequehad an optimal in place sorting algorithm though.Gankra commentedon Oct 30, 2015
@retep998 the thing is std has no optimal or inplace sorting! All we have is naive merge sort (because it was argued that our sort should be stable). Our sort support is a bit trash imo. Quicksort (unstable) or wikisort (stable but complicated) would be good to have here. Maybe even expose insertionsort!
Even then, it's genuinely unclear to me what would be optimal here. Seems like linearizing the array to make it contiguous and avoid modulo logic could yield huge benefits.
petrochenkov commentedon Oct 30, 2015
sortis stable? o_OAt least a good thing is that it's not documented, it's still possible to fix it and add
stable_sortas a separate function.Gankra commentedon Oct 30, 2015
Changing that may be an unacceptable break.
abonander commentedon Oct 31, 2015
It'd be cool, if a little overkill, to have a crate with a bunch of different sorting functions. That might make a good crate for contain-rs.
bluss commentedon Oct 31, 2015
Oh no, we haven't documented that it's a stable sort. That's a strange oversight.
petrochenkov commentedon Oct 31, 2015
@bluss
"Oh yes" you mean?
Why should
sortbe stable by default? Stability is not usually needed. "Don't pay for what you don't use" and everything like this.Gankra commentedon Oct 31, 2015
The current situation was definitely an active decision. I'm having trouble finding it, though.
I basically agree that it's a weird cost, but there's possibly an argument to be had that it's the "safer" default, and unstable_sort could easily be the opt-in to less reliable behavior.
bluss commentedon Oct 31, 2015
@petrochenkov It should be stable by default because a stable sort is more versatile. Reordering equally ordered elements in sort is a potential gotcha, too, and Rust wants to be a nice language. The third party crate space is open to find other sorting algorithms with different tradeoffs.
Gankra commentedon Oct 31, 2015
Some discussion:
#11064
Mention [T]::sort is stable in docs
Rollup merge of rust-lang#29579 - steveklabnik:gh27322, r=apasel422
Rollup merge of rust-lang#29579 - steveklabnik:gh27322, r=apasel422
nico-abram commentedon Feb 22, 2020
Why was this closed? The PR linked by bors has nothing to do with VecDeque as far as I can see, and I cannot find a way to sort a VecDeque optimally in std. Someone (@hyeonu in the rust discord) mentioned From VecDeque for Vec and back guarantees to not allocate (In the docs), but it (1) requires ownership of the VecDeque (So can't use it to sort &mut VecDeque afaik) and (2) requires moving some data around before beginning the sort(Which shouldn't be necessary unless I'm missing something).
I'm not sure if there are other scenarios that it would make sense to sort that provide random access but are not contiguous memory from first to last (Which the current sort in std requires because it uses slices), but there might be.
Mark-Simulacrum commentedon Feb 22, 2020
It seems like this should be possible, at least. A slightly non-optimal implementation would be to sort the front and back slices separately and then swap elements back and forth as needed (second step of merge sort, basically).
retep998 commentedon Apr 1, 2020
Closed because of #69425 I assume