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

Icematix

Zeiger auf das interne Array? Hier:

std::vector<int> myVector(100);
int* myIntAttay = &myVector[0];

wxSkip

Nexus schrieb:

Nein, mach sowas nicht! Das widerspricht dem Prinzip der Kapselung und Objektorientierung.

std::sort() wird mit ziemlicher Sicherheit effizienter sortieren, als irgendwas, das du schreiben würdest. Die Standardbibliothek wurde nämlich über Jahre hinweg entwickelt und man kann davon ausgehen, dass die Entwickler sich auch über Optimierungsmöglichkeiten Gedanken gemacht haben.

So sieht ein Aufruf aus. Mehr Infos findest du unter www.cplusplus.com.
std::sort(vec.begin(), vec.end());

1.Eine friend-Funktion widerspricht dem Prinzip aber nicht, oder?
2.Wenn ich Sicherheit wollte, würde ich nicht C++ programmieren

Doch gerade eine friend-Funktion widerspricht dem Prinzip. Deshalb muss die Klasse selbst auch sagen, wer ihre Freunde sind. Ohne Einladung bleibt man vor der Tür stehen.

SideWinder: Ja du scheinst recht zu haben - meine Information ist auch schon etwas älter.

Nexus

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!

wxSkip schrieb:

2.Wenn ich Sicherheit wollte, würde ich nicht C++ programmieren

In der Tat sehr einfallsreich. Dirty Hacks, wie du sie gerade versuchst, würde ich nicht als modernes C++ bezeichnen. Aber weil es möglich ist, darf man nicht mehr selbst nachdenken, genau.

Sag einfach, warum du meinst, direkt auf die Interna zugreifen zu wollen. Du kannst

Iteratoren benutzen
Indizes benutzen, genau wie beim C-Array
Icematix' Variante einsetzen, weil std::vector das garantiert. Aber stell dich darauf ein, dass du im Debug-Modus keine Sicherheitsabfragen mehr hast.

Im Ernst: Wenn dein Compiler und deine Standardbibliotheken irgendetwas taugen, sollten alle Möglichkeiten ungefähr gleich schnell sein (deaktivierbare Laufzeitchecks mal nicht berücksichtigt).

wxSkip

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

Nexus

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 überladenen operator[] oder noch besser at() verwenden.

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

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.

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.