std::map<> und Iteratoren.



  • Hi. 🙂

    Ich brauche eigentlich eine std::map<std::string, x>. Allerdings habe ich später nur zwei Iteratoren, um auf die Map zuzugreifen. Um zu vermeiden, dauernd neue std::strings() aus den Iteratoen erstellen zu müssen, wollte ich mir also eine std::map<Range, x> bauen. (Range wäre dann meine Klasse).
    Jetzt muss ich den String aber jedes Mal kopieren. Die einzige Möglichkeit, die mir eingefallen ist:

    // std::map<std::string, std::string> m_dummy; <--
    
      bool add(std::string name, void x))
      {
        m_dummy[name] = name;
        m_map[Range(m_dummy[name].begin(), m_dummy[name].end())] = x;
        return true;
      }
      bool remove(std::string name)
      {
        if (m_dummy.find(name) != m_dummy.end())
        {
          m_map.erase(Range(m_dummy[name].begin(), m_dummy[name].end()));
          m_dummy.erase(name);
          return true;
        }
        return false;
      }
    

    Hat jemand dazu eine ordentliche Idee? Denn hier mit zwei Maps hantieren zu müssen, erscheint mir irgendwie unpraktisch.

    Ach ja, ich muss für eine std::map<> ja auch std::less<> zulassen, hat da jemand vielleicht auch etwas besseres? (Quasi strcmp() für Iteratoren. 🙄 )

    bool operator < (Range range) const
      {
        if (end - begin == range.end - range.begin)
        {
          std::pair<std::string::const_iterator, std::string::const_iterator> 
            p = std::mismatch(begin, end, range.begin);
          if (p.first != end)
          {
            return *p.first < *p.second;
          }
          return false;
        }
        else if(end - begin < range.end - range.begin)
        {
          return true;
        }
        else
        {
          return false;
        }
      }
    

  • Mod

    cooky451 schrieb:

    Hi. 🙂

    Ich brauche eigentlich eine std::map<std::string, x>. Allerdings habe ich später nur zwei Iteratoren, um auf die Map zuzugreifen. Um zu vermeiden, dauernd neue std::strings() aus den Iteratoen erstellen zu müssen, wollte ich mir also eine std::map<Range, x> bauen. (Range wäre dann meine Klasse).

    Hier hast du mich verloren. Warum musst du neue Strings erstellen?



  • SeppJ schrieb:

    Hier hast du mich verloren. Warum musst du neue Strings erstellen?

    Vielleicht übersehe ich da etwas ganz Grobes, aber ich habe keinen Weg gefunden find und operator[] bei einer std::map<std::string, x> mit Iteratoren zu nutzen.


  • Mod

    cooky451 schrieb:

    SeppJ schrieb:

    Hier hast du mich verloren. Warum musst du neue Strings erstellen?

    Vielleicht übersehe ich da etwas ganz Grobes, aber ich habe keinen Weg gefunden find und operator[] bei einer std::map<std::string, x> mit Iteratoren zu nutzen.

    Irgendwie verstehe ich dich gerade nicht. Wieso willst du find oder [] benutzen, wenn du schon einen Iterator hast? Oder willst du einen Iterator zu einem bestimmen Element? Das ist wiederum das was find macht.



  • SeppJ schrieb:

    Irgendwie verstehe ich dich gerade nicht. Wieso willst du find oder [] benutzen, wenn du schon einen Iterator hast? Oder willst du einen Iterator zu einem bestimmen Element? Das ist wiederum das was find macht.

    Nein ich habe zwei Iteratoren, quasi einen String. Und ich will mit find() wissen ob dieser String bereits in der Map vorhanden ist, bzw. mit operator[] will ich auf das Element des Schlüssels zugreifen. Steht ganz oben, eigentlich möchte ich nur eine std::map<std::string, x>.

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



  • Was spricht gegen eine for-Schleife, wie die folgende:

    for(auto it = map.begin(); it != map.end(); ++it)
        if(it->first.length() == suchstring_lenght && std::equal(it->first.begin(), it->first.end(), suchstring_begin))
            // Treffer gefunden
    

  • Mod

    Da ist ja der ganze Vorteil der map weg, wenn du sie durchiterierst zum Suchen

    Mir ist da was eingefallen, was gehen könnte. Ich melde mich gleich.



  • SeppJ schrieb:

    Da ist ja der ganze Vorteil der map weg, wenn du sie durchiterierst zum Suchen

    Stimmt, daran hab ich gerade nicht gedacht 🤡



  • cooky451 schrieb:

    (Quasi strcmp() für Iteratoren. 🙄 )

    std::lexicographical_compare 😉



  • 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.


Log in to reply