Array2D: Evolution von manueller Speicherverwaltung zur STL

[DocShoe]

Hallo,

ich habe etwas im Forum gelesen und bin auf einen Thread gestoßen, in dem es um die Überarbeitung der FAQ geht. In einem Posting ging es dabei um die Implementierung einer Klasse für 2D-Arrays, und weil das Thema immer wieder auftaucht und ich gerade Bock drauf hatte habe ich eine C++ Lösung auf Basis von std::vector, die evolutionär aus manueller Speicherverwaltung entsteht. Bitte spart nicht mit Kritik und Verbesserungsvorschlägen, das ist der erste Anlauf

Das Problem:
Immer wieder werden zweidimensionale Arrays für verschiedene Lösungen gebraucht, seien es Matrizen oder Spielfelder. Der folgende Thread entwickelt aus einer naiven C++ Lösung mit rohen, besitzenden Zeigern eine C++ Lösung, die die komplette Speicherverwaltung wegkapselt und sich auf die reine Array-Funktionalität beschränkt.

2D-Array Version 1: manuelle Speicherverwaltung und rohe Zeiger
In dieser Version wird zunächst der Speicher für die Zeiger auf die einzelnen Zeilen angefordert und anschließend Speicher für die jeweilige Zeile selbst. Manuelle Speicherverwaltung und rohe Zeiger sind in mehreren Punkten fehleranfällig:

• sie ist nicht Exception-safe und führt im Fall einer nicht-gefangenen Exception zur Speicherlecks.
• rohe Zeiger besitzen keine Informationen mehr über die Anzahl und Größe der einzelnen Dimensionen. Man muss die Größen der Dimensionen bei jedem Funktionsaufruf übergeben.
• kein geprüfter Zugriff auf Elemente, es kann auf Elemente außerhalb der Arraygrenzen zugegriffen werden.
• die einzelnen Elemente sind nicht initialisiert und haben nach ihrer Erzeugung zufällige Werte
• Durch wiederholte Benutzung dieser Technik schleichen sich leicht Flüchtigkeitsfehler ein wie zB das Vertauschen der Dimensionen oder die Benutzung von delete anstatt von delete[] bei der Freigabe des Speichers.
• Die Klasse funktioniert nur für den Datentyp double
• der Speicher ist nicht zusammenhängend und damit nicht besonders Cache-freundlich.

#include <cstddef>
#include <stdexcept>

void client( double** Array,
	     std::size_t Rows,
             std::size_t Cols )
{
   // Exception führt zu Speicherleck, weil sie im Aufrufer nicht gefangen wird und der Aufrufer den Speicher
   // nicht mehr freigeben kann.
   throw std::runtime_error( "Boom" );
}

void driver()
{
   const std::size_t Rows = 7;
   const std::size_t Cols = 4;

   // Speicher anfordern
   double** Array = new double*[Rows];
   for( size_t i = 0; i < Cols; ++i )
   {
      Array[i] = new double[Cols];
   }
   client( Array, Rows, Cols );

   // ... Speicher wieder freigeben
   for( size_t i = 0; i < Cols; ++i )
   {
      delete[] Array[i];
   }
   delete[] Array;
}

2D-Array Version 2: manuelle Speicherverwaltung und Bündelung der Informationen in einem struct.
Diese Version behebt den Nachteil, dass man die Größen der Dimensionen mitführen muss, löst aber alle anderen Probleme nicht:

• sie ist nicht Exception-safe und führt im Fall einer nicht-gefangenen Exception zur Speicherlecks.
• kein geprüfter Zugriff auf Elemente, es kann auf Elemente außerhalb der Arraygrenzen zugegriffen werden.
• die einzelnen Elemente sind nicht initialisiert und haben nach ihrer Erzeugung zufällige Werte
• Durch wiederholte Benutzung dieser Technik schleichen sich leicht Flüchtigkeitsfehler ein, zB die Benutzung von delete anstatt von delete[] bei der Freigabe des Speichers.
• Die Klasse funktioniert nur für den Datentyp double
• der Speicher ist nicht zusammenhängend und damit nicht besonders Cache-freundlich.

#include <cstddef>
#include <stdexcept>

struct Array2D
{
   double** Data    = nullptr;
   std::size_t Rows = 0;
   std::size_t Cols = 0;
};

void client( const Array2D& Array )
{
   // Exception führt zu Speicherleck, weil sie im Aufrufer nicht gefangen wird und der Aufrufer den Speicher 
   // nicht mehr freigeben kann.
   throw std::runtime_error( "Boom" );
}

void driver()
{
   const std::size_t Rows = 7;
   const std::size_t Cols = 4;

   // Speicher anfordern
   Array2D Array;
   Array.Data = new double*[Rows];
   for( std::size_t i = 0; i < Rows; ++i )
   {
      Array.Data[i] = new double[Cols];
   }
   Array.Rows	= Rows;
   Array.Cols	= Cols;

   client( Array );

   // ... Speicher wieder freigeben
   for( std::size_t i = 0; i < Array.Rows; ++i )
   {
      delete[] Array.Data[i];
   }
   delete[] Array.Data;
}

2D-Array Version 3: manuelle Speicherverwaltung und Bündelung der Informationen in einem struct und die Freigabe des Speichers im Destruktor.
Diese Version löst zwar das Problem der Freigabe des Speichers, bringt aber neue Probleme mit sich:

• Array2D-Objekte sind zwar kopierbar, führen dann aber durch doppelte Freigabe des Speichers zu undefiniertem Verhalten (Rule of three/Rule of five)
• der Zustand eines Array2D-Objektes ist von außen veränderbar und erlaubt das manuelle Freigeben des Speichers. Die doppelte Freigabe des Speichers im Destruktor führt dann zu undefiniertem Verhalten
• kein geprüfter Zugriff auf Elemente, es kann auf Elemente außerhalb der Arraygrenzen zugegriffen werden.
• die einzelnen Elemente sind nicht initialisiert und haben nach ihrer Erzeugung zufällige Werte
• Die Klasse funktioniert nur für den Datentyp double
• der Speicher ist nicht zusammenhängend und damit nicht besonders Cache-freundlich.

#include <cstddef>
#include <stdexcept>

struct Array2D
{
   double** Data    = nullptr;
   std::size_t Rows = 0;
   std::size_t Cols = 0;

   Array( std::size_t Rows,
          std::size_t Cols ) :
      Rows( Rows ),
      Cols( Cols )
   {
      Data = new double*[Rows];
      for( std::size_t i = 0; i < Rows; ++i )
      {
         Data[i] = new double[Cols];
      }
   }

   ~Array2D()
   {
      for( std::size_t i = 0; i < Rows; ++i )
      {
         delete[] Data[i];
      }
      delete[] Data;
   }
};

void client( Array2D Array )
{
   // Boom!
   // Hier wird der Speicher des Arrays manuell freigegeben. Am Ende der Funktion
   // wird der Destruktor von Array aufgerufen, der den Speicher erneut freigibt
   // und damit undefiniertes Verhalten erzeugt.
   delete[] Array.Data;
}

void driver()
{
   const std::size_t Rows = 7;
   const std::size_t Cols = 4;

   Array2D Array( Rows, Cols );

   // Dieser Funktionsaufruf erzeugt subtil undefiniertes Verhalten:
   // Der Funktionsaufruf erzeugt eine Kopie des Objektes und ruft die Funktion
   // client() mit der Kopie auf. Sowohl Array als auch die Kopie zeigen auf
   // den gleichen Speicher, da bei einer Kopie eine exakte Kopie von Array
   // erzeugt wird. Der Speicher wird dann zwei Mal freigegeben: Ein Mal beim
   // Zerstören der Kopie und ein zweites Mal beim Zerstören von Array (und ein 
   // drittes Mal in der Funktion client).
   client( Array );
}

2D-Array Version 4: manuelle Speicherverwaltung und Kapselung der Informationen in einer Klasse.
Diese Version löst viele der vorherigen Probleme, erfordert dafür aber auch relativ viel Code. Einige Probleme sind immer noch nicht gelöst:

• kein geprüfter Zugriff auf Elemente, es kann auf Elemente außerhalb der Arraygrenzen zugegriffen werden.
• Die Klasse funktioniert nur für den Datentyp double
• der Speicher ist nicht zusammenhängend und damit nicht besonders Cache-freundlich.
• relativ viel Code für ein einfaches Array

#include <cstddef>

class Array2D
{
public:
   Array2D() = default;
   Array2D( std::size_t Rows,
            std::size_t Cols )
   {
       // Speicher für Arraydaten anfordern
       allocate( Rows, Cols );
   }

   // Kopierkonstruktor und Zuweisungsoperator
   Array2D( const Array2D& other )
   {
      // Array aus bestehendem Array erzeugen
      clone( other );
   }

   Array2D& operator=( const Array2D& other )
   {
      // Array aus bestehendem Array erzeugen
      clone( other );
      return *this;
   }

   // Movekonstruktor und move-Zuweisungsoperator
   Array2D( Array2D&& other )
   {
      // Daten des anderen Arrays übernehmen
      Rows_ = other.rows();
      Cols_ = other.cols();
      Data_ = other.data();

      // Da dieses Objekt jetzt für den angeforderten Speicher verantwortlich
      // ist muss er dem anderen Objekt "weggenommen" werden, damit es zu keiner
      // doppelten Freigabe kommt.
      other.Data_ = nullptr;
   }

   Array2D& operator=( Array2D&& other )
   {
      // Speicher freigeben
      deallocate();

      // Daten des anderen Arrays übernehmen
      Rows_ = other.rows();
      Cols_ = other.cols();
      Data_ = other.data();

      // Da dieses Objekt jetzt für den angeforderten Speicher verantwortlich
      // ist muss er dem anderen Objekt "weggenommen" werden, damit es zu keiner
      // doppelten Freigabe kommt.
      other.Data_ = nullptr;
      return *this;
   }

   ~Array2D()
   {
      deallocate();
   }

   std::size_t rows() const
   {
      return Rows_;
   }

   std::size_t cols() const
   {
      return Cols_;
   }

   std::size_t size() const
   {
      return rows() * cols();
   }

   bool empty() const
   {
      return Data_;
   }

   double** data()
   {
      return Data_;
   }

   double const* const* data() const
   {
      return Data_;
   }

private:
   void clone( const Array2D& other )
   {
      // Schritt 1: benutzten Speicher freigeben
      deallocate();

      // Schritt 2: Speicher für die neuen Daten anfordern
      allocate( other.rows(), other.cols() );

      // Schritt 3: Daten aus dem zu kopierenden Array kopieren
      for( std::size_t r = 0; r < rows(); ++r )
      {
         for( std::size_t c = 0; c < cols(); ++c )
         {
            Data_[r][c] = other.Data_[r][c];
         }
      }
   }

   void allocate( std::size_t Rows,
                  std::size_t Cols )
   {
      Data_ = new double*[Rows];
      for( std::size_t r = 0; r < Rows; ++r )
      {
         Data_[r] = new double[Cols];
         for( std::size_t c = 0; c < Cols; ++c )
         {
            Data_[r][c] = 0.0;
         }
      }
      Rows_ = Rows;
      Cols_ = Cols;
   }

   void deallocate()
   {
      for( std::size_t i = 0; i < Rows_; ++i )
      {
         delete[] Data_[i];
      }
      delete[] Data_;
      Data_ = nullptr;
   }

   double** Data_	= nullptr;
   std::size_t Rows_	= 0;
   std::size_t Cols_	= 0;
};


void client( const Array2D& Array )
{
   // tu was mit dem Array
}

void driver()
{
   const std::size_t Rows = 7;
   const std::size_t Cols = 4;

   Array2D Array1( Rows, Cols );
   client( Array1 );
}

2D-Array Version 5: manuelle Speicherverwaltung und Kapselung der Informationen in einer Klasse.
In dieser Version kann der Zugriff auf die Arrayelemente geprüft werden, aber diese Probleme sind immer noch nicht glöst:

• Die Klasse funktioniert nur für den Datentyp double
• der Speicher ist nicht zusammenhängend und damit nicht besonders Cache-freundlich.

#include <cstddef>
#include <stdexcept>

class Array2D
{
public:
   Array2D() = default;
   Array2D( std::size_t Rows,
            std::size_t Cols )
   {
      // Speicher für Arraydaten anfordern
      allocate( Rows, Cols );
   }

   // Kopierkonstruktor und Zuweisungsoperator
   Array2D( const Array2D& other )
   {
      // Array aus bestehendem Array erzeugen
      clone( other );
   }

   Array2D& operator=( const Array2D& other )
   {
      // Array aus bestehendem Array erzeugen
      clone( other );
      return *this;
   }

   // Movekonstruktor und move-Zuweisungsoperator
   Array2D( Array2D&& other )
   {
      // Daten des anderen Arrays übernehmen
      Rows_ = other.rows();
      Cols_ = other.cols();
      Data_ = other.Data_;

      // Da dieses Objekt jetzt für den angeforderten Speicher verantwortlich
      // ist muss er dem anderen Objekt "weggenommen" werden, damit es zu keiner
      // doppelten Freigabe kommt.
      other.Data_ = nullptr;
   }

   Array2D& operator=( Array2D&& other )
   {
      // Speicher freigeben
      deallocate();

      // Daten des anderen Arrays übernehmen
      Rows_ = other.rows();
      Cols_ = other.cols();
      Data_ = other.Data_;

      // Da dieses Objekt jetzt für den angeforderten Speicher verantwortlich
      // ist muss er dem anderen Objekt "weggenommen" werden, damit es zu keiner
      // doppelten Freigabe kommt.
      other.Data_ = nullptr;
      return *this;
   }

   ~Array2D()
   {
      deallocate();
   }

   std::size_t rows() const
   {
      return Rows_;
   }

   std::size_t cols() const
   {
      return Cols_;
   }

   double& operator()( std::size_t Row,
                       std::size_t Col )
   {
      return Data_[Row][Col];
   }

   const double& operator()( std::size_t Row,
                             std::size_t Col ) const
   {
      return Data_[Row][Col];
   }

   double& at( std::size_t Row,
               std::size_t Col )
   {
      check_bounds( Row, Col );
      return Data_[Row][Col];
   }

   const double& at( std::size_t Row,
                     std::size_t Col ) const
   {
      check_bounds( Row, Col );
      return Data_[Row][Col];
   }

private:
   void clone( const Array2D& other )
   {
      // Schritt 1: benutzten Speicher freigeben
      deallocate();

      // Schritt 2: Speicher für die neuen Daten anfordern
      allocate( other.rows(), other.cols() );

      // Schritt 3: Daten aus dem zu kopierenden Array kopieren
      for( std::size_t r = 0; r < rows(); ++r )
      {
         for( std::size_t c = 0; c < cols(); ++c )
         {
            Data_[r][c] = other.Data_[r][c];
         }
      }
   }

   void allocate( std::size_t Rows,
                  std::size_t Cols )
   {
      Data_ = new double*[Rows];
      for( std::size_t r = 0; r < Rows; ++r )
      {
         Data_[r] = new double[Cols];
         for( std::size_t c = 0; c < Cols; ++c )
         {
            Data_[r][c] = 0.0;
         }
      }
      Rows_ = Rows;
      Cols_ = Cols;
   }

   void deallocate()
   {
      for( std::size_t i = 0; i < Rows_; ++i )
      {
         delete[] Data_[i];
      }
      delete[] Data_;

      Rows_ = 0;
      Cols_ = 0;
      Data_ = nullptr;
   }

   void check_bounds( std::size_t Row,
                      std::size_t Col ) const
   {
      if( Row >= rows() || Col >= cols() )
      {
         throw std::out_of_range( "Ungültiger Arrayindex beim Zugriff auf Array2D" );
      }
   }

   double** Data_	= nullptr;
   std::size_t Rows_	= 0;
   std::size_t Cols_	= 0;
};


void client( const Array2D& Array )
{
   // geprüfter Zugriff auf Elemente des Array
   double v1 = Array.at( 0, 0 );

   // Zeiger auf erstes Element des Array
   double const*  v2 = &Array( 0,0 );
}

void driver()
{
   const std::size_t Rows = 7;
   const std::size_t Cols = 4;

   Array2D Array1( Rows, Cols );
   client( Array1 );
}

2D-Array Version 6: Kapselung der Informationen in einer Klasse und Benuzung von std::vector.
Das Problem des nicht-linearen Speichers ist durch Verwendung von std::vector gelöst. Durch Benutzung von std::vector entfallen zusätzlich einige Methoden, die ohne std::vector notwendig waren.
Lediglich ein Problem bleibt:

• Die Klasse funktioniert nur für den Datentyp double

#include <cstddef>
#include <vector>

class Array2D
{
public:
   Array2D() = default;
   Array2D( Array2D&& other ) = default;
   Array2D( const Array2D& other ) = default;

   Array2D( std::size_t Rows,
            std::size_t Cols ) :
      Data_( Rows * Cols ),
      Rows_( Rows ),
      Cols_( Cols )
   {
   }

   std::size_t rows() const
   {
      return Rows_;
   }

   std::size_t cols() const
   {
      return Cols_;
   }

   std::size_t size() const
   {
      return Data_.size();
   }

   bool empty() const
   {
      return Data_.empty();
   }

   // Zugriff auf Elemente des Arrays
   double& operator()( std::size_t Row,
                       std::size_t Col )
   {
      return Data_[calc_index( Row, Col )];
   }

   const double& operator()( std::size_t Row,
                             std::size_t Col ) const
   {
      return Data_[calc_index( Row, Col )];
   }

   double& at( std::size_t Row,
               std::size_t Col )
   {
      return Data_.at( calc_index( Row, Col ) );
   }

   const double& at( std::size_t Row,
                     std::size_t Col ) const
   {
      return Data_.at( calc_index( Row, Col ) );
   }

private:
   std::size_t calc_index( std::size_t Row,
                           std::size_t Col ) const
   {
      // Zeilen- und Spaltenindex in linearen Index umrechnen
      return Row * cols() + Col;
   }

   std::vector<double>  Data_;
   std::size_t Rows_	= 0;
   std::size_t Cols_	= 0;
};


void client( const Array2D& Array )
{
   // geprüfter Zugriff auf Elemente des Array
   double v1 = Array.at( 0, 0 );

   // Zeiger auf erstes Element des Array
   double const*  v2 = &Array( 0,0 );
}

void driver()
{
   const std::size_t Rows = 7;
   const std::size_t Cols = 4;

   Array2D Array1( Rows, Cols );
   client( Array1 );
}

2D-Array Version 7: Version als Template Klasse.
Diese Version ist als Template realisiert und erlaubt die Benutzung für verschiedene Datentypen. Es gibt immer noch einige Dinge, die verbesserungswürdig sind, aber prinzipiell ist die Klasse so benutzbar. Einziger Nachteil: Der Zugriff auf die Elemente erfolgt nicht mehr über eckige Klammern, sondern über runde, weil sich der operator[] nicht für zwei Parameter überladen lässt.

Möglich Verbesserungen:

• iterator Unterstützung für alle Elemente/Zeilen/Spalten
• eine Art array_view für einzelnen Zeilen oder Spalten
• verschiedene Komfortfunktionen (zB resize, swap, ...)
• Vergleichsoperatoren ==, !=, ...
• strong exception safety
• Auswahl des zu Grunde liegenden Container per Template Parameter
• ...

#include <cstddef>
#include <vector>

template<typename T>
class Array2D
{
public:
   using value_type      = T;
   using reference  	 = T&;
   using const_reference = const T&;

   Array2D() = default;
   Array2D( Array2D&& other ) = default;
   Array2D( const Array2D& other ) = default;

   Array2D( std::size_t Rows,
            std::size_t Cols ) :
      Data_( Rows * Cols ),
      Rows_( Rows ),
      Cols_( Cols )
   {
   }

   std::size_t rows() const
   {
      return Rows_;
   }

   std::size_t cols() const
   {
      return Cols_;
   }

   std::size_t size() const
   {
      return Data_.size();
   }

   bool empty() const
   {
      return Data_.empty();
   }

   // Zugriff auf Elemente des Arrays
   reference operator()( std::size_t Row,
                         std::size_t Col )
   {
      return Data_[calc_index( Row, Col )];
   }

   const_reference operator()( std::size_t Row,
                               std::size_t Col ) const
   {
      return Data_[calc_index( Row, Col )];
   }

   reference& at( std::size_t Row,
                  std::size_t Col )
   {
      return Data_.at( calc_index( Row, Col ) );
   }

   const_reference at( std::size_t Row,
                       std::size_t Col ) const
   {
      return Data_.at( calc_index( Row, Col ) );
   }

private:
   std::size_t calc_index( std::size_t Row,
                           std::size_t Col ) const
   {
      return Row * cols() + Col;
   }

   std::vector<value_type> Data_;
   std:.size_t Rows_ = 0;
   std::size_t Cols_ = 0;
};


void client( const Array2D<double>& Array )
{
   // geprüfter Zugriff auf Elemente des Array
   double v1 = Array.at( 0, 0 );

   // Zeiger auf erstes Element des Array
   double const*  v2 = &Array( 0,0 );
}

void driver()
{
   const std::size_t Rows = 7;
   const std::size_t Cols = 4;

   Array2D<double> Array1( Rows, Cols );
   client( Array1 );
}

2D-Array Version 8: Endgültige Version der Beispielklasse.
Es wird nicht mehr zwingend std::vector als zu Grunde liegender Container verwendet, über einen zweiten Template Parameter lässt sich der Container-Typ festlegen. Die Methodenaufrufe für size(), empty(), begin() und resize() werden nicht mehr direkt auf dem Container aufgerufen, sondern über freie Funktionen, die sich für eigene Container spezialisieren lassen. Das wird notwendig, wenn der Container andere Methoden benutzt oder Methoden fehlen, die dann implementiert werden müssen.

Diese Dinge sind immer noch verbesserungswürdig:

• iterator Unterstützung für alle Elemente/Zeilen/Spalten
• eine Art array_view für einzelnen Zeilen oder Spalten
• verschiedene Komfortfunktionen (zB resize, swap, ...)
• Vergleichsoperatoren ==, !=
• strong exception safety
• Adaption an Container über eine traits-Klasse
• ...

#include <cstddef>
#include <list>
#include <vector>
#include <stdexcept>

// freie Funktionen zur Umsetzung bestimmter Anforderungen an den Array-Containerdatentyp. Standardmäßig werden
// alle STL-Container unterstützt, für eigene Container-Typen müssen ggf. diese Funktionen spezialisiert werden.
template<typename ContainerType>
inline std::size_t array2d_container_size( const ContainerType& ct )
{
   return ct.size();
}

template<typename ContainerType>
inline bool array2d_container_empty( const ContainerType& ct )
{
   return ct.empty();
}

// eigentlich reicht std::begin, aber um einen Satz von Funktionen mit konsistenter Benennung zu haben 
// wird hier array2d_container_begin benutzt.
template<typename ContainerType>
inline auto array2d_container_begin( ContainerType& ct ) -> decltype( ct.begin() )
{
   return ct.begin();
}

template<typename ContainerType>
inline auto array2d_container_begin( const ContainerType& ct ) -> decltype( ct.begin() )
{
   return ct.begin();
}

template<typename ContainerType>
inline void array2d_container_resize( ContainerType& ct,
                                      std::size_t Rows,
                                      std::size_t Cols )
{
   ct.resize( Rows * Cols );
}

// Die eigentliche Array2D Klasse mit std::vector als Standard-Container
template<typename T, typename container_type = std::vector<T>>
class Array2D
{
public:
   using value_type      = T;
   using reference       = T&;
   using const_reference = const T&;

   Array2D() = default;
   Array2D( Array2D&& other ) = default;
   Array2D( const Array2D& other ) = default;

   Array2D( std::size_t Rows,
            std::size_t Cols ) :
      Rows_( Rows ),
      Cols_( Cols )
   {
      array2d_container_resize( Data_, Rows, Cols );
   }

   std::size_t rows() const
   {
      return Rows_;
   }

   std::size_t cols() const
   {
      return Cols_;
   }

   std::size_t size() const
   {
      return array2d_container_size( Data_ );
    }

   bool empty() const
   {
      return array2d_container_empty( Data_ );
   }

   // Zugriff auf Elemente des Arrays
   reference operator()( std::size_t Row,
                         std::size_t Col )
   {
      return element_at( Row, Col );
   }

   const_reference operator()( std::size_t Row,
                               std::size_t Col ) const
   {
      return element_at( Row, Col );
   }

   reference& at( std::size_t Row,
                  std::size_t Col )
   {
      check_bounds( Row, Col );
      return element_at( Row, Col );
   }

   const_reference at( std::size_t Row,
                       std::size_t Col ) const
   {
      check_bounds( Row, Col );
      return element_at( Row, Col );
   }

private:
   void check_bounds( std::size_t Row,
                      std::size_t Col ) const
   {
      if( Row >= rows() || Col >= cols() )
      {
         throw std::out_of_range( "Ungültiger Arrayindex beim Zugriff auf Array2D" );
      }
   }

   std::size_t calc_index( std::size_t Row,
                           std::size_t Col ) const
   {
      return Row * cols() + Col;
   }

   reference element_at( std::size_t Row,
                         std::size_t Col )
   {
      auto pos = array2d_container_begin( Data_ );
      std::advance( pos, calc_index( Row, Col ) );
      return *pos;
   }

   const_reference element_at( std::size_t Row,
                               std::size_t Col ) const
   {
      return const_cast<reference>( const_cast<Array2D*>( this )->element_at( Row, Col ) );
   }

   container_type Data_;
   std::size_t    Rows_ = 0;
   std::size_t    Cols_ = 0;
};


// 2D Array mit std::list<double> als zu Grunde liegender Container
using Array2D_t = Array2D<double, std::list<double>>;

void client( Array2D_t& Array )
{
   Array.at( 1, 0 ) = 10.0;
   double v2 = Array( 1,0 );
}

void driver()
{
   const std::size_t Rows = 7;
   const std::size_t Cols = 4;

   Array2D_t Array( Rows, Cols );
   client( Array );
}
```

[zeropage]

Finde ich gut

Habe es mal gebookmarkt, falls irgendwo irgendwann die Frage nach einem 2DArray auftauchen sollte.

[Jockelx]

@docshoe sagte in Array2D: Evolution von manueller Speicherverwaltung zur STL:

Nachteil: Der Zugriff auf die Elemente erfolgt nicht mehr über eckige Klammern, >sondern über runde, weil sich der operator[] nicht für zwei Parameter überladen lässt.

Doch. Der Erste muss nur ein Proxy (oder wie du es nennen magst) zurück geben.

[DocShoe]

@jockelx
nein und ja. Der operator[] lässt sich nicht für zwei Parameter überladen, aber man kann natürlich einen Proxy zurückgeben, der selbst wieder den operator[] überlädt. Die Klasse kann sowieso nicht als in-place Ersatz für den naiven Ansatz benutzt werden, und wenn man das doch tut muss man halt auch noch den Elementzugriff anfassen.

Edit:
Selbst wenn man ihn für zwei Parameter überladen könnte sähe der Aufruf dann so aus

Array2D<double> Arr;
double v = Arr[0,0];

was auch nicht so aussieht wieder der Zugriff auf ein Array aus Arrays. Mit nem Proxyobjekt kommt man dem wohl am nächsten, wenn es unbeding so aussehen muss.

[DNKpp]

Hey,
ich hatte auch schon öfter an sowas gedacht und auch umgesetzt. Letztendlich finde ich es aber deutlich angenehmer, wenn dieses Array2D lediglich ein Wrapper um einen templatisierten Container ist. Im Endeffekt limitierst du hier lediglich den Benutzer dieser Klasse, der gerne eine Abstraktion nutzen würde. Im Endeffekt kann es dir eigentlich egal sein, ob die Daten nun als plain Array, std::array, std::vector oder std::list vorliegen; es geht lediglich darum eine Abstraktionsebene zwischen den Eindimensionalen- und Mehrdimensionalen-Indexzugriff zu kreieren. Prinzipiell kann man das gut mit einem std::string_view vergleichen; du möchtest eine View mit entsprechendem Interface auf die Daten erstellen, dafür musst du den MemoryOwner aber nicht besitzen.

[DocShoe]

@dnkpp
Ich denke, das sind zwei unterschiedliche Szenarien. In deinem Fall gibt es bestehende Daten, die iwie organisiert sind, und man möchte ein einfaches Interface, um sie wie ein 2D-Array zu behandeln. Die Klasse, die das Interface zur Verfügung stellt, besitzt die Daten nicht, sondern erlaubt nur den Zugriff auf die Elemente. array2d_view wäre da wohl ein passender Name.

Den Fall, für den ich die Klasse geschrieben habe ist ein anderer. Hier besitzt das Array die Daten und es ist für Fälle gedacht, wo eine andere Darstellung als 2D keinen Sinn ergibt. Mir fällt kein Argument ein, warum man ein Schachfeld als std::vector implementieren sollte und bei jedem Zugriff entweder den linearen Index umrechnen oder ein array2d_view drüberlegen muss. Oder eine Implementation als std::list, wo man keinen wahlfreien Zugriff auf die Elemente hat sondern sich erst durch die Liste hangeln muss. In diesem Fall kaschiert array2d_view sogar die Benutzung eines ungeeigneten Containers, da es einen einfachen und schnellen Zugriff vorgaukelt.

Mal sehen, wenn ich Zeit und Bock haben sollte kann ich ja Version 8 bauen, in der man den zu Grunde liegenden Containertyp als template Parameter festlegen kann. Ich nehm´ den Punkt aber mal als potenziellen Nachteil in die Liste auf, wobei mir aber wirklich kein Grund gegen std::vector einfällt. Wobei... wenn so ein Array mehrere GiB oder sogar TiB groß sein kann möchte man als Container vielleicht eine Klasse haben, die nur Teile im Speicher hält und die Arraydaten auf der HD liegen.

Edit:
Version 8 ergänzt

[Th69]

Gibt es einen Grund, warum du die Funktionsparameter und Klassenmember mit einem Großbuchstaben schreibst (also Row, Col etc. anstatt row, col etc.)? Finde ich nicht einheitlich (stattdessen z.B. other) und auch gegen die häufigst verwendeten Coding Guidelines.

[DocShoe]

@th69
Äh, ne, gibts nicht. Ist wohl verbesserungswürdig

[Swordfish]

Bekommt das Ding noch einen Iterator?

[DocShoe]

@swordfish
Von mir jetzt erst Mal nicht. Habe ich ja unter mögliche Verbesserungen aufgeführt... kannst dich austoben, wenn du magst. Oder wenn mir später noch mal langweilig wird. Obwohl Iteratoren wieder ein Kapitel für sich sind, dazu macht man besser ein eigenes Kapitel/FAQ. Zumal ich mich mit dem Thema auch nicht wirklich gut auskenne. Ne naive Lösung ist kein Problem, aber ob das dann tutorial-tauglich ist weiß ich nicht. Und eine boost Lösung finde ich hier unpassend, weil einem vorgekaut wird, wie man eine Array Klasse entwickelt und einem für die Iteratoren dann boost um die Ohren gehauen wird.

[hustbaer]

Die ganzenarray2d_container_xyz Funktionen würde man normalerweise eher in eine Traits-Klasse packen. Guck z.B. wie es std::basic_string mit den char-Traits macht.

Was den Indexingoperator angeht: Man könnte ihn auch ne "Index2D" struct als Parameter nehmen lassen, die nen (nicht-explicit) ctor mit zwei size_t hat. Und dann mit myArray2D[{x, y}] aufrufen. Ist natürlich auch nicht gerade schön.

Bevor ich mit nem Proxy arbeite würde ich aber auf jeden Fall mal gucken was für Code dabei rauskommt. Also ob der ganze Overhead wirklich wegoptimiert werden kann.

[titan99_]

@lemon03 sagte in Array2D: Evolution von manueller Speicherverwaltung zur STL:

Finde ich gut
Habe es mal gebookmarkt, falls irgendwo irgendwann die Frage nach einem 2DArray auftauchen sollte.

Finde ich auch und habe es auch gebookmarkt.

@docshoe sagte in Array2D: Evolution von manueller Speicherverwaltung zur STL:

eine Art array_view für einzelnen Zeilen oder Spalten

Also dann sind je nach dem (wenn container_type = std::vector) nur die Zeilen oder die Spalten im Speicher zusammenhängend (?).

Eventuell praktisch wäre für mein derzeitige Problemstellung:

• wenn die Spalten unterschiedliche Datentypen haben könnten
• wenn die Spalten Namen als std::string haben könnten
• wenn das Array2D eine Ausgabe als std::ostream (?) als csv-Dateiformat haben könnte

[Th69]

@titan99_: Das wäre aber dann kein 2D-Array mehr, sondern eine Tabelle (data table).

[DocShoe]

@hustbaer
Die Sache mit den traits gefällt mir, das nehme ich mal in die to-do Liste auf. Eigentlich braucht man auch nur die resize() Funktionalität. size und empty hängen direkt von Rows_ und Cols_ ab, begin lässt sich über std::begin realisieren. Auf der anderen Seite ist die Bündelung der Funktionalität in einer traits-Klasse besser handhabbar, weil alles an einer Stelle gemacht werden kann.

@Titan99

• wenn die Spalten unterschiedliche Datentypen haben könnten
  Wenn die Elemente alle unterschiedlich sein sollen nimmste halt den entsprechenden Datentyp (variant, any, etc.). Oder baust dir deinen eigenen mit deinen Anforderungen.
• wenn die Spalten Namen als std::string haben könnten
  Strings für Spalten- oder Zeilennamen braucht man je nach Anwendungsfall, die immer mitzuschleppen halte ich für keine gute Idee.
• wenn das Array2D eine Ausgabe als std::ostream (?) als csv-Dateiformat haben könnte
  Finde ich auch nicht gut. Du brauchst jetzt gerade die Daten im CSV Format, aber was ist bei jemandem, der die kompakt im Binärformat schreiben möchte? Oder ein anderes Trennzeichen als das Semikolon? Oder die Zellen in einzelne oder doppelte Hochkommata einfassen möchte, weil die Zelle ein Trennzeichen als Dateninhalt enthält?

Wenn du eine Klasse Datatable brauchst kannst du die doch einfach über Komposition realisieren. Dann bauste noch deine Spaltenüberschriften und Stream I/O dazu und fertig ist die Laube. Das geht mit weniger als 100 Zeilen Code.