🚀 go-pugleaf

On Thu, 10 Jan 2008 23:46:39 +0000, Sektor van Skijlen wrote:

> Dnia Thu, 10 Jan 2008 19:47:02 +0100, Maciej Piechotka skrobie:
>> On Thu, 10 Jan 2008 16:31:12 +0000, Sektor van Skijlen wrote:
> 
>> >> > Z ciekawości, zajrzałem co ma Java. Java posiada algorytm
>> >> > java.util.Collections.sort() (w dwóch wersjach, jedna z
>> >> > komparatorem). Pierwszym argumentem jest LISTA (nie zakres
>> >> > elementów). W żadnej klasie dziedziczącej po *.Collections nie
>> >> > jest ona przesłonięta.
>> >> > 
>> >> > Co więcej, *.Collections.sort() ma gwarancję, że jest stabilny.
>> >> > Ciekawe, dlaczego?
>> > 
>> >> Bo nie dawali wersji niestabilnej?
>> > 
>> > Zgadza się. A dlaczego nie dali wersji niestabilnej?
> 
>> Jeśli mnie pamięć nie myli to java.util.Collections.sort() kopjuje całą
>> listę do tablicy, sortuje tablicę i wstawia do listy.
> 
>> Uniwersalny stable sort:
>> template <class iterator>
>> void my_sort(iterator from, iterator to) {
>>         typename iterator::difference_type distance =
>>         std::distance(from,
>> to);
>>         typename iterator::value_type *refs = new typename
>> iterator::value_type[distance];
>>         std::copy(from, to, refs);
>>         std::stable_sort(&refs[0], &refs[distance]);
>>         std::copy(&refs[0], &refs[distance], from); delete[] refs;
>> }
> 
>> Problem - kopiuje wszystko do osobnej tablicy
> 
> To jest akurat żaden problem. Prawdziwy problem jest w pierwszej
> linijce. std::distance dla zbiorników dwukierunkowych posiada liniowy
> koszt w długość ciągu.
> 
> Oczywiście można to zamortyzować stosując vector zamiast tablicy i kazać
> mu się rozrastać w miarę dodawania elementów. Wtedy nie musisz liczyć
> elementów distance'm. Natomiast jeśli już i tak przekopiowałeś elementy
> do wektora, to po cholerę stosować stable_sort - zastosuj normalne sort.
> 

Co do std::vector to nie byłem pewien co do unieważnień iteratorów a nie 
chciało mi się grzebać w dokumentacji. Co do stable_sort to chciałem 
emulować java.util.Collections.sort, które sortuje stabilnie. Dla mnie to 
podejście nie jest najlepsze jeśli mówimy o optymalizacji.

#include <algorithm>
#include <list>
#include <vector>

template <class iterator>
void universal_stable_sort(iterator from, iterator to) {
  std::vector<typename iterator::value_type> refs;
  std::copy(from, to, refs.begin());
  std::stable_sort(refs.begin(), refs.end());
  std::copy(refs.begin(), refs.end(), from);
}

template <class iterator>
void universal_sort(iterator from, iterator to) {
  std::vector<typename iterator::value_type> refs;
  std::copy(from, to, refs.begin());
  std::sort(refs.begin(), refs.end());
  std::copy(refs.begin(), refs.end(), from);
}

Pozdrawiam
-- 
I've probably left my head... somewhere. Please wait untill I find it.
Homepage (pl_PL): http://uzytkownik.jogger.pl/
(GNU/)Linux User: #425935 (see http://counter.li.org/)