Dynarray Implementation

[Sone]

iksepschensaif schrieb:

Sone schrieb:

Ich hab sicherheitshalber mal hinzugefügt, dass wenn eine Exception im Dtor des zu zerstörenden Objektes fliegt (in _destroyAllUntil ), einfach alles deallokiert wird und der Zeiger auf Null gesetzt wird (damit der Dtor übersprungen wird).

Dir fehlen Grundlagen. Lies mal das durch: http://home.ustc.edu.cn/~zixin/More%20Effective%20C++/MAGAZINE/SU_FRAME.HTM#destruct

Ja, aber wenn ich wirklich so tue als ob nichts passiert, und es gibt doch irgendeinen doofen Programmierer der einen Destruktor eine Exception emittieren lässt, dann ... leckt der ganze Speicher... was ist so falsch, einfach auf diesen Fall einzugehen?
Wieso muss man immer so tun als ob es keine schlechten User gibt?
Das ein Dtor nie eine Exception nach außen kommen lassen darf, ist mir schon klar.

Edit: Btw: Geändert.

[ScottZhang]

[...] with both of these is that they have fundamentally the same problem we just described for destroy! For example, consider the following code: ¤ Sutter, P145

T* p = new T[10];
delete[] p;

Looks like normal harmless C++, doesn't it? But have you ever wondered what new[] and delete[] do if a T destructor throws? Even if you have wondered, you can't know the answer for the simple reason that there is none: The standard says you get undefined behavior if a T destructor throws anywhere in this code, which means that any code that allocates or deallocates an array of objects whose destructors could throw can result in undefined behavior. [...]

Hast dus nicht gelesen? Undefinded bleibt undefined, egal ob man drauf reagiert. :xmas1:

[Sone]

ScottZhang schrieb:

Hast dus nicht gelesen? Undefinded bleibt undefined, egal ob man drauf reagiert. :xmas1:

Ach, es ist undefiniertes Verhalten? Na dann ^^

[glühnase]

Sone schrieb:

Wieso muss man immer so tun als ob es keine schlechten User gibt?

Weil der Code, wenn du ihn auf schlechte User auslegst, selbst schlecht wird.

Natürlich kannst du die üblichen Fehlerquellen durch Compiletime-Mechanismen oder Assertions abfangen, die passieren ja auch guten Usern. Aber wenn du anfängst, selbstverständliche Dinge massiv zu verkomplizieren, nur weil jemand sie mit Absicht (oder grober Dummheit) falsch verwenden könnte, ist etwas nicht mehr gut. Solchen Leuten darf das Programm ruhig mit voller Wucht um die Ohren fliegen.

<:xmas2:>

[Sone]

glühnase schrieb:

Sone schrieb:

Wieso muss man immer so tun als ob es keine schlechten User gibt?

Weil der Code, wenn du ihn auf schlechte User auslegst, selbst schlecht wird.

Das ist mal ein Merksatz.

[Sone]

*push*
So, wie sieht's aus? Unschönheiten usw. muss es doch bestimmt noch geben. :xmas1:

Edit: Ich setz' mich am besten mal an einen ausführlichen Test.

[meinbester]

Sone schrieb:

Ich setz' mich am Besten mal an einen ausführlichen Test.

Am besten ohne allzu viele Rechtschreibfehler.

[Sone]

meinbester schrieb:

Sone schrieb:

Ich setz' mich am Besten mal an einen ausführlichen Test.

Am besten ohne allzu viele Rechtschreibfehler.

Willkommen im Internet.
Außerdem markiert der Duden das als eine rechtschreiblich schwierigige Verbindung

[TyRoXx]

Warum gibt es keinen Standardkonstruktor?

[Sone]

TyRoXx schrieb:

Warum gibt es keinen Standardkonstruktor?

Weil Dynarray eine feste Größe hat.
Es macht keinen Sinn ein Dynarray zu erzeugen bevor man die Größe nicht kennt.

[TyRoXx]

Sone schrieb:

TyRoXx schrieb:

Warum gibt es keinen Standardkonstruktor?

Weil Dynarray eine feste Größe hat.
Es macht keinen Sinn ein Dynarray zu erzeugen bevor man die Größe nicht kennt.

Ich kenne die Größe doch: Null.
Eine Klasse ohne Standardkonstruktor ist unhandlich und es gibt hier keinen technischen Grund, keinen zu haben.

[Sone]

TyRoXx schrieb:

Sone schrieb:

TyRoXx schrieb:

Warum gibt es keinen Standardkonstruktor?

Weil Dynarray eine feste Größe hat.
Es macht keinen Sinn ein Dynarray zu erzeugen bevor man die Größe nicht kennt.

Ich kenne die Größe doch: Null.
Eine Klasse ohne Standardkonstruktor ist unhandlich und es gibt hier keinen technischen Grund, keinen zu haben.

Sehen wir uns mal an, was man mit einem Dynarray der Größe 0 überhaupt richtig tun kann.

• Mit einem anderen Dynarray tauschen - sinnlos, da wir gleich ein neues Objekt erzeugen und das andere moven könnten.
• Ein anderes Objekt zuweisen - könnten wir gleich im Ctor machen.

Nicht viel, oder?
Ich habe schon öfter mit dem Gedanken gespielt, Dynarrray s der Größe Null zu verbieten.

Um das ganze nochmal anders zu argumentieren, was schrieb ich am Anfang:

Sone schrieb:

Es ist eigentlich das schöne Äquivalent zu

int* array = new int[size];

bzw. mit VLAs

int array[size];

Du kannst kein echtes VL/Heap-Array ohne Größe erzeugen, entsprechend wäre das hier nicht sinnvoll.
Falls man jedoch auf einen Default-Konstruktor angewiesen ist, kann man es ja zur not binden.

[camper]

Sone schrieb:

Ich habe schon öfter mit dem Gedanken gespielt, Dynarrray s der Größe Null zu verbieten.

Den Nullzustand hast du schon, weil die Klasse move-bar ist.

[camper]

Ich habe ich es mal versucht, das Ganze einigermaßen zu ordnen. Konstruktordelegation verkompliziert die Sache hier unnötig, weil der Prinzipalkonstruktor tatsächlich nur unvollständig initialisiert.
Ein paar Hilfsfunktionen vereinfachen die Angelegenheit.
Habe auch auf Defaultargumente verzichtet, weil ich nicht darüber nachdenken wollte, in welchen Fällen das Kopieren von Objekten im Defaultfall evtl. ineffizient ist.
Die Codeduplikation hält sich hier in Grenzen. Habe auch kein Argument gesehen, das bei einer Klasse wie dieser überzeugend gegen

Dynarray& operator=(Dynarray rhs) noexcept

spricht.

#include <memory>
#include <iterator>
#include <stdexcept>
#include <type_traits>

template <typename Allocator, typename InputIterator>
typename std::allocator_traits<Allocator>::pointer
alloc_copy(Allocator& alloc, typename std::allocator_traits<Allocator>::size_type n, InputIterator first)
{
    typename std::allocator_traits<Allocator>::pointer p = std::allocator_traits<Allocator>::allocate( alloc, n );
    typename std::allocator_traits<Allocator>::size_type i = 0;
    try
    {
        for ( ; i != n; )
        {
            std::allocator_traits<Allocator>::construct( alloc, p, *first );
            ++p;
            ++i;
            ++first;
        }
    }
    catch (...) // constructor failure or failure of any Iterator-Op
    {
        for ( ; i--; )
            std::allocator_traits<Allocator>::destroy( alloc, --p );
        std::allocator_traits<Allocator>::deallocate( alloc, p, n );
        throw;
    }
    return p - n;
}

template <typename Allocator>
typename std::allocator_traits<Allocator>::pointer
alloc_fill_n(Allocator& alloc, typename std::allocator_traits<Allocator>::size_type n)
{
    typename std::allocator_traits<Allocator>::pointer p = std::allocator_traits<Allocator>::allocate( alloc, n );
    typename std::allocator_traits<Allocator>::size_type i = 0;
    try
    {
        for ( ; i != n; )
        {
            std::allocator_traits<Allocator>::construct( alloc, p );
            ++p;
            ++i;
        }
    }
    catch (...)
    {
        for ( ; i--; )
            std::allocator_traits<Allocator>::destroy( alloc, --p );
        std::allocator_traits<Allocator>::deallocate( alloc, p, n );
        throw;
    }
    return p - n;
}

template <typename Allocator>
typename std::allocator_traits<Allocator>::pointer
alloc_fill_n(Allocator& alloc, typename std::allocator_traits<Allocator>::size_type n, const typename std::allocator_traits<Allocator>::value_type& v)
{
    typename std::allocator_traits<Allocator>::pointer p = std::allocator_traits<Allocator>::allocate( alloc, n );
    typename std::allocator_traits<Allocator>::size_type i = 0;
    try
    {
        for ( ; i != n; )
        {
            std::allocator_traits<Allocator>::construct( alloc, p, v );
            ++p;
            ++i;
        }
    }
    catch (...)
    {
        for ( ; i--; )
            std::allocator_traits<Allocator>::destroy( alloc, --p );
        std::allocator_traits<Allocator>::deallocate( alloc, p, n );
        throw;
    }
    return p - n;
}

template <typename T, typename Allocator = std::allocator<T>>
class Dynarray : private Allocator
{
public:
    // types
    typedef T value_type;
    typedef Allocator allocator_type;
    static_assert( std::is_same<value_type, typename std::allocator_traits<allocator_type>::value_type>::value, "allocator must be compatibel!" );
    typedef typename std::allocator_traits<allocator_type>::size_type size_type;
    typedef typename std::allocator_traits<allocator_type>::difference_type difference_type;
    typedef typename std::allocator_traits<allocator_type>::pointer pointer;
    typedef typename std::allocator_traits<allocator_type>::const_pointer const_pointer;

    typedef pointer iterator;
    typedef const_pointer const_iterator;

    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

public:
    // constructors
    // 0. default
    Dynarray() noexcept
        : allocator_type(), mSize(0), mArrayPtr( nullptr )
    {}
    Dynarray(const allocator_type& a) noexcept
        : allocator_type(a), mSize(0), mArrayPtr( nullptr )
    {}
    // 1. by size
    Dynarray(size_type s)
        : allocator_type(), mSize(s), mArrayPtr( alloc_fill_n( alloc(), mSize ) )
    {}
    Dynarray(size_type s, allocator_type& a)
        : allocator_type(a), mSize(s), mArrayPtr( alloc_fill_n( alloc(), mSize ) )
    {}
    Dynarray(size_type s, const value_type& val)
        : allocator_type(), mSize(s), mArrayPtr( alloc_fill_n( alloc(), mSize, val ) )
    {}
    Dynarray(size_type s, const value_type& val, allocator_type& a)
        : allocator_type(a), mSize(s), mArrayPtr( alloc_fill_n( alloc(), mSize, val ) )
    {}
    // 2. by initializer_list
    Dynarray(std::initializer_list<value_type> l)
        : allocator_type(), mSize(size), mArrayPtr( alloc_copy( alloc(), mSize, l.begin() ) )
    {}
    Dynarray(std::initializer_list<value_type> l, const allocator_type& a)
        : allocator_type(a), mSize(size), mArrayPtr( alloc_copy( alloc(), mSize, l.begin() ) )
    {}
    // 3. by ForwardIterator
    template<typename ForwardIterator,
             typename std::enable_if<std::is_convertible<
                 typename std::conditional<std::is_class<ForwardIterator>::value || std::is_pointer<ForwardIterator>::value, std::iterator_traits<ForwardIterator>, std::false_type>::type::iterator_category,
                 std::forward_iterator_tag>::value, int>::type = 0>
    Dynarray(ForwardIterator first, ForwardIterator last)
        : allocator_type(), mSize( std::distance( first, last ) ), mArrayPtr( alloc_copy( alloc(), mSize, first ) )
    {}
    template<typename ForwardIterator,
             typename std::enable_if<std::is_convertible<
                 typename std::conditional<std::is_class<ForwardIterator>::value || std::is_pointer<ForwardIterator>::value, std::iterator_traits<ForwardIterator>, std::false_type>::type::iterator_category,
                 std::forward_iterator_tag>::value, int>::type = 0>
    Dynarray(ForwardIterator first, ForwardIterator last, const allocator_type& a)
        : allocator_type(a), mSize( std::distance( first, last ) ), mArrayPtr( alloc_copy( alloc(), mSize, first ) )
    {}

    // copy/move
    Dynarray(const Dynarray& other)
        : allocator_type( std::allocator_traits<allocator_type>::select_on_container_copy_construction( other.alloc() ) ), mSize( other.mSize ), mArrayPtr( alloc_copy( alloc(), mSize, other.begin() ) )
    {}
    Dynarray(const Dynarray& other, const allocator_type& a)
        : allocator_type(a), mSize( other.mSize ), mArrayPtr( alloc_copy( alloc(), mSize, other.begin() ) )
    {}
    Dynarray(Dynarray&& other) noexcept
        : allocator_type( std::move( other.alloc() ) ), mSize( other.mSize ), mArrayPtr( other.mArrayPtr )
    {
        other.mSize = 0;
        other.mArrayPtr = nullptr;
    }
    Dynarray(Dynarray&& other, const allocator_type& a) noexcept
        : allocator_type(a), mSize( other.mSize ), mArrayPtr( other.mArrayPtr )
    {
        other.mSize = 0;
        other.mArrayPtr = nullptr;
    }

    // copy/move-assign
    Dynarray& operator=(Dynarray rhs) noexcept
    {
        swap( rhs );
        return *this;
    }
    // initializer_list

    Dynarray& operator=(std::initializer_list<value_type> l)
    {
        Dynarray tmp(l);
        swap( tmp );
        return *this;
    }

    // swap
    void swap(Dynarray& other) noexcept
    {
        swap_( other, std::allocator_traits<allocator_type>::propagate_on_container_swap );
    }
    friend void swap(Dynarray& a, Dynarray& b) noexcept
    {
        a.swap( b );
    }

    // destroy
    ~Dynarray() noexcept
    {
        if ( !empty() )
        {
            for ( size_type n = mSize; n-- != 0; )
                std::allocator_traits<allocator_type>::destroy( alloc(), mArrayPtr + n );
            std::allocator_traits<allocator_type>::deallocate( alloc(), mArrayPtr, mSize );
        }
    }

    allocator_type get_allocator() const noexcept { return alloc(); }

    /// Element Access:
    iterator begin() noexcept { return mArrayPtr; }
    const_iterator begin() const noexcept { return mArrayPtr; }
    const_iterator cbegin() const noexcept { return begin(); }

    iterator end() noexcept { return mArrayPtr + mSize; }
    const_iterator end() const noexcept { return mArrayPtr + mSize; }
    const_iterator cend() const noexcept { return end(); }

    reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
    const_reverse_iterator rbegin() const noexcept { return reverse_iterator(end()); }
    const_reverse_iterator crbegin() const noexcept { return rbegin(); }

    reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
    const_reverse_iterator rend() const noexcept { return reverse_iterator(begin()); }
    const_reverse_iterator crend() const noexcept { return rend(); }

          reference operator[](size_type index) noexcept {return mArrayPtr[index];}
    const_reference operator[](size_type index) const noexcept {return mArrayPtr[index];}

    const_reference at(size_type index) const
    {
        return index < mSize ? operator[](index) : throw std::out_of_range("index out of range");
    }

    reference at(size_type index)
    {
        return index < mSize ? operator[](index) : throw std::out_of_range("index out of range");
    }

    /// Data access:
    const_pointer data() const noexcept {return begin();}
          pointer data() noexcept {return begin();}

    /// front/back access:
    const_reference front() const noexcept { return *begin(); }
          reference front() noexcept { return *begin(); }
    const_reference back() const noexcept { return *(end() - 1); }
          reference back() noexcept { return *(end() - 1); }

    /// Capacity:
    size_type size() const noexcept {return mSize;}
    bool empty() const noexcept {return size() == 0;}

private:

    size_type mSize; /// Size of the array (in elements)
    pointer mArrayPtr; /// Internal pointer to the array

    allocator_type& alloc() noexcept { return *this; }
    const allocator_type& alloc() const noexcept { return *this; }

    void swap_(Dynarray& other, std::true_type) noexcept
    {
        swap( alloc(), other.alloc() );
        swap( mSize, other.mSize );
        swap( mArrayPtr, other.mArrayPtr );
    }

    void swap_(Dynarray& other, std::false_type) noexcept
    {
        swap( mSize, other.mSize );
        swap( mArrayPtr, other.mArrayPtr );
    }
};

int instances = 0;

void may_throw()
{
  if (rand()%100 == 0)
    throw 0;
}

struct test {
  test() { may_throw(); ++instances; }
  test(test const&) { may_throw(); ++instances; }
 ~test() { --instances; }
};

#include <iostream>
int main()
{
  srand(0);

  try { Dynarray<test> d(1000); Dynarray<int> e(0,100); }
  catch (...) {}

  Dynarray<int> a,b;
  static_assert(noexcept(Dynarray<int>()),"");
  static_assert(noexcept(Dynarray<int>(std::move(a))),"");
  static_assert(noexcept(a=Dynarray<int>()),"");
  static_assert(noexcept(a.swap(b)),"");

  std::cout << instances << '\n';
}

Nebenbei bemerkt scheint gcc 4.7 die noexcept-Spezifikation für Destruktoren nicht korrekt umzusetzen - hier hilft die explizite Angabe. gcc 4.8 und clang kommen auch ohne aus.

[iksepschensaif]

Gibt es einen Grund, weshalb rbegin & co immer noch nicht noexcept sind?

[Sone]

@camper: Toll. Guck ich mir heute an, und sehe mir an wie du die einzelnen Sachen umgesetzt hast.

iksepschensaif schrieb:

Gibt es einen Grund, weshalb rbegin & co immer noch nicht noexcept sind?

Der Ctor von reverse_iterator ist nicht noexcept -spezifiziert.
Wofür ich eigentlich keinen Grund sehe, aber was solls.

[Sone]

Was mir aufgefallen ist: sehr schön umgesetzt mit den alloc_*-Funktionen!

Ok, erstens kommt bei dir häufig was langes vor, ist natürlich gut lesbar, aber kürzbar. Bspw. 14 - 20:

for ( ; i != n; ) 
        { 
            std::allocator_traits<Allocator>::construct( alloc, p, *first ); 
            ++p; 
            ++i; 
            ++first; 
        }

statt

while ( i++ != n ) 
            std::allocator_traits<Allocator>::construct( alloc, p++, *first++ );

Dazu kommt in den ... handlern Code wiederholt vor, sogar Zeichengleich:

for ( ; i--; )
            std::allocator_traits<Allocator>::destroy( alloc, --p );
        std::allocator_traits<Allocator>::deallocate( alloc, p, n );

Das muss man doch auslagern.

static_assert( std::is_same<value_type, typename std::allocator_traits<allocator_type>::value_type>::value, "allocator must be compatibel!" );

Das ist mir gar nicht aufgefallen, gut!
Aber wieso ein Default-Ctor?

camper schrieb:

Sone schrieb:

Ich habe schon öfter mit dem Gedanken gespielt, Dynarrray s der Größe Null zu verbieten.

Den Nullzustand hast du schon, weil die Klasse move-bar ist.

Das verstehe ich nicht.

Was ich meinte ist, dass es keine sinnvolle Verwendung für null-sized Dynarrays gibt, weil man damit nichts machen kann.
Es geht nicht darum, dass es die Größe Null nicht annehmen darf - das ist ja schon gegeben.
Ich meinte, das man ihn nicht so erzeugen darf.
Und das lässt du ja...

[camper]

Sone schrieb:

statt

while ( i++ != n ) 
            std::allocator_traits<Allocator>::construct( alloc, p++, *first++ );

Wenn du sicherstellst, das auch im Falle von Exceptions immer richtig gezählt wird...

Sone schrieb:

Dazu kommt in den ... handlern Code wiederholt vor, sogar Zeichengleich:

for ( ; i--; )
            std::allocator_traits<Allocator>::destroy( alloc, --p );
        std::allocator_traits<Allocator>::deallocate( alloc, p, n );

Das muss man doch auslagern.

Da geht sicher was.
Richtig zufrieden bin ich mit der jetzigen Struktur sowieso nicht. Man könnte man z.B. der Dynarrayklasse eine Basisklasse geben, die sich nur um die Allokation kümmert, während Dynarray selbst nur die Initialisierung vornimmt. Die alloc_-Funktionen wären dann eher im Stile von uninitialized_ zu schreiben.
Kürzer wird es dadurch aber vermutlich nicht.

Sone schrieb:

Aber wieso ein Default-Ctor?

Wenn ein Nullzustand sowieso existiert, gibt es keinen Grund dessen Erzeugung unnötig komplex zu halten. Gelegentlich legt man Objekte (z.B. in einem Array) an, ohne Ihne gleich Werte zuornen zu können.

Evtl. sollten noch weitere Konstruktorn hinzugefügt werden:
- für InputIteratoren mit expliziter Größenangabe (muss man überlegen, was bei Lesefehlern passieren soll - Abbruch oder Initialisierung mit einem Defaultwert?)
- Konvertierung für andere Container

[TyRoXx]

Spricht etwas gegen erase , clear oder shrink_to_fit ?

[Shade Of Mine]

TyRoXx schrieb:

Spricht etwas gegen erase , clear oder shrink_to_fit ?

Ja.
Das Dynarray ist per Definition immer voll.