Problem bei der Wahl des Containers

[drakon]

Wenn du den vector nicht veränderst kannst du auch Iteratoren auf diese Range behalten.

Du könntest auch Zeiger auf die Elemente der gewünschten Range holen und speichern, aber du hast die gleiche Probleme, wie bei Iteratoren (wegen Invalidierung bei Veränderung des vectors).

[Ad aCTa]

Ich glaube, ich habe eine Idee. Ich benutze ja die pair-Vektoren u.a. auch für das finden der richtigen Position, damit ich z.B. im richtigen Subtree lande.

An sich könnte ich das ja in eine Liste verwandeln. Damit habe ich das Kopier-Problem nicht mehr, da ich neue Inhalte ja einfach einfügen kann. Wie ist so das Suchverhalten in einer sortieren Liste?
À propos: gibt es in der STL eine Liste, die gleich sortierend einfügt, also an der richtigen Stelle, dass ich nicht auch noch sort() anwenden muss? push_back() kann das ja unmöglich machen.

[drakon]

Ad aCTa schrieb:

À propos: gibt es in der STL eine Liste, die gleich sortierend einfügt, also an der richtigen Stelle, dass ich nicht auch noch sort() anwenden muss? push_back() kann das ja unmöglich machen.

std::set und std::multiset

[unskilled]

es gibt auch noch priority-que, auch wenn die hier vll nicht die klügste ist ;o)
ich würde für das erstellen eines baumes btw boost::ptr_vector oder wie der heißt verwenden - das einfügen braucht so zwar jedes mal ein new (statt eines placement news), aber dafür musst du immer nur nen paar byte umkopieren und kannst trotzdem ne binäre suche nutzen... aber ich hab kein plan, ob das das non plus ultra ist... das durchiterieren wird so jeweils eine dereferenzierung länger dauern - das kann man also denke ich vernachlässigen...

oder spricht da was dagegen?

nur eine funktion, die sortiert einfügt, kenne ich nicht - aber sind ja nur 2 zeilen ( std::(binary_)search und dann container::insert )

das ganze lohnt sich aber halt auch erst bei "richtigen" b-bäumen - und wird bei b-bäumen kleinerer ordnung viel zu lahm sein

was du auch machen könntest, wäre weiterhin vector zu nutzen und nen eigenes pair zu schreiben, was das eigentliche pair eben pimpelt(nur per pointer hält) - sollte aufs gleiche hinauskommen

bb

[Ad aCTa]

Hm... ja. In dem vector mit den Schlüssel/Wert-Paaren (ich nenne es ab jetzt std::pair) sind natürlich nur Zeiger enthalten, die die Objekte vom Allokator kommen (er sollte möglichst STL-kompatibel sein).

Der Algorithmus fängt so an:
k sei der zu suchende Schlüssel, x der aktuelle Knoten

• Suche die kleinste Position j in den Schlüsseln von x, welche größergleich dem Suchschlüssel ist.

• Wenn es ein innerer Knoten ist

• Wenn so eine Position j existiert:

• Wenn der Schlüssel x.k an Position j gleich k ist, wurde der Schlüssel gefunden

• sonst muss der Schlüssel in einem Unterbaum x.c mit Position j sein.

• ...

• ...

In Pseudo-C++:

iterator pos = std::find_if(paare.begin(), paare.end(), compare());
if(!kindknoten.empty()) // Kinder vorhanden ---> das ist ein innerer Knoten
   if(pos != paare.end()) // Wenn diese Position existiert
     if(pos.second == k) // Wenn der gefundene Schlüssel gleich Suchschlüssel ist
        // Erfolg!...
     else
         // Der Schlüssel muss in einem der Kindknoten sein. Die Zeiger sind im Vektor "kindknoten"
         size_t j = pos - paare.begin(); // absolute Position aus Iterator bestimmen
         return kindknoten[j].suche(k); // rekrusiver Aufruf

Das klappt ja wunderbar. Angenommen, ich verwende für die Bewarung der Paar-Zeiger jetzt ein std::set, kann ich diese Berrechnung in Zeile 8 nicht durchführen. Mit der bestimme ich aber die Position im Vektor mit den Kindverweisen. Ach, das ist zum Mäusemelken.

[Ad aCTa]

Kann man irgendwie (außer durch Sachen wie operator -()) von einem Iterator darauf schließen, auf das wievielte Element in der Sequenz er zeigt? Ich brauche ja nur den Offset.

[OhneName]

Ad aCTa schrieb:

Kann man irgendwie (außer durch Sachen wie operator -()) von einem Iterator darauf schließen, auf das wievielte Element in der Sequenz er zeigt? Ich brauche ja nur den Offset.

Wie wärs mit

typename iterator_traits<input_iterator>::difference_type
  distance( input_iterator pos1, input_iterator pos2 );

?

[unskilled]

wieso willst du nen b-baum durch nen avl-baum implementieren?
was spricht denn ggn nen pointer-vektor und es so zu machen, wie ich geschrieben hatte?

bb

[Ad aCTa]

Die Pairs sind ja gepimpelt. Sie werden vom Allokator erzeugt, und diese Zeiger packe ich momentan in ein std::set (ja, es ist schon komisch, einen Baum mit einem Baum zu implementieren).

> was spricht denn ggn nen pointer-vektor und es so zu machen, wie ich geschrieben hatte?

Nun ja, das hier:

> nur eine funktion, die sortiert einfügt, kenne ich nicht - aber sind ja nur 2 zeilen (std::(binary_)search und dann container::insert)

(Statt binary_search() meinst du wohl sort()). Das Einfügen am Ende ist schön billig, aber den z.B. 1024-Elemente langen Vektor anschließend zu sortieren, ist m.E. nicht ganz ohne. Deshalb hätte ich gerne einen Container, bei dem es
entweder:
günstig ist, ist der Mitte ein zu fügen (das kann vector nicht sein)
oder:
günstig ist, ihn zu sortieren, wenn man nur schlecht in der Mitte einfügen kann

Sortieren ist nie so schnell, deshalb wollte ich das erst mal vermeinden und lieber einen Container benutzen, der beim Einfügen bereits sortiert. Der leider einzige Container, der das kann, ist std::set. Bei ihm ist Einfügen in der Mitte auch sehr günstig. Aber eigentlich wäre mir eine std::list lieber, nur, die fügt nicht sortierend ein, die müsste man dann auch erst mit list::sort() sortieren. Aber std::list hat noch ein anderes Schmankerl: splice(). Wenn ich die Liste teilen muss (wie oben geschildert), kann ich die durch splice() teilen und die alte Liste wird gleich gelöscht, eine Move-Semantik wie ich sie wollte. Aber std::set hat sowas natürlich nicht. Grrrrrrr

[Ad aCTa]

Hm... so gesehen kann ich auch eine std::list verwenden. Da der sort()-Algorithmus der Liste ja optimiert ist, kann das nicht der Flaschenhals sein. Nur eine paar allgemeine Fragen:

std::list<pointer> payload;

// Erzeuge einfach mal ein paar Key/Values mit dem Allokator
pointer n = allocate(5);
construct(n,     std::make_pair("Brnold", "Schwarzennegger"));
construct(n + 1, std::make_pair("Frnold", "Mustermann"));
construct(n + 2, std::make_pair("Irnold", "Schwarzennegger"));
construct(n + 3, std::make_pair("Krnold", "Hellermann"));
construct(n + 4, std::make_pair("Xrnold", "Dunklermann"));
payload.push_back(n + 3);
payload.push_back(n + 2);
payload.push_back(n + 1);
payload.push_back(n + 4);
payload.push_back(n);
payload.sort(); // Sortieren nicht vergessen!

/* Ich will jetzt das Element in der Mitte finden. Das ist wohl das unperformanteste an der Liste, der Wert ist logischweise "Irnold": */

typename std::list<pointer>::iterator half = payload.begin();
std::advance(half, payload.size() / 2); // geht das irgendwie eleganter?

/* Jetzt muss die Liste in der Mitte geteilt werden. Der mittlere Wert muss ganz raus. Den Effekt kann man durch Ausgabe ja leicht erreichen: */
for(std::set<pointer>::iterator iter = payload.begin(); iter != half; ++iter) {
   std::cout << (*iter)->first << std::endl;
}
/* Das gibt logischerweise
Brnold
Frnold
aus. Jetzt will ich das aber in eine neue Liste packen (verschieben), bloß wie? */

std::list<pointer neue_liste;
neue_liste.splice(neue_liste.begin(), payload, payload.begin(), half); // das könnte doch klappen, splice schiebt von einschließlich begin bis half, aber nimmt half nicht auf, das wollte ich
// Aber die Test-Ausgabe:
for(std::list<pointer>::iterator i = neue_liste.begin(); i != neue_liste.end(); ++i)
	std::cout << (*i)->first << std::endl;
/*
Ausgabe:
Brnold
Frnold
Brnold
Frnold
Irnold
Krnold
Xrnold

What the hell??!
*/

Was mache ich falsch?

[hustbaer]

Ich hab irgendwie den Eindruck, dass du dich da ein wenig in etwas verrannt hast. Wenn das Umkopieren von z.B. 1000 Zeigern zu langsam ist, dann ist vermutlich 1000 einfach zu breit, d.h. du solltest den Baum schmäler machen.