Dynarray Implementation

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

[krümelkacker]

TyRoXx schrieb:

Spricht etwas gegen erase , clear oder shrink_to_fit ?

DynArray ist als VLA-Ersatz gedacht.

[knivil]

Sone schrieb:

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

Also wenn Arrays (Multi)Mengen repraesentieren, dann sollte auch eine Moeglichkeit bestehen, die leere Menge zu repraesentieren. Siehe Haskell [] | [a] vs. Maybe. Meine Algorithmen akzeptieren meist leere Mengen und ich spare mir eine seperate Fehlerabfrage.

[TyRoXx]

Shade Of Mine schrieb:

TyRoXx schrieb:

Spricht etwas gegen erase , clear oder shrink_to_fit ?

Ja.
Das Dynarray ist per Definition immer voll.

Was soll das bedeuten?

krümelkacker schrieb:

TyRoXx schrieb:

Spricht etwas gegen erase , clear oder shrink_to_fit ?

DynArray ist als VLA-Ersatz gedacht.

Und das heißt?

Es ist ja nicht so als würde Dynarray diese Operationen im jetzigen Zustand verhindern. Ein freies erase ist bloß unnötig ineffizient.

template <class T, class A>
void erase(Dynarray<T, A> &a, typename Dynarray<T, A>::iterator begin, typename Dynarray<T, A>::iterator end)
{
	Dynarray<T, A> remaining(a.size() - std::distance(begin, end));
	std::move(a.begin(), begin, remaining.begin());
	std::move(end, a.end(), remaining.begin() + std::distance(a.begin(), begin));
	a = std::move(remaining);
}

EDIT: Besser, aber noch nicht so gut wie eine Methode.

clear als Methode würde den Speicher noch nicht freigeben (äquivalent zu .erase(begin(), end()) ). So kann man in einen Nullzustand gelangen, ohne sofort eine teure Deallokation machen zu müssen.

EDIT 2: Warum sagt mir denn niemand, dass ein Allocator beim Freigeben die Größe verlangt? So ist günstiges Verkleinern wie bei vector natürlich nicht möglich.

[krümelkacker]

TyRoXx schrieb:

krümelkacker schrieb:

DynArray ist als VLA-Ersatz gedacht.

Und das heißt?

Wann will, dass sich

void foo(int x) {
  DynArray<double> da(x);
  ...
}

so ähnlich verhält wie

void foo(int x) {
  double da[x]; // C99 VLA feature
  ...
}

ohne, dass man am Sprachkern noch rumfummeln muss und damit auf die C99-Regeln verzichten kann

[camper]

krümelkacker schrieb:

TyRoXx schrieb:

krümelkacker schrieb:

DynArray ist als VLA-Ersatz gedacht.

Und das heißt?

Wann will, dass sich

void foo(int x) {
  DynArray<double> da(x);
  ...
}

so ähnlich verhält wie

void foo(int x) {
  double da[x]; // C99 VLA feature
  ...
}

ohne, dass man am Sprachkern noch rumfummeln muss und damit auf die C99-Regeln verzichten kann

Also braucht man noch einen entsprechenden Allokator. Wobei ich keine Ahnung habe, wie dann move unterstützt werden könnte.

[krümelkacker]

Im ursprünglichen Proposal steht auch nichts von Allokatoren oder Move-Operationen. Die Stack-Allokation wäre dann QoI/Compiler-Magie. Und ich würde das wahrscheinlich auch so basteln, dass, falls der Stack schon "recht voll" ist oder die geforderte Größe eine gewisse Grenze überschreitet, trotzdem auf den Freispeicher ausgewichen wird.

Ein Move könnte man trotzdem noch zulassen. Allerdings muss dann im Konstruktor geprüft werden, woher das Quellobjekt den Speicher herbekommen hat und ggf doch einfach kopieren, wenn es Stack-Speicher war.

Die Stack-Optimierung könnte so aussehen, dass der dynarray-Klasse noch einen besonderern, privaten Konstruktor bekommt, der dann ggf automatisch aufgerufen wird und worüber der allozierte Stack-Speicher empfangen werden kann.