C++ Algoritmi

Da Andreabont's Wiki.

Il C++ vengono definiti nella libreria standard algorithm una serie di algoritmi generici di uso comune, in questa pagina saranno elencati i più noti.

Inizializzazione

std::fill

Questa funzione serve a riempire il contenitore con un valore specificato. Accetta come primo e secondo parametro l'iteratore della struttura iniziale e finale, e come terzo il valore da assegnare.

std::vector<int> miovettore(5,0);  // 0, 0, 0, 0, 0
std::fill(miovettore.begin(), miovettore.end(), 1); // 1, 1, 1, 1, 1

std::fill_n

Questa funzione serve a riempire il contenitore con un valore uguale da un punto fino ad un'altro specificato numericamente. Accetta come primo parametro l'iteratore della struttura da cui partire, come secondo parametro il numero di assegnamenti da fare a partire dal primo, e come terzo il valore da assegnare.

std::vector<int> miovettore(5,0);  // 0, 0, 0, 0, 0
std::fill_n(miovettore.begin(), 3, 1); // 1, 1, 1, 0, 0

std::generate

Questa funzione serve a inizializzare un contenitore attraverso una funzione passata.

std::vector<int> miovettore(5,0);  // 0, 0, 0, 0, 0
std::generate(miovettore.begin(), miovettore.end(), []{ static int n = 0; return n++; }); // 0, 1, 2, 3, 4

Ordinamento

Questi algoritmi lavorano sulle strutture dati standard ordinabili, attraverso l'uso degli iteratori e dell'operatore di confronto <, il quale va passato come funtore se non è presente come operatore dell'oggetto passato.

std::sort

L'ordine degli elementi uguali non è garantito che sia preservato. Normalmente è implementato come introsort.

#include <algorithm>
#include <vector>

std::vector<int> myvector = {3, 5, 1, 2, 4, 8, 7};
std::sort(myvector.begin(), myvector.end());

std::stable_sort

L'ordine degli elementi uguali è garantito che sia preservato.

#include <algorithm>
#include <vector>

std::vector<int> myvector = {3, 5, 1, 2, 4, 8, 7};
std::stable_sort(myvector.begin(), myvector.end());

std::is_sorted

Controlla se la struttura dati passata è ordinata in ordine crescente. Torna true se è ordinato, false altrimenti,

#include <algorithm>
#include <vector>

std::vector<int> myvector = {3, 5, 1, 2, 4, 8, 7};
bool sorted = std::is_sorted(myvector.begin(), myvector.end());

std::shuffle

Questo algoritmo utilizza una funziona casuale passata per prendere un contenitore e metterlo in disordine.

#include <random>
#include <algorithm>
#include <vector>

std::vector<int> myvector = {1, 2, 3, 4, 5, 6, 7};
std::random_device rd;
std::mt19937 rand(rd());
std::shuffle(myvector.begin(), myvector.end(), rand);

std::reverse

Questa funzione serve a invertire l'ordine della sequenza data. Funziona accettando come parametri l'iteratore di inizio e di fine della sequenza da trattare.

std::vector<int> miovettore = {2, 1, 3, 5, 4} 
std::reverse(miovettore.begin(), miovettore.end()); // 4, 5, 3, 1, 2

Confronto

Questi algoritmi permettono di definire degli operatori di confronto tra alcuni oggetti complessi.

std::lexicographical_compare

Ritorna true se le due stringhe passate sono in ordine alfabetico. Utilizzabile in congiunzione con std::sort.

std::vector<std::string> list = {"aa", "ab", "ba", "cb"};

std::sort(std::begin(list), std::end(list) ,[](const std::string& a, const std::string& b) {
    return std::lexicographical_compare(std::begin(a), std::end(a), std::begin(b), std::end(b));
});

Iterazione

Questi algoritmi permettono di iterare su un range di elementi.

std::for_each

Chiama una funzione passata ad ogni elemento della lista.

#include <algorithm>
#include <vector>
#include <iostream>

std::vector<int> miovettore = {1, 2, 3, 4, 5};
std::for_each(miovettore.begin(), miovettore.end(), [](int i){std::cout << i << '\n';});

Verifica

Questi algoritmi permettono di verificare una condizione su un range di elementi.

std::all_of

Ritorna true se tutti gli elementi del range rispettano la condizione passata.

#include <algorithm>
#include <vector>

std::vector<int> myvector = {1, 2, 3, 4, 5};
bool result = std::all_of(myvector.begin(), myvector.end(), [](int i){return i>0;});

std::any_of

Ritorna true se almeno uno degli elementi del range rispetta la condizione passata.

#include <algorithm>
#include <vector>

std::vector<int> myvector = {1, 2, 3, 4, 5};
bool result = std::any_of(myvector.begin(), myvector.end(), [](int i){return i>3;});

std::none_of

Ritorna true se nessuno degli elementi del range rispetta la condizione passata.

#include <algorithm>
#include <vector>

std::vector<int> myvector = {1, 2, 3, 4, 5};
bool result = std::none_of(myvector.begin(), myvector.end(), [](int i){return i<0;});

Ricerca

Gli algoritmi di ricerca permettono ricevono due itaeratori (inizio e fine) di una struttura dati e il valore cercato, ritornano true se lo trovano, false altrimenti.

std::binary_search

Implementa la ricerca dicotomica su una struttura dati voluta. E' necessario che la struttura dati sia precedentemente ordinata in ordine crescente e disponga dell'operatore <.

#include <algorithm>
#include <vector>

std::vector<int> miovettore = {1, 2, 3, 4, 5};
bool found = std::binary_search(miovettore.begin(), miovettore.end(), 3);

std::count

Conta quanti elementi uguali a quello passato sono presenti nel range.

#include <algorithm>
#include <vector>

std::vector<int> miovettore = {1, 2, 2, 2, 5};
std::count(miovettore.begin(), miovettore.end(), 2); // Ritorna 3

std::count_if

Conta quanti elementi che soddisfano la condizione data sono presenti nel range.

#include <algorithm>
#include <vector>

std::vector<int> miovettore = {1, 2, 2, 2, 5};
std::count_if(miovettore.begin(), miovettore.end(), [](int i){return i%2 == 0;}); // Ritorna 3

Operazioni sugli insiemi

Queste operazioni vengono eseguite sui contenitori set.

Intersezione

std::set<int> a = {1,2,3,4,5};
std::set<int> b = {3,4,5,6,7};
std::set<int> c;

std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::inserter(c, c.begin()));

// Il set "c" contene ora 3, 4, 5

Differenza

std::set<int> a = {1,2,3,4,5};
std::set<int> b = {4,5};
std::set<int> c;

std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::inserter(c, c.begin()));

// il set "c" ora contiene 1, 2, 3

Unione

std::set<int> a = {1,2,3,4};
std::set<int> b = {4,5,6,7};
std::set<int> c;

std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::inserter(c, c.begin()));

// il set "c" ora contiene 1, 2, 3, 4, 5, 6, 7