Choose jour language!

---

|

REČNIK PODATAKA - MAPE U C++

Mape u C++ su kolekcije podataka koje čuvaju podatke čijim vrednostima se pristupa pomoću jedinstvenog ključa. To je zapravo rečnik podataka i deklariše se na sledeći način:
​
map<tip_ključa,tip_vrednosti>naziv_mape;

​Posmatrajmo sledeći problem: 

Zadati imena grupe učenika u jednom odeljenju. Uneti njihove prosečne ocene na kraju školske godine. odrediti prosek grupe i odrediti koliko je učenika postiglo uspeh iznad prosečnog
Rešenje: Ovaj primer ćemo rešiti upotrebom mapa, tako što će se za ključ upotrebiti ime učenika, a kao vrdnost unutar mape smestiti njihov uspeh.
​Da bi koristili mape u C++ unutar fajla mora se uključiti datoteka zaglavlja map:

#include < map >

​ Zatim je potrebno deklarisati mapu:

map < string, double> prosek;

Vidimo da će tipovi za ključeve biti string i to se odnosi na imena učenika, dok će tipovi vrednosti biti double, s obzirom da su vrednosti u stvari prosečne ocene, dakle, realni brojevi.

---

Inicijalizacija mape

​Jedan od načina da mapu popunimo sa vrednostima je da je inicijalizujemo i to je slučaj kada unapred znamo podatke o učenicima, njihova imena i ostvarene uspehe, tj. njihove prosečne ocene na kraju godine.

prosek={

{"Mika",4.52},
{"Milica",4.78},
{"Nikola",3.89 }

};

---

Iteracije kroz mapu c++

​U svakom ciklusu petlje se uzima sledeći par koji sadrži i ključ i vrednost(Ime učenika i prosek). Pristup ključu se ostvaruje pomoću atributa first, dok se pristup vrednosti ostvaruje pomoću atributa second.

//ispisivanje podataka smeštenih unutar mape
for(auto parKljucVrednost: prosek){

cout << parKljucVrednost.first << " " << parKljucVrednost.second << endl;

}

Slika 1: Ispisivanje elemenata u mapi-izvrsenje programa

---

Učitavanje mape c++

​Drugi način da se mapa popuni vrednostima je učitavanje sa standardnog ulaza, kada se od korisnika zatraži da unese ime učenika, kao i njegov ostvaren uspeh.
Unošenje para kluč vrednost, može se dodati u mapu na njen kraj sa funkcijom insert. Posmatrajmo sledeći kod:

//Ucitavanje para kljuc vrednost u mapu;
int n;
string ime;
double prosek;
cout << " Unesi broj ucenika" << endl;
cin >> n;
for(int i = 0; i < n; i++){

cout << "Unesi ime ucenika " << endl;
cin >> ime;
cout << "unesi prosek " << endl;
cin >> prosek;
prosekMap.insert(pair <string, double> (ime,prosek));

}
//ispisivanje podataka smeštenih unutar mape
for(auto parKljucVrednost: prosek){

cout << parKljucVrednost.first << " " << parKljucVrednost.second << endl;

}

---

Prepisivanje iz jedne mape u drugu c++

Deklariše se mapa prosekMap2 koja će imati iste elemente kao i mapa 1. Prilikom deklarisanja treba proslediti pokazivače na početak i kraj prve mape.

//prepisivanje mape
cout << "Mapa 2: "<< endl;
map < string, double>prosekMap2(prosekMap.begin(),prosekMap.end());
ispisi(prosekMap2);

​Ovde smo ispisivanje vrednosti mape premestili u posebnu funkciju ispisi, kojoj se za parametar prosleđuje pokazivač na mapu koju treba ispisati.

void ispisi(map < string, double> prosekMap){

//ispisivanje podataka smeštenih unutar mape
for(auto parKljucVrednost: prosek){

cout << parKljucVrednost.first << " " << parKljucVrednost.second << endl;

}

}

Posle pokretanja:

Slika 2: Prepisivanje elemenata iz jedne u drugu mapu-izvrsenje programa

---

Ispisivanje mape pomoću iteratora

Definišemo iterator (kursor) koji pokazuje na određen par unutar mape i može lako da se premešta kroz mapu:

map<string, double>::iterator itr;
​
Ispisivanje kroz petlju bi bilo:

void ispisi2(map < string, double> prosekMap){

//ispisivanje podataka smeštenih unutar mape
map < string, double >::iterator itr;
for(itr = prosekMap.begin(); itr !=prosekMap.end(); ++itr ){

cout << itr -> first << " " << itr -> second << endl;

}

}

---

Brisanje elemenata u mapi c++

Brisanje elemenata iz mape se može ostvariti funkcijom erase​

​Brisanje elemenata sa odrećenom vrednošću ključa

​Ako želimo da obrišemo element čiji je ključ npr vrednost imeZaBrisanje, to se može uraditi na sledeći način:

//Brisanje elemenata sa odrećenom vrednošću ključa
string imeZaBrisanje = "Nikola";
prosekMap2.erase(imeZaBrisanje);
cout << "Posle brisanja, mapa 2 izgleda " << endl;
ispisi2(prosekMap2);

---

Brisanje svih  elemenata u mapi

//Brisanje elemenata sa odrećenom vrednošću ključa
prosekMap2.clear();
cout << "Posle brisanja, komandom clear broj elemenata u mapi 2 je " << prosekMap2.size();

​Posle brisanja mapa 2 neće imati ni jedan element, tj. veličina mape je nula.

---

Pronalaženje vrednosti po kljucu c++

​Ukoliko se zna ključ, prvo se pomocu find funkcije vrati iterator koji pokazuje na onaj par ciji je ključ prosledjen funkciji. Zatim se pomoću iteratora može izvući vrednost, kao što je pokazano u sledećem kodu:

//pretraga mape
string kljuc="Mika";
map<string, double>::iterator it;
it=prosekMap.find(kljuc);
cout << endl << it -> first << " ima prosek " << it->second;

---

​Sortiranje mape po vrednosti

​Prvo treba prebaciti elemente u vector:

// Deklarisanje vektora parova iz mape
vector < pair < string, double > > A;

// Copy key-value pair from Map
// to vector of pairs
for (auto& it : prosekMap) {

A.push_back(it);

}

​Zatim se vrši sortiranje funkcijom sort

sort(A.begin(),A.end());
cout << " Posle sortiranja mapa izgleda: " << endl;
cout << "Sortiran vektor:" << endl;
for(auto & it:A)
{

cout << it.first << ": " << it.second << endl;

}

Posle pokretanja:

Slika 3: Sortiranje mape-izvrsenje programa

---

Prolazak kroz vektor sa parovima ključ-vrednost kao elementima (pair<string,int>) bi mogao da bude i na sledeći način:

sort(A.begin(),A.end());
cout << " Posle sortiranja mapa izgleda: " << endl;
cout << "Sortiran vektor:" << endl;
for(pair<string,int> par:A) {

cout << par.first << " "<< par.second << endl;

}

PRIMER SA UPOTREBOM MAPA: Pogledajte primer broj 11 sa webstrane: Kvalifikacije za okružna takmičenja

---

Neuređene mape(unordered engl. map)

Neuređene mape se koriste kada nije potrebno voditi računa o redosledu ključeva, a sa druge strane, veća je brzina pristupa pojedinim ključevima u nesortiranoj mapi.
Da bi koristili neodređene mape potrebno je uključiti sledeće zaglavlje:
Pogledajmo razlike između uređene i neuređene mape, tj. njihove prednosti i mane:

#include

map protiv unordered_map

Osobine za map:

• Implementacija: map je implementiran kao uravnoteženo binarno stablo pretraživanja (najčešće crveno-crno stablo).
• Sortiranje: Ključevi u map su uvijek sortirani u rastućem poretku.
• Kompleksnost: Operacije umetanja, brisanja i pristupa elementima imaju složenost O(log n) zbog strukture stabla.
• Redosled iteracije: Iteracija kroz map će uvek biti u sortiranom redosledu ključeva.

Kada se koristi:

• Kada je potrebno sortirano skladištenje parova ključ-vrednost.
• Kada je potrebna logaritamska vremenska složenost operacija.
• Kada je bitan redosled iteracije.

Osobine za unordered_map:

• Implementacija: unordered_map je implementiran kao heš tabela.
• Sortiranje: Ključevi u unordered_map nisu sortirani; elementi su raspoređeni na osnovu rezultata heš funkcije.
• Kompleksnost: Operacije umetanja, brisanja i pristupa elementima imaju prosečnu složenost O(1), ali u najgorem slučaju složenost može biti O(n) zbog mogućih sudara heš vrednosti.
• Redosled iteracije: Iteracija kroz unordered_map ne prati nikakav redosled ključeva.

​

Kada se koristi?

• Kada je potrebno brže skladištenje i pristup elementima (u proseku).
• Kada nije bitan redosled ključeva.
• Kada se radi sa velikim skupovima podataka i kada su sudari heš vrednosti minimalni ili dobro kontrolisani.

Primer za uređenu mapu

Tekst: Zadati 3 para za mapu, a zatim ispisati parove kluč vrednost.
Rešenje:

#include < iostream >
#include < map >

using namespace std;


int main() {

map mojaMapa;
mojaMapa[1] = "jedan";
mojaMapa[3] = "tri";
mojaMapa[2] = "dva";
for (const auto& par: mojaMapa) {

cout << par.first << ": " << par.second << endl;

}
return 0;

}

Izlaz:

1: jedan
2: dva
3: tri

Primer za neuređenu mapu

Tekst: Zadati 3 para za neuređenu mapu, a zatim ispisati parove kluč vrednost.
Rešenje:

#include < iostream >
#include < unordered_map >

using namespace std;

int main() {

unordered_map< int, string > mojaNeuređenaMapa;
mojaNeuređenaMapa[1] = "jedan";
mojaNeuređenaMapa[3] = "tri";
mojaNeuređenaMapa[2] = "dva";
for (const auto& par: mojaNeuređenaMapa) {

cout << par.first << ": " << par.second << endl;

}
return 0;

}