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.

Metoda / član	Kratak opis	Kratak primer
`vector v;`	Konstruktor: kreira prazan vektor tipa `T`.	`std::vector v; // prazan vektor`
`push_back(val)`	Dodaje element na kraj vektora.	`v.push_back(5); // v: {5}`
`pop_back()`	Uklanja poslednji element (ne vraća ga).	`v.pop_back(); // uklanja poslednji element`
`size()`	Vraća broj elemenata u vektoru (tip `size_t`).	`std::cout << v.size();`
`capacity()`	Kapacitet rezervisanog prostora (može biti ≥ `size()`).	`v.reserve(100); std::cout<`
`reserve(n)`	Rezerviše prostor za ≥ `n` elemenata (sprečava često realokiranje).	`v.reserve(50); // efikasnije dodavanje`
`resize(n)`	Menja veličinu vektora na `n` (dodatni elementi default-init).	`v.resize(3); // v ima 3 elementa`
`clear()`	Uklanja sve elemente (ne menja kapacitet).	`v.clear(); // v.size() == 0`
`empty()`	Vraća `true` ako je vektor prazan (`size()==0`).	`if (v.empty()) std::cout<<"prazan";`
`operator[] / at(i)`	`v[i]` je brži, ali NE proverava granice; `at(i)` baca izuzetak ako je i van opsega.	`v[0] = 1; int x = v.at(0);`
`begin(), end()`	Iteratori za petlje i algoritme (`for(auto it=v.begin(); it!=v.end(); ++it)`).	`for(auto x : v) std::cout<`
`insert(pos, val)`	Umeće vrednost pre pozicije `pos`. Može biti skupo (pomera elemente).	`v.insert(v.begin()+1, 42);`
`erase(pos)`	Uklanja element na `pos` (pomera preostale elemente).	`v.erase(v.begin()+2);`
`emplace_back(args...)`	Konstruše element direktno na kraju (efikasnije za složene tipove).	`v.emplace_back(1); // kao push_back, ali efikasnije`
`shrink_to_fit()`	Pokušava da smanji kapacitet na veličinu (nije garantovano).	`v.shrink_to_fit();`
`data()`	Vraća pokazivač na kontinualni niz elemenata (`T*`), koristan za C interop.	`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

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++.

Uvod u vektore

Osnovni koncept vektora

Osnovna sintaksa u C++

Iteracija kroz vektor

Kapacitet i performanse

Napredne operacije

Primer: Dinamičko čitanje podataka

Primenjeni primeri u algoritmima

Zadaci za vežbu

Zaključak

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

Zadaci za vežbu

Zadatak 1: Unos i ispis elemenata vektora

Zadatak 2: Pronalaženje najvećeg elementa

Zadatak 3: Sabiranje elemenata vektora

Zadatak 4: Brisanje određenog elementa

Vektori u drugim programskim jezicima

Primer u C# jeziku

Analiza performansi vektora

Kombinovanje vektora sa drugim strukturama

Zaključak i dalji koraci

Zadaci za vežbu

Zadatak 1: Unos i ispis elemenata vektora

Zadatak 2: Pronalaženje najvećeg elementa

Zadatak 3: Sabiranje elemenata vektora

Zadatak 4: Brisanje određenog elementa

Zadatak 5: Sortiranje objekata u vektoru

Podešavanja kolačića

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