Beste Art ein Array zurückzuliefern

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

[buzzword]

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.

[schorsch code]

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)

[Ein ehemaliger Benutzer]

vielleicht StackAsFixedVector?

[1r0ll|\/|4514h]

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.

[1r0ll|\/|4514h]

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.

[1r0ll|\/|4514h]

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

[1r0ll|\/|4514h]

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;
}

[na ja]

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.

[v]

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.

[evilissimo]

Wer garantiert mir dass das alle Compiler tun?

[v]

niemand...aber so wichtig ist die garantie ja nicht wenn es mal auf nem uralt-compiler nicht so gemacht wird.

[camper]

1r0ll|/|4514h schrieb:

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

das habe ich auch gefragt

1r0ll|/|4514h schrieb:

camper schrieb:

das kopieren beim rückgeben per funktion

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

nö, nicht vollständig. nehmen wir doch einfach mal einen std::vector und schauen uns das an:

typedef std::vector<int> v;
v foo()
{
    return v( 1000 );
}

void bar()
{
    v b;
    // mach irgendwas mit b...
    b = foo();
}

der compiler darf hier in foo das kopieren von a per RVO unterlassen, er kann aber auf keinen fall das copy-asignment in bar() vermeiden, und hier wir es auf jedenfall zu einem kopieren kommen. im übrigen ist (N)RVO sehr zerbrechlich; man muss aufpassen, um dem compiler diese möglichkeit nicht von vornherein zu verbauen.

schauen wir uns an, was mit meinem Array pasiert:

typedef Array<int> v;
v foo()
{
    return v( 1000 );
}

void bar()
{
    v b;
    // mach irgendwas mit b...
    b = foo();
}

das return statement in foo() bewirkt zunächst den aufruf von operator ref und dann die benutzung des move-konstruktors Array(Ref) - der compiler darf das nicht wegoptimieren, denn es ist kein copy-ctor. selbiges passiert dann bei der zuweisung in bar(), um der signatur des zuweisungsoperators gerecht zu werden. im endeffekt kommt es zu 2 aufrufen von operator ref, 2 aufrufen des move-ctors, und einem des zuweisungsoperators. in keinem dieser funktionen kommt es zu einem deep copy - und alle sind hinreichend trivial, dass wir annehmen können, dass der optimierer hier noch einiges einsparen kann, da ja nur builtins getauscht werden.

ach ja, nebenbei - das genze funktioniert nicht mit vc++, wegen der art wie vc++ 8.5.3 absatz 5 interpretiert.

natürlich kann man das ganze mit smart-pointern ebenfalls lösen (und dann kontrolliert man ganz genau, wann kopiert wird). der nachteil ist aber eben, dass das array dann kein value-typ ist - man kann damit nicht operieren wie mit richtigen containern.