Sortieren eines Arrays mit Objekten, Kopien vermeiden

[FBIagent]

Hallo Ihr

Ich verwende std::sort um ein Array auf Pointer zu sortieren. Das Array auf Pointern resultierte hier aus einem Array auf Objekte direkt. Da ich mir sicher war, das std::sort meine Objekte kopiert, habe ich ein zweites Array mit Pointern auf die Objekte erstellt um das Kopieren zu verhindern.

Habt Ihr vieleicht eine bessere Idee wie man das lösen könnte?

Relevant wären Zeile 87 bis 97.

#include <iostream>
#include <cstdint>
#include <type_traits>
#include <algorithm>

using namespace std;

template<class T, T V1, T V2>
struct is_arithmetic_greater
{
	static_assert(is_arithmetic<T>::value, "Only arithmetic types allowed for T!");
	static const bool value = V1 > V2;
};

template<class T>
class LineAxis
{
	static_assert(is_integral<T>::value && is_signed<T>::value, "Only signed integral types allowed for T!");
	
private:
	T* _src;
	T* _dst;
	T _delta;
	T _step;
	T _error;
public:
	LineAxis()
	{}

	void init(T* src, T* dst)
	{
		_src = src;
		_dst = dst;
		_delta = abs(*dst - *src);
		_step = *src < *dst ? 1 : -1;
		_error = _delta;
	}

	bool operator<(LineAxis<T>& other) { return _delta > other._delta; }
	bool operator>(LineAxis<T>& other) { return _delta < other._delta; }
	bool operator==(LineAxis<T>& other) { return _delta == other._delta; }

	void tryStep(T greatestDelta)
	{
		_error += _delta;
		if (_error >= greatestDelta)
		{
			step();
			_error -= greatestDelta;
		}
	}

	void step()
	{
		*_src += _step;
	}

	bool arrived()
	{
		return *_src == *_dst;
	}

	T delta()
	{
		return _delta;
	}
};

// Description:
// Goes through all line points with any given number of AXES and calls the callback for each point
//
// Template Params:
// T	TYPE	- signed arithmetic type which describes each axis
// AXES	VALUE	- number of axes for source and destination point 
//
// Function Params:
// srcPoint	- the source point of the line
// dstPoint	- the destination point of the line
// callback	- the callback to which each line point is passed
template<class T, size_t AXES>
void for_each_line_point(T srcPoint[AXES], T dstPoint[AXES], void (*callback)(T point[AXES]))
{
	static_assert(is_integral<T>::value && is_signed<T>::value, "Only signed integral types allowed for T!");
	static_assert(is_arithmetic_greater<size_t, AXES, 0>::value, "AXES must be at least 1!");

	LineAxis<T> axes[AXES];
	LineAxis<T>* pAxes[AXES];

	for (size_t i = 0;i < AXES;++ i)
	{
		pAxes[i] = &axes[i];
		pAxes[i]->init(&srcPoint[i], &dstPoint[i]);
	}

	// sort, we need the axis with the greatest delta at index 0, the other axes does not matter
	sort(pAxes, pAxes + AXES, [](LineAxis<T>* a, LineAxis<T>* b) {return a->delta() > b->delta();});

	(*callback)(srcPoint);

	while (!pAxes[0]->arrived())
	{
		pAxes[0]->step();

		for (size_t i = 1;i < AXES;++ i)
		{
			pAxes[i]->tryStep(pAxes[0]->delta());
		}

		(*callback)(srcPoint);
	}
}

int main(int argc, char** argv)
{
	int srcPoint[2];
	srcPoint[0] = 1;
	srcPoint[1] = 1;
	int dstPoint[2];
	dstPoint[0] = 11;
	dstPoint[1] = 5;

	for_each_line_point<int, 2>(srcPoint, dstPoint, [](int point[2]){
		cout << point[0] << ", " << point[1] << endl;
	});

	cin.get();
	return 0;
}

 

[Technipion]

Hallo FBIagent,
wenn ich dich richtig verstanden habe, möchtest du die Elemente sortieren ohne dass sie kopiert werden?
Heapsort könnte etwas für dich sein. Die Funktion std::sort verwendet meines Wissens den Quicksort-Algorithmus, da dieser in den meisten Fällen schneller läuft (allerdings mit der gleichen asymptotischen Laufzeit wie Heapsort). Falls die Operation "Kopieren" bei deinen Objekten hohe Kosten mit sich bringt, solltest du dir Heapsort mal anschauen, der benutzt nämlich nur die Swap-Operation (und die kostet ja bekanntlich viel weniger).

Dein Programm soll soweit ich das gesehen habe eine Linie rastern
Du hast das aber ganz schön 'ausführlich' implementiert
Hier noch ein paar andere Methoden zur Anregung: http://de.wikipedia.org/wiki/Rasterung_von_Linien

Das war glaube ich der erste Code den ich hier gesehen habe, der so richtig C++11 nutzt
Grüße Technipion

 

[FBIagent]

Hallo FBIagent,
wenn ich dich richtig verstanden habe, möchtest du die Elemente sortieren ohne dass sie kopiert werden?
Heapsort könnte etwas für dich sein. Die Funktion std::sort verwendet meines Wissens den Quicksort-Algorithmus, da dieser in den meisten Fällen schneller läuft (allerdings mit der gleichen asymptotischen Laufzeit wie Heapsort). Falls die Operation "Kopieren" bei deinen Objekten hohe Kosten mit sich bringt, solltest du dir Heapsort mal anschauen, der benutzt nämlich nur die Swap-Operation (und die kostet ja bekanntlich viel weniger).

Boah, da bin ich ganz schön eingerostet.
Ich habe nochmal darüber nachgedacht, und wen ich es mir recht überlege habe ich ja mit dem Array einen Pointer auf Speicher mit "AXES * sizeof(LineAxis<T>)" größe. Da komme ich ja gar nicht um das Kopieren herum.

Außerdem ist mir gar nicht mehr aufgefallen das ich eigentlich nur index 0 mit der Axe mit dem grösten delta tauschen muss. 3 Kopien so wie es jetzt aus sieht:

#include <iostream>
#include <cstdint>
#include <type_traits>

using namespace std;

template<class T, T V1, T V2>
struct is_arithmetic_greater
{
	static_assert(is_arithmetic<T>::value, "Only arithmetic types allowed for T!");
	static const bool value = V1 > V2;
};

template<class T>
class LineAxis
{
	static_assert(is_integral<T>::value, "Only integral types allowed for T!");
	
private:
	T* _src;
	T* _dst;
	T _delta;
	int8_t _step;
	T _error;
public:
	LineAxis()
	{}

	void init(T* src, T* dst)
	{
		_src = src;
		_dst = dst;
		_delta = abs(*dst - *src);
		_step = *src < *dst ? 1 : -1;
		_error = _delta;
	}

	bool operator<(LineAxis<T>& other) { return _delta > other._delta; }
	bool operator>(LineAxis<T>& other) { return _delta < other._delta; }
	bool operator==(LineAxis<T>& other) { return _delta == other._delta; }

	void tryStep(T greatestDelta)
	{
		_error += _delta;
		if (_error >= greatestDelta)
		{
			step();
			_error -= greatestDelta;
		}
	}

	inline void step()
	{
		*_src += _step;
	}

	inline bool arrived()
	{
		return *_src == *_dst;
	}

	inline T delta()
	{
		return _delta;
	}
};

// Description:
// Goes through all line points with any given number of AXES and calls the callback for each point
//
// Template Params:
// T	TYPE	- signed arithmetic type which describes each axis
// AXES	VALUE	- number of axes for source and destination point 
//
// Function Params:
// srcPoint	- the source point of the line
// dstPoint	- the destination point of the line
// callback	- the callback to which each line point is passed
template<class T, size_t AXES>
void for_each_line_point(T srcPoint[AXES], T dstPoint[AXES], void (*callback)(T point[AXES]))
{
	static_assert(is_integral<T>::value, "Only integral types allowed for T!");
	static_assert(is_arithmetic_greater<size_t, AXES, 0>::value, "AXES must be at least 1!");

	LineAxis<T> axes[AXES];

	axes[0].init(&srcPoint[0], &dstPoint[0]);
	T greatestDelta = axes[0].delta();
	size_t greatestAxisIdx = 0;

	for (size_t i = 1;i < AXES;++ i)
	{
		axes[i].init(&srcPoint[i], &dstPoint[i]);
		if (axes[i].delta() > greatestDelta)
		{
			greatestDelta = axes[i].delta();
			greatestAxisIdx = i;
		}
	}

	LineAxis<T> greatestAxis = axes[greatestAxisIdx];
	axes[greatestAxisIdx] = axes[0];
	axes[0] = greatestAxis;

	(*callback)(srcPoint);

	while (!axes[0].arrived())
	{
		axes[0].step();

		for (size_t i = 1;i < AXES;++ i)
		{
			axes[i].tryStep(axes[0].delta());
		}

		(*callback)(srcPoint);
	}
}

int main(int argc, char** argv)
{
	int srcPoint[2];
	srcPoint[0] = 1;
	srcPoint[1] = 1;
	int dstPoint[2];
	dstPoint[0] = 11;
	dstPoint[1] = 5;

	for_each_line_point<int, 2>(srcPoint, dstPoint, [](int point[2]){
		cout << point[0] << ", " << point[1] << endl;
	});

	cin.get();
	return 0;
}

Dein Programm soll soweit ich das gesehen habe eine Linie rastern
Du hast das aber ganz schön 'ausführlich' implementiert
Hier noch ein paar andere Methoden zur Anregung: http://de.wikipedia.org/wiki/Rasterung_von_Linien

Diesen Artikel kenne ich natürlich

Wie meinst du das "ausführlich" implementiert? Das es mit egal wie vielen Axen funktioniert?

Mein Ziel war den Algorithmus so zu gestalten, dass er mit beliebig vielen Axen funktioniert. Ich gehe davon aus, das ein Programm das Linien rastern möchte schon zur Compiletime weis in welcher dimension es rastern möchte. Es sollte so viel wie möglich zur Compiletime bekannt sein, um so wenig wie möglich zur Laufzeit machen zu müssen. Zum einen habe ich mit dem Template die gebrauchte Speichermenge zur Compiletime bereits festgelegt, und durch selbiges sollte der Compiler auch in der Lage sein die Zählschleifen zur Compiletime aufzurollen.

Das war glaube ich der erste Code den ich hier gesehen habe, der so richtig C++11 nutzt
Grüße Technipion

Leider scheint IntelliSense von Visual Studio 2012 mit der Komplexität nicht klarzukommen. Zumindest bekomme ich immer wieder eine Fehlermeldung bei komplexeren Templatecode wonach das Syntax-Highlightning nicht mehr funktioniert und an Auto-Completion ist erst garnciht zu denken.