Beste Art ein Array zurückzuliefern

GPC

MatthiasK schrieb:

Nun habe ich noch eine Frage: Kann man das folgende auch schneller ausführen?

Ich wüßte jetzt nicht wie.

GPC

Wegen dem Array, das ginge mit Pointern so:

int * createArray(size_t sz) {
  return new int[sz];
};

void killArray(int *arr) {
  delete [] arr;
};

int main(int argc, char **argv) {
  int *arr = createArray(5);  //erstellen
  //mit arr arbeiten
  killArray(arr);  //löschen
  return 0;
};

Mathias

Du kannst den Speicherbereich als ganzes kopieren. Ist allerdings nicht so ganz die feine Art (in C durchaus üblich in C++ nur in Ausnahmefällen eine gute Lösung, da man sich dadurch z.B. die Kopierkontruktoren aushebelt).
Generell würde ich auch nicht mit Arrays arbeiten, sondern mit STL-Containern.
Das mag bei einfachen Sachen etwas Zeit kosten, dafür handelt man sich in Bezug auf Sicherheit, Erweiterbarkeit und Zugriff auf die Datenstruktur weniger Probleme ein.

otze

nächste möglichkeit: shared_array von boost benutzen, anstatt zeigern. im gegensatz zu der möglichkeit, einen vector zurückzugeben, wird hierbei nicht das array intern kopiert(bei einem array mit mehreren 1000 elementen und komplexen copy constructor seeehr teuer )

GV

void foo(int* array1) {
  int array2[1000];

    memcpy( reinterpret_cast<char*>(array2)
        , reinterpret_cast<char*>(array1)
        , sizeof( array2 ) );

}

Aber wie Matthias schon sagte, das sollte nicht erste Wahl sein.
Vor allem muss man vorsichtig sein, von wo bis wo man kopiert. Man kann den Speicher ganz schön durcheinander bringen damit.

otze schrieb:

nächste möglichkeit: shared_array von boost benutzen, anstatt zeigern. im gegensatz zu der möglichkeit, einen vector zurückzugeben, wird hierbei nicht das array intern kopiert(bei einem array mit mehreren 1000 elementen und komplexen copy constructor seeehr teuer )

Return Value Optimization.

Ich würde sagen ob man Zeiger oder Referenz verwenden soll, kommt darauf an, ob man ein Array erzeugen oder modifizieren will. Wenn es erzeugt werden soll, würde ich einen Zeiger verwenden und für das Modifizieren eine Referenz. Hier ein Beispiel mit Ansatz einer Array-Klasse:

#include <iostream>
using namespace std;

template<typename T>
class Array
{
	T *m_data;
	size_t m_capacity;

public:

	//Default-Konstruktor
	Array()
		: m_data(0), m_capacity(0) {}

	//Konstruktor für ein Array mit bestimmter Kapazität
	explicit Array(size_t capacity)
		: m_data(new T[capacity]), m_capacity(capacity)	{}

	//Konstruktor zum Kopieren aus einem C-Array
	Array(const T *const data, size_t n)
		: m_data(new T[n]), m_capacity(n)
	{
		memcpy(m_data, data, n*sizeof(T));
	}

	//Kopier-Konstruktor
	Array(const Array& prototype)
		: m_data(new T[prototype.m_capacity]), m_capacity(prototype.m_capacity)
	{
		memcpy(m_data, prototype.m_data, m_capacity*sizeof(T));
	}

	//Destruktor
	~Array()
	{
		if(m_data != 0)
			delete[] m_data;
	}

	T &operator[](int index) const
	{
		return m_data[index];
	}

	size_t Capacity() const
	{
		return m_capacity;
	}
};

//Ausgabe-Operator für Array
template<typename T>
ostream &operator<<(ostream &output, const Array<T> &a)
{
	int i;

	output << "{";
	for (i=0; i<a.Capacity()-1; ++i)
		output << a[i] << ", ";

	if(a.Capacity()>0)
		output << a[i];

	output << "}";
	return output;
}

//erzeugt ein Array-Objekt aus einem C-Array
Array<int> *testCopyFromCArray()
{
	int numbers[] = {38, 432, 543, 6542};
	return new Array<int>(numbers, sizeof(numbers)/sizeof(int));
}

//füllt ein Array mit Abbildungen (Mappings) der Zahlen 1 bis Feldkapazität
template<typename T>
void map(const Array<T> &a, T (*mapping) (T))
{
	for(int i=1; i<=a.Capacity(); ++i)
		a[i-1] = mapping(i);
}

int quad(int x) {return x*x;}

int main()
{
	Array<int> *a = testCopyFromCArray();
	Array<int> b(10);

	cout << "Kapazit\x84t von a: " << a->Capacity() << endl;
	cout << "Inhalt von a: " << *a << endl;
	delete a;

	map(b, quad);
	cout << "Kapazit\x84t von b: " << b.Capacity() << endl;
	cout << "Inhalt von b: " << b;

	cin.get();
}

camper

Ich kann hier keinen Vorteil gegenüber std::vector erkennen ...

MatthiasK schrieb:

Hallo, der Titel sagt glaub ich alles zu meiner Frage. Ich will eine Funktion schreiben, die mir ein Array zurückliefert. Einfach mit "return" geht das ja nicht. Was ist die beste (heißt für mich vor allem: schnellste) Variante?

Das kommt darauf an:
- ist die array-grösse statisch und wenn ja, ist diese grösse bereits beim compilieren bekannt ?
- sind die array elemente PODs oder memcopyable oder wenigstens memmovable ?

otze

camper schrieb:

Ich kann hier keinen Vorteil gegenüber std::vector erkennen ...

größter unterschied: vector hat eine dynamische größe, das array da oben statisch(naja fast^^, zumidnest ist sie nach dem ctor unveränderlich)

vielleicht StackAsFixedVector?

Also zu deiner ersten Frage gibt es mehrere Antworten. Wenn du nicht mit irgendwelchen Libs (stl, oder gar boost) rumhantieren willst, dann lese weiter:

zunächst mal die Möglichkeit, wie sie hier von einigen beschrieben wurde:

int* foo()
{
   int* arr=new int[2];
   // irgendwie, irgendwas
   return arr;
}

das sieht zwar toll aus, kann aber auch böse sein.

Beispiel?

int main()
{
   foo(); // Hier motzt der Compiler *nicht* rum
   ...
}

Da fehlt die Speicherfreigabe, muss zwar nicht schlimm sein, kann aber.

Die andere Möglichkeit `a la Win-API, ist einen Zeiger an die Funktion zu übergeben. Der Speicher ist vorher reserviert worden. Kann natürlich auch innerhalb der Funktion gemacht werden. (Und das wird zu einem Problem, wenn man die Varianten mischt)

void foo(int* array, size_t size)
{

Funktioniert, erfordert aber Durchhaltevermögen und Überblick. Mit C++ kann aber besserer gelöst werden.

Kennst du std::auto_ptr? Damit solltest du auf keinen Fall Arrays verwalten, es wäre aber keine schlechte Idee soetwas für Arrays zu schreiben. Problem: Es kann sehr kompliziert werden. Aber ein Copy&Paste von auto_ptr sollte meistens ausreichend sein. Nur vergiss nicht das entsprechende delete anzupassen.

Nennen wir mal diese neue Klasse auto_array. Dann sieht das Ergebnis in etwa so aus:

auto_array foo()
{

   auto_array<int> arr(new int[2]);
   // irgendwie, irgendwas
   return arr;
}

int main()
{
   foo(); // Am Ende der Funktion wird der Speicher freigegeben.

   auto_array<int> bar = foo();
   // Ich habe schon seit Jahren kein C++ mehr angerührt, 
   // aber hoffe mal das soetwas funktioniert:
   delete [] bar;
}

Auf deine 2. Frage, ob man die Schleife optimieren kann:
void foo(int* array1) {
int array2[1000];
for(int i = 0; i < 1000; i++) array2[i] = array1[i];
}

Ich habe mal gehört dass ein Vergleich mit 0 schneller gehen soll, als mit einer anderen Zahl. Könnte auch ein Gerücht sein. Probiere einfach. Sonst fällt mir nichts mehr ein.

Muss paar Sachen ergänzen. Ich sende viel zu schnell ab, ohne noch mal durchzulesen.

[quote="1r0ll|\/|4514h"]

auto_array foo()
{

   auto_array<int> arr(new int[2]);
   // irgendwie, irgendwas
   return arr;
}

int main()
{
   foo(); // Am Ende der Funktion wird der Speicher freigegeben.

   auto_array<int> bar = foo();
   // Ich habe schon seit Jahren kein C++ mehr angerührt, 
   // aber hoffe mal das soetwas funktioniert:
   delete [] bar;
}

Die Rückgabe der Funktion kann natürlich auch in einem normalen Pointer gespeichert werden:

int* bar = foo();

Solltest, dann aber mit der Speicherfreigabe aufpassen. auto_array macht aber (alles) automatisch. D.h. das delete [] bar in der Main-Funktion oben wäre garnicht notwendig.

Auf deine 2. Frage, ob man die Schleife optimieren kann:
void foo(int* array1) {
int array2[1000];
for(int i = 0; i < 1000; i++) array2[i] = array1[i];
}

Gab es nicht mal soetwas wie std::copy()?

CStoll

1r0ll|/|4514h schrieb:

auto_array foo()
{

   auto_array<int> arr(new int[2]);
   // irgendwie, irgendwas
   return arr;
}

int main()
{
   foo(); // Am Ende der Funktion wird der Speicher freigegeben.
   
   auto_array<int> bar = foo();
   // Ich habe schon seit Jahren kein C++ mehr angerührt, 
   // aber hoffe mal das soetwas funktioniert:
   delete [] bar;
}

Wenn du dein auto_array vernünftig gebaut hast, kümmert sich der Konstruktor selbständig um das delete[] - damit ist die letzte Zeile überflüssig.

@Schleife: Ich würde dort eher auf Bibliotheksfunktionen (std::copy oder strcpy) zurückgreifen als es selber zu schreiben.

camper

ein auto_array ist ja ganz nett, aber hat eben leider den nachteil, dass die referenzsemantik überall sichtbar bleibt, ausserdem müssen wir uns noch irgendwie die grösse merken (wenn diese statisch wäre, arbeitet man gleich mit structs (siehe boost::array). also etwa so (entwurf)

typedef unsigned long long u64; // zwecks alignment
template<class T, class X>
struct enable_if_same
{
};

template<class X>
struct enable_if_same<X, X>
{
    typedef char type;
};

template<typename T>
class Array
{
private:
// wir nehmen union hier, um uns etwas schreibarbeit zu sparen
// wenn T ein POD ist, können wir es nat. einfacher haben - da es dort keinen unterschied macht, ob wir zwischen copy-c'tor oder copy-assign verwenden
    union
    {
        u64* mem_;
        T* array_;
    };
    std::size_t size_;
    struct Ref
    {
        Array* ref_;
        Ref(Array* ref) : ref_( ref ) {}
    };
    operator Ref() { return Ref( this ); } // non-const
public:
    Array() : array_(), size_() {}
    explicit Array(std::size_t size)
    : mem_( new u64[ size_ * sizeof T / sizeof u64 ] ), size_( size ) {}
// Konstruktoren zum Kopieren
    // non-const lvalues - deep copy
    Array(Array& rhs)
    : mem_( new u64[ rhs.size_ * sizeof T / sizeof u64 ] ), size_( rhs.size_ )
    {
// jetzt in abhängigkeit von T:
        for ( std::size_t i = 0; i < size_; ++i )
        {
            new( array_ + i ) T( rhs.array_[ i ] );
        }
// oder per memcpy falls T ein POD ist oder memcopyable ist
// evtl. noch Duff's device für loop-unrolling
    }
    // non-const rvalues (z.B. Funktionsergebnisse) - move
    Array(Ref ref) : mem_( ref.ref_->mem_ ), size_( ref.ref_->size_ )
    {
        ref.ref_->mem_ = 0;
    }
// const lvalue - deep copy
    template <class T>
    Array(T& rhs, typename enable_if_same<Array const,T>::type = 0)
    : // ...
    {
         // siehe Array(Array& rhs) c'tor
    }

    ~Array()
    {
// wenn T einen trivialen destruktor hat, können wir uns das hier sparen:
        for ( std::size_t i = 0; i < size_; ++i )
        {
            array_[ i ].~T();
        }

        delete [] mem_;
    }

    Array& operator=(Array rhs)
    {
        if ( mem_ != 0 ) delete [] mem_;
        mem_ = rhs.mem_;
        rhs.mem_ = 0;
    }

    T& operator[](std::size_t i) { return array_[ i ]; }
    const T& operator[](std::size_t i) const { return array_[ i ]; }

    std::size_t size() const { return size_; }
};

und schon haben wir ein array, dass sich normal kopieren lässt, aber das kopieren beim rückgeben per funktion vermeidet, so wie es auto_array täte.

@camper & @me: Wieso eigentlich nicht gleich einen std::vector zurückgeben?

camper schrieb:

das kopieren beim rückgeben per funktion

Soweit ich weiß können manche Compiler das wegoptimieren.

evilissimo

Hi,

warum nicht einfach auf bestehendes wie boost::shared_array oder boost::scoped_array zurückgreifen?

boost::shared_array<int> MyFuncShared()
{
   boost::shared_array<int> arr( new int[10] );
   for( size_t i = 0; i < 10; ++i)
      arr[i] = i; 
   return arr;
}
boost::scoped_array<int> MyFuncScoped()
{
   boost::scoped_array<int> arr( new int[10] );
   for( size_t i = 0; i < 10; ++i)
      arr[i] = i; 
   return arr;
}

evilissimo schrieb:

Hi,

warum nicht einfach auf bestehendes wie boost::shared_array oder boost::scoped_array zurückgreifen?

boost::shared_array<int> MyFuncShared()
{
   boost::shared_array<int> arr( new int[10] );
   for( size_t i = 0; i < 10; ++i)
      arr[i] = i; 
   return arr;
}
boost::scoped_array<int> MyFuncScoped()
{
   boost::scoped_array<int> arr( new int[10] );
   for( size_t i = 0; i < 10; ++i)
      arr[i] = i; 
   return arr;
}

Vorteil gegenüber std::vector?

evilissimo

Es werden weniger daten kopiert und bei einem zeiger müsste man auch auf die ownership achten.

Es werden weniger daten kopiert

Der Compiler macht aus

std::vector<int> MyFuncShared()

sowieso

void MyFuncShared(std::vector<int>& v)

also vom kopieren ändert sich nichts.