std::sort vs. std::stable_sort

esskar

hi.

irgendwie scheint es mit std::sort unter windows ein problem zu geben (ich benutze die STL die an sich beim SDK dabei ist). An einer gewissen Stelle bekommt meine Kompare-Funktion ein Invalides-Objekt zum vergleich und steigt dann natürlich aus. std::stable_sort funzt prima. gibt es da irgendwelche erfahrungen?

Du solltest lieber sagen welchen Compiler du benutzt und ein minimales, compilierbares Beispiel posten.

Das hat mit Windows nichts zu tun. Meine Theorie ist, dass du was falsch machst, was sich aber in deinem Fall gerade beim stable sort nicht bemerkbar macht.
Zeig mal Code, so kann man nur wild rumraten.

Walli

Der Unterschied zwischen eine stabilen und einem instabilen Sortierverfahren ist der, daß sich die Reihenfolge von Objekten mit gleichem Schlüssel während des Sortierens nicht verändert. Vielleicht hilft diese Information den Fehler einzugrenzen.

EDIT: Satzbau

stable_sort stürzt nicht so oft ab wie sort...sieht man doch schon am namen.

esskar

ich benutz VC 6.

class SuperListView
{
public:
   class Item
   {
      public:
         Item();
         Item(const Item & item);
         ~Item();

         void Release();

	void SetText(const char *text);
	const char *GetText() const;
	const Item & operator=(const Item & item);

      protected:
         std::string   m_text;
   };

public:
   typedef std::vector<Item>  Row;
   typedef std::vector<Row>   Table;

protected:
   Table m_container;
}

struct Less : public std::binary_function <SuperListView::Row, SuperListView::Row, bool> 
{
   Less(long idx) { Index = idx; }

   bool operator()(const SuperListView::Row & left, const SuperListView::Row & right) const
   {
      return strcmpi(left[Index].GetText(), right[Index].GetText()) <= 0 ? true : false;
   }

   long	Index;
};

struct Greater : public std::binary_function <SuperListView::Row, SuperListView::Row, bool> 
{
   Greater(long idx) { Index = idx; }

   bool operator()(const SuperListView::Row & left, const SuperListView::Row & right) const
   {
      return strcmpi(left[Index].GetText(), right[Index].GetText()) >= 0 ? true : false;
   }

   long	Index;
};

void SuperListView::Sort(long columnidx)
{
   std::stable_sort(m_container.begin(), m_container.end(), Less(columnidx));
   m_sortidx = columnidx;
}

HumeSikkins

struct Less

strcmpi(left[Index].GetText(), right[Index].GetText()) <= 0

Fällt dir da nichts auf? Du sagst left ist kleiner als right, gdw. left kleiner-oder-gleich right ist. Das ist keine zu sort passende Ordnung.
Denn in deinem Fall sagst du, dass zwei gleiche Werte nich äquivalent sind.

Denn:
Sei Left = A und Right = A.
Äquivalenz heißt hier: !(Left Less Right) && !(Right Less Left)
Du sagst nun, dass Less = LessEqual ist ->
!(Lef LessEqual Right) && !(Right LessEqual Left) =
!(A LessEqual A) && !(A LessEqual A) =
!(true) && !(true) =
false && false = false
<=> A == A ist false.
Ups.

phlox81

Und evtl. noch die STL Fixes für den VC installieren, dann könnte sort auch was schneller sein

7H3 N4C3R

Auch wenns leicht OT ist: Welche Fixes und vor allem, woher?

phlox81

7H3 N4C3R schrieb:

Auch wenns leicht OT ist: Welche Fixes und vor allem, woher?

Die STL Implementation vom VC6.0 ist, äh, leicht fehlerhaft,
bzw. suboptimal, so das es einen Fix (meherere Header) gibt, die
man im Verzeichnis auswechselt, dann sind einige Dinge mit der STL
schneller oder einfach nur sicherer.

http://www.dinkumware.com/vc_fixes.html

Devil

esskar

aha.
danke für den Less fix.
Jetzt gehts.
Und auch danke für den Link.