C++ => std :: karta

Anmärkningar

För att använda någon av std::map eller std::multimap bör rubrikfilen <map> inkluderas.
std::map och std::multimap båda håller sina element sorterade enligt tangenternas stigande ordning. Vid std::multimap sker ingen sortering för värden på samma tangent.
Den grundläggande skillnaden mellan std::map och std::multimap är att std::map one inte tillåter duplicerade värden för samma nyckel som std::multimap gör.
Kartor implementeras som binära sökträd. Så search() , insert() , erase() tar Θ (log n) tid i genomsnitt. För ständig tidsanvändning använd std::unordered_map .
size() och empty() -funktioner har Θ (1) tidskomplexitet, antalet noder cachelagras för att undvika att gå igenom trädet varje gång dessa funktioner kallas.

Åtkomst till element

En std::map tar par (key, value) som input.

Tänk på följande exempel på std::map kartinitialisering:

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

I en std::map kan element läggas till enligt följande:

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

I exemplet ovan, om nyckeln stackoverflow redan finns, kommer det att uppdateras till 2. Om det inte redan finns, skapas en ny post.

På en std::map kan element nås direkt genom att ge nyckeln som ett index:

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

Observera att operator[] av operator[] på kartan faktiskt kommer att infoga ett nytt värde med den frågade nyckeln på kartan. Det betyder att du inte kan använda den på en const std::map , även om nyckeln redan är lagrad på kartan. För att förhindra detta införande, kontrollera om elementet finns (till exempel genom att find() ) eller använda at() som beskrivs nedan.

C ++ 11

Element av en std::map kan nås med at() :

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

Observera att at() kommer att kasta ett std::out_of_range undantag om behållaren inte innehåller det begärda elementet.

I båda containrarna std::map och std::multimap kan element nås med iteratorer:

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"

Initiera en std :: karta eller std :: multimap

std::map och std::multimap båda kan initieras genom att tillhandahålla nyckelvärdespar separerade med komma. Nyckelvärdespar kan tillhandahållas av antingen {key, value} eller kan uttryckligen skapas av std::make_pair(key, value) . Eftersom std::map inte tillåter duplikatnycklar och kommaoperatören utför från höger till vänster, skulle paret till höger skrivas över med paret med samma tangent till vänster.

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

Båda kan initieras med 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}

Ta bort element

Tar bort alla element:

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

Ta bort element från någonstans med hjälp av 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}

Ta bort alla element i ett intervall:

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}

Ta bort alla element som har ett angivet värde som nyckel:

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}

Ta bort element som uppfyller ett predikat pred :

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

Infoga element

Ett element kan infogas i en std::map bara om dess nyckel inte redan finns på kartan. Givet till exempel:

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

Ett nyckelvärdspar sätts in i en std::map genom funktionen för insert() . Det kräver ett pair som ett 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));
```
Funktionen insert() returnerar ett pair bestående av en iterator och ett bool :
- Om införandet lyckades pekar iteratorn på det nyinförda elementet och bool värdet är true .
- Om det redan fanns ett element med samma key misslyckas införandet. När det händer pekar iteratorn på elementet som orsakar konflikten, och bool är värdet är false .
Följande metod kan användas för att kombinera insättning och sökoperation:
```
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
}
```
För bekvämlighet ger std::map kartbehållaren abonnentoperatören åtkomst till element på kartan och att infoga nya om de inte finns:
```
fruits_count["apple"] = 10;
```
Även om det är enklare förhindrar det användaren från att kontrollera om elementet redan finns. Om ett element saknas skapar std::map::operator[] implicit std::map::operator[] det, initialiserar det med standardkonstruktören innan det skrivs över med det medföljande värdet.

insert() kan användas för att lägga till flera element samtidigt med hjälp av en parad lista över par. Denna version av insert () returnerar ogiltig:
```
fruits_count.insert({{"apricot", 1}, {"jackfruit", 1}, {"lime", 1}, {"mango", 7}}); 
```

insert() kan också användas för att lägga till element genom att använda iteratorer som anger början och slutet av value_type värden:

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

Exempel:

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

Tidskomplexitet för en insättningsoperation är O (log n) eftersom std::map implementeras som träd.

C ++ 11

Ett pair kan konstrueras uttryckligen med make_pair() och emplace() :

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

Om vi vet var det nya elementet kommer att infogas, kan vi använda emplace_hint() att ange en iterator- hint . Om det nya elementet kan sättas in strax före hint kan insättningen göras i konstant tid. Annars uppträder det på samma sätt som 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);

Iterera över std :: karta eller std :: multimap

std::map eller std::multimap kan korsas på följande sätt:

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

Medan iterering över en std::map eller en std::multimap föredras användningen av auto att undvika värdelösa implicita omvandlingar (se detta SO-svar för mer information).

Söker i std :: karta eller i std :: multimap

Det finns flera sätt att söka i en nyckel i std::map eller i std::multimap .

För att få iteratorn för den första förekomsten av en nyckel kan funktionen find() användas. Det returnerar end() om nyckeln inte finns.

  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.

Ett annat sätt att hitta om en post finns i std::map eller i std::multimap är att använda funktionen count() som räknar hur många värden som är associerade med en given nyckel. Eftersom std::map bara associerar ett värde med varje tangent, kan dess count() -funktion bara returnera 0 (om tangenten inte finns) eller 1 (om den är). För std::multimap kan count() returnera värden större än 1 eftersom det kan vara flera värden associerade med samma tangent.
```
 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;
```
Om du bara bryr dig om att något element finns, är find strängt bättre: det dokumenterar din avsikt och för multimaps kan det stoppa när det första matchande elementet har hittats.
När det gäller std::multimap kan det finnas flera element med samma nyckel. För att få detta intervall används equal_range() som returnerar std::pair med iterator nedre gräns (inklusive) respektive övre gräns (exklusiv). Om nyckeln inte finns, skulle båda iteratorerna peka på 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
```

Kontrollerar antalet element

Containern std::map har en medlemsfunktion empty() , som returnerar true eller false , beroende på om kartan är tom eller inte. size() returnerar antalet element lagrat i en std::map kartbehållare:

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

Typer av kartor

Vanlig karta

En karta är en associerande behållare som innehåller nyckelvärdespar.

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

I ovanstående exempel, std::string är nyckeltypen, och size_t är ett värde.

Nyckeln fungerar som ett index på kartan. Varje nyckel måste vara unik och måste beställas.

Om du behöver mutlipleelement med samma nyckel, multimap använda multimap (förklaras nedan)

Om din värdetyp inte anger någon beställning eller om du vill åsidosätta standardbeställningen kan du tillhandahålla en:

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

Om StrLess komparator returnerar false för två nycklar, betraktas de desamma även om deras faktiska innehåll skiljer sig åt.

Multi-Map

Multimap gör det möjligt att lagra flera nyckelvärdespar med samma nyckel på kartan. Annars är dess gränssnitt och skapelse mycket lik den vanliga kartan.

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

Hash-Map (Oordnad karta)

En hashkarta lagrar nyckelvärdespar som liknar en vanlig karta. Det beställer dock inte elementen med avseende på nyckeln. Istället används ett hashvärde för nyckeln för att snabbt komma åt de nödvändiga paren med nyckelvärde.

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

Oordnade kartor är vanligtvis snabbare, men elementen lagras inte i någon förutsägbar ordning. Exempelvis genom att iterera över alla element i ett unordered_map ger elementen i en till synes slumpmässig ordning.

Skapa std :: karta med användardefinierade typer som nyckel

För att kunna använda en klass som nyckel på en karta är allt som krävs av nyckeln att den är copiable och assignable . Beställningen på kartan definieras av det tredje argumentet till mallen (och argumentet till konstruktören, om den används). Detta är standardvärde för std::less<KeyType> , som är standard för < operatören, men det finns inget krav på att använda standardvärdena. Skriv bara en jämförelseoperatör (helst som ett funktionellt objekt):

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

I C ++ måste "jämför" -predikatet vara en strikt svag ordning . I synnerhet måste compare(X,X) returnera false för alla X dvs om CmpMyType()(a, b) returnerar true, då CmpMyType()(b, a) måste returnera falskt, och om båda returnerar falskt anses elementen vara lika (medlemmar i samma ekvivalensklass).

Strikt svag beställning

Detta är en matematisk term för att definiera en relation mellan två objekt.
Dess definition är:

Två objekt x och y är likvärdiga om både f (x, y) och f (y, x) är falska. Observera att ett objekt alltid (av den irreflexiva invarianten) motsvarar sig själv.

När det gäller C ++ betyder det att om du har två objekt av en viss typ, ska du returnera följande värden jämfört med operatören <.

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

Hur du definierar motsvarande / mindre är helt beroende av typen av objekt.

Modified text is an extract of the original Stack Overflow Documentation

Licensierat under CC BY-SA 3.0

Inte anslutet till Stack Overflow

C++
std :: karta

Sök…

Anmärkningar

Åtkomst till element

Initiera en std :: karta eller std :: multimap

Ta bort element

Infoga element

Iterera över std :: karta eller std :: multimap

Söker i std :: karta eller i std :: multimap

Kontrollerar antalet element

Typer av kartor

Vanlig karta

Multi-Map

Hash-Map (Oordnad karta)

Skapa std :: karta med användardefinierade typer som nyckel

Strikt svag beställning