C++ => std :: kaart

Opmerkingen

Om een van std::map of std::multimap het headerbestand <map> worden opgenomen.
std::map en std::multimap houden beide elementen gesorteerd volgens de oplopende volgorde van toetsen. In het geval van std::multimap vindt er geen sortering plaats voor de waarden van dezelfde sleutel.
Het fundamentele verschil tussen std::map en std::multimap is dat de std::map one geen dubbele waarden toestaat voor dezelfde sleutel als std::multimap .
Kaarten worden geïmplementeerd als binaire zoekbomen. Dus search() , insert() , erase() kost gemiddeld Θ (log n) tijd. Gebruik std::unordered_map gebruik met constante tijd.
size() functies size() en empty() hebben time (1) tijdcomplexiteit, het aantal knooppunten wordt in de cache opgeslagen om te voorkomen dat elke keer dat deze functies worden aangeroepen, door de boom loopt.

Toegang tot elementen

Een std::map neemt (key, value) paren als invoer.

Beschouw het volgende voorbeeld van std::map initialisatie:

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

In een std::map kunnen elementen als volgt worden ingevoegd:

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

Als in het bovenstaande voorbeeld de key- stackoverflow al aanwezig is, wordt de waarde ervan bijgewerkt naar 2. Als deze nog niet aanwezig is, wordt een nieuw item gemaakt.

In een std::map zijn elementen rechtstreeks toegankelijk door de sleutel als index op te geven:

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

Merk op dat het gebruik van de operator[] op de kaart daadwerkelijk een nieuwe waarde met de opgevraagde sleutel in de kaart invoegt . Dit betekent dat u het niet kunt gebruiken op een const std::map , zelfs als de sleutel al in de map is opgeslagen. Om dit invoegen te voorkomen, controleert u of het element bestaat (bijvoorbeeld met behulp van find() ) of gebruikt u at() zoals hieronder beschreven.

C ++ 11

Elementen van een std::map zijn toegankelijk via at() :

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

Merk op dat at() een uitzondering std::out_of_range als de container niet het gevraagde element bevat.

In beide containers std::map en std::multimap zijn elementen toegankelijk via iterators:

C ++ 11

// 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"

Een std :: map of std :: multimap initialiseren

std::map en std::multimap beide kunnen worden geïnitialiseerd door sleutel / waarde-paren van elkaar gescheiden door komma's. Sleutel / waarde-paren kunnen worden geleverd door {key, value} of kunnen expliciet worden gemaakt door std::make_pair(key, value) . Omdat std::map geen dubbele sleutels toestaat en de komma-operator van rechts naar links werkt, wordt het paar aan de rechterkant overschreven door het paar met dezelfde sleutel aan de linkerkant.

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 kunnen worden geïnitialiseerd met iterator.

// 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}

Elementen verwijderen

Alle elementen verwijderen:

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

Element verwijderen van ergens met behulp van iterator:

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 elementen uit een bereik verwijderen:

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}

Alle elementen verwijderen met een opgegeven waarde als sleutel:

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}

Het verwijderen van elementen die een predikaat voldoen pred :

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

Elementen invoegen

Een element kan alleen in een std::map worden ingevoegd als de sleutel nog niet in de kaart aanwezig is. Gegeven bijvoorbeeld:

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

Een sleutel / waarde-paar wordt in een std::map ingevoegd via de insert() . Het vereist een 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));
```
De functie insert() retourneert een pair bestaat uit een iterator en een bool :
- Als het invoegen is gelukt, wijst de iterator naar het nieuw ingevoegde element en is de bool waarde true .
- Als er al een element met dezelfde key , mislukt het invoegen. Wanneer dat gebeurt, wijst de iterator naar het element dat het conflict veroorzaakt, en de bool is value is false .
De volgende methode kan worden gebruikt om het invoegen en zoeken te combineren:
```
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
}
```
Voor het gemak biedt de container std::map de subscript-operator toegang tot elementen in de kaart en nieuwe in te voegen als deze niet bestaan:
```
fruits_count["apple"] = 10;
```
Hoewel eenvoudiger, voorkomt het dat de gebruiker controleert of het element al bestaat. Als een element ontbreekt, maakt std::map::operator[] impliciet, initialiseert het met de standaardconstructor voordat het wordt overschreven met de opgegeven waarde.

insert() kan worden gebruikt om meerdere elementen tegelijk toe te voegen met behulp van een lijst met paren. Deze versie van insert () retourneert ongeldig:
```
fruits_count.insert({{"apricot", 1}, {"jackfruit", 1}, {"lime", 1}, {"mango", 7}}); 
```

insert() kan ook worden gebruikt om elementen toe te voegen met iterators die het begin en einde van value_type waarden 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());

Voorbeeld:

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
    }
}

Tijdcomplexiteit voor een invoegbewerking is O (log n) omdat std::map als bomen wordt geïmplementeerd.

C ++ 11

Een pair kan expliciet worden geconstrueerd met make_pair() en emplace() :

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

Als we weten waar het nieuwe element zal worden ingevoegd, kunnen we emplace_hint() gebruiken om een iterator- hint . Als het nieuwe element vlak voor de hint kan worden ingevoegd, kan het invoegen in constante tijd worden uitgevoerd. Anders gedraagt het zich op dezelfde manier als emplace() :

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);

Itereren over std :: map of std :: multimap

std::map of std::multimap kan op de volgende manieren worden doorlopen:

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

Hoewel het herhaald wordt over een std::map of een std::multimap , heeft het gebruik van auto voorkeur om nutteloze impliciete conversies te voorkomen (zie dit antwoord dus voor meer informatie).

Zoeken in std :: map of in std :: multimap

Er zijn verschillende manieren om een sleutel te zoeken in std::map of in std::multimap .

Om de iterator te krijgen van de eerste keer dat een sleutel voorkomt, kan de functie find() worden gebruikt. Retourneert end() als de sleutel niet bestaat.

  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.

Een andere manier om te achterhalen of een vermelding bestaat in std::map of in std::multimap is de functie count() , die telt hoeveel waarden aan een gegeven sleutel zijn gekoppeld. Omdat std::map slechts één waarde aan elke sleutel koppelt, kan de functie count() alleen 0 (als de sleutel niet aanwezig is) of 1 (als dit het geval is) retourneren. Voor std::multimap kan count() waarden retourneren die groter zijn dan 1, omdat er meerdere waarden kunnen zijn gekoppeld aan dezelfde sleutel.
```
 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;
```
Als het je alleen kan schelen of er een element bestaat, is find strikt beter: het documenteert je intentie en voor multimaps kan het stoppen zodra het eerste overeenkomende element is gevonden.
In het geval van std::multimap kunnen er verschillende elementen zijn met dezelfde sleutel. Om dit bereik te krijgen, wordt de functie equal_range() gebruikt die respectievelijk std::pair retourneert met iterator ondergrens (inclusief) en bovengrens (exclusief). Als de sleutel niet bestaat, wijzen beide iterators naar 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
```

Aantal elementen controleren

De container std::map heeft een lidfunctie empty() , die true of false retourneert, afhankelijk van of de map leeg is of niet. De size() retourneert het aantal elementen dat is opgeslagen in een std::map container:

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;
}

Typen kaarten

Normale kaart

Een kaart is een associatieve container die sleutel / waarde-paren bevat.

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

In het bovenstaande voorbeeld is std::string het sleuteltype en size_t is een waarde .

De sleutel fungeert als een index op de kaart. Elke sleutel moet uniek zijn en worden besteld.

Als u meerdere elementen met dezelfde sleutel nodig hebt, kunt u overwegen multimap (hieronder uitgelegd)

Als uw waardetype geen bestelling opgeeft of als u de standaardbestelling wilt overschrijven, kunt u er een opgeven:

#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;

Als StrLess comparator false retourneert voor twee sleutels, worden ze als hetzelfde beschouwd, zelfs als hun werkelijke inhoud verschilt.

Multi-Map

Met Multimap kunnen meerdere sleutel / waarde-paren met dezelfde sleutel worden opgeslagen op de kaart. Anders lijkt de interface en de creatie erg op de gewone kaart.

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

Hash-Map (ongeordende kaart)

Een hash-kaart slaat sleutel / waarde-paren op, vergelijkbaar met een gewone kaart. Het rangschikt de elementen echter niet met betrekking tot de sleutel. In plaats daarvan wordt een hash- waarde voor de sleutel gebruikt om snel toegang te krijgen tot de benodigde sleutel / waarde-paren.

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

Niet-geordende kaarten zijn meestal sneller, maar de elementen worden niet in een voorspelbare volgorde opgeslagen. Als u bijvoorbeeld alle elementen in een unordered_map krijgt u de elementen in een schijnbaar willekeurige volgorde.

Het maken van std :: map met door de gebruiker gedefinieerde typen als sleutel

Om een klasse als sleutel in een kaart te kunnen gebruiken, is het enige dat van de sleutel vereist is dat deze kan worden copiable en kan worden assignable . De volgorde binnen de kaart wordt bepaald door het derde argument voor de sjabloon (en het argument voor de constructor, indien gebruikt). Dit wordt standaard ingesteld op std::less<KeyType> , dat standaard wordt gebruikt door de operator < , maar er is geen vereiste om de standaardwaarden te gebruiken. Schrijf gewoon een vergelijkingsoperator (bij voorkeur als een functioneel object):

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

In C ++ moet het predikaat "vergelijken" een strikt zwakke volgorde zijn . In het bijzonder moet compare(X,X) voor elke X false . dat wil zeggen als CmpMyType()(a, b) true retourneert, dan moet CmpMyType()(b, a) false retourneren en als beide false retourneren, worden de elementen als gelijk beschouwd (leden van dezelfde equivalentieklasse).

Strikte zwakke bestelling

Dit is een wiskundige term om een relatie tussen twee objecten te definiëren.
De definitie is:

Twee objecten x en y zijn equivalent als zowel f (x, y) en f (y, x) onwaar zijn. Merk op dat een object altijd (door de onveranderlijke irreflexiviteit) gelijkwaardig is aan zichzelf.

In termen van C ++ betekent dit dat als u twee objecten van een bepaald type hebt, u de volgende waarden moet retourneren in vergelijking met de operator <.

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

Hoe u equivalent / minder definieert, is volledig afhankelijk van het type object.

Modified text is an extract of the original Stack Overflow Documentation

Licentie onder CC BY-SA 3.0

Niet aangesloten bij Stack Overflow

C++
std :: kaart

Zoeken…

Opmerkingen

Toegang tot elementen

Een std :: map of std :: multimap initialiseren

Elementen verwijderen

Elementen invoegen

Itereren over std :: map of std :: multimap

Zoeken in std :: map of in std :: multimap

Aantal elementen controleren

Typen kaarten

Normale kaart

Multi-Map

Hash-Map (ongeordende kaart)

Het maken van std :: map met door de gebruiker gedefinieerde typen als sleutel

Strikte zwakke bestelling