🚀 go-pugleaf

On Sat, 12 Jan 2008 19:49:40 +0000, Sektor van Skijlen wrote:

> Dnia Fri, 11 Jan 2008 20:07:35 +0100, Maciej Piechotka skrobie:
>> 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.
> 
> Ależ cóż ma do rzeczy kwestia unieważniania iteratorów, jeśli wykonujesz
> taką operację:
> 
> vector<T> vec;
> // tu wektor jest pusty
> std::copy( from, to, std::back_inserter( vec ) ); 

Jestem 'niedzielnym programistą' i std::back_inserter jeszcze nie znałem 
(tzn. zapewne gdzieś jest opisane w 'Thinking in C++', ale nie pamiętałem).

A to miejsce było tym, którego się bałem.

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/)