Uvod u vektore

Vektori predstavljaju jednu od najvažnijih struktura podataka u modernom programiranju. Oni omogućavaju dinamičko čuvanje elemenata istog tipa, što znači da se veličina vektora može menjati tokom izvršavanja programa. Za razliku od statičkih nizova, vektori automatski upravljaju memorijom i nude jednostavan interfejs za dodavanje, brisanje i pristup elementima.

U ovoj lekciji naučićemo osnovne pojmove vezane za vektore, kako funkcionišu, zašto su efikasni i kako se koriste u različitim algoritmima. Za praktične primere u jeziku C++, pogledaj i detaljnu lekciju Dinamički niz (std::vector) u C++.

Osnovni koncept vektora

Vektor je zapravo dinamički niz elemenata istog tipa. On omogućava da se broj elemenata automatski menja u skladu sa potrebama programa, bez ručnog upravljanja memorijom.

• Vektori pripadaju standardnoj biblioteci jezika C++ (STL – Standard Template Library).
• Automatski proširuju kapacitet kada se doda više elemenata nego što je trenutno predviđeno.
• Elementima se pristupa preko indeksa, kao i kod običnog niza.

Osnovna sintaksa u C++

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

int main() {
    // Deklaracija vektora celih brojeva
    vector<int> brojevi;

    // Dodavanje elemenata
    brojevi.push_back(10);
    brojevi.push_back(20);
    brojevi.push_back(30);

    // Ispis elemenata
    for (int i = 0; i < brojevi.size(); i++) {
        cout << brojevi[i] << " ";
    }

    cout << endl;
    return 0;
}

Ovaj primer prikazuje kako se vektor koristi kao dinamički niz. Korišćenjem push_back() dodajemo elemente, dok size() vraća trenutni broj elemenata u vektoru.

Iteracija kroz vektor

Vektori se mogu prolaziti pomoću petlji i iteratora. U modernom C++-u često se koristi range-based for petlja, koja je kraća i čitljivija.

vector<int> brojevi = {1, 2, 3, 4, 5};

// Range-based for petlja
for (int x : brojevi) {
    cout << x << " ";
}

Kapacitet i performanse

Svaki vektor ima svoj size (trenutni broj elemenata) i capacity (rezervisanu memoriju). Kada se kapacitet popuni, vektor automatski alocira više memorije — obično duplo od trenutnog kapaciteta. Ova tehnika omogućava brzo dodavanje elemenata uz minimalan broj realokacija.

• reserve(n) — unapred rezerviše memoriju za n elemenata.
• shrink_to_fit() — smanjuje kapacitet na stvarnu veličinu.

Napredne operacije

Pored osnovnih operacija dodavanja i pristupa elementima, vektor nudi i napredne funkcije:

• insert() — ubacuje element ili niz elemenata na određenu poziciju.
• erase() — briše element ili opseg elemenata.
• clear() — briše sve elemente iz vektora.

Primer: Dinamičko čitanje podataka

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

int main() {
    vector<int> brojevi;
    int n;
    cout << "Unesi brojeve (0 za kraj): ";
    while (cin >> n && n != 0) {
        brojevi.push_back(n);
    }

    cout << "Ukupno uneto: " << brojevi.size() << " brojeva." << endl;
    return 0;
}

Ovaj primer ilustruje fleksibilnost vektora — korisnik ne mora unapred znati koliko će podataka uneti.

Primenjeni primeri u algoritmima

• Dinamičko skladištenje elemenata tokom izvršavanja algoritma (npr. kod generisanja kombinacija ili permutacija).
• Implementacija steka, reda, grafa ili matrice pomoću vektora.
• Manipulacija nizovima promenljive dužine u takmičarskim zadacima.

Zadaci za vežbu

• Napisati program koji učitava N brojeva i ispisuje njihov zbir i aritmetičku sredinu.
• Napraviti funkciju koja vraća najveći element vektora.
• Napraviti funkciju koja obrće redosled elemenata vektora.

Zaključak

Vektori su osnovna struktura podataka koja omogućava jednostavan, siguran i efikasan rad sa nizovima promenljive dužine. Zahvaljujući automatskom upravljanju memorijom i bogatoj funkcionalnosti, oni su standardan alat u modernom programiranju i u osnovi mnogih algoritama i struktura podataka.

Brzi pregled: najčešće metode std::vector

Donja tabela sadrži osnovne metode, kratak opis i mali primer upotrebe — idealno za brzo ponavljanje.

std::vector v; // prazan vektor

v.push_back(5); // v: {5}

v.pop_back(); // uklanja poslednji element

std::cout << v.size();

v.reserve(100); std::cout<

v.reserve(50); // efikasnije dodavanje

v.resize(3); // v ima 3 elementa

v.clear(); // v.size() == 0

if (v.empty()) std::cout<<"prazan";

v[0] = 1; int x = v.at(0);

for(auto x : v) std::cout<

v.insert(v.begin()+1, 42);

v.erase(v.begin()+2);

v.emplace_back(1); // kao push_back, ali efikasnije

v.shrink_to_fit();

int* p = v.data();

Savet za učenike: ako očekuješ veliki broj umetanja, koristi reserve(n) pre dodavanja; ako ti je često potrebno umetanje/brisanje u sredini, razmisli o std::list ili std::deque.

Zadaci za vežbu

U nastavku su dati jednostavni zadaci koji pomažu učenicima da primene stečeno znanje o vektorima u C++-u. Preporučuje se da svaki zadatak samostalno pokušate da rešite pre nego što pogledate primer rešenja.

Zadatak 1: Unos i ispis elemenata vektora

Napisati program koji unosi n celih brojeva u vektor i zatim ih ispisuje na ekranu.

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

int main() {
    int n;
    cout << "Unesite broj elemenata: ";
    cin >> n;

    vector<int> brojevi(n);
    cout << "Unesite elemente vektora:\n";
    for (int i = 0; i < n; i++) {
        cin >> brojevi[i];
    }

    cout << "Uneti elementi su: ";
    for (int x : brojevi) {
        cout << x << " ";
    }
    return 0;
}
  

Zadatak 2: Pronalaženje najvećeg elementa

Korišćenjem metode max_element() iz biblioteke <algorithm> pronaći najveći element u vektoru.

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

int main() {
    vector<int> brojevi = {12, 45, 7, 33, 89, 21};
    int maksimum = *max_element(brojevi.begin(), brojevi.end());
    cout << "Najveći element u vektoru je: " << maksimum;
    return 0;
}
  

Zadatak 3: Sabiranje elemenata vektora

Koristeći petlju ili funkciju accumulate() iz biblioteke <numeric>, izračunati sumu svih elemenata vektora.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main() {
    vector<int> brojevi = {5, 10, 15, 20};
    int suma = accumulate(brojevi.begin(), brojevi.end(), 0);
    cout << "Suma svih elemenata vektora je: " << suma;
    return 0;
}
  

Zadatak 4: Brisanje određenog elementa

Izbrisati sve pojave broja 10 iz vektora koristeći metodu erase() i algoritam remove().

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

int main() {
    vector<int> brojevi = {10, 20, 10, 30, 40, 10};
    brojevi.erase(remove(brojevi.begin(), brojevi.end(), 10), brojevi.end());

    cout << "Vektor nakon brisanja: ";
    for (int x : brojevi)
        cout << x << " ";
    return 0;
}
  

Napomena: Ovi zadaci su odlična vežba za razumevanje osnovnih operacija sa vektorima — unos, ispis, pronalaženje maksimuma, sabiranje elemenata i brisanje određenih vrednosti.

Vektori u drugim programskim jezicima

Iako je pojam vektora najpoznatiji u C++ jeziku kroz klasu std::vector, sličan koncept postoji i u drugim jezicima, samo pod različitim imenima.

• C#: koristi listu (List<T>) koja funkcioniše gotovo isto kao vektor u C++.
• Python: koristi dinamičke liste (list) koje automatski rastu i smanjuju se po potrebi.
• Java: koristi klase ArrayList i Vector, koje omogućavaju rad sa promenljivim brojem elemenata.

Suština je ista: dinamički niz koji se automatski proširuje i olakšava rad sa skupovima podataka nepoznate veličine.

Primer u C# jeziku

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<int> brojevi = new List<int>();

        brojevi.Add(10);
        brojevi.Add(20);
        brojevi.Add(30);

        foreach (int x in brojevi)
        {
            Console.Write(x + " ");
        }
    }
}

Klasa List<T> u C# jeziku ima iste osnovne operacije kao i std::vector u C++: dodavanje (Add), uklanjanje (Remove), pristup elementima i dinamičko proširenje.

Analiza performansi vektora

Razumevanje performansi vektora je ključno prilikom pisanja efikasnih algoritama. Dodavanje elementa na kraj vektora ima prosečnu složenost O(1), dok umetanje na početak ili u sredinu ima složenost O(n) zbog pomeranja elemenata.

Najvažnije karakteristike performansi:

• Pristup elementima:O(1)
• Dodavanje na kraj:amortizovano O(1)
• Umetanje / brisanje u sredini:O(n)

Zato su vektori odličan izbor za strukture podataka gde se elementi često dodaju na kraj, ali nisu idealni za česta umetanja u sredinu.

Kombinovanje vektora sa drugim strukturama

Vektori često čine osnovu za složenije strukture podataka, kao što su:

• Matrice: Vektor vektora (npr. vector<vector<int>> u C++) predstavlja dvodimenzionalni niz.
• Grafovi: Reprezentacija grafa pomoću liste susedstva — vektor gde svaki element sadrži listu čvorova povezanih sa datim čvorom.
• Redovi i stekovi: Mogu se jednostavno implementirati pomoću vektora i funkcija push_back() i pop_back().

// Primer matrice kao vektora vektora
vector<vector<int>> matrica(3, vector<int>(3, 0));
matrica[1][2] = 5;

Ovakva fleksibilnost čini vektor jednom od najuniverzalnijih struktura podataka u programiranju.

Zaključak i dalji koraci

Vektori su polazna tačka za razumevanje drugih dinamičkih struktura podataka kao što su liste, redovi i mape. U nastavku oblasti „Strukture podataka“ biće prikazane i druge strukture koje se često koriste zajedno sa vektorima, uključujući:

• Povezane liste
• Stekove i redove
• Skupove i mape

Za detaljnu implementaciju vektora u jeziku C++ pogledaj: Dinamički niz (std::vector) u C++.

Zadaci za vežbu

U nastavku su dati jednostavni zadaci koji pomažu učenicima da primene stečeno znanje o vektorima u C++-u. Preporučuje se da svaki zadatak samostalno pokušate da rešite pre nego što pogledate primer rešenja.

Zadatak 1: Unos i ispis elemenata vektora

Napisati program koji unosi n celih brojeva u vektor i zatim ih ispisuje na ekranu.

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

int main() {
    int n;
    cout << "Unesite broj elemenata: ";
    cin >> n;

    vector<int> brojevi(n);
    cout << "Unesite elemente vektora:\n";
    for (int i = 0; i < n; i++) {
        cin >> brojevi[i];
    }

    cout << "Uneti elementi su: ";
    for (int x : brojevi) {
        cout << x << " ";
    }
    return 0;
}
    

Zadatak 2: Pronalaženje najvećeg elementa

Korišćenjem metode max_element() iz biblioteke <algorithm> pronaći najveći element u vektoru.

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

int main() {
    vector<int> brojevi = {12, 45, 7, 33, 89, 21};
    int maksimum = *max_element(brojevi.begin(), brojevi.end());
    cout << "Najveći element u vektoru je: " << maksimum;
    return 0;
}
    

Zadatak 3: Sabiranje elemenata vektora

Koristeći petlju ili funkciju accumulate() iz biblioteke <numeric>, izračunati sumu svih elemenata vektora.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main() {
    vector<int> brojevi = {5, 10, 15, 20};
    int suma = accumulate(brojevi.begin(), brojevi.end(), 0);
    cout << "Suma svih elemenata vektora je: " << suma;
    return 0;
}
    

Zadatak 4: Brisanje određenog elementa

Izbrisati sve pojave broja 10 iz vektora koristeći metodu erase() i algoritam remove().

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

int main() {
    vector<int> brojevi = {10, 20, 10, 30, 40, 10};
    brojevi.erase(remove(brojevi.begin(), brojevi.end(), 10), brojevi.end());

    cout << "Vektor nakon brisanja: ";
    for (int x : brojevi)
        cout << x << " ";
    return 0;
}
    

Napomena: Klikom na svako dugme možete prikazati ili sakriti rešenje. Ovi zadaci su odlična vežba za razumevanje osnovnih operacija sa vektorima — unos, ispis, pronalaženje maksimuma, sabiranje elemenata i brisanje određenih vrednosti.

Zadatak 5: Sortiranje objekata u vektoru

Napisati program koji definiše strukturu Ucenik sa imenom i godinama, unosi nekoliko učenika u vektor i sortira ih po godinama rastuće.

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

struct Ucenik {
    string ime;
    int godine;
};

// Funkcija za poređenje učenika po godinama
bool poredi(const Ucenik &a, const Ucenik &b) {
    return a.godine < b.godine;
}

int main() {
    vector<Ucenik> ucenici = {
        {"Ana", 17}, {"Marko", 16}, {"Jelena", 18}, {"Petar", 15}
    };

    sort(ucenici.begin(), ucenici.end(), poredi);

    cout << "Učenici sortirani po godinama:\n";
    for (auto &u : ucenici) {
        cout << u.ime << " (" << u.godine << " godina)\n";
    }

    return 0;
}
    

Napomena: Poslednji zadatak uvodi rad sa strukturama i sortiranjem vektora objekata — koristan korak ka naprednijem razumevanju STL-a u C++.