C++
std :: map

Bemerkungen

Zugriff auf Elemente

Eine std::map (key, value) Paare als Eingabe.

Betrachten Sie das folgende Beispiel für die Initialisierung von std::map :

std::map < std::string, int > ranking { std::make_pair("stackoverflow", 2), 
                                        std::make_pair("docs-beta", 1) };

In einer std::map können Elemente wie folgt eingefügt werden:

ranking["stackoverflow"]=2;
ranking["docs-beta"]=1;

In dem obigen Beispiel, wenn der Schlüssel stackoverflow bereits vorhanden ist, wird sein Wert auf 2 aktualisiert werden , wenn es nicht bereits vorhanden ist , wird ein neuer Eintrag erstellt werden soll.

In einer std::map kann auf Elemente direkt zugegriffen werden, indem der Schlüssel als Index angegeben wird:

std::cout << ranking[ "stackoverflow" ] << std::endl;

Beachten Sie, dass bei Verwendung des operator[] auf der Karte tatsächlich ein neuer Wert mit dem abgefragten Schlüssel in die Karte eingefügt wird. Das bedeutet, dass Sie es nicht auf einer const std::map , selbst wenn der Schlüssel bereits in der Map gespeichert ist. Um diese Einfügung zu verhindern, prüfen Sie, ob das Element vorhanden ist (beispielsweise mit find() ) oder verwenden Sie at() wie unten beschrieben.

std::cout << ranking.at("stackoverflow") << std::endl;

In beiden Containern std::map und std::multimap kann auf Elemente mit Iteratoren zugegriffen werden:

// Example using begin()
std::multimap < int, std::string > mmp { std::make_pair(2, "stackoverflow"),
                                         std::make_pair(1, "docs-beta"),
                                         std::make_pair(2, "stackexchange")  };
auto it = mmp.begin();
std::cout << it->first << " : " << it->second << std::endl; // Output: "1 : docs-beta"
it++;
std::cout << it->first << " : " << it->second << std::endl; // Output: "2 : stackoverflow"
it++;
std::cout << it->first << " : " << it->second << std::endl; // Output: "2 : stackexchange"

// Example using rbegin()
std::map < int, std::string > mp {  std::make_pair(2, "stackoverflow"),
                                    std::make_pair(1, "docs-beta"),
                                    std::make_pair(2, "stackexchange")  };
auto it2 = mp.rbegin();
std::cout << it2->first << " : " << it2->second << std::endl; // Output: "2 : stackoverflow"
it2++;
std::cout << it2->first << " : " << it2->second << std::endl; // Output: "1 : docs-beta"

Std :: map oder std :: multimap initialisieren

std::map und std::multimap beide durch Angabe von durch Komma getrennten Schlüssel-Wert-Paaren initialisiert werden. Schlüssel-Wert-Paare können entweder von {key, value} bereitgestellt werden oder explizit von std::make_pair(key, value) . Da std::map keine doppelten Schlüssel zulässt und der Kommaoperator von rechts nach links ausgeführt wird, wird das rechte Paar mit dem gleichen Schlüssel links überschrieben.

std::multimap < int, std::string > mmp { std::make_pair(2, "stackoverflow"),
                                     std::make_pair(1, "docs-beta"),
                                     std::make_pair(2, "stackexchange")  };
// 1 docs-beta
// 2 stackoverflow
// 2 stackexchange

std::map < int, std::string > mp {  std::make_pair(2, "stackoverflow"),
                                std::make_pair(1, "docs-beta"),
                                std::make_pair(2, "stackexchange")  }; 
// 1 docs-beta
// 2 stackoverflow

Beide konnten mit Iterator initialisiert werden.

// From std::map or std::multimap iterator
std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {6, 8}, {3, 4}, 
                               {6, 7} };
                       // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 8}, {6, 7}, {8, 9}
auto it = mmp.begin();
std::advance(it,3); //moved cursor on first {6, 5}
std::map< int, int > mp(it, mmp.end()); // {6, 5}, {8, 9}

//From std::pair array
std::pair< int, int > arr[10];
arr[0] = {1, 3};
arr[1] = {1, 5};
arr[2] = {2, 5};
arr[3] = {0, 1};
std::map< int, int > mp(arr,arr+4); //{0 , 1}, {1, 3}, {2, 5}

//From std::vector of std::pair
std::vector< std::pair<int, int> > v{ {1, 5}, {5, 1}, {3, 6}, {3, 2} };
std::multimap< int, int > mp(v.begin(), v.end()); 
                        // {1, 5}, {3, 6}, {3, 2}, {5, 1}

Elemente löschen

Alle Elemente entfernen:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
mmp.clear(); //empty multimap

Element mit Hilfe des Iterators irgendwo entfernen:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                            // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9}
auto it = mmp.begin();
std::advance(it,3); // moved cursor on first {6, 5}
mmp.erase(it); // {1, 2}, {3, 4}, {3, 4}, {6, 7}, {8, 9}

Alle Elemente eines Bereichs entfernen:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                            // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9}
auto it = mmp.begin();
auto it2 = it;
it++; //moved first cursor on first {3, 4}
std::advance(it2,3);  //moved second cursor on first {6, 5}
mmp.erase(it,it2); // {1, 2}, {6, 5}, {6, 7}, {8, 9}

Entfernen aller Elemente mit einem angegebenen Wert als Schlüssel:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                            // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9}
mmp.erase(6); // {1, 2}, {3, 4}, {3, 4}, {8, 9}

Entfernen von Elementen , die ein Prädikat erfüllen pred :

std::map<int,int> m;
auto it = m.begin();
while (it != m.end())
{
   if (pred(*it))
       it = m.erase(it);
   else
       ++it;
}

Elemente einfügen

Ein Element kann nur dann in eine std::map eingefügt werden, wenn sein Schlüssel nicht bereits in der Map vorhanden ist. Zum Beispiel gegeben:

std::map< std::string, size_t > fruits_count;

• Ein Schlüsselwertpaar wird über die insert() in eine std::map eingefügt. Es erfordert ein pair als Argument:

  fruits_count.insert({"grapes", 20});
  fruits_count.insert(make_pair("orange", 30));
  fruits_count.insert(pair<std::string, size_t>("banana", 40));
  fruits_count.insert(map<std::string, size_t>::value_type("cherry", 50));
  

  Die Funktion insert() gibt ein pair das aus einem Iterator und einem bool Wert besteht:

  • Wenn das Einfügen erfolgreich war, zeigt der Iterator auf das neu eingefügte Element, und der bool Wert ist true .
  • Wenn bereits ein Element mit demselben key , schlägt das Einfügen fehl. In diesem Fall zeigt der Iterator auf das Element, das den Konflikt verursacht, und der bool Wert ist " false .

  Die folgende Methode kann zum Kombinieren von Einfügungs- und Suchvorgängen verwendet werden:

  auto success = fruits_count.insert({"grapes", 20});
  if (!success.second) {           // we already have 'grapes' in the map
      success.first->second += 20; // access the iterator to update the value
  }
  

• Der Container std::map bietet dem std::map die Möglichkeit, auf Elemente in der Map zuzugreifen und neue Elemente einzufügen, falls diese nicht vorhanden sind:

  fruits_count["apple"] = 10;
  

  Dies verhindert zwar, dass der Benutzer bereits überprüft, ob das Element bereits vorhanden ist. Wenn ein Element fehlt, erstellt std::map::operator[] implizit und initialisiert es mit dem Standardkonstruktor, bevor es mit dem angegebenen Wert überschrieben wird.

• insert() können Sie mehrere Elemente auf einmal mit einer geschweiften Liste von Paaren hinzufügen. Diese Version von insert () gibt void zurück:

  fruits_count.insert({{"apricot", 1}, {"jackfruit", 1}, {"lime", 1}, {"mango", 7}}); 
  

• insert() kann auch zum Hinzufügen von Elementen verwendet werden, indem Iteratoren verwendet werden, die den Anfang und das Ende der Werte von value_type :

  std::map< std::string, size_t > fruit_list{ {"lemon", 0}, {"olive", 0}, {"plum", 0}};
  fruits_count.insert(fruit_list.begin(), fruit_list.end()); 
  

Beispiel:

std::map<std::string, size_t> fruits_count;
std::string fruit;
while(std::cin >> fruit){
    // insert an element with 'fruit' as key and '1' as value
    // (if the key is already stored in fruits_count, insert does nothing)
    auto ret = fruits_count.insert({fruit, 1});
    if(!ret.second){            // 'fruit' is already in the map 
        ++ret.first->second;    // increment the counter
    }
}

Die Zeitkomplexität für eine Einfügeoperation ist O (log n), da std::map als Bäume implementiert ist.

std::map< std::string , int > runs;
runs.emplace("Babe Ruth", 714);
runs.insert(make_pair("Barry Bonds", 762));

std::map< std::string , int > runs;
auto it = runs.emplace("Barry Bonds", 762); // get iterator to the inserted element
// the next element will be before "Barry Bonds", so it is inserted before 'it'
runs.emplace_hint(it, "Babe Ruth", 714);

Iteration über std :: map oder std :: multimap

std::map oder std::multimap kann auf folgende Weise durchlaufen werden:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                               
//Range based loop - since C++11
for(const auto &x: mmp) 
    std::cout<< x.first <<":"<< x.second << std::endl;

//Forward iterator for loop: it would loop through first element to last element
//it will be a std::map< int, int >::iterator
for (auto it = mmp.begin(); it != mmp.end(); ++it)
std::cout<< it->first <<":"<< it->second << std::endl; //Do something with iterator

//Backward iterator for loop: it would loop through last element to first element
//it will be a std::map< int, int >::reverse_iterator
for (auto it = mmp.rbegin(); it != mmp.rend(); ++it)
std::cout<< it->first <<" "<< it->second << std::endl; //Do something with iterator

Während über einen Iterieren std::map oder std::multimap , die Verwendung von auto bevorzugt nutzlos implizite Konvertierungen zu vermeiden (siehe diese SO Antwort für weitere Details).

Suchen in std :: map oder in std :: multimap

Es gibt mehrere Möglichkeiten, einen Schlüssel in std::map oder in std::multimap zu suchen.

• Um den Iterator des ersten Vorkommens eines Schlüssels zu erhalten, kann die Funktion find() verwendet werden. Es gibt end() wenn der Schlüssel nicht vorhanden ist.

    std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
    auto it = mmp.find(6);
    if(it!=mmp.end())
        std::cout << it->first << ", " << it->second << std::endl; //prints: 6, 5
    else
        std::cout << "Value does not exist!" << std::endl;
  
    it = mmp.find(66);
    if(it!=mmp.end())
        std::cout << it->first << ", " << it->second << std::endl; 
    else
        std::cout << "Value does not exist!" << std::endl; // This line would be executed.
  

• Eine andere Möglichkeit, um herauszufinden, ob ein Eintrag in std::map oder in std::multimap ist, ist die Funktion count() , die zählt, wie viele Werte einem bestimmten Schlüssel zugeordnet sind. Da std::map jedem Schlüssel nur einen Wert zuordnet, kann die Funktion count() nur 0 (wenn der Schlüssel nicht vorhanden ist) oder 1 (falls vorhanden) zurückgeben. Für std::multimap kann count() Werte größer als 1 zurückgeben, da dem gleichen Schlüssel mehrere Werte zugeordnet werden können.

   std::map< int , int > mp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
   if(mp.count(3) > 0) // 3 exists as a key in map
       std::cout << "The key exists!" << std::endl; // This line would be executed.
   else
       std::cout << "The key does not exist!" << std::endl;
  

  Wenn Sie nur darauf achten, ob ein Element vorhanden ist, ist find strikt besser: Es dokumentiert Ihre Absicht und kann bei multimaps aufhören, sobald das erste passende Element gefunden wurde.

• Im Fall von std::multimap könnten mehrere Elemente den gleichen Schlüssel haben. Um diesen Bereich zu erhalten, wird die Funktion equal_range() verwendet, die std::pair mit Iterator-Untergrenze (einschließlich) und Obergrenze (exklusiv) zurückgibt. Wenn der Schlüssel nicht vorhanden ist, zeigen beide Iteratoren auf end() .

    auto eqr = mmp.equal_range(6);
    auto st = eqr.first, en = eqr.second;
    for(auto it = st; it != en; ++it){
        std::cout << it->first << ", " << it->second << std::endl; 
    }
        // prints: 6, 5
        //         6, 7
  

Anzahl der Elemente prüfen

Der Container std::map hat eine Memberfunktion empty() , die true oder false zurückgibt, je nachdem, ob die Map leer ist oder nicht. Die Elementfunktion size() gibt die Anzahl der Elemente zurück, die in einem std::map Container gespeichert sind:

std::map<std::string , int> rank {{"facebook.com", 1} ,{"google.com", 2}, {"youtube.com", 3}};
if(!rank.empty()){
    std::cout << "Number of elements in the rank map: " << rank.size() << std::endl;
}
else{
    std::cout << "The rank map is empty" << std::endl;
}

Arten von Karten

Regelmäßige Karte

Eine Map ist ein assoziativer Container, der Schlüsselwertpaare enthält.

#include <string>
#include <map>
std::map<std::string, size_t> fruits_count;

Im obigen Beispiel ist std::string der Schlüsseltyp und size_t ist ein Wert .

Der Schlüssel dient als Index in der Karte. Jeder Schlüssel muss eindeutig sein und muss bestellt werden.

• Wenn Sie mehrere Elemente mit demselben Schlüssel benötigen, ziehen Sie die Verwendung von multimap Betracht (unten erklärt).

• Wenn Ihr Werttyp keine Reihenfolge angibt oder Sie die Standardreihenfolge überschreiben möchten, können Sie eine angeben:

  #include <string>
  #include <map>
  #include <cstring>
  struct StrLess {
      bool operator()(const std::string& a, const std::string& b) {
          return strncmp(a.c_str(), b.c_str(), 8)<0;
                 //compare only up to 8 first characters
      }
  }
  std::map<std::string, size_t, StrLess> fruits_count2;
  

  Wenn der StrLess Komparator für zwei Schlüssel den StrLess false zurückgibt, werden sie als identisch betrachtet, auch wenn der tatsächliche Inhalt unterschiedlich ist.

Multi-Map

Mit Multimap können mehrere Schlüsselwertpaare mit demselben Schlüssel in der Karte gespeichert werden. Ansonsten ist die Benutzeroberfläche und Erstellung der normalen Map sehr ähnlich.

 #include <string>
 #include <map>
 std::multimap<std::string, size_t> fruits_count;
 std::multimap<std::string, size_t, StrLess> fruits_count2;

Hash-Map (ungeordnete Karte)

Eine Hash-Map speichert Schlüsselwertpaare ähnlich einer regulären Map. Es ordnet die Elemente jedoch nicht in Bezug auf den Schlüssel an. Stattdessen wird ein Hashwert für den Schlüssel verwendet, um schnell auf die erforderlichen Schlüssel-Wert-Paare zuzugreifen.

#include <string>
#include <unordered_map>
std::unordered_map<std::string, size_t> fruits_count;

Ungeordnete Karten sind normalerweise schneller, aber die Elemente werden nicht in einer vorhersagbaren Reihenfolge gespeichert. Wenn Sie beispielsweise alle Elemente in einer unordered_map durchlaufen, werden die Elemente in einer scheinbar zufälligen Reihenfolge angezeigt.

Erstellen von std :: map mit benutzerdefinierten Typen als Schlüssel

Um eine Klasse als Schlüssel in einer Map verwenden zu können, muss der Schlüssel copiable und assignable . Die Reihenfolge innerhalb der Map wird durch das dritte Argument der Vorlage (und das Argument des Konstruktors, falls verwendet) definiert. Der Standardwert ist std::less<KeyType> , der standardmäßig auf den < Operator, aber es gibt keine Notwendigkeit , die Standardeinstellung zu verwenden. Schreiben Sie einfach einen Vergleichsoperator (vorzugsweise als Funktionsobjekt):

struct CmpMyType
{
    bool operator()( MyType const& lhs, MyType const& rhs ) const
    {
        //  ...
    }
};

In C ++ muss das Vergleichselement "Compare" eine strikte schwache Reihenfolge sein . Insbesondere muss der compare(X,X) für jedes X false . dh wenn CmpMyType()(a, b) true zurückgibt, muss CmpMyType()(b, a) false zurückgeben, und wenn beide false zurückgeben, werden die Elemente als gleich betrachtet (Mitglieder derselben Äquivalenzklasse).

Strikte schwache Reihenfolge

Dies ist ein mathematischer Begriff, um eine Beziehung zwischen zwei Objekten zu definieren.
Seine Definition ist:

Zwei Objekte x und y sind gleichwertig, wenn sowohl f (x, y) als auch f (y, x) falsch sind. Beachten Sie, dass ein Objekt (durch die Irreflexivitätsinvariante) immer sich selbst entspricht.

In C ++ bedeutet dies, wenn Sie zwei Objekte eines bestimmten Typs haben, sollten Sie die folgenden Werte zurückgeben, wenn Sie sie mit dem Operator <vergleichen.

X    a;
X    b;

Condition:                  Test:     Result
a is equivalent to b:       a < b     false
a is equivalent to b        b < a     false

a is less than b            a < b     true
a is less than b            b < a     false

b is less than a            a < b     false
b is less than a            b < a     true

Wie Sie Äquivalent / Weniger definieren, hängt völlig vom Typ Ihres Objekts ab.