Introduction to Vectors

Vectors are one of the most important data structures in modern programming. They allow dynamic storage of elements of the same type, meaning that the size of a vector can change during program execution. Unlike static arrays, vectors automatically manage memory and provide a simple interface for adding, removing, and accessing elements.

In this lesson, we will learn the basic concepts related to vectors: how they work, why they are efficient, and how they are used in various algorithms. For practical examples in C++, you can also check the detailed lesson Dynamic Array (std::vector) in C++.

Basic Concept of Vectors

A vector is essentially a dynamic array of elements of the same type. It allows the number of elements to grow or shrink automatically according to the needs of the program, without manual memory management.

Vectors are part of the C++ Standard Library (STL – Standard Template Library).
They automatically increase their capacity when more elements are added than currently allocated.
Elements are accessed by index, just like in a regular array.

Basic Syntax in C++


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

int main() {
    // Declaration of a vector of integers
    vector<int> numbers;

    // Adding elements
    numbers.push_back(10);
    numbers.push_back(20);
    numbers.push_back(30);

    // Printing elements
    for (int i = 0; i < numbers.size(); i++) {
        cout << numbers[i] << " ";
    }

    cout << endl;
    return 0;
}

This example shows how a vector is used as a dynamic array. By using push_back(), we add elements, while size() returns the current number of elements in the vector.

Iterating Through a Vector

Vectors can be traversed using loops and iterators. In modern C++, the range-based for loop is commonly used because it is shorter and more readable.


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

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

Capacity and Performance

Each vector has a size (the current number of elements) and a capacity (the amount of allocated memory). When the capacity is exceeded, the vector automatically allocates more memory — usually doubling the current capacity. This strategy enables fast element insertion with a minimal number of reallocations.

reserve(n) — pre-allocates memory for n elements.
shrink_to_fit() — reduces the capacity to match the actual size.

Advanced Operations

In addition to basic operations like adding and accessing elements, vectors provide several advanced functions:

insert() — inserts an element or a range of elements at a specific position.
erase() — removes an element or a range of elements.
clear() — removes all elements from the vector.

Example: Dynamic Input Reading


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

int main() {
    vector<int> numbers;
    int n;
    cout << "Enter numbers (0 to stop): ";
    while (cin >> n && n != 0) {
        numbers.push_back(n);
    }

    cout << "Total entered: " << numbers.size() << " numbers." << endl;
    return 0;
}

This example illustrates the flexibility of vectors — the user does not need to know in advance how many values will be entered.

Practical Use in Algorithms

Dynamic storage of elements during algorithm execution (e.g. generating combinations or permutations).
Implementing stacks, queues, graphs, or matrices using vectors.
Handling variable-length arrays in competitive programming tasks.

Practice Tasks

Write a program that reads N numbers and prints their sum and average.
Create a function that returns the maximum element of a vector.
Create a function that reverses the order of elements in a vector.

Conclusion

Vectors are a fundamental data structure that enables simple, safe, and efficient handling of variable-length arrays. Thanks to automatic memory management and rich functionality, vectors are a standard tool in modern programming and form the basis of many algorithms and data structures.

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

Introduction to Vectors

Basic Concept of Vectors

Basic Syntax in C++

Iterating Through a Vector

Capacity and Performance

Advanced Operations

Example: Dynamic Input Reading

Practical Use in Algorithms

Practice Tasks

Conclusion

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`