🚀 go-pugleaf

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 ) );
// tu wektor ma elementy, ale żadnych iteratorów jeszcze z niego nie pobrano!
std::sort( vec.begin(), vec.end() );
// tu użyto iteratorów z obu końców, przy czym
//  - początek i koniec stały się niewłaściwe, lecz nie osobliwe; ponieważ
//    i tak nikt nie zapamiętał nigdzie tych wartości, niewłaściwość jest
//    w tym wypadku bez znaczenia
std::copy( vec.begin(), vec.end(), from ); // możemy, bo liczebność się nie zmieniła



-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethouris(O)gmail.com>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"Java is answer for a question that has never been stated"