Felder als STL Container

Dangling

hey,
ich soll Felder sortieren mit versch. Sortieralgorithmen (bubblesort u.ä.).
soll für die Felder den STL-Container vector aus der Standard Template Library STL verwenden.

inwiefern kann ich ein "normales" array, z.B.

const int l = 10; //Größe des Arrays
	int A[l] = { 39, 12, 72, 11, 18, 46, 83, 21, 10, 1 };

in einen STL-Container umwandeln?
wie include ich die STL? bestimmter befehl?

zudem sieht einer meiner sortieralgorithemen immoment so aus:

void bubbleSort(int my_array[], int l) {

	bool vertauscht = true;

	int j = 0;

	int tmp;

	while (vertauscht) {

		vertauscht = false;

		j++;

		for (int i = 0; i < l - j; i++) {

			if (my_array[i] > my_array[i + 1]) {

				tmp = my_array[i];

				my_array[i] = my_array[i + 1];

				my_array[i + 1] = tmp;

				vertauscht = true;
			}
		}
	}
}

muss ich meinen sortiercode verändern wenn ich stl-container statt arrays verwende?
wenn ja: wie?

vielen dank für hilfe

Annahme: dein Compiler kann halbwegs C++11 (z.B. VS2013 für Windows besser VS2015)

Dangling schrieb:

inwiefern kann ich ein "normales" array, z.B.
const int l = 10; //Größe des Arrays
	int A[l] = { 39, 12, 72, 11, 18, 46, 83, 21, 10, 1 };
in einen STL-Container umwandeln?
wie include ich die STL? bestimmter befehl?

#include <vector>
....
std::vector<int> A = { 39, 12, 72, 11, 18, 46, 83, 21, 10, 1 };

Dangling schrieb:

muss ich meinen sortiercode verändern wenn ich stl-container statt arrays verwende?
wenn ja: wie?

Du musst eine Referenz auf den Vector entgegennehmen. Der Vector kennt seine Länge => kein Längenparameter

Da du offensichtlich keine Ahnung bzgl. der STL hast, solltest du vorher vielleicht mal ein Buch zu Rate ziehen.

Dangling

aber wenn ich bei meinem code einfach alles von

int A[]

in

vector<int> A

umwandel (*s.u.), taucht die fehlermeldung
"debug assertion failed
expression: vector subscript out of range"

bsp für umwandlung:

vector <int> A= { 39, 12, 72, 11, 18, 46, 83, 21, 10, 1 };

void insertionSort(vector<int> my_array, int l)
{
	int i, j, tmp;

	for (i = 1; i < (int)my_array.size(); i++)
	{
		j = i;

		while (j > 0 && my_array[j - 1] > my_array[j])
		{
			tmp = my_array[j];

			my_array[j] = my_array[j - 1];

			my_array[j - 1] = tmp;

			j--;

		}
	}
}

Dangling schrieb:

aber wenn ich bei meinem code einfach alles von
int A[]
in
vector<int> A
umwandel (*s.u.), taucht die fehlermeldung
"debug assertion failed
expression: vector subscript out of range"

Dein Algorithmus ist fehlerhaft. Mit einem Array hättest du das nicht bemerkt.

Unabhängig davon nochmal zur Wiederholung:
Du musst eine Referenz auf den Vector entgegennehmen. Der Vector kennt seine Länge => kein Längenparameter

Th69

Und informier dich mal über Iteratoren, dann kannst du den Sortieralgorithmus für verschiedene Container (als auch Arrays) benutzen.

Dangling

alles klar.
gebe die vektoren nun als refernz an die funktionen.
und so klappt alles auch,
außer bei meinem mergesort algorithmus (bei dem taucht immer noch die "out of range" fehlermeldung auf!):

//sortieralgorithmus:

void merge(vector<int> &my_array, vector <int> &tmp_array, int leftPos, int rightPos, int rightEnd)
{
	int leftEnd = rightPos - 1;
	int tmpPos = leftPos;
	int numElements = rightEnd - leftPos + 1;

	while ((leftPos <= leftEnd) && (rightPos <= rightEnd))
	{
		if (my_array[leftPos] <= my_array[rightPos])
		{
			tmp_array[tmpPos] = my_array[leftPos];
			tmpPos = tmpPos + 1;
			leftPos = leftPos + 1;
		}
		else
		{
			tmp_array[tmpPos] = my_array[rightPos];
			tmpPos = tmpPos + 1;
			rightPos = rightPos + 1;
		}
	}

	while (leftPos <= leftEnd)
	{
		tmp_array[tmpPos] = my_array[leftPos];
		tmpPos = tmpPos + 1;
		leftPos = leftPos + 1;
	}

	while (rightPos <= rightEnd)
	{
		tmp_array[tmpPos] = my_array[rightPos];
		tmpPos = tmpPos + 1;
		rightPos = rightPos + 1;
	}

	int i = 0;

	while (i < numElements)
	{
		my_array[rightEnd] = tmp_array[rightEnd];
		i = i + 1;
		rightEnd = rightEnd - 1;
	}
}

void mergeSort(vector<int> &my_array, vector <int> &tmparray, int left, int right)
{
	if (left < right)
	{
		int center = (left+right) / 2;

		mergeSort(my_array, tmparray, left, center);
		mergeSort(my_array, tmparray, center + 1, right);
		merge(my_array, tmparray, left, center + 1, right);
	}
}

//in der main()
vector <int> A= { 39, 12, 72, 11, 18, 46, 83, 21, 10, 1 };
vector <int> mergearray;

mergeSort(tmp_A, mergearray, 0, (int)tmp_A.size() - 1);

finde nicht den fehler

Dangling schrieb:

außer bei meinem mergesort algorithmus (bei dem taucht immer noch die "out of range" fehlermeldung auf!):
//in der main()
vector <int> A= { 39, 12, 72, 11, 18, 46, 83, 21, 10, 1 };
vector <int> mergearray;

mergeSort(tmp_A, mergearray, 0, (int)tmp_A.size() - 1);
finde nicht den fehler

Wie viele Elemente hat mergearray hier?
Ist mergearray[0] ein gültiger Zugriff?

Dangling

manni66 schrieb:

Wie viele Elemente hat mergearray hier?
Ist mergearray[0] ein gültiger Zugriff?

zunächst ist das mergearray leer also ist es wohl kein gültiger zugriff

habs nun so probiert:

void merge(vector<int> &my_array, vector <int> &tmp_array, int leftPos, int rightPos, int rightEnd)
{
	int leftEnd = rightPos - 1;
	int tmpPos = leftPos;
	int numElements = rightEnd - leftPos + 1;

	while ((leftPos <= leftEnd) && (rightPos <= rightEnd))
	{
		if (my_array[leftPos] <= my_array[rightPos])
		{
			//tmp_array[tmpPos] = my_array[leftPos];
			tmp_array.push_back((int)my_array[leftPos]);
			tmpPos = tmpPos + 1;
			leftPos = leftPos + 1;
		}
		else
		{
			//tmp_array[tmpPos] = my_array[rightPos];
			tmp_array.push_back((int)my_array[rightPos]);
			tmpPos = tmpPos + 1;
			rightPos = rightPos + 1;
		}
	}

	while (leftPos <= leftEnd)
	{
		//tmp_array[tmpPos] = my_array[leftPos];
		tmp_array.push_back((int)my_array[leftPos]);
		tmpPos = tmpPos + 1;
		leftPos = leftPos + 1;
	}

	while (rightPos <= rightEnd)
	{
		//tmp_array[tmpPos] = my_array[rightPos];
		tmp_array.push_back((int)my_array[rightPos]);
		tmpPos = tmpPos + 1;
		rightPos = rightPos + 1;
	}

	int i = 0;

	while (i < numElements)
	{
		my_array[rightEnd] = tmp_array[rightEnd];
		i = i + 1;
		rightEnd = rightEnd - 1;
	}
}

void mergeSort(vector<int> &my_array, vector <int> &tmparray, int left, int right)
{
	if (left < right)
	{
		int center = (left+right) / 2;

		mergeSort(my_array, tmparray, left, center);
		mergeSort(my_array, tmparray, center + 1, right);
		merge(my_array, tmparray, left, center + 1, right);
	}
}

nur ist die sortierung nun nicht mehr richtig!
bei den zahlen: 54, 43, 23, 87, 34
kommt raus: 43, 54, 23, 43, 54

Dangling schrieb:

nur ist die sortierung nun nicht mehr richtig!
bei den zahlen: 54, 43, 23, 87, 34
kommt raus: 43, 54, 23, 43, 54

Tja, dann war das push_back wohl nicht die richtige Lösung. Versuche etwas anderes!

Dangling

manni66 schrieb:

Tja, dann war das push_back wohl nicht die richtige Lösung. Versuche etwas anderes!

leider kenne ich mich nicht mit stl-containern aus
ich hab nun etwas gegoogelt und es scheint "insert" der richtige befehl zu sein um einen bestimmten wert an eine stelle im vektor einzufuege?!
nur funktioniert es so

tmp_array.insert(tmpPos, my_array[leftPos]);

leider nicht (als ersatz für

tmp_array[tmpPos] = my_array[leftPos];

<-hier noch mit arrays)

vllt vorschläge wie ich das richtig ersetzen könnte oder welcher befehl gut wäre?

Man kann einen std::vector mit einer definierten Größe leer anlegen bzw. mit einem Funktionsaufruf die gewünschte Größe setzen.
Wie das geht steht in deiner C++-Referenz.