Heap

Hallo miteinander

Ich habe eine Verständnis-Frage:
Wenn ich sowas habe:
return heap[1].second;

und die heaps so gefüllt werden:
heap.insertItem(3, "apple");

Dann ist heap[1].first = 3 und heap[1].second = "apple", oder?

volkard

SonjaZ schrieb:

Hallo miteinander

Ich habe eine Verständnis-Frage:
Wenn ich sowas habe:
return heap[1].second;

und die heaps so gefüllt werden:
heap.insertItem(3, "apple");
Dann ist heap[1].first = 3 und heap[1].second = "apple", oder?

Wenn Du sagst, woher heap kommt, aus welcher API, aus welchem Lehrbuch oder woher? Dann könnte ich es vielleicht herausfinden.

Es kommt von privat. Aber was noch hilfreich wäre: Folgendes wird noch definiert:
typedef pair<Key, Element> Item;
vector<Item> heap;

volkard

SonjaZ schrieb:

Es kommt von privat. Aber was noch hilfreich wäre: Folgendes wird noch definiert:
typedef pair<Key, Element> Item;
vector<Item> heap;

Deine Vermutung mit first und second ist höchst wahrscheinlich wahr.
Es kommt nicht von privat.

Ok, besten Dank!
Da ich diese "Konvention" eben nirgends gelesen habe, war ich mir nicht ganz sicher. Allerdings würde der Code (für mich) keinen Sinn machen, wenn dies irgendwie anders wäre.

Liebe Grüsse und danke,
Sonja

bmario

Wenn ich das richtig verstehe, dann wird an dieser Stelle:

heap.insertItem(3, "apple");

implizit der Konstruktor pair<Value,Key>(Value, Key) aufgerufen.

DocShoe

Müsste das bei einem einelementigen heap nicht heap[0] heissen?

volkard

DocShoe schrieb:

Müsste das bei einem einelementigen heap nicht heap[0] heissen?

Vermutlich. Vielleicht aus einem Algorithmenbuch geholt, das für Pascal war. Mit heap[1] gibt's hübschere Tafelbildchen.

krümelkacker

SonjaZ schrieb:

typedef pair<Key, Element> Item;
vector<Item> heap;

Was ist Key und was ist Element?
Ich rate: Key=int und Element=std::string

SonjaZ schrieb:

Wenn ich sowas habe:
return heap[1].second;

und die heaps so gefüllt werden:
heap.insertItem(3, "apple");

heap ist nur ein Name. In diesem Fall bezieht sich der Name auf ein vector<Item>-Objekt, wobei Item synonym zu pair<Key,Element> ist. Mit anderen Worten, der Vektor speichert Key/Element-Paare. Ein solcher Vektor bietet aber keine Funktion mit Namen "insertItem" an.

Das Einfügen könnte so aussehen:

heap.insert(pos,Item(3,"apple"));

wobei pos ein Iterator ist, der die Einfüge-Position angibt.

SonjaZ schrieb:

Dann ist heap[1].first = 3 und heap[1].second = "apple", oder?

Diese Frage kann man Dir erst beantworten, wenn Du kompilierbaren Code zeigst. Nebenbei: Der Index für das erste Element eines Vektors ist 0.

Schau in Dein C++ Lehrbuch oder auch auf der Seite http://www.cplusplus.com/reference/ nach, wie Vektoren (std::vector) und Pair (std::pair) funktioniert bzw benutzbar ist. Das Klassen-Template vector wird in der Kopfdatei <header> und pair wird in <utility> definiert.

Ja, ein pair-Objekt besitzt zwei Datenelemente: first und second.

So sieht ein kompilierbares Beispiel aus:

#include <iostream>
#include <ostream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

typedef int Key;
typedef string Element;
typedef pair<Key,Element> Item;

int main()
{
  vector<Item> heap;
  heap.push_back(Item(42,"forty-two"));
  cout << heap[0].first << endl;
  cout << heap[0].second << endl;
}