Kann ich auf die Elemente in einer c++ - std::map und einem integer-index?

Ich habe eine Karte von Elementen, die ich möchte zu Durchlaufen. Natürlich, der standard-Weg, dies zu tun wäre mit einer for-Schleife mit

for (map<string, int> iterator it = myMap.begin(); it != myMap.end(); ++it) {
    string thisKey = it->first;
    int thisValue = it->second;
}

aber wenn ich versuchen und machen diese Schleife laufen parallel mit OpenMP ist parallel für konstruieren, es funktioniert nicht, und das ist (scheinbar) ein bekanntes Problem, da Sie nicht erkennen, diese Art von loop-Konstrukt.

So, mein backup-plan war mit einem integer-index-iterator und den Zugriff auf die Liste der Schlüssel und Werte, die durch den index, als ich tun würde in C# etwa so:

for (int i = 0; i < myMap.Count; ++i) {
    string thisKey = myMap.Keys[i];
    string thisValue = myMap.Values[i];
}

... aber ich kann nicht scheinen zu finden, eine entsprechende Methode in C++. Gibt es eine Möglichkeit in C++, dass ich bewusst bin?

  • Sind Sie sicher, dass std::map ist der beste Behälter für das erreichen wollen?
  • Das Durchlaufen einer Karte ist ein Baum traversal, es ist nicht eine einfache Bedienung. Auch wenn Sie in der Lage waren, zu indizieren, wie Sie wollen, es würde nicht parallelisieren für Sie.
  • wie viele Paare sind in dieser Karte von Euch?
  • Mark: Danke, dass so ziemlich beantwortet meine Frage. Ich denke, dass meine aktuelle Lösung (iterieren über den Baum und kopieren Sie die Ergebnisse in Vektoren, dann Durchlaufen Sie die Vektoren) ist wahrscheinlich der beste Weg zu gehen. JK: für diese spezielle Anwendung, 99991.
InformationsquelleAutor Charles | 2011-08-02
  1. 7

    Ich weiß nicht, etwas über OpenMP, also ich weiß nicht, ob es optimiert die folgende oder nicht. Aber man könnte std::advance, etwa so:

    #include <map>
#include <string>
#include <iterator>
#include <iostream>

typedef std::map<std::string, int> Map;

int main() {
  Map m;
  m["one"] = 1;
  m["two"] = 2;
  for(int i = 0; i < m.size(); ++i) {
    Map::iterator it = m.begin();
    std::advance(it, i);
    std::string thiskey = it->first;
    int thisValue = it->second;
    std::cout << thiskey << "\n";
  }
}

    Aber bewusst sein, dass std::advance ist O(n), so dass Ihre (single-threaded) Komplexität ist O(n^2).

    BEARBEITEN: Wenn Sie kopieren Sie die map-Elemente in einen Vektor, erkennen, die Sie tun können, dass in einer Erklärung:

    std::vector<Map::value_type> v(m.begin(), m.end());

    also:

    #include <map>
#include <string>
#include <iterator>
#include <iostream>
#include <vector>

typedef std::map<std::string, int> Map;

int main() {
  Map m;
  m["one"] = 1;
  m["two"] = 2;
  int i = 0;
  for( std::vector<Map::value_type> v(m.begin(), m.end());
    i < v.size(); ++i) {
    std::string thiskey = v[i].first;
    int thisValue = v[i].second;
    std::cout << thiskey << "\n";
  }
}
    • Ich versuchte wirklich, dass.. es ist schrecklich langsam. Ich verliere fast die ganze Zeit, die ich gewinnen, indem Sie es multi-threaded, und ich habe 24 threads gehen. Meine jetzige Lösung jetzt ist, zu deklarieren einer vector<string> und ein vector<int>, vergrößern Sie Sie, und sichern Sie die Daten in die Vektoren dann auf diese Weise.. es fügt sehr wenig overhead, aber es scheint wie eine kluge.
    • Könnte es besser sein, halten Sie einen einzigen Vektor von map::value_type. Siehe mein edit. (Hmmm, aber das wird nicht reserve genug initial memory.)
    InformationsquelleAutor Robᵩ
  2. 5

    Hier sind ein paar Optionen, die relativ schmerzlos.

    1. Halten std::vector oder std::deque für den array-Zugriff, und eine separate map-Werte. Die Bein-Arbeit ist, sicherzustellen, dass Sie konsequent ist Ihre problem.

    2. Verwenden boost::multi_index zur Gewährleistung der Konsistenz zwischen den beiden index-Strukturen. Als ein Wort der Warnung, compile-Zeiten sind ziemlich lang mit dieser option. Erwägen Sie die Verwendung das pimpl-idiom wenn Sie diesen Weg gehen.

    Habe ich keine Erfahrung mit OpenMP, so kann ich nicht spekulieren, ob eine dieser Optionen wäre sinnvoll, in der Praxis.

    InformationsquelleAutor Tom Kerr
Schreibe einen Kommentar