Dynarray Implementation

[camper]

Sone schrieb:

camper schrieb:

TyRoXx schrieb:

Der Destruktor ist implizit noexcept(true) .

oh?

Ich glaube, TyRoXx verwechselt da den Dtor mit Deallokationsfunktionen.

Nicht unbedingt.

n3337 schrieb:

12.4 Destructors [class.dtor]
[...]
3 A declaration of a destructor that does not have an exception-specification is implicitly considered to have
the same exception-specification as an implicit declaration (15.4).

Die Exceptionspezifikation eines implizit deklarierten Destruktors hängt von den Exceptionsspezifikationen der Funktionen ab, die von diesem aufgerufen würden, d.h. den Destruktoren der Member und der direkten oder virtuellen Basisklassen. Wenn keiner dieser Destruktoren direkt oder indirekt eine explizite Exceptionspezifikation erhält, läuft das somit tatsächlich im Allgemeinen auf eine Sepzifikation noexcept(true) hinaus.
Die Exceptionspezifikation ist mAn Teil der Schnittstelle und sollte somit nicht implizit von privaten Details der Klasse abhängen - deshalb halte ich eine explizite Angabe für sinnvoll. Der Standard macht es anders, man kann also durchaus auch andere Ansicht sein.

[iksepschensaif]

Lol, 5 Seiten Ratschläge und es funktioniert immer noch nicht.
Abgesehen von den Warnungen, wenn man deinen Code kompiliert (schonmal mit -Wall -Wextra getestet?), es hat noch einige Bugs.

Hier mal ein einfaches Testprogramm:

int instances = 0;

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

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

int main()
{
  srand(0);

  try { Dynarray<test> d(1000); }
  catch (...) {}

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

Wenn Zeile 12 etwas abändert, dürfte der Fehler etwas klarer werden.

~test() { std::cout << --instances << '\n'; }

[Sone]

iksepschensaif schrieb:

Lol, 5 Seiten Ratschläge und es funktioniert immer noch nicht.
Abgesehen von den Warnungen, wenn man deinen Code kompiliert (schonmal mit -Wall -Wextra getestet?), es hat noch einige Bugs.

Hier mal ein einfaches Testprogramm:

int instances = 0;

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

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

int main()
{
  srand(0);

  try { Dynarray<test> d(1000); }
  catch (...) {}

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

Wenn Zeile 12 etwas abändert, dürfte der Fehler etwas klarer werden.

~test() { std::cout << --instances << '\n'; }

Gefixed. Da war ein Missverständnis, ich dachte der Dtor wird dann nicht mehr aufgerufen ... jetzt ist das geklärt. (Und noch eine kleine Fallunterscheidung für den einen delegation Ctor )

Vielen Dank :xmas1:

Edit: o.O eine bleibt immer übrig. Setz mich dran...

[Sone]

Ach, dein Beispiel ist doch bescheuert.
Man muss das may_throw vor die Inkrementierung setzen, ist doch klar.

Edit: Ihr seit ganz sicher, dass man bei einer Exception aus dem Dtor einfach nix aufräumen muss?

[Sone]

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

[iksepschensaif]

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

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