Swap-Proxy für Zeiger



  • 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.



  • 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 😞



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

    du hast keinen operator- der passt.



  • 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()));
    


  • 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.



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



  • 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



  • 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 😃



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



  • 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...



  • hustbaer schrieb:

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

    Den Vorschlag gab's schon.



  • Shade Of Mine schrieb:

    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...

    Vektor nein, Baum vermutlich ja

    @gab_es_schon:
    Im Prinzip ja, aber anscheinend hat es 3,1415 nicht verstanden.
    Er schreibt ja "da muss ich dann halt irgendwie mein eigenes splice hineinbringen".
    Daher nochmal mein Hinweis mit ner anderen Formulierung: Liste komplett neu aufbauen.
    Dafür braucht er kein Splice, und auch keine 4 Zeiger pro Element anpassen, sondern nur 2.


Anmelden zum Antworten