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

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

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.

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 mapefor(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česnikastring 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 mapefor (const auto& par : ucesnici) {
        std::cout << "Učesnik: " << par.first
                  << ", Broj učešća: " << par.second
                  << std::endl;
    }
  
    return0;
}
    

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

 using namespace  std;