Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (ANSI-Standard) » Intervalle mit std::map ?

Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 <
000
08.02.2006, 15:03 Uhr
stephanw
localhorst


Hi,

mangels Kaffee und mangels Erfahrung mit Maps überblicke die Möglichkeiten nicht ganz, die sich durch eigene Vergleichskriterien ergeben...
Ich habe Float-Schlüssel und Int-Werte. Die Float-Schlüssel sollen Intervalle ergeben. Jedes Intervall soll dann auf einen Int-Wert zeigen. Bsp:

0.0f ... 1.5f --> 100
1.5f ... 4.0f --> 50
usw.

Lässt sich durch geschickte Wahl eines Vgl.-kriteriums sowas machen oder muss ich das selber bauen ? Gibt es evtl. andere Lösungen im Std ?

Danke

PS: das Problem mit Testen auf float-Gleichheit ist mir bewusst
--
Reden ist Schweigen und Silber ist Gold.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
08.02.2006, 19:20 Uhr
(un)wissender
Niveauwart


Uh, ich weiß nicht recht was du tun willst.
Das Float-Interval soll der Schlüssel sein?
--
Wer früher stirbt ist länger tot.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
002
09.02.2006, 05:43 Uhr
Spacelord
Hoffnungsloser Fall


Hi,
da müsstest du dir für dein Intervall ne eigene Klasse schreiben,diese dann als Schlüssel nutzen und nen Konvertierungskonstruktor von float nach Intervall vorsehen um nen float Wert als Suchkriterium nutzen zu können(entsprechenden Vergleichsoperator vorausgesetzt).
Um allerdings aus nem float nen Intervall herstellen zu können müsste der Konstruktor ja wieder wissen in welchem Intervall der float Wert liegt.Diese Information müsste also irgendwo statisch hinterlegt sein.Wenn sich der Abbildungswert also nicht ständig ändert könnte man diesen Wert auch gleich zu nem Attribut der "statischen Intervallinformationen" machen.

MfG Spacelord
--
.....Ich mach jetzt nämlich mein Jodeldiplom.Dann hab ich endlich was Eigenes.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
003
09.02.2006, 08:59 Uhr
stephanw
localhorst


@(un)-wissender:

Es gibt (fest definierte) Intervalle von reellen Zahlen (floats). Zu jedem Intervall gehört ein Integer (ebenfalls fest). Nun möchte zu einer reellen Zahl den zugehörigen Int finden. Bezogen auf obiges Bsp. also findInt(1.0f) == 100 , findInt(3.0f) == 50 . Irgendwie hatte ich gedacht, das ließe sich relativ einfach mittels eines Std-Containers machen, bisher fiel mir nicht ein wie.

@Spacelord: um ein Intervall als Schlüssel zu verwenden, müsste ich "<" dafür bereitstellen. Der lässt sich für nicht-überlappende Intervalle noch herstellen, ok.
Zitat:
Um allerdings aus nem float nen Intervall herstellen zu können müsste der Konstruktor ja wieder wissen in welchem Intervall der float Wert liegt
Ich hatte gehofft, genau dafür eine map<float,int> nutzen zu können, in der also nur die Intervall-Grenzen als Paare von (float,int) abgelegt werden. Dann wäre der Zugriff auf den "richtigen" Int zwar nicht direkt möglich (oder doch ?), aber evtl. mit wenig Aufwand.

Aber ich denke auch nochmal über die "statischen Intervallinformationen" nach und die direkte Lösung über Intervall-Objekte als Schlüssel.

Danke !
--
Reden ist Schweigen und Silber ist Gold.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
004
09.02.2006, 19:40 Uhr
(un)wissender
Niveauwart


Jo, muss wohl eine eigene Klasse sein.
--
Wer früher stirbt ist länger tot.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
005
09.02.2006, 21:43 Uhr
Spacelord
Hoffnungsloser Fall


Hi,
also die Idee mit der std::map würde ich an deiner Stelle ganz fallen lassen.Damit drehst du dich warscheinlich nur im Kreis.
Ich hab mal ne grobe Variante zusammengeschustert in der ich allerdings keine gossartige Fehlerüberprüfung durchführe(keine Überprüfung auf Intervallüberlappung etc.).

Also in etwa in dieser Richtung würde ich es lösen:

float_intervall.h

C++:
#ifndef __FLOAT_INTERVALL_H
#define __FLOAT_INTERVALL_H

class float_intervall
{
public:
    float_intervall(float _start=0.0,float _end=0.0,int a_int=0)
        :start(_start),end(_end),associated_int(a_int){};
    ~float_intervall(){};
    int get_associated_int()const{return associated_int;}
    bool contains(float f)const{return(f >= start && f <= end); }//Rundungsprobleme ignoriert ;)
private:
    float start;
    float end;
    int associated_int;
};

#endif



intervall_map.h

C++:
#ifndef __INTERVALL_MAP_H
#define __INTERVALL_MAP_H

#include "float_intervall.h"
#include <vector>
#include <algorithm>
#include <functional>

class intervall_map
{
public:
    intervall_map(){init();}
    ~intervall_map(){}

    int find_associated_int(float f)const
    {
        int value=0;
        std::vector<float_intervall>::const_iterator it;
        it = std::find_if(intervalls.begin(),intervalls.end(),
            std::bind2nd(std::mem_fun_ref(&float_intervall::contains),f));
        if(it != intervalls.end())
            value = (*it).get_associated_int();

        return value;
    }
private:
    std::vector<float_intervall> intervalls;
    void init()
    {
        intervalls.push_back(float_intervall(0.0f,1.5f,50));
        intervalls.push_back(float_intervall(1.6f,2.9f,100));
        intervalls.push_back(float_intervall(11.32f,17.65f,23));
    }
};

#endif



zum Testen:

C++:
#include <iostream>
#include "intervall_map.h"

int main()
{
    intervall_map imap;
    std::cout<<"Das int zu 0,9 ist: "<<imap.find_associated_int(0.9f)<<std::endl;
    std::cout<<"Das int zu 12,0 ist: "<<imap.find_associated_int(12.0f)<<std::endl;

    return 0;
}



MfG Spacelord
--
.....Ich mach jetzt nämlich mein Jodeldiplom.Dann hab ich endlich was Eigenes.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
006
13.02.2006, 11:29 Uhr
stephanw
localhorst


Im Prinzip hab ich es ähnlich, halt ein Vector von Intervallen. Nur habe ich es nicht so elegant mit find_if und Adaptern+Bindern gemacht ;-) . Was mir daran nicht so gut gefällt ist, dass man immer den kompletten Intervall-Vector durchlaufen muss (O(n)), daher dachte ich ursprünglich an die Map. Ok, danke trotzdem sehr herzlich. Bei Gelegenheit mach ich mir vielleicht nochmal Gedanken darum.
--
Reden ist Schweigen und Silber ist Gold.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
007
15.02.2006, 09:57 Uhr
RHBaum



Das intervall ist doch fest ? damit kannst dir den start und endwert doch selber aussrechnen ? Genau so wie fuer jeden beliebigen auf wert deinen Intervall-index zurueckrechnen kannst ...

also bei nem gleichmaessigen intervall, dann waere dMin = index * intervall und dmax = (index +1) * intervall ....
wie man nun von nen beliebiegen Wert auf den passenden Index fuers intervall zurueckrechnet, ueberlass ich deiner mathematischen Phantasie ^^
wenn den index hasst, kannst sogar in nem vector nen einfachen lookup machen ^^

Somit kannst dein intervall doch auf nen Index - integer reduzieren und voiala klappt es sogar mit vectoren .... wenn die kette der intervalle wirklich vortlaufend ist, wuerd ich da keine map nehmen ... hasst hingegen luecken drin .... bietet sich die map an ...

Ups ich sehe grade, deine intervalle sind nicht gleichmaessig ......

dann koennt ich dir vielleicht nahelegen dass das ende des einen intervalls vom Anfang des Nachfolgenden bestimmt wird .....
somit kannst dein Kriterium auf einen float reduzieren ....

also ne std::map<float,int> wuerde sich anbieten ....

eintragen muesstest dann nur die startwerte + den zugehoerigen int wert ...
Wichtig, fuer das letzte intervall musst zusaetzlich den Abschlusswert eintragen, damit das vorherige intervall gueltig wird(nen endwert hat)

Suchen in der map kannst dann releativ einfach mit upper_bound und lower_bound (natuerlich nicht mit find ! )

also wenn deine map eintrage bei den flots bei 0.0, 1.5, 4.0,9.0 ... etc hat, wuerde dir lower_bound(3.0) nen iterator auf das element mit 1.5 geben, und upper_bound(3.0) den iterator auf das element bei 4.0 ...

lower_bound(4.0) wurde den iterator auf 4.0, und upper_bound(4.0) den iterator auf 9.0 geben !

Prinzip verstanden ?

Ciao ...

Dieser Post wurde am 15.02.2006 um 10:19 Uhr von RHBaum editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
008
15.02.2006, 19:20 Uhr
stephanw
localhorst


Hm, laut Josuttis' "The C++ Standard Library" gibt lower_bound(key) die Position des ersten Paares, dessen Schlüssel >= key ist. Demnach würde lower_bound(3.0) einen Iterator auf das Paar mit Schlüssel 4.0 geben. Darum hab ich das nicht genommen.
--
Reden ist Schweigen und Silber ist Gold.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
009
15.02.2006, 21:27 Uhr
Spacelord
Hoffnungsloser Fall


Hi,
also wenn du schon Code hast der dem von weiter oben ähnlich ist würde ich da gar keinen grossen Wirbel mehr mit der map machen.
Wenn du den vector bei der "Befüllung" schon sortierst und nen Vergleichsoperator zur Verfügung stellst kommst du mit binary_search auch auf ne logarithmische Laufzeit und hast den imho "schöneren" Code(im Sinne von: auch in 3 Jahren noch nachvollziehbar).

Zu dem Thema,welche Suchmethode man zu welchem Zweck einsetzt und für weitere Infos über upper/lower_bound und equal_range ist dieser Artikel hier recht gut:
www.aristeia.com/Papers/CUJ_Dec_2001.pdf

MfG Spacelord
--
.....Ich mach jetzt nämlich mein Jodeldiplom.Dann hab ich endlich was Eigenes.

Dieser Post wurde am 15.02.2006 um 21:28 Uhr von Spacelord editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 <     [ C / C++ (ANSI-Standard) ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: