C++ => std :: mapa

Uwagi

Aby użyć dowolnej ze std::map lub std::multimap należy dołączyć plik nagłówka <map> .
std::map i std::multimap utrzymują swoje elementy posortowane zgodnie z rosnącą kolejnością klawiszy. W przypadku std::multimap nie występuje sortowanie według wartości tego samego klucza.
Podstawowa różnica między std::map i std::multimap polega na tym, że std::map one nie zezwala na powielanie wartości dla tego samego klucza, co robi std::multimap .
Mapy są implementowane jako drzewa wyszukiwania binarnego. Tak więc search() , insert() , erase() zajmuje średnio Θ (log n) czas. Do pracy w trybie ciągłym używaj std::unordered_map .
Funkcje size() i empty() mają złożoność czasową Θ (1), liczba węzłów jest buforowana, aby uniknąć przechodzenia przez drzewo przy każdym wywołaniu tych funkcji.

Dostęp do elementów

std::map przyjmuje jako dane wejściowe pary (key, value) .

Rozważ następujący przykład inicjalizacji std::map :

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

W std::map elementy można wstawiać w następujący sposób:

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

W powyższym przykładzie, jeśli przepełnienie stackoverflow kluczy jest już obecne, jego wartość zostanie zaktualizowana do 2. Jeśli nie jest już obecny, zostanie utworzony nowy wpis.

W std::map elementy można uzyskać bezpośrednio, podając klucz jako indeks:

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

Zauważ, że użycie operator[] na mapie spowoduje wstawienie nowej wartości z pytanym kluczem do mapy. Oznacza to, że nie można go używać na const std::map , nawet jeśli klucz jest już zapisany na mapie. Aby temu zapobiec, sprawdź, czy element istnieje (na przykład za pomocą find() ) lub użyj at() jak opisano poniżej.

C ++ 11

Elementy std::map są dostępne za pomocą at() :

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

Zauważ, że at() wyrzuci wyjątek std::out_of_range jeśli kontener nie zawiera żądanego elementu.

W obu kontenerach std::map i std::multimap dostęp do elementów można uzyskać za pomocą iteratorów:

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"

Inicjalizacja std :: map lub std :: multimap

Zarówno std::map i std::multimap można zainicjować, podając pary klucz-wartość oddzielone przecinkiem. Pary klucz-wartość mogą być dostarczone przez {key, value} lub mogą być jawnie utworzone przez std::make_pair(key, value) . Ponieważ std::map nie zezwala na duplikowanie kluczy, a operator przecinków wykonuje od prawej do lewej, para po prawej stronie zostanie zastąpiona parą z tym samym kluczem po lewej stronie.

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

Oba można zainicjować za pomocą iteratora.

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

Usuwanie elementów

Usuwanie wszystkich elementów:

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

Usuwanie skądś elementu za pomocą iteratora:

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}

Usuwanie wszystkich elementów z zakresu:

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}

Usuwanie wszystkich elementów mających podaną wartość jako klucz:

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}

Usuwanie elementów spełniających predykat pred :

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

Wstawianie elementów

Element można wstawić do std::map tylko wtedy, gdy jego klucz nie jest już obecny na mapie. Biorąc na przykład:

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

Para klucz-wartość jest wstawiana do std::map poprzez funkcję członka insert() . Wymaga pair jako argumentu:
```
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));
```
Funkcja insert() zwraca pair składającą się z iteratora i wartości bool :
- Jeśli wstawienie zakończyło się pomyślnie, iterator wskazuje na nowo wstawiony element, a wartość bool jest true .
- Jeśli był już element z tym samym key , wstawianie kończy się niepowodzeniem. Kiedy tak się dzieje, iterator wskazuje element powodujący konflikt, a bool ma wartość false .
Aby połączyć operację wstawiania i wyszukiwania, można użyć następującej metody:
```
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
}
```
Dla wygody std::map zapewnia operatorowi indeksu dolnego dostęp do elementów na mapie i wstawianie nowych, jeśli nie istnieją:
```
fruits_count["apple"] = 10;
```
Chociaż jest to prostsze, uniemożliwia użytkownikowi sprawdzenie, czy element już istnieje. Jeśli brakuje elementu, std::map::operator[] domyślnie go tworzy, inicjując go z domyślnym konstruktorem przed nadpisaniem go podaną wartością.

insert() może być użyty do dodania kilku elementów jednocześnie za pomocą stężonej listy par. Ta wersja insert () zwraca void:
```
fruits_count.insert({{"apricot", 1}, {"jackfruit", 1}, {"lime", 1}, {"mango", 7}}); 
```

insert() można również używać do dodawania elementów za pomocą iteratorów oznaczających początek i koniec wartości 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());

Przykład:

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

Złożoność czasowa operacji wstawiania wynosi O (log n), ponieważ std::map są implementowane jako drzewa.

C ++ 11

pair może być skonstruowana jawnie za pomocą make_pair() i emplace() :

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

Jeśli wiemy, gdzie zostanie wstawiony nowy element, wówczas możemy użyć emplace_hint() aby określić hint iteratora. Jeśli nowy element można wstawić tuż przed hint , wstawianie może być wykonane w stałym czasie. W przeciwnym razie zachowuje się tak samo jak 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);

Iterowanie po std :: map lub std :: multimap

std::map lub std::multimap można przeglądać w następujący sposób:

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

Podczas iteracji po std::map lub std::multimap , preferowane jest użycie auto aby uniknąć niepotrzebnych niejawnych konwersji (więcej informacji można znaleźć w tej odpowiedzi SO ).

Wyszukiwanie w std :: map lub w std :: multimap

Istnieje kilka sposobów wyszukiwania klucza w std::map lub w std::multimap .

Aby uzyskać iterator pierwszego wystąpienia klucza, można użyć funkcji find() . Zwraca end() jeśli klucz nie istnieje.

  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.

Innym sposobem sprawdzenia, czy istnieje wpis w std::map lub w std::multimap jest użycie funkcji count() , która zlicza, ile wartości jest powiązanych z danym kluczem. Ponieważ std::map kojarzy tylko jedną wartość z każdym klawiszem, jego funkcja count() może zwrócić tylko 0 (jeśli klucz nie jest obecny) lub 1 (jeśli jest). W przypadku std::multimap count() może zwracać wartości większe niż 1, ponieważ z tym samym kluczem może być powiązanych kilka wartości.
```
 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;
```
Jeśli zależy ci tylko na tym, czy istnieje jakiś element, find jest zdecydowanie lepszy: dokumentuje twoje zamiary, a dla multimaps może zatrzymać się po znalezieniu pierwszego pasującego elementu.
W przypadku std::multimap może istnieć kilka elementów mających ten sam klucz. Aby uzyskać ten zakres, używana jest funkcja equal_range() która zwraca odpowiednio std::pair z iteratorem odpowiednio dolną granicę (włącznie) i górną granicę (wyłącznie). Jeśli klucz nie istnieje, oba iteratory wskazują na 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
```

Sprawdzanie liczby elementów

Kontener std::map ma funkcję empty() , która zwraca true lub false , w zależności od tego, czy mapa jest pusta, czy nie. Funkcja członkowska size() zwraca liczbę elementów przechowywanych w std::map :

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

Rodzaje map

Zwykła mapa

Mapa to kontener asocjacyjny zawierający pary klucz-wartość.

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

W powyższym przykładzie std::string jest typem klucza , a size_t jest wartością .

Klucz działa jak indeks na mapie. Każdy klucz musi być unikalny i musi zostać zamówiony.

Jeśli potrzebujesz wielu elementów z tym samym kluczem, rozważ użycie multimap (wyjaśnione poniżej)

Jeśli twój typ wartości nie określa żadnego zamówienia lub chcesz zastąpić domyślne zamówienie, możesz podać jeden:

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

Jeśli komparator StrLess zwraca wartość false dla dwóch kluczy, są one uważane za takie same, nawet jeśli ich rzeczywista zawartość różni się.

Wiele map

Multimapa pozwala na przechowywanie wielu par klucz-wartość z tym samym kluczem na mapie. W przeciwnym razie jego interfejs i tworzenie jest bardzo podobne do zwykłej mapy.

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

Mapa hash (mapa nieuporządkowana)

Mapa skrótów przechowuje pary klucz-wartość podobne do zwykłej mapy. Nie porządkuje jednak elementów w odniesieniu do klucza. Zamiast tego używana jest wartość skrótu dla klucza, aby szybko uzyskać dostęp do potrzebnych par klucz-wartość.

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

Nieuporządkowane mapy są zwykle szybsze, ale elementy nie są przechowywane w żadnej przewidywalnej kolejności. Na przykład iteracja po wszystkich elementach w unordered_map daje elementy w pozornie losowej kolejności.

Tworzenie std :: map z typami zdefiniowanymi przez użytkownika jako klucz

Aby móc użyć klasy jako klucza na mapie, wszystko, czego wymaga się od klucza, to możliwość copiable i assignable . Kolejność na mapie jest definiowana przez trzeci argument szablonu (i argument konstruktora, jeśli jest używany). Domyślnie jest to std::less<KeyType> , domyślnie jest to operator < , ale nie ma wymogu używania wartości domyślnych. Po prostu napisz operator porównania (najlepiej jako obiekt funkcjonalny):

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

W C ++ predykat „porównaj” musi mieć ścisłą słabą kolejność . W szczególności compare(X,X) musi zwrócić false dla dowolnego X tzn. jeśli CmpMyType()(a, b) zwraca true, to CmpMyType()(b, a) musi zwracać false, a jeśli oba zwracają false, elementy są uważane za równe (członkowie tej samej klasy równoważności).

Ściśle słabe zamawianie

Jest to termin matematyczny służący do zdefiniowania relacji między dwoma obiektami.
Jego definicja to:

Dwa obiekty xiy są równoważne, jeśli oba f (x, y) i f (y, x) są fałszywe. Zauważ, że obiekt jest zawsze (przez niezmienniczość nierefleksyjną) sam w sobie.

W kategoriach C ++ oznacza to, że jeśli masz dwa obiekty danego typu, powinieneś zwrócić następujące wartości w porównaniu z operatorem <.

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

To, jak zdefiniujesz ekwiwalent / mniej, zależy całkowicie od rodzaju twojego obiektu.

Modified text is an extract of the original Stack Overflow Documentation

Licencjonowany na podstawie CC BY-SA 3.0

Nie związany z Stack Overflow

C++
std :: mapa

Szukaj…

Uwagi

Dostęp do elementów

Inicjalizacja std :: map lub std :: multimap

Usuwanie elementów

Wstawianie elementów

Iterowanie po std :: map lub std :: multimap

Wyszukiwanie w std :: map lub w std :: multimap

Sprawdzanie liczby elementów

Rodzaje map

Zwykła mapa

Wiele map

Mapa hash (mapa nieuporządkowana)

Tworzenie std :: map z typami zdefiniowanymi przez użytkownika jako klucz

Ściśle słabe zamawianie