Grade 12 · Data structures and the STLCitește în română

The STL vector container

Original: Containerul vector din STL

O(n log n)C++1751 lines1 example

The idea

vector<int> is an array that manages its own memory: push_back adds at the end (O(1) on average), size() gives the number of elements, and v[i] accesses position i directly. The program reads n values, prints them in reverse order, then gets the sorted distinct values: sort orders them, unique moves the consecutive duplicates to the end and returns an iterator to their start, and erase deletes them. The last line is the number of distinct values.

Original description (Romanian)

vector<int> este un tablou care își gestionează singur memoria: push_back adaugă la final (în medie O(1)), size() dă numărul de elemente, iar v[i] accesează direct poziția i. Programul citește n valori, le afișează în ordine inversă, apoi obține valorile distincte sortate: sort le ordonează, unique mută duplicatele consecutive la final și întoarce un iterator spre începutul lor, iar erase le șterge. Ultima linie este numărul de valori distincte.

Complexity
O(n log n), from sorting
Grade
Grade 12 (Clasa a XII-a)

Examples

Example 1

Input

8
5 3 9 3 1 5 5 7

Expected output

7 5 5 1 3 9 3 5
1 3 5 7 9
5

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

vector-operatii-stl.cpp
/*
 * Titlu: Containerul vector din STL
 * Clasa: 12
 * Capitol: Structuri de date și STL
 * Descriere: vector<int> este un tablou care își gestionează singur memoria:
 *            push_back adaugă la final (în medie O(1)), size() dă numărul de
 *            elemente, iar v[i] accesează direct poziția i. Programul citește n
 *            valori, le afișează în ordine inversă, apoi obține valorile distincte
 *            sortate: sort le ordonează, unique mută duplicatele consecutive la
 *            final și întoarce un iterator spre începutul lor, iar erase le șterge.
 *            Ultima linie este numărul de valori distincte.
 * Complexitate: O(n log n), de la sortare
 *
 * Exemplu
 * Intrare:
 * 8
 * 5 3 9 3 1 5 5 7
 * Ieșire:
 * 7 5 5 1 3 9 3 5
 * 1 3 5 7 9
 * 5
 */
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> v;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        v.push_back(x);
    }

    for (int i = (int)v.size() - 1; i >= 0; i--)
        cout << v[i] << (i > 0 ? ' ' : '\n');

    vector<int> distincte = v; // o copie, ca să nu stricăm vectorul inițial
    sort(distincte.begin(), distincte.end());
    distincte.erase(unique(distincte.begin(), distincte.end()), distincte.end());
    for (int i = 0; i < (int)distincte.size(); i++)
        cout << distincte[i] << (i + 1 < (int)distincte.size() ? ' ' : '\n');
    cout << distincte.size() << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.