Wie heißt das private Array mit dem Inhalt des std::vector?

[wxSkip]

Nexus schrieb:

wxSkip schrieb:

1.Eine friend-Funktion widerspricht dem Prinzip aber nicht, oder?

Natürlich widerspricht es dem Prinzip, du müsstest schliesslich den std::vector verändern!

Nein, ich wollte ja gerade eine eigene Vektor-Klasse machen, die von std::vector erbt, und da würde ich ja nicht den std::vector ändern

[wxSkip]

Nexus schrieb:

wxSkip schrieb:

Bei Icematix' Variante stürzt das Programm aber immer ab, wahrscheinlich, weil vec[0] eine Referenz zurückgibt.

Wahrscheinlich eher, weil du die besagten Sicherheitsabfragen nicht mehr hast und ausserhalb des gültigen Bereichs zugreifst.

Schreib dein Programm zuerst korrekt und optimiere dann. Für ersteres kannst du den normalen std::vector::operator[] verwenden.

Programm: (nur ein Testprogramm)

vector<int> vec;
    vec[0] = 12345;
    int *ip = &vec[0];
    printf("%d", *ip);

-> stürzt ab, obwohl ohne Kompilierfehler

[GEFAHR GEFAHR GEFAHR]

Wenn du dich in die Klassenhierarchie einklinkst, brichst du damit die Kapselung auf. Es mag vielleicht die eleganteste Methode sein, dies zu tun, ändert aber nichts am eigentlichen Problem.

Das Testprogramm ist falsch, weil der Vector keine elemente enthält. Du greifst auf das nullste Element zu, obwohl es nie erzeugt wurde. Ändere die zweite Zeile in einen push_back()-Aufruf. Genau aus diesem Grund raten wir dir hier zu Iteratoren.

[Nexus]

wxSkip schrieb:

Nein, ich wollte ja gerade eine eigene Vektor-Klasse machen, die von std::vector erbt

Davon rate ich dir ebenfalls ab. Nur weil du die Methoden nicht neu deklarieren willst, solltest du nicht von std::vector erben. Aggregation ist in dem Falle sinnvoller.

wxSkip schrieb:

und da würde ich ja nicht den std::vector ändern

Ja, aber wenn du in deiner eigenen Klasse ein friend nach aussen machst, kannst du immer noch nicht auf std::vector zugreifen.

Aber wie gesagt: Das ist alles gar nicht nötig.

wxSkip schrieb:

Programm: (nur ein Testprogramm)

vector<int> vec;
    vec[0] = 12345;
    int *ip = &vec[0];
    printf("%d", *ip);

-> stürzt ab, obwohl ohne Kompilierfehler

Eben, dein Code ist inkorrekt. Das ist das gleiche Problem wie hier:

int vec[2];
vec[2] = 12345;

P.S.: Versteh das nicht falsch, aber wenn du solche Problematik nicht erkennst, bezweifle ich mal, dass du auf die Schnelle ein besseres und dennoch allgemeingültiges std::sort() hinkriegst. Du bist wahrscheinlich besser beraten, wenn du vorgefertigte Lösungen anwenden würdest, da diese auch bugfrei sind. Es gibt nichts Schlimmeres als undefiniertes Verhalten, das man erst Minuten nach dem Auftreten erkennt.

[mann ey!]

wxSkip schrieb:

Nein, ich wollte ja gerade eine eigene Vektor-Klasse machen, die von std::vector erbt

Wie kommt man denn auf die Idee, von std::vector zu erben? Wozu soll das gut sein? Was hilft Dir das denn, wenn Du etwas sortieren willst?

[wxSkip]

GEFAHR GEFAHR GEFAHR schrieb:

Wenn du dich in die Klassenhierarchie einklinkst, brichst du damit die Kapselung auf. Es mag vielleicht die eleganteste Methode sein, dies zu tun, ändert aber nichts am eigentlichen Problem.

Das Testprogramm ist falsch, weil der Vector keine elemente enthält. Du greifst auf das nullste Element zu, obwohl es nie erzeugt wurde. Ändere die zweite Zeile in einen push_back()-Aufruf. Genau aus diesem Grund raten wir dir hier zu Iteratoren.

Danke, wenn ich den Vektor mit 5 initialisiere, funktionierts!

[wxSkip]

mann ey! schrieb:

wxSkip schrieb:

Nein, ich wollte ja gerade eine eigene Vektor-Klasse machen, die von std::vector erbt

Wie kommt man denn auf die Idee, von std::vector zu erben? Wozu soll das gut sein? Was hilft Dir das denn, wenn Du etwas sortieren willst?

Dann kann ich mir dort meine eigenen Funktionen machen oder friend-Funktionen deklarieren oder so...

[wxSkip]

Komisch... Mein Quicksort für Vektoren ist schneller als mein Quicksort für C-Arrays mit der Adresse des Arrays aufgerufen, obwohl beide genau denselben Algorithmus nutzen.

[Blue-Tiger]

wxSkip schrieb:

Komisch... Mein Quicksort für Vektoren ist schneller als mein Quicksort für C-Arrays mit der Adresse des Arrays aufgerufen, obwohl beide genau denselben Algorithmus nutzen.

Koenntest du bitte mal Implementierung und Testprogramm posten, damit andere das auch nachvollziehen koennen?

[wxSkip]

Gerne!

template<class Type> inline void vquicksort2(myvector<Type> &in, register int size, register int pos = 0)
{
    register Type tmp;
    register int right = pos + size - 1;
    register int left = pos;
    register double av = (in.at(pos) + in.at(pos+size-1)) / 2.0;

    while(left < right)
    {
        if (in.at(left) > av)
        {
            if (av > in.at(right))
            {
                tmp = in.at(left);
                in.at(left) = in.at(right);
                in.at(right) = tmp;
                left++;
            }
            right--;
        }
        else
        {
            if (av <= in.at(right)) right--;
            left++;
        }
    }
    if(left == right && in.at(left) <= av) left++;

    if((right = left-pos) < 2)return;
    else vquicksort2(in, right, pos);
    if((right = size-left+pos) < 2) return;
    else vquicksort2(in, right, left - pos);
}

[Blue-Tiger]

Du hast das Testprogramm vergessen

[wxSkip]

Ach so, das Programm, was das aufruft...

#include <algorithm>
#include <vector>
#include <iostream>
#include <ctime>

#define SIZE 20000000

using namespace std;

template <class Type> inline void vquicksort2(vector<Type> &in, register int size, register int pos = 0);

inline double getProgramTime()
{
    return clock() / (double)CLOCKS_PER_SEC;
}

int main()
{
    vector<double> v1(SIZE), v2(SIZE), v3(SIZE);
    for(int c = 0; c < SIZE; c++) v1[c] = rand();
    for(int c = 0; c < SIZE; c++) v2[c] = v1[c];
    printf("Start.\n");
    register double y = getProgramTime();
    sort(v1.begin(), v1.end());
    cout << "Sort-Zeit: " << getProgramTime() - y << "s\n";
    y = getProgramTime();
    vquicksort2(v2, v2.size());
    cout << "Vquicksort2-Zeit: " << getProgramTime() - y << "s\n";
}

template <class Type> inline void vquicksort2(vector<Type> &in, register int size, register int pos = 0)
{
    register Type tmp;
    register int right = pos + size - 1;
    register int left = pos;
    register double av = (in.at(pos) + in.at(pos+size-1)) / 2.0;

    while(left < right)
    {
        if (in.at(left) > av)
        {
            if (av > in.at(right))
            {
                tmp = in.at(left);
                in.at(left) = in.at(right);
                in.at(right) = tmp;
                left++;
            }
            right--;
        }
        else
        {
            if (av <= in.at(right)) right--;
            left++;
        }
    }
    if(left == right && in.at(left) <= av) left++;

    if((right = left-pos) < 2)return;
    else vquicksort2(in, right, pos);
    if((right = size-left+pos) < 2) return;
    else vquicksort2(in, right, left - pos);
}

[Blue-Tiger]

Ich hab mal simpl std::vector statt myvector verwendet. Damit kompiliert das Progamm auch, allerdings ist das array am Ende nicht richtig sortiert -- ist es das denn wenn du myvector verwendest?

int main(int argc, char** argv)
{
	if (argc != 3)
		return 0;

	srand(42);

	unsigned N = atoi(argv[1]);
	vector<int> a;

	for (unsigned i = 0; i < N; ++i)
		a.push_back(rand());

	if (argv[2][0] == 's')
		std::sort(a.begin(), a.end());
	else
		vquicksort2(a, a.size());

	cout << a[0] << '\t' << a[N/2] << '\t' << a[N-1] << '\n'; // compare outputs to see if numbers are identical
	return 0;
}

Ausgabe:

g++ -O3 -DNDEBUG test.cpp -o test
tom@blulap:~$ time ./test 10000000 c
503	1692224497	205946697

real	0m0.722s
user	0m0.550s
sys	0m0.120s
tom@blulap:~$ time ./test 10000000 s
503	1073448061	2147483606

real	0m1.957s
user	0m1.730s
sys	0m0.110s

[Blue-Tiger]

Ach ja: "register" hat heutzutage keine Funktion mehr, der Compiler weiss selbst, welche Werte er im Register haelt 'inline' ist vermutlich genauso ueberfluessig.

[wxSkip]

Nein, das ist nicht sortiert... da muss ich noch den Fehler suchen...

[wxSkip]

OK, so gehts:

template <class Type> inline void vquicksort2(vector<Type> &in, register int size, register int pos = 0)
{
    register Type tmp;
    register int right = pos + size - 1;
    register int left = pos;
    register double av = (in.at(pos) + in.at(pos+size-1)) / 2.0;

    while(left < right)
    {
        if (in.at(left) > av)
        {
            if (av > in.at(right))
            {
                tmp = in.at(left);
                in.at(left) = in.at(right);
                in.at(right) = tmp;
                left++;
            }
            right--;
        }
        else
        {
            if (av <= in.at(right)) right--;
            left++;
        }
    }
    if(left == right && in.at(left) <= av) left++;

    if((right = left-pos) < 2)return;
    else vquicksort2(in, right, pos);
    if((right = size-left+pos) < 2) return;
    else vquicksort2(in, right, left);
}

[wxSkip]

Und jetzt ists auch deutlich langsamer

[Enttäuscht]

Und ich dachte jetzt hätte es endlich jemand geschafft in O(log n) zu sortieren

[wxSkip]

Enttäuscht schrieb:

Und ich dachte jetzt hätte es endlich jemand geschafft in O(log n) zu sortieren

Argh! Das ist doch bewiesen, dass das nicht geht!

[wxSkip]

Also in dem Fall:
Mein Quicksort , der mit &(vec[0]) direkt auf dem Array arbeitet, ist nicht ganz so schnell, ich melde mich dann wieder, wenn ich Quicksort imperativ implementiert habe