Swap-Proxy für Zeiger

314159265358979

Guten Abend.
Ich arbeite gerade wieder mal an der Optimierung meiner List-Implementierung. Ich möchte das Sortieren beschleunigen, das momentan durch einen Mergesort erledigt wird. Ich habe überlegt, die List auf einen vector<T*> zu mappen und dann die Elemente hinter den Zeigern zu tauschen. Der Vorteil: Ich kann einen schnelleren Algorithmus verwenden wie Quicksort, da ich nun Random Access habe. Mein Problem liegt in Zusammenhang mit std::sort. Da Sort ja die Elemente selbst tauscht, kann ich nicht direkt auf einen vector<T*> mappen, sondern muss mir hier eine Proxy Klasse erstellen, und genau da scheitert es.

Mein bisheriger Code dafür:

template <typename T>
class swap_proxy
{
    T* obj;

public:
    swap_proxy(T* o) : obj(o) {}

    static bool less(const swap_proxy& a, const swap_proxy& b)
    {
        return *a.obj < *b.obj;
    }

    friend void swap(swap_proxy& a, swap_proxy& b)
    {
        using std::swap;
        swap(*a.obj, *b.obj);
    }
};

Das Problem liegt darin, dass ich irgendwie erreichen muss, dass bei sort mein eigenes swap aufgerufen wird anstatt dem std::swap, welches dann op = / copy ctor aufruft und dadurch wild die Zeiger mischt. Manche Implementierungen verwenden dann auch noch iter_swap, warum auch immer.
Hat jemand eine Idee?

314159265358979

Ich habe es nun getestet, indem ich swap-Funktion ins namespace std gelegt habe. (Ja ich weiß, das ist böse)

Benötigte Zeit für 10 Mio Elemente:
Mergesort: 23-24 sek
std::sort: 7-8 sek

Wäre super, wenn mir jemand eine schönere Lösung zeigen könnte, ich möchte nicht unbedingt Quicksort selbst implementieren müssen

Edit: Sortierung stimmt scheinbar doch nicht so ganz, wen es interessiert, und falls mir jemand sagt, wo der Fehler liegt: http://ideone.com/oPkFl

314159265358979

Ist die Fragestellung so kompliziert, hat niemand Lust mir zu helfen oder einfach noch niemand eine Idee?

Nexus

314159265358979 schrieb:

Ist die Fragestellung so kompliziert, hat niemand Lust mir zu helfen oder einfach noch niemand eine Idee?

Wahrscheinlich bist du einfach zu ungeduldig.

Warum sollte std::sort() die Zeiger durcheinander bringen? Zeigertausch reicht ja. Du musst halt ein Sortierkriterium angeben, das dereferenziert.

Du sortierst nur die Zeiger im Vektor. Die Liste bleibt unverändert.

314159265358979

gastgast schrieb:

Du sortierst nur die Zeiger im Vektor. Die Liste bleibt unverändert.

Korrekt, deshalb brauche ich mein eigenes swap und muss erreichen, dass es auch aufgerufen wird.

Nexus

Ah, der Vektor ist ein Abbild der Liste.

Ich würde zu Iteratoren greifen, die bei der Dereferenzierung automatisch die Listenelemente zurückgeben. Boost hat transform_iterator , vielleicht kannst du den in Kombination mit Boost.Range einsetzen (statt des std::vector s). Und ansonsten dürfte es nicht allzu schwierig sein, selbst so einen Iterator zu schreiben.

314159265358979

Ich möchte hier nicht unbedingt eine Abhängigkeit von boost herumschleppen, deshalb wäre eine andere Lösung wohl besser

Nexus

Dann schreib dir wie gesagt einen Random-Access-Iterator, der bei der Dereferenzierung auch noch den Zeiger dereferenziert. Diesen konstruierst du dann von einem std::vector::iterator .

SeppJ

314159265358979 schrieb:

Ich möchte hier nicht unbedingt eine Abhängigkeit von boost herumschleppen, deshalb wäre eine andere Lösung wohl besser

Inwiefern kann man von einer Header-only Bibliothek abhängig sein? Zum Ausführen des Programm braucht man es nicht und zum Übersetzen liefer den Header doch einfach mit.

ipsec

314159265358979 schrieb:

Ich möchte hier nicht unbedingt eine Abhängigkeit von boost herumschleppen, deshalb wäre eine andere Lösung wohl besser

Nexus schrieb:

Und ansonsten dürfte es nicht allzu schwierig sein, selbst so einen Iterator zu schreiben.

Eigentlich brauchts du nur einen Iterator, der bei Dereferenzierung seinen referenzierten Pointer dereferenziert. Ideal in diesem Fall wäre boost::indirect_iterator , wenn du kein boost willst, ist der aber auch schnell selbst geschrieben.

314159265358979

Also mein erster Versuch sieht so aus:

template <typename T>
class List<T>::sort_iterator : public std::iterator<std::random_access_iterator_tag, T>
{
    pointer* pos;

public:
    explicit sort_iterator(pointer* p) : pos(p) {}

    sort_iterator& operator ++ ()    { ++pos; return *this; }
    sort_iterator  operator ++ (int) { sort_iterator iter(pos); ++pos; return *this; }

    sort_iterator& operator -- ()    { --pos; return *this; }
    sort_iterator  operator -- (int) { sort_iterator iter(pos); --pos; return *this; }

    sort_iterator& operator += (size_type n) { pos += n; return *this; }
    sort_iterator& operator -= (size_type n) { pos -= n; return *this; }

    sort_iterator operator + (size_type n) const { return sort_iterator(pos + n); }
    sort_iterator operator - (size_type n) const { return sort_iterator(pos - n); }

    reference operator [] (size_type n) { return pos[n]; }

    reference operator *  () { return **pos; }
    pointer   operator -> () { return *pos; }

    bool operator == (const sort_iterator& iter) const { return pos == iter.pos; }
    bool operator != (const sort_iterator& iter) const { return !(*this == iter); }

    bool operator < (const sort_iterator& iter) const { return pos < iter.pos; }
    bool operator > (const sort_iterator& iter) const { return iter < *this; }

    bool operator >= (const sort_iterator& iter) const { return !(*this > iter); }
    bool operator <= (const sort_iterator& iter) const { return !(*this < iter); }
};

allerdings bekomme ich beim Aufruf

std::sort(sort_iterator(&v[0]), sort_iterator(&v[0] + v.size()));

die Fehlermeldungen:

/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_algo.h||In function 'void std::sort(_RAIter, _RAIter) [with _RAIter = List<int>::sort_iterator]':|
/Users/markusgrech/Desktop/test_/List.h:555|5|instantiated from 'void List<T>::new_sort() [with T = int]'|
/Users/markusgrech/Desktop/test_/main.cpp:20|16|instantiated from here|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_algo.h|5206|error: no match for 'operator-' in '__last - __first'|
/Users/markusgrech/Desktop/test_/List.h|672|note: candidates are: List<T>::sort_iterator List<T>::sort_iterator::operator-(List<T>::size_type) const [with T = int, List<T>::sort_iterator = List<int>::sort_iterator, List<T>::size_type = long unsigned int]|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_iterator.h|320|note: template<class _Iterator> typename std::reverse_iterator::difference_type std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<Iterator>&)|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_iterator.h|373|note: template<class _IteratorL, class _IteratorR> decltype ((__y->base() - __x->base())) std::operator-(const std::reverse_iterator<_IteratorL>&, const std::reverse_iterator<_IteratorR>&)|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_iterator.h|1053|note: template<class _IteratorL, class _IteratorR> decltype ((__x->base() - __y->base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_bvector.h|179|note: std::ptrdiff_t std::operator-(const std::_Bit_iterator_base&, const std::_Bit_iterator_base&)|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_algo.h||In function 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = List<int>::sort_iterator]':|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_algo.h:5208|4|instantiated from 'void std::sort(_RAIter, _RAIter) [with _RAIter = List<int>::sort_iterator]'|
/Users/markusgrech/Desktop/test/List.h:555|5|instantiated from 'void List<T>::new_sort() [with T = int]'|
/Users/markusgrech/Desktop/test_/main.cpp:20|16|instantiated from here|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_algo.h|2175|error: no match for 'operator-' in '__last - __first'|
/Users/markusgrech/Desktop/test_/List.h|672|note: candidates are: List<T>::sort_iterator List<T>::sort_iterator::operator-(List<T>::size_type) const [with T = int, List<T>::sort_iterator = List<int>::sort_iterator, List<T>::size_type = long unsigned int]|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_iterator.h|320|note: template<class _Iterator> typename std::reverse_iterator::difference_type std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<Iterator>&)|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_iterator.h|373|note: template<class _IteratorL, class _IteratorR> decltype ((__y->base() - __x->base())) std::operator-(const std::reverse_iterator<_IteratorL>&, const std::reverse_iterator<_IteratorR>&)|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_iterator.h|1053|note: template<class _IteratorL, class _IteratorR> decltype ((__x->base() - __y->base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_bvector.h|179|note: std::ptrdiff_t std::operator-(const std::_Bit_iterator_base&, const std::_Bit_iterator_base&)|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_algobase.h:579|18|instantiated from '_BI2 std::__copy_move_backward_a(_BI1, _BI1, _BI2) [with bool _IsMove = true, _BI1 = List<int>::sort_iterator, _BI2 = List<int>::sort_iterator]'|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_algobase.h:588|34|instantiated from '_BI2 std::__copy_move_backward_a2(_BI1, _BI1, _BI2) [with bool _IsMove = true, _BI1 = List<int>::sort_iterator, _BI2 = List<int>::sort_iterator]'|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_algobase.h:659|15|instantiated from '_BI2 std::move_backward(_BI1, _BI1, _BI2) [with _BI1 = List<int>::sort_iterator, _BI2 = List<int>::sort_iterator]'|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_algo.h:2107|8|instantiated from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = List<int>::sort_iterator]'|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_algo.h:2177|4|instantiated from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = List<int>::sort_iterator]'|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_algo.h:5208|4|instantiated from 'void std::sort(_RAIter, _RAIter) [with _RAIter = List<int>::sort_iterator]'|
/Users/markusgrech/Desktop/test/List.h:555|5|instantiated from 'void List<T>::new_sort() [with T = int]'|
/Users/markusgrech/Desktop/test_/main.cpp:20|16|instantiated from here|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_algobase.h|543|error: no match for 'operator-' in '__last - __first'|
/Users/markusgrech/Desktop/test_/List.h|672|note: candidates are: List<T>::sort_iterator List<T>::sort_iterator::operator-(List<T>::size_type) const [with T = int, List<T>::sort_iterator = List<int>::sort_iterator, List<T>::size_type = long unsigned int]|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_iterator.h|320|note: template<class _Iterator> typename std::reverse_iterator::difference_type std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_iterator.h|373|note: template<class _IteratorL, class _IteratorR> decltype ((__y->base() - __x->base())) std::operator-(const std::reverse_iterator<_IteratorL>&, const std::reverse_iterator<_IteratorR>&)|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_iterator.h|1053|note: template<class _IteratorL, class _IteratorR> decltype ((__x->base() - __y->base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)|
/Developer/usr/local/bin/../lib/gcc/x86_64-apple-darwin10.4.0/4.6.0/../../../../include/c++/4.6.0/bits/stl_bvector.h|179|note: std::ptrdiff_t std::operator-(const std::_Bit_iterator_base&, const std::_Bit_iterator_base&)|
||=== Build finished: 18 errors, 0 warnings ===|

und damit kann ich nichts anfangen

Shade Of Mine

no match for 'operator-' in '__last - __first'

du hast keinen operator- der passt.

Nexus

Ich würde ausserdem einen Iterator und nicht einen Zeiger wrappen. Auch ist ein Aufruf mit

std::sort(sort_iterator(v.begin()), sort_iterator(v.end()));

schöner, weniger fehleranfällig und aussagekräftiger als

std::sort(sort_iterator(&v[0]), sort_iterator(&v[0] + v.size()));

krümelkacker

Das kommt mir alles sehr komisch vor, was hier versucht wird. Warum nicht einfach alle List<T>-Iteratoren in einen Vector packen und diese dann mit einem speziellen "indirect_comparator" vergleichen? Dann würde man sich die Zuweisungen über T::operator=(T) sparen und kann hinterher alle Knoten entsprechend der Reihenfolge im Vektor neu verlinken. Das ist doch gerade das coole an Listen, dass man die "Elemente nicht umkopieren muss", sondern die Element-speichernden Knoten nur neu zu verlinken braucht.

314159265358979

Ich werde für predefined types die Kopiervariante nehmen, da sie sicherlich schneller ist, als 4 Zeiger zu ändern

krümelkacker

Bei einfachen skalaren Typen, kannst Du auch gleich die Werte in einen Vector kopieren (statt Iteratoren o.ä.), diese dann sortieren und dann in einem Rutsch zurück in der Liste ablegen. Sollte Speicherzugriffstechnisch besser sein als Dein jetziger Ansatz.

Wie auch immer, ich halte nichts von der Idee, Sonderbehandlungen für list<T>::sort in Abhängigkeit von T einzuführen, welche dann andere Anforderungen/Eigenschaften haben (wie zB, dass neuer Speicher reserviert werden muss). Das "schnelle Sortieren" einer Liste kann ein Nutzer dann auch so haben:

list<int> l = ...;
  {
    vector<int> v;
    v.reserve(l.size());
    v.assign(l.begin(),l.end());
    sort(v.begin(),v.end());
    copy(v.begin(),v.end(),l.begin());  
  }
  // l ist sortiert.

:p

314159265358979

Hm, da hast du wohl recht. Allerdings würde ich meine Liste trotzdem gerne direkt mit std::sort sortieren, da das schneller geht als mein momentaner Algorithmus. Da muss ich dann halt irgendwie mein eigenes splice hineinbringen.

Bin noch sehr am herumüberlegen, wie ich mir das vorstelle, ich denke das merkt man

hustbaer

Zeiger auf die Nodes in einen Vektor stecken, Vektor sortieren, und danach die Liste anhand der Reihenfolge im Vektor komplett neu aufbauen.

Shade Of Mine

hustbaer schrieb:

Zeiger auf die Nodes in einen Vektor stecken, Vektor sortieren, und danach die Liste anhand der Reihenfolge im Vektor komplett neu aufbauen.

Wäre es nicht eigentlich sogar schneller in den vector sortiert einzufügen? uU einfach in einen baum einfügen...