std::map<> und Iteratoren.



  • Also ich muß sagen, ich kann dir auch nicht so ganz folgen.

    deine_map.find(dein_string)

    liefert, wenn dein string in der map vorkommt, einen iterator auf die Position des Paares oder, bei nicht vorkommen, end().


  • Mod

    Vermutlich Kanonen auf Spatzen oder zu umständlich gedacht:

    #include <string>
    #include <algorithm>
    
    class RangeOrString
    {
    private:
      std::string *string_content;
      std::string::iterator *range_begin;
      std::string::iterator *range_end;
    
      void swap(RangeOrString &other)
      {
        std::swap(string_content, other.string_content);
        std::swap(range_begin, other.range_begin);
        std::swap(range_end, other.range_end);
      }
    
    public:
      operator std::string() const
      {
        if (string_content)
          return *string_content;
        else
          return
            std::string(*range_begin, *range_end);
      }
    
      RangeOrString(const std::string &string): 
        string_content(new std::string(string)),
        range_begin(0),
        range_end(0) {}
    
      RangeOrString(const char* string): 
        string_content(new std::string(string)),
        range_begin(0),
        range_end(0) {}
    
      RangeOrString(const std::string::iterator &range_begin, const std::string::iterator &range_end): 
        string_content(0),
        range_begin(new std::string::iterator(range_begin)),
        range_end(new std::string::iterator(range_end)) {}
    
      RangeOrString(const RangeOrString& other): 
        string_content((other.string_content) ? (new std::string(*other.string_content)) : 0),
        range_begin((other.range_begin) ? (new std::string::iterator(*other.range_begin)) : 0),
        range_end((other.range_end) ? (new std::string::iterator(*other.range_end)) : 0) {}
    
      ~RangeOrString()  { delete string_content; delete range_begin; delete range_end; }
    
      RangeOrString& operator=(const RangeOrString &other)
      {
        if (this != &other) 
          {
            RangeOrString tmp(other);
            swap(tmp);
          }
        return *this; 
      }
    
      friend bool operator<(const RangeOrString& lhs, const RangeOrString& rhs)
      {
        return std::lexicographical_compare((lhs.string_content ? lhs.string_content->begin() : *lhs.range_begin),
                                            (lhs.string_content ? lhs.string_content->end() : *lhs.range_end),
                                            (rhs.string_content ? rhs.string_content->begin() : *rhs.range_begin),
                                            (rhs.string_content ? rhs.string_content->end() : *rhs.range_end));
      }
    };
    
    #include<map>
    #include<iostream>
    
    using namespace std;
    
    int main()
    {
      map<RangeOrString, int> foo;
      foo["ABC"] = 1;
      foo["DEF"] = 2;
      foo["GHI"] = 3;
      foo["JKL"] = 4;
    
      string suchstring = "DEF";
    
      string::iterator begin = suchstring.begin();
      string::iterator end = suchstring.end();
    
      cout << foo.find(RangeOrString(begin,end))->second << '\n';
    }
    

    Keine unnötigen Stringkopieraktionen. Dafür ein bisschen Pointergeschiebeoverhead. Muss man abwägen, was besser ist.



  • 314159265358979 schrieb:

    std::lexicographical_compare 😉

    Ah super, wusste doch, dass es so was gibt. Das Problem wäre schon mal gelöst.

    @SeppJ ich hoffe mal deine Idee klappt! 🙂

    stefkowa schrieb:

    Also ich muß sagen, ich kann dir auch nicht so ganz folgen.

    deine_map.find(dein_string)

    Dann lies den Thread, ich habs doch jetzt eigentlich ausführlich genug erklärt. "dein_string" existiert nicht und aus Zeitrgründen möchte ich ohn auch nicht erstellen.



  • Vielleicht wird's klarer, wenn in der map nur ranges stehen auf strings in einem ptr_container.



  • SeppJ schrieb:

    😮

    Das muss ich mir erst mal angucken. :p
    Was ich aber gleich sagen kann ist, dass es mir nicht darum ging, dass ich den String das eine Mal nicht kopieren muss. Bzw. irgendwie schon, aber an der Stelle ist Performance egal. Mich nervt nur, dass ich zwei std::map's habe. Ich suche quasi eine std::map<> mit zwei Keys, so in der Art. Ich habe gerade aber selbst noch eine Idee, mal gucken ob das klappt. (Ich bastel was drum rum. In der OOP heißt es ja: Problem verschoben, Problem behoben.)



  • Was ich aber gleich sagen kann ist, dass es mir nicht darum ging, dass ich den String das eine Mal nicht kopieren muss. Bzw. irgendwie schon, aber an der Stelle ist Performance egal.

    Was spricht dann gegen deine folgende Lösung?

    Plätzchen schrieb:

    Nur dann sieht der Zugriff halt so aus:
    my_map.find(std::string(begin, end));
    my_map[std::string(begin, end)];

    Wenn dir die Geschwindigkeit egal ist, kannst du das doch wunderbar so machen.


  • Mod

    cooky451 schrieb:

    SeppJ schrieb:

    😮

    Das muss ich mir erst mal angucken. :p
    Was ich aber gleich sagen kann ist, dass es mir nicht darum ging, dass ich den String das eine Mal nicht kopieren muss. Bzw. irgendwie schon, aber an der Stelle ist Performance egal. Mich nervt nur, dass ich zwei std::map's habe. Ich suche quasi eine std::map<> mit zwei Keys, so in der Art. Ich habe gerade aber selbst noch eine Idee, mal gucken ob das klappt. (Ich bastel was drum rum. In der OOP heißt es ja: Problem verschoben, Problem behoben.)

    Aber was hält dich dann davon ab, so wie in deinem allerersten Satz einfach neue Strings aus den Iteratoren zu erstellen? Oder wenn's sein muss, einen Wrapper um die Map zu machen, der den Operator[] und find auch jeweils mit zwei Iteratoren überlädt? (Ok, bei Operator[] ein bisschen unschön, nimm eben Operator () dafür).



  • Irgendwer schrieb:

    Wenn dir die Geschwindigkeit egal ist, kannst du das doch wunderbar so machen.

    Ne, zwei Maps sind nervig. 🙂

    SeppJ schrieb:

    Oder wenn's sein muss, einen Wrapper um die Map zu machen

    Das erschien mir doch eher unschön. Auf die Idee, einfach meine Range-Klasse zu erweiten, bin ich irgendwie gar nicht gekommen. Mit deinem Ansatz sollte es aber ganz gut laufen. Ich habe ein paar Veränderungen gemacht, da ich nicht verstanden habe:
    - warum du Pointer auf Iteratoren gewählt hast
    - warum bool operator < als friend besser ist
    - was das "swap()" soll?

    struct Range
    {
    public:
      std::string::const_iterator begin;
      std::string::const_iterator end;
    
      Range(const std::string& string)
        : m_content(new std::string(string))
      {
        begin = m_content->begin();
        end = m_content->end();
      }
    
      Range(const char *string)
        : m_content(new std::string(string))
      {
        begin = m_content->begin();
        end = m_content->end();
      }
    
      Range(std::string::iterator first, 
        std::string::iterator second)
        : m_content(0), begin(first), end(second)
      {}
    
      Range(const Range& range)
        : m_content(range.m_content ? new std::string(*range.m_content) : 0)
      {
        if (m_content)
        {
          begin = m_content->begin();
          end = m_content->end();
        }
        else
        {
          begin = range.begin;
          end = range.end;
        }
      }
    
      ~Range()
      {
        delete m_content;
      }
    
      Range& operator = (const Range& range)
      {
        if (this != &range)
        {
          delete m_content;
          if (range.m_content)
          {
            m_content = new std::string(*range.m_content);
            begin = m_content->begin();
            end = m_content->end();
          }
          else
          {
            m_content = 0;
            begin = range.begin;
            end = range.end;
          }
        }
        return *this;
      }
      bool operator == (const Range& range) const
      {
        if (range.end - range.begin == end - begin)
        {
          return std::equal(begin, end, range.begin);
        }
        return false;
      }
      bool operator != (const Range& range) const
      {
        return !(range == *this);
      }
      bool operator < (const Range& range) const
      {
        return std::lexicographical_compare(begin, end, range.begin, range.end);
      }
      bool operator > (const Range& range) const
      {
        return std::lexicographical_compare(range.begin, range.end, begin, end);
      }
      std::string content()
      {
        if (m_content)
          return *m_content;
        return std::string(begin, end);
      }
    private:
      const std::string* m_content;
    };
    

  • Mod

    cooky451 schrieb:

    - warum du Pointer auf Iteratoren gewählt hast

    Damit sie Null sein können. Im Nachhinein gesehen ist es aber wohl praktischer es so wie du zu machen und nur einen Zeiger zu behalten. Ich habe die Klasse quasi so runtergetippt wie es mir in den Kopf kam, ohne groß zu designen.

    - warum bool operator < als friend besser ist

    Damit es eine freie Funktion ist und Konvertierungen greifen

    - was das "swap()" soll?

    Nun, es wird im Kopierkonstruktor benutzt. Da könnte man es natürlich auch explizit hinschreiben, aber da so eine Funktion sicher auch sonst ganz praktisch ist, habe ich sie ausgegliedert.



  • Warum kann hier keiner das Problem ordentlich beschreiben? Dann würdet ihr vlt. sogar selbst auf die Lösung kommen.



  • Tja - keine Ahnung warum du denkst, du bräuchtest eine zweite map - und ebenfalls keine Ahnung was die Range-Klasse nun für einen Vorteil haben soll.

    Überleg mal was hier passiert:

    Range * p;
    {
    	std::string name = "cookie";
    	p = new Range(name.begin(),name.end());
    }
    std::cout << p->content();
    

    Irgendwie keine gute Idee, einfach Iteratoren zu kopieren und als member zu speichern.



  • sinnfrei schrieb:

    Tja - keine Ahnung warum du denkst, du bräuchtest eine zweite map

    Wenn du eine bessere Idee hast, nur her damit. 😉



  • Ne, zwei Maps sind nervig. 🙂

    Also, dann scheine ich dein Problem immer noch nicht verstanden zu haben.

    Ich habe folgendes verstanden: Du hast eine Map<string, X> und begin/end-Iteratoren auf irgendwelche strings. Jetzt möchtest du wissen, ob der string [begin, end) in deiner Map vorhanden ist oder nicht? Stimmt das?



  • Irgendwer schrieb:

    Ich habe folgendes verstanden: Du hast eine Map<string, X> und begin/end-Iteratoren auf irgendwelche strings. Jetzt möchtest du wissen, ob der string [begin, end) in deiner Map vorhanden ist oder nicht? Stimmt das?

    Ja. Aber ohne jedes Mal einen neuen std::string erstellen zu müssen.



  • Ich hoffe ich hab folgendes richtig verstanden:

    • du möchtest eine std::map<string, x> verwenden, wobei x für irgendeinen Datentyp steht.
    • du hast allerdings nur zwei std::string::const_iterator(en)

    Jetzt will mir nicht ganz klar sein, was genau gegen

    typedef std::map<std::string, irgendwas> myMap;
    typedef std::string::const_iterator cStrIt;
    // ...
    void mapInsert(cStrIt& beg, cStrIt& end, irgendwas value) {
        myMap[std::string(beg,end)] = value;
    }
    

    spricht.
    Wozu solltest du hier eine zweite map benötigen, wenn es ohnehin nicht perfomancerelevant ist, dass du jedesmal temporäre string-obj erstellst?

    Deine Klasse Range ist ja nichts anderes als ein wrapper um einen string - nicht mehr. Also kannst du ihn dir auch gleich sparen, weil du einfach nichts gewinnst wenn du eine std::map<Range,x> anlegst.
    Du musst das Range-obj erstellen, und im Konstruktor wird dann wiederrum der string erzeugt. Also kannste auch gleich string nehmen.



  • moep - natürlich muss eine map vom Typ myMap erstellt werden, nicht direkt darauf gearbeitet werden .... Oo
    Hatte erst was anderes da stehen und einfach vergessen entsprechend richtig zu editieren. Sollte aber klar sein was ich meinte.



  • Irgendwer2 schrieb:

    Wozu solltest du hier eine zweite map benötigen, wenn es ohnehin nicht perfomancerelevant ist, dass du jedesmal temporäre string-obj erstellst?

    Es ist nicht performancerelevant, wie lange es dauert einen neuen String in die Map einzufügen. Es ist sehr relevant, wie lange es dauert um ein Element zu finden.

    Irgendwer2 schrieb:

    Du musst das Range-obj erstellen, und im Konstruktor wird dann wiederrum der string erzeugt. Also kannste auch gleich string nehmen.

    Nein. Die Konstruktoren für (std::string) und (const char*) erzeugen einen String. Der (iterator, iterator) erzeugt keinen. Der Kopier-Konstruktor erzeugt nur einen String, wenn die kopierte Range auch einen eigenen String hat.



  • Was ich aber gleich sagen kann ist, dass es mir nicht darum ging, dass ich den String das eine Mal nicht kopieren muss. Bzw. irgendwie schon, aber an der Stelle ist Performance egal.

    Es ist sehr relevant, wie lange es dauert um ein Element zu finden.

    Wie passt das zusammen?

    Nebenfrage: Wie kommst du überhaupt an diese Iteratoren? Wieso hast du keine Möglichkeit direkt mit den Strings zu arbeiten?

    Vielleicht macht es mehr Sinn, das Design so zu vereinfachen, dass du mit Strings hantieren kannst, anstatt dir so eine komische Range Klasse zu bauen.

    Aber wenn das alles nicht geht, scheinst du ja mit der Range eine Lösung gefunden zu haben.



  • Irgendwer schrieb:

    Wie passt das zusammen?

    Die Bemerkung bezog sich nur auf das Einfügen in die Map. Sorry, falls das missverständlich war.

    Irgendwer schrieb:

    Nebenfrage: Wie kommst du überhaupt an diese Iteratoren? Wieso hast du keine Möglichkeit direkt mit den Strings zu arbeiten?

    Jain. Also ja, aber dann müsste ich dauernd Substrings erstellen - was auch nicht Sinn der Sache ist. So muss ich nur Iteratoren hin und her bewegen.

    Irgendwer schrieb:

    Aber wenn das alles nicht geht, scheinst du ja mit der Range eine Lösung gefunden zu haben.

    Hmja, ich mache gerade ein paar Tests und der Performancegewinn bewegt sich zwischen Faktor 25 und 1. Da soll man mal schlau draus werden. 😃



  • 😃


Anmelden zum Antworten