Choose jour language!

---

|

REČNIK PODATAKA - MAPE U C++

Sadržaj stranice

Dobrodošli na stranicu posvećenu mapama u C++! Ova stranica nudi sve ključne informacije, primere koda i praktične savete o radu sa mapama. Pomoću tabele sadržaja možete brzo preskočiti na interesantne sekcije i pronaći sadržaj koji vas zanima.

• Uvod
• Deklaracija i Inicijalizacija
• Iteracija i Pristup Elementima
• Testiranje koda
• Učitavanje elemenata u mapu
• Prepisivanje Elementima iz jedne mape u drugu
• Brisanje Elemenata
• Pronalaženje Elementa u mapi
• Sortiranje Mapi
• Uređene i neuređene mape
• Primeri praktične upotrebe
• Dodaci

Uvod

Mape u C++ su kolekcije podataka koje čuvaju podatke čijim vrednostima se pristupa pomoću jedinstvenog ključa. One predstavljaju implementaciju koncepta "rečnika" (dictionary) u kome se svaki ključ povezuje sa odgovarajućom vrednošću. Koristeći mape, programeri mogu efikasno organizovati i pretraživati podatke, jer pristup elementima preko ključeva omogućava brže operacije nego kod sekvencijalnih kontejnera.

Osim toga, mape se koriste u mnogim aplikacijama gde je potreban brz pristup podacima, kao što su baze podataka, keširanje rezultata i mnogi algoritmi. Standardna C++ biblioteka nudi std::map, koji je implementiran kao balansirano stablo (npr. crveno-crno stablo), što garantuje vremensku složenost od O(log n) za osnovne operacije poput umetanja, brisanja i pretrage.

Mapa se deklariše na sledeći način:

std::map<tip_ključa, tip_vrednosti> naziv_mape;
    

U narednim sekcijama, detaljno ćemo objasniti kako se mape koriste, kako se manipuliše njihovim elementima, te kako se vrši iteracija, brisanje i sortiranje podataka.

Deklaracija i inicijalizacija 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 utvrditi koliko je učenika postiglo uspeh iznad prosečnog.

Rešenje: Ovaj primer ćemo rešiti upotrebom mapa, tako što će se za ključ koristiti ime učenika, a kao vrednost unutar mape smestiti njihov uspeh.

Da bi se koristile mape u C++ unutar fajla, mora se uključiti datoteka zaglavlja map:

#include <map>
    

Zatim je potrebno deklarisati mapu:

std::map<string, double> prosek;
    

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

Inicijalizacija mape:

Jedan od načina da mapu popunimo sa vrednostima je da je inicijalizujemo, š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}
};
    

Iteracija i Pristup Elementima

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){
    std::cout << parKljucVrednost.first << " " 
                << parKljucVrednost.second << std::endl;
}
    

Slika 1: Ispisivanje elemenata u mapi-izvrsenje programa

Vrste iteracija i štampanje elemenata mape

U C++ postoje dva osnovna načina za iteraciju kroz mapu: korišćenjem opsežne petlje (for) i upotrebom iteratora. Oba pristupa imaju svoje prednosti i primene, a u nastavku su prikazane njihove karakteristike i preporuke za upotrebu.

1. Opsežna for petlja (range-based for loop)

Ovaj pristup je intuitivan i čini kod preglednijim, naročito kada radite sa mapom koja ne zahteva modifikaciju elemenata tokom iteracije.

std::map<string, int> ucesnici = { {"Marko", 3}, {"Ana", 2}, {"Ivan", 1} };
for (const auto& par : ucesnici) {
    std::cout << par.first << ": " << par.second << std::endl;
}
    

Prednosti:

• Jednostavan i lak za razumevanje.
• Efikasnost: Koristi const auto& da izbegne kopiranje parova.
• Pogodan za slučajeve kada nije potrebna direktna kontrola nad elementima mape.

Nedostaci:

• Manjak fleksibilnosti kada je potrebna modifikacija elemenata ili specifično pozicioniranje.

2. Iteratori

Iteratori omogućavaju veću fleksibilnost jer pružaju direktan pristup elementima, što može biti korisno kada je potrebno menjati sadržaj mape ili kontrolisati tok iteracije.

std::map<string, int> ucesnici = { {"Marko", 3}, {"Ana", 2}, {"Ivan", 1} };
for (auto it = ucesnici.begin(); it != ucesnici.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}
    

Prednosti:

• Omogućava promenu vrednosti elemenata tokom iteracije.
• Omogućava pristup složenim operacijama, poput brisanja trenutnog elementa (it = ucesnici.erase(it)).

Nedostaci:

• Kod može postati manje čitljiv, posebno za početnike.
• Složeniji pristup u poređenju sa opsežnom petljom.

Poređenje performansi:

Za iteraciju kroz sve elemente mape, oba pristupa su podjednako efikasna jer imaju vremensku složenost O(n). Opsežna for petlja je često pogodnija kada radite samo sa očitavanjem elemenata, dok iteratori pružaju više fleksibilnosti za modifikacije.

Preporuke za upotrebu:

• Koristite opsežnu petlju (for) kada vam je potrebna jednostavna iteracija kroz sve elemente bez izmene sadržaja.
• Koristite iteratore kada je potrebno menjati vrednosti elemenata, preskakati određene elemente ili brisati elemente iz mape tokom iteracije.

Testirajte svoj kod ovde

// Ovde pišite C++ kod...

Unesite podatke za program: Run Code

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 ključ-vrednost može se dodati u mapu na njen kraj pomoću funkcije insert. Posmatrajmo sledeći kod:

// Učitavanje para ključ-vrednost u mapu;
int n;
string ime;
double prosek;
std::cout << "Unesi broj učenika" << std::endl;
std::cin >> n;
for(int i = 0; i < n; i++){
    std::cout << "Unesi ime učenika" << std::endl;
    std::cin >> ime;
    std::cout << "Unesi prosek" << std::endl;
    std::cin >> prosek;
    prosekMap.insert(pair<string, double>(ime, prosek));
}
// Ispisivanje podataka smeštenih unutar mape
for(auto parKljucVrednost : prosekMap){
    std::cout << parKljucVrednost.first << " "
                << parKljucVrednost.second << std::endl;
}
    

Unos podataka u mapu sa proverom da li vrednost ključa već postoji u mapi – unos podataka u mapu sa operatorom []

Primer:

#include <iostream>
#include <map>
#include <string>
using namespace std;
  
int main() {
    map<string, int> ucesnici;
  
    // Primer unosa učesnika
    string unosi[] = {"Marko", "Ana", "Marko", "Ivan", "Ana"};
    for (const string& ime : unosi) {
        ucesnici[ime]++; // Povećava broj učešća (podrazumevana vrednost za nove ključeve je 0)
    }
  
    // Ispis mape
    for (const auto& par : ucesnici) {
        std::cout << "Učesnik: " << par.first
                  << ", Broj učešća: " << par.second
                  << std::endl;
    }
  
    return 0;
}
    

Objašnjenje:
Operator [] – Ako ključ (npr. "Marko") ne postoji u mapi, kreira ga sa podrazumevanom vrednošću (0 za int). Zatim se vrednost povećava za 1.

Napomena: Ako koristimo:
ucesnici["NoviUcesnik"]++;
To dodaje "NoviUcesnik" sa vrednošću 1, čak i ako nije bio prethodno unet.
Da bismo to izbegli, koristimo find:
auto it = ucesnici.find("NoviUcesnik");
if (it != ucesnici.end()) {
it->second++;
} else {
std::cout << "Učesnik nije pronađen!" << std::endl;
}

Napomena za korisnike

Ako ne želite da u C++ kodu stalno pišete prefiks std:: ispred funkcija, tipova i ostalih članova standardne biblioteke, možete uneti naredbu:

 using namespace  std;

Ova naredba govori prevodiocu da u daljem delu koda automatski koristi std prostor imena, čime se eliminiše potreba za stalnim navođenjem prefiksa.

Prednosti:

• Jednostavost i preglednost: Skraćuje kod i olakšava pisanje, što je korisno u manjim projektima, primerima i obrazovnim situacijama.
• Brže pisanje koda: Nema potrebe za stalnim navođenjem std::, što može ubrzati razvoj i testiranje jednostavnih programa.

Nedostaci:

• Mogući konflikti imena: U većim projektima ili prilikom korišćenja više biblioteka, using namespace std; može dovesti do sukoba imena, jer različite biblioteke mogu imati funkcije ili tipove sa istim imenima.
• Nedovoljna eksplicitnost: Kada se koristi using namespace std;, nije odmah jasno poreklo pojedinih simbola, što može otežati razumevanje koda pri njegovom održavanju ili pri radu u timovima.
• Profesionalni standardi: U profesionalnim projektima se često preporučuje eksplicitno navođenje std:: kako bi se jasno definisalo poreklo svakog simbola, što povećava čitljivost i održivost koda.

Zaključno, korišćenje using namespace std; je praktično za manje projekte i primere, ali se u većim ili profesionalnim kodnim bazama preporučuje eksplicitno navođenje std:: prefiksa.

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

Prepisivanje iz jedne mape u drugu

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: prosekMap){
        cout << parKljucVrednost.first << " " << parKljucVrednost.second << endl;
    }
}
        

Ako kombinujemo dodeljivanje mape, unos novih parova u mapu i konačno kopiranje sadržaja sa jedne mape na drugu, kompletan kod bi bio:

Rad sa C++ mapom: Ubacivanje i Kopiranje

Ovaj primer demonstrira kako da kreirate mapu za čuvanje imena studenata i njihovih prosečnih ocena, ubacite nove unose sa korisničkim inputom, kopirate mapu i odštampate njen sadržaj.

#include <iostream>
#include <map>
#include <string>
using namespace std;

// Funkcija za štampanje sadržaja mape
void printMap(map<string, double> prosekMapa)
{
    // Korišćenje iteratora za prolazak kroz mapu
    map<string, double>::iterator iter;
    for(iter = prosekMapa.begin(); iter != prosekMapa.end(); ++iter)
    {
        // Štampanje ključa i vrednosti (ime studenta i prosečna ocena)
        cout << iter -> first << " " << iter -> second << endl;
    }
}

int main()
{
    // Kreiranje mape za čuvanje imena studenata i njihovih prosečnih ocena
    map<string, double> prosekMapa;
    prosekMapa =
    {
        {"Mihailo", 4.52},
        {"Milica", 4.78},
        {"Nikola", 3.89}
    };

    // Promenljiva za broj studenata koji se unose
    int n;
    string imeStudenta;
    double prosek;

    // Upit korisniku da unese broj studenata
    cout << "Unesite broj studenata" << endl;
    cin >> n;

    // Petlja za unos imena i prosečne ocene svakog studenta
    for(int i = 0; i < n; i++)
    {
        cout << "Unesite ime studenta" << endl;
        cin >> imeStudenta;
        cout << "Unesite prosečnu ocenu" << endl;
        cin >> prosek;

        // Ubacivanje novog imena studenta i ocene u mapu
        prosekMapa.insert(pair<string, double>(imeStudenta, prosek));
    }

    // Kreiranje kopije originalne mape (prosekMapa)
    cout << "Mapa 2: " << endl;
    map<string, double> prosekMapa2(prosekMapa.begin(), prosekMapa.end());

    // Štampanje kopirane mape
    printMap(prosekMapa2);

    return 0;
}
    

Posle pokretanja:

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

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 svih elemenata u mapi
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.

Brisanje elemenata u mapama: Preporuke i oprez

Funkcija erase omogućava brisanje elemenata iz mape pomoću ključa, iteratora ili opsega iteratora. Međutim, prilikom korišćenja ove funkcije treba obratiti pažnju na nekoliko potencijalnih grešaka:

1. Brisanje nepostojećeg ključa

Ako pokušate da obrišete ključ koji ne postoji u mapi, erase neće izazvati grešku, ali neće imati efekta. Kako biste izbegli nepotrebne operacije, preporučuje se prethodna provera prisustva ključa:

auto it = mapa.find(kljuc);
if (it != mapa.end()) {
    mapa.erase(it);
}
        

2. Brisanje tokom iteracije

Kada brišete elemente dok iterirate kroz mapu, upotrebite povratnu vrednost erase (novi iterator koji pokazuje na sledeći element) kako biste izbegli invalidaciju iteratora:

for (auto it = mapa.begin(); it != mapa.end(); ) {
    if (uslov) {
        it = mapa.erase(it);
    } else {
        ++it;
    }
}
        

3. Brisanje više elemenata (opsežno brisanje)

Kada želite da obrišete sve elemente u datom opsegu, koristite erase sa opsegom iteratora:

mapa.erase(mapa.begin(), mapa.find("kljucevi_do_ovde"));
        

4. Uticaj na performanse

Funkcija erase ima složenost O(log N) za pojedinačne elemente, dok brisanje celog opsega može biti brže jer se operacije optimizuju za veće skupove podataka. Preporučuje se da birate pristup u zavisnosti od broja elemenata za brisanje.

5. Praktični saveti

• Kada koristiti find pre erase: Kod kritičnih sistema ili gde postoji neizvesnost o prisustvu ključa.
• Kada koristiti direktno erase: Kada ste sigurni da ključ postoji ili u jednostavnim slučajevima.

6. Primer greške

Ukoliko koristite iterator koji je postao nevalidan nakon brisanja:

auto it = mapa.erase(mapa.begin());
cout << it->first; // Ispravno, iterator je validan.
        

Pronalaženje vrednosti u mapi

Pronalaženje vrednosti po ključu

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

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

Pronalaženje elemenata po vrednosti

Ako želimo da pronađemo element u mapi na osnovu vrednosti (ne ključa), potrebno je iterirati kroz celu mapu i proveriti da li neka vrednost odgovara zadatoj:

double trazenaVrednost = 9.5;
bool pronadjen = false;

for (auto it : prosekMap) {
    if (it.second == trazenaVrednost) {
        cout << "Pronađen: " << it.first << " sa prosekom " << it.second << endl;
        pronadjen = true;
        break;
    }
}

if (!pronadjen) {
    cout << "Nema studenta sa zadatim prosekom!" << endl;
}
        

Ova metoda pretražuje mapu po vrednostima, ali zbog iteracije kroz sve elemente ima vremensku složenost O(n).

Sortiranje mape po vrednosti

Prvo treba prebaciti elemente u vector:

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

// Kopiranje parova ključ-vrednost iz mape u vector parova
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 ovako: " << endl;
cout << "Sortiran vector:" << endl;
for(auto& it : A) {
    cout << it.first << ": " << it.second << endl;
}
        

Ako objedinimo prethodne delove koda u jednu celinu, koja treba da zada početnu mapu proseka studenata, doda još n studenata i njihove proseke, obriše studenta pod nazivom Nickolas, prepiše podatke u novu mapu i na kraju sortira tu mapu po vrednosti i odštampa je, onda bi to izgledalo kao u nastavku:

Primer objedinjene koda

U ovom delu objedinjavamo prethodne delove koda u jedan kompletan program. Program demonstrira kako da kreirate mapu za čuvanje imena studenata i njihovih prosečnih ocena, da dodate nove unose putem korisničkog unosa, obrišete određeni element iz mape, i na kraju sortirate podatke po prosečnoj oceni koristeći vektor i prilagođeni komparator.

#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// Funkcija za ispis sadržaja mape
void printMap(const map<string, double>& averageMap)
{
    for (const auto& iter : averageMap)
    {
        cout << iter.first << " " << iter.second << endl;
    }
}

// Prilagođeni komparator za sortiranje parova po vrednosti (drugom elementu para) u rastućem redosledu
bool compareByValue(const pair<string, double>& a, 
                      const pair<string, double>& b)
{
    return a.second < b.second;
}

int main()
{
    // Kreiranje mape za čuvanje imena studenata i njihovih prosečnih ocena
    map<string, double> averageMap =
    {
        {"Michael", 4.52},
        {"Milica", 4.78},
        {"Nickolas", 3.89}
    };

    // Korisnički unos dodatnih studenata
    int n;
    string studentName;
    double avg;

    cout << "Enter the number of students" << endl;
    cin >> n;

    for(int i = 0; i < n; i++)
    {
        cout << "Enter student name" << endl;
        cin >> studentName;
        cout << "Enter average score" << endl;
        cin >> avg;

        // Dodavanje imena studenta i prosečne ocene u mapu
        averageMap[studentName] = avg;
    }

    // Kreiranje kopije mape i brisanje određenog elementa
    map<string, double> averageMap2(averageMap.begin(), averageMap.end());
    string nameToDelete = "Nickolas";
    averageMap2.erase(nameToDelete);

    cout << "After deletion, map 2 looks like: " << endl;
    printMap(averageMap2);

    // Kopiranje elemenata mape u vektor parova radi sortiranja
    vector<pair<string, double>> A(averageMap2.begin(), averageMap2.end());

    // Sortiranje vektora po vrednostima (prosečnim ocenama) u rastućem redosledu koristeći prilagođeni komparator
    sort(A.begin(), A.end(), compareByValue);

    // Ispis sortiranih imena studenata i njihovih ocena
    cout << "Sorted vector (by average score):" << endl;
    for(const auto& it : A)
    {
        cout << it.first << ": " << it.second << endl;
    }

    return 0;
}
    

Dodatno objašnjenje:
Program započinje uključivanjem potrebnih zaglavlja i postavljanjem std prostora imena. Definisane su dve pomoćne funkcije:

• printMap – Ispisuje svaki par ključ-vrednost iz mape.
• compareByValue – Prilagođeni komparator koji se koristi sa funkcijom sort kako bi se parovi sortirali u rastućem redosledu na osnovu vrednosti.

U funkciji main kreira se početna mapa sa imenima studenata i prosečnim ocenama. Nakon toga, program traži od korisnika da unese dodatne podatke o studentima, koji se dodaju u mapu. Napravlja se kopija mape, iz koje se briše određeni unos ("Nickolas"). Preostali elementi mape se zatim kopiraju u vektor, koji se sortira u rastućem redosledu po prosečnoj oceni koristeći prilagođeni komparator. Na kraju, sortirani podaci se ispisuju na konzoli.

Posle izvršenja:

Slika 3: Sortiranje mape-izvrsenje programa

---

Prolazak kroz vektor sa parovima ključ-vrednost kao elementima (pair<string,int>) može 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;
}
        

Sortiranje mape po vrednosti u opadajućem poretku
Primer: Zapisani su rezultati 4 četvrtfinalna meča, 2 polufinalna meča i finalnog meča nokaut faze turnira (ukupno 7 mečeva). Rezultati dati na ulazu nisu sortirani (na primer, poslednji red na ulazu ne znači nužno da je taj meč poslednji odigran). Odrediti pobednika i drugoplasiranog na turniru.

Pretpostavimo da su u mapu već uneti sortirani podaci. U C++, pošto std::map ne podržava direktno sortiranje po vrednosti (jer se ona sortira po ključu), možete prebaciti parove iz mape u vektor, sortirati vektor po vrednosti, i zatim ispisati prva dva učesnika sa najvećim brojem učešća. Evo primera kako to može da se uradi:

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    map<string, int> ucesnici = {
        {"Petar", 5},
        {"Ana", 8},
        {"Marko", 3},
        {"Jovana", 7}
    };

    // Prebacivanje parova u vektor
    vector<pair<string, int>> ucesniciVektor(ucesnici.begin(), ucesnici.end());

    // Sortiranje vektora po vrednosti, opadajuće
    sort(ucesniciVektor.begin(), ucesniciVektor.end(), 
         [](const pair<string, int> &a, const pair<string, int> &b) {
             return a.second > b.second; // Sortira opadajuće po broju učešća
         });

    // Ispis prvih dva učesnika sa najvećim brojem učešća
    cout << "Prva dva učesnika sa najvećim brojem učešća su:\n";
    for (int i = 0; i < min(2, (int)ucesniciVektor.size()); ++i) {
        cout << ucesniciVektor[i].first << " (" 
             << ucesniciVektor[i].second << " učešća)" << endl;
    }

    return 0;
}
        

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

Sortiranje mape prema vrednostima – nastavak
Standardna std::map u C++ uvek održava redosled elemenata prema ključu. Ovo je korisno kada je sortiranje prema ključevima poželjno, ali ako želite da mapu sortirate prema vrednostima, neophodno je koristiti alternativne pristupe jer std::map ne podržava direktno sortiranje prema vrednostima.

Sortiranje prebacivanjem u vektor parova
Jedan od najčešće korišćenih pristupa je prebacivanje elemenata mape u vektor parova i zatim korišćenje std::sort sa prilagođenim komparatorom:

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    map ucesnici = {{"Ana", 5}, {"Marko", 3}, {"Ivan", 8}};

    // Prebacivanje u vektor
    vector> vektor(ucesnici.begin(), ucesnici.end());

    // Sortiranje prema vrednostima
    sort(vektor.begin(), vektor.end(),
        [](const pair& a, const pair& b) {
            return a.second > b.second; // Opadajući redosled
        });

    // Ispis sortiranih elemenata
    for (const auto& par : vektor) {
        cout << par.first << ": " << par.second << endl;
    }

    return 0;
}
        

Korisni saveti:
Performanse: Ovaj pristup je efikasan za manje skupove podataka, ali za veće mape može biti sporiji jer se celokupan sadržaj kopira u vektor.
Stabilnost: Funkcija std::sort nije stabilna, što znači da elementi sa istim vrednostima neće nužno zadržati originalni redosled.
Alternativa: Korišćenje std::multimap – ako su vrednosti ključne za sortiranje, razmislite o korišćenju std::multimap, koja može sadržati duplikate ključeva i održavati redosled prema ključu.

#include <iostream>
#include <map>
using namespace std;

int main() {
    multimap obrnuto;

    // Pretvaranje iz mape
    map ucesnici = {{"Ana", 5}, {"Marko", 3}, {"Ivan", 8}};
    for (const auto& par : ucesnici) {
        obrnuto.insert({par.second, par.first});
    }

    // Ispis sortiranih elemenata
    for (const auto& par : obrnuto) {
        cout << par.second << ": " << par.first << endl;
    }

    return 0;
}
        

Napomena o prilagođenim komparatorima:
Ako želite da direktno koristite std::map sa sortiranim vrednostima, možete koristiti prilagođeni komparator, ali to zahteva dodatno praćenje parova ključeva i vrednosti, što često nije praktično.

Preporuka:
Za dinamične strukture: Koristite vektore ili std::multimap.
Za fiksne strukture: Prebacivanje u vektor i sortiranje je jednostavniji pristup.

Ova proširena sekcija pruža korisnicima dodatne uvide o sortiranju prema vrednostima i alternativama koje bolje odgovaraju različitim potrebama.

Uređene i neuređene mape

Neuređene mape (unordered 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:

#include <unordered_map>

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

Zadatak: Zadati 3 para za mapu, a zatim ispisati parove ključ-vrednost.

#include <iostream>
#include <map>

using namespace std;

int main() {
    map<int, string> 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

Zadatak: Zadati 3 para za neuređenu mapu, a zatim ispisati parove ključ-vrednost.

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

Primeri korišćenja u praksi

Mape u C++ su korisne za rešavanje širokog spektra realnih problema gde je potrebno uspostaviti vezu između ključa i vrednosti.

1. Brojanje frekvencija reči u tekstu

Jedan od klasičnih primera primene mape je brojanje koliko se puta svaka reč pojavljuje u tekstu:

#include <iostream>
#include <map>
#include <string>
#include <sstream>

using namespace std;

int main() {
    string tekst = "ovo je primer teksta u kojem brojimo reci reci su kljucne";
    map<string, int> frekvencije;

    // Podela teksta na reči
    stringstream ss(tekst);
    string rec;
    while (ss >> rec) {
        frekvencije[rec]++;
    }

    // Ispis rezultata
    for (const auto& par : frekvencije) {
        cout << "Reč: " << par.first << ", Pojavljivanja: " << par.second << endl;
    }
    
    return 0;
}
    

Praktična primena: Ovaj primer može biti osnova za implementaciju jednostavnog analizatora teksta, npr. za prebrojavanje ključnih reči u dokumentima.

2. Praćenje ocena studenata

Mapa se može koristiti za praćenje proseka ocena studenata:

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() {
    map<string, double> studenti;
    studenti["Marko"] = 8.5;
    studenti["Ana"] = 9.2;
    studenti["Ivan"] = 7.8;

    // Ispis proseka ocena
    for (const auto& par : studenti) {
        cout << "Student: " << par.first << ", Prosek: " << par.second << endl;
    }
    
    return 0;
}
    

Praktična primena: Ovaj pristup može se koristiti u sistemima za upravljanje školama ili univerzitetima.

3. Implementacija telefonskog imenika

Mapa omogućava jednostavno kreiranje telefonskog imenika gde se imena mapiraju na brojeve telefona:

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() {
    map<string, string> imenik;
    imenik["Marko"] = "0641234567";
    imenik["Ana"] = "0659876543";

    // Pretraga u imeniku
    string trazenoIme = "Ana";
    if (imenik.find(trazenoIme) != imenik.end()) {
        cout << "Broj telefona za " << trazenoIme << ": " << imenik[trazenoIme] << endl;
    } else {
        cout << "Kontakt nije pronađen." << endl;
    }
    
    return 0;
}
    

Praktična primena: Ovakva struktura može se koristiti u aplikacijama za upravljanje kontaktima.

Predlozi za dodatna proširenja

• Dodati primere za složenije aplikacije, poput implementacije rang lista, sistema za glasanje ili upravljanje inventarom.
• Uključiti vizuelne prikaze podataka pomoću biblioteka za grafiku ili izveštaje (npr. sortirane rang-liste ili grafikone).

Dodaci: Napredne funkcije i poređenje sa unordered_map

Funkcija emplace

Funkcija emplace omogućava umetanje elemenata u mapu direktno na njihovoj lokaciji u memoriji, čime se često smanjuju troškovi kopiranja u poređenju sa insert. To može dovesti do boljih performansi, posebno kod umetanja složenijih tipova podataka. Na primer:

#include <iostream>

#include <map>


using namespace std;


int main() {

    map<string, int> ucesnici;

    
    // Umetanje pomoću emplace

    ucesnici.emplace("Marko", 5);

    ucesnici.emplace("Ana", 3);

    
    for (const auto& par : ucesnici) {

        cout << "Ucesnik: " << par.first << ", Broj ucesca: " << par.second << endl;

    }

    
    return 0;

}

        

Razlika u odnosu na insert:

Dok insert prima već kreirani par (ili kopiju), emplace konstruiše objekat direktno na odgovarajućoj lokaciji, čime se izbegavaju dodatne operacije kopiranja ili premještanja.

Poređenje std::map i std::unordered_map

• std::map:
  • Implementacija zasnovana na uravnoteženom binarnom stablu (npr. Red-Black Tree).
  • Održava elemente sortiranim po ključu.
  • Operacije umetanja, pretrage i brisanja imaju logaritamsku složenost O(log n).
  • Pogodno kada je redosled elemenata važan.
• std::unordered_map:
  • Implementacija zasnovana na hash tabeli.
  • Elementi nisu sortirani.
  • Operacije umetanja, pretrage i brisanja imaju prosečnu složenost O(1), ali mogu biti O(n) u najgorem slučaju.
  • Pogodno kada je performansa pretrage prioritet, a redosled nije bitan.

Kada koristiti koju?

• std::map: Kada je redosled bitan ili kada treba iterirati kroz elemente u sortiranom poretku.
• std::unordered_map: Kada je potrebna brza pretraga, a redosled nije važan.

---

Prethodno
​|< Dinamčki niz-vector

Sledeće
​​​Dvodimenzionalni nizovi - matrice >|

---