3. Anfängerfrage: Über Teilmenge von Indeces iterieren

Anfängerfrage: Über Teilmenge von Indeces iterieren

  • S

    Hallo!

    Ich habe einen sortierten Vektor (vector<int>) mit dem Inhalt sagen wir mal:

    meinVektor[0] = 0;
    meinVektor[1] = 1;
    meinVektor[2] = 2;
    meinVektor[3] = 2;
    meinVektor[4] = 2;
    meinVektor[5] = 3;
    meinVektor[6] = 4;

    Nun soll mir eine Suchfunktion alle Indeces zurückliefern mit dem zugehörigen Wert z.B. 2. In diesem Fall also 2 bis 4. Ich nehme mal an, das macht man mit Iteratoren...

    Also Pseudocodemässig sowas:

    vector<int>::iterator sucheInVector(vector<int> vec, int value) {
  // Hier kommt Suchalgorithmus
  // ...
  // Dieser liefert dann die zwei Zahlen zurück:
  int lowIndex = 2;
  int hiIndex = 4;

  return IteratorKreierenMit(lowIndex, hiIndex);  // <- Was kommt hier?
}

    Durch was muss ich im Pseudocode IteratorKreierenMit ersetzen, damit ich einen Iterator zurückgeben kann, der von lowIndex bis hiIndex iteriert?

    Oder wie macht man das?

    //Edit: Ich habe bereits gesucht, finde leider nur Beispiele, wo über den ganzen Vektor iteriert wird... Irgendwie werde ich daraus nicht schlau.

    //Edit2: Im Prinzip könnte ich einfach ein Struct zurückgeben, wo hiIndex und loIndex drin gespeichert ist, aber ich möchte es jetzt mal mit Iteratoren versuchen...

    0
  • .

    Also ich würde einfach ein Iterator-Pair zurückgeben:

    return make_pair (find (vec.begin (), vec.end ()), find (vec.rbegin (), vec.rend ()).base () );
    0
  • S

    Vielen Dank für die Antwort. Also es muss eine Lösung mit den loIndex und hiIndex sein. Denn die Suche macht eine binäre Suche und ich verwende nicht die internen Funktionen find().
    Sowas vielleicht? Ist das sauber?

    return make_pair(vec.begin()+lowIndex, vec.begin()+hiIndex);
    0
  • .

    Eigentlich schon, aber warum verwendest du nicht einfach für deinen Suchalgorithmus Iteratoren? Desweiteren bin ich mir ziemlich sicher, dass das mit der STL-find Funktion (oder einer eigenen find Funktion) am "schönsten" ist, schließlich ist es dann ein Einzeiler!

    0
  • S

    Weil was ich brauche ist ein MultiMap in einem Vektor mit Suchzeit Log(n)! Ich habe so viele Einträge bis der Speicher voll ist, deswegen wäre eine Linked List o.ä. sehr verschwenderisch. Deswegen kommt alles in einen Vektor und dann wird am Schluss einmal sortiert, und gut ist...
    Es geht mir aber auch darum, die Sprache besser kennen zu lernen.

    0
  • C

    seeplusplus schrieb:

    Weil was ich brauche ist ein MultiMap in einem Vektor mit Suchzeit Log(n)!

    Wenn du eine MultiMap brauchst, nimm doch eine:

    #include <map>
std::multimap<int,int> daten;
    0
  • S

    Siehe letzten Beitrag. Die Daten müssen im Speicher aneinandergereiht sein (minimaler Speichergebrauch); sortiert soll erst am Schluss werden und die Suchzeit muss O(log(n)) sein. Ich glaube die std::MultiMap hat diese Eigenschaften nicht.

    Wieviel effektiver Speicher wird bei einem std::MultiMap<DWORD,DWORD> benötigt, pro Eintrag? Ich nehme an mehr als 8, oder täusche ich mich da?

    0
  • C

    Bin ich mir auch nicht sicher, dürfte etwa 8..12 für die Verpointerung plus die eigentlichen Daten sein.

    Aber wenn du wirklich Vektoren brauchst, dann nimm wenigstens die STL-Algorithmen - guter Ansatz wäre z.B. sort() (wie der Name schon sagt, zum Sortieren) und equal_range() (liefert dir einen Iterator-Bereich mit identischem Suchschlüssel).

    0
  • ?

    seeplusplus schrieb:

    Ich habe bereits gesucht, finde leider nur Beispiele, wo über den ganzen Vektor iteriert wird... Irgendwie werde ich daraus nicht schlau.

    Die STL-Algorithmen, die Iteratoren verwenden, bekommen gewöhnlich einen Start-Iterator und einen End-Iterator und iterieren solange der aktuelle Iterator ungleich dem End-Iterator ist.
    Der Start-Iterator muss sich NICHT auf den Anfang des Containers beziehen, sondern auf die Position des Elements bei dem die Iteration beginnen soll.
    Der End-Iterator muss sich NICHT auf das Ende des Containers beziehen, sondern auf die Position hinter dem letzten Element über das iteriert werden soll.
    Hier ein einfaches Beispiel:

    #include <iostream>
#include <iterator>
#include <vector>
using namespace std;

int main()
{
	vector<int> test;
	int ersterIndex = 2;
	int letzterIndex = 4;

	for (int i=0; i<10; ++i)
		test.push_back(i);

	copy(
		test.begin() + ersterIndex,
		test.begin() + letzterIndex + 1,
		ostream_iterator<int>(cout, "\n"));

    cin.get();
}
    0
  • S

    Okay, ich verwende jetzt std::sort(), sortierter Vektor, make_pair mit End-Iterator Index+1. Vielen Dank für die vielen Hinweise, wäre nicht selbst darauf gekommen.

    0
Anmelden zum Antworten