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.

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