Sort (diskuse)

[#Tom]

Já nejradějí třídím takto:

#include <iostream>
#include <vector>
#include <algorithm>
#include "Rational"

using namespace std;

int main() {
  vector<XMath::Rational<int> > cisla;
  vector<XMath::Rational<int> >::const_iterator ci;
  cisla.push_back(XMath::Rational<int>(2, 3));
  cisla.push_back(XMath::Rational<int>(3, 4));
  cisla.push_back(XMath::Rational<int>(1, 2));
  cisla.push_back(XMath::Rational<int>(4, 5));
  cout << "Čísla na začátku" << endl;
  for (ci = cisla.begin(); ci != cisla.end(); ++ci) {
    cout << *ci << endl;
  }
  sort(cisla.begin(), cisla.end());
  cout << "Čísla na konci" << endl;
  for (ci = cisla.begin(); ci != cisla.end(); ++ci) {
    cout << *ci << endl;
  }
  return 0;
}

Sestupné třídění obstará funkce sort. Stačí zadat iterátory ukazující na začátek a konec seznamu, třídění se potom provede jakoby zázračně samo. Pokud nejsou použity vestavěné číselné typy, je potřeba napsat přetížené operátory porovnání.

Pro přeložení jsou potřeba dva hlavičkové soubory se šablonami, které jsou k dispozici tady.

Třídit lze i jinak – man qsort. Často je zbytečné se namáhat s psaním třídicího kódu a postačují funkce z knihovny C nebo STL.

[Sinuhet]

/**
 * 1. Dedit od konkretnich typu (std::vector<FileInfo*>) se moc nedoporucuje.
 *    Akorat tam podivne redeklarujete stadardni metody - docela bych chtel
 *    videt jejich definice.
 *
 * 2. Pokud chcete kontrolu pod g++/libstdc++ pouzijte
 *
 *      g++ -D _GLIBCXX_CONCEPT_CHECKS -D _GLIBCXX_DEBUG -o file.o file.cc
 *
 *    a nemusite sasit s at. Plus vam to ohlida spoustu dalsich veci.
 *
 * 3. Nasledujici kod jsem netestoval.
 *
 */

#include <vector>
#include <algorithm>

#include "FileInfo.h"


bool lt_file_info(const FileInfo* f1, const FileInfo* f2)
{
        if( f1->isDots() != f2->isDots() )
                return f1->isDots() < f2->isDots();

        if( f1->isDir() != f2->isDir() )
                return f1->isDir() < f2->isDir();

        // zjistete si, co tahle funkce vraci a podle toho se
        // zaridte (a co prebira - podle deklarace, kterou jste
        // uvedl, gchar, ale getName vraci std::string)
        return g_utf8_collate(f1->getName(), f2->getName());
}

void test()
{
        std::vector<FileInfo*> file_list;

        std::sort(file_list.begin(), file_list.end(), lt_file_info);
}

[Jardík]

g_utf8_collate vrací -1, když str1 je před str2, 0, když jsou shodné, 1, když str1 je za str2. Funkce přebírá const gchar* (gchar je typedef na char) a to není problém. std::string má metodu c_str(), která ten ukazatel vrací. Problém je, že vaše řešení není možné použít, nebere ohled na sloupec, dle kterého se řadí a na vzestupnost/sestupnost. S tím ukazatelem na fci by nebyl problém, deklaroval bych jí jako static, problém by byl, že bych pak neměl ukazatel this a pak bych stejně nezjistil, dle čeho řadit. qsort ze stdlib.h se taky použít nedá. Asi si budu muset napsat nejakej ten quicksort sám.

[podlesh]

tím ukazatelem na fci by nebyl problém, deklaroval bych jí jako static, problém by byl, že bych pak neměl ukazatel this a pak bych stejně nezjistil, dle čeho řadit.

Omlouvám se že vám do toho lezu jako člověk co se s C++ rozloučil dávno před STL... ale podle dokumentace ten třetí parametr metody sort není funkce, ale functor (tedy objekt)! Tedy stačí udělat objekt jako potomek binary_function, kterů bude třídit podle toho co je potřeba.

Něco je o tom psáno zde, i s příklady.

[Sinuhet]

Funktor se musi tvarit jako funkce (od toho to je funktor). Proto tam muzete tlacit i obycejne funkce.

[Sinuhet]

Pro jine pripady (razeni podle data) samozrejme nadefinujete jinou porovnavaci funkci a budete volat sort s jinou porovnavaci funkci. Taky muzete udelat malou hirearchii trid s virtualnim 'operator<'. Jak je ctena libost. Ale nechapu, proc si chcete vyrabet svuj vlastni sort - tim si akorat pridelate praci a nadefinovani vsech porovnani se stejne nevyhnete.

[mkoubik]

A co zkusit quicksort. Já v C++ neumim, tak dělam soukromej GTK+-2.0/C klon, ale k řazení jsem se ještě nedostal. Nejlepší by bylo, kdyby byl v GTK nějakej widget jako GtkTreeView u kterýho když klikneš na záhlaví sloupce, tak se seřadí. To asi neexistuje, že ne?

[Jardík]

Existuje. Potom to porovnávací fci předává iterátory, ale je to strašně pomalý. Pokaždé, když přidáš položku, tak se to přeřazuje.

[Josef Kufner]

Ve standardní knihovně jazyka C je funkce sort, ktera dostane pointer na zacatek, velikost jednoho, pocet a pointer na porovnavaci funkci. Rychle, jednoduche.

[Luk]

To už se tu řešilo. Někdo ale věří, že to zvládne lépe