Algoritmi STL

lower_bound e upper_bound sono funzioni di ricerca binaria integrate.

lower_bound - una funzione che, in tempo logaritmico, trova l'elemento più piccolo in un array ordinato maggiore o uguale al valore dato k.
Prende i limiti dell'array e il valore di k come argomenti.
Restituisce un iteratore all'elemento trovato o alla fine (non inclusa) dell'array se tale elemento non esiste.
Puoi leggere ulteriori informazioni nella documentazione.

upper_bound - una funzione che in tempo logaritmico in un array ordinato trova l'elemento più piccolo strettamente maggiore del valore dato k.
Prende i limiti dell'array e il valore di k come argomenti.
Restituisce un iteratore all'elemento trovato o alla fine (non inclusa) dell'array se tale elemento non esiste.
Puoi leggere ulteriori informazioni nella documentazione.

Vale la pena chiarire che l'uso di queste funzioni su un set o multiset non funziona in tempo logaritmico a causa della mancanza di iteratori nelle raccolte ad accesso casuale di cui sopra.
Tuttavia, queste raccolte hanno metodi incorporati corrispondenti (ovvero, è necessario utilizzarle "attraverso un punto").

Esempi:
  vettore a = { 0, 1, 3, 5, 7 }; vector::iteratore it; it = lower_bound(a.begin(), a.end(), 4); // *it == 5 it = lower_bound(a.begin(), a.end(), 5); // *it == 5 it = lower_bound(a.begin(), a.end(), 8); // it == a.end() it = upper_bound(a.begin(), a.end(), 4); // *it == 5 it = upper_bound(a.begin(), a.end(), 5); // *it == 7 it = upper_bound(a.begin(), a.end(), -1); // *it == 0 // sottraendo gli iteratori, puoi ottenere l'indice dell'elemento trovato int ind = lower_bound(a.begin(), a.end(), 4) - a.begin(); // ind == 3 // è necessario utilizzare metodi anziché funzioni per raccolte di insiemi e simili set s{ 1, 3, 5 }; set::iterator sit; sit = s.lower_bound(3); // *seduto == 3 sit = s.upper_bound(3); // *seduto == 5  

unique - una funzione che comprime tutte le sequenze di elementi consecutivi identici in uno in un tempo lineare.
Come argomento, vengono passati i confini dell'array, all'interno dei quali è necessario applicare la compressione.
Un iteratore viene restituito alla nuova estremità (non inclusiva) dell'array. Dovresti stare attento con gli elementi dopo la nuova fine ma prima di quella vecchia, poiché avranno un valore indefinito.
Puoi leggere ulteriori informazioni nella documentazione.

Se stai utilizzando questa funzione su un vettore, è conveniente ridimensionare utilizzando il risultato restituito (ne parleremo più avanti).

Esempi:
  vettore a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 }; unico(a.begin(), a.end()); // a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?] // usare la funzione univoca è comodo da fare // matrice ausiliaria per la compressione delle coordinate a = { 235, 10, 41, 10, 41, 41, 235, 500, 500 }; sort(a.begin(), a.end()); // a = [10, 10, 41, 41, 41, 235, 235, 500, 500] a.resize(unique(a.begin(), a.end()) - a.begin()); // a = [10, 41, 235, 500]  

merge - una funzione che unisce due array ordinati, vale a dire, in tempo lineare ottiene un array ordinato, che consiste degli elementi del primo e del secondo array.
Richiede 5 argomenti: due limiti per ciascun array e il limite sinistro della destinazione (dove verranno posizionati gli elementi dell'array risultante).
Ulteriori dettagli sono disponibili nella documentazione.

Esempi: // gli array di origine devono essere ordinati vettore a = { 1, 3, 5, 7 }; vettore b = { 2, 4, 6 }; // necessita che la destinazione sia abbastanza grande vettore c(7); merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 3, 4, 5, 6, 7] // gli elementi possono essere ripetuti un = {1, 2, 4, 4}; b = {2, 3, 3, 3, 4, 4}; c.resize(10); merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]  Questa funzione è molto utile nel contesto del merge sort.

nth_element è una funzione che consente di trovare l'ennesimo elemento in un array in ordine di tempo lineare.
La funzione accetta l'estremità sinistra dell'array, un iteratore alla posizione di cui deve essere trovato il valore in ordine ordinato e l'estremità destra dell'array.
Dopo aver applicato la funzione, il valore richiesto si troverà nel punto indicato dall'iteratore, mentre i valori rimanenti acquisiranno un ordine caotico, ma a sinistra dell'ennesimo ci saranno valori non più di esso, e a destra non meno. Cioè, dovrebbe essere chiaro che questa funzione distrugge l'ordine originale degli elementi.
Puoi leggere di più nella documentazione (https://www.cplusplus.com/reference/algorithm/nth_element/).

Esempio: vettore a = { 4, 0, 3, 9, 2, 1, 8, 5, 6, 7 }; // cerca l'elemento all'indice 4 // prestare attenzione all'ordine degli argomenti nth_element(a.begin(), a.begin() + 4, a.end()); // a = [#, #, #, #, 4, $, $, $, $, $] // dove # <= 4 e 4 <= $  

Una permutazione di lunghezza n è una raccolta ordinata senza ripetizioni dei numeri 1, 2, ..., n. Ad esempio, [3, 1, 2] e [5, 4, 3, 2, 1] sono permutazioni, ma [1, 2, 1, 3] e [1, 2, 4] non lo sono.

Se l'attività si riduce al fatto che è necessario iterare su tutte le permutazioni di lunghezza n, è possibile utilizzare un comodo meccanismo in C ++, che si chiama "next_permutation".

Puoi saperne di più nella documentazione, ma il punto è che questa funzione cambia l'array passato alla successiva permutazione in ordine lessicografico (che è generalmente chiaro e il suo nome).

Per utilizzare next_permutation, devi includere la libreria dell'algoritmo (ovvero scrivi #include <algorithm> all'inizio del programma)

Esempi: vettore arr; arr = {1, 2, 3}; // l'array è [1, 2, 3] next_permutation(arr.begin(), arr.end()); // passa l'intero array alla funzione // l'array ora è [1, 3, 2] arr = { 2, 3, 1 }; // l'array è [2, 3, 1] next_permutation(arr.begin(), arr.end()); // passa l'intero array alla funzione // l'array ora è [3, 1, 2] next_permutation(arr.begin() + 1, arr.begin() + 3); // è possibile applicare una funzione a una parte di un array, ma in pratica ciò è raramente necessario // l'array ora è [3, 2, 1]
In questo caso, la funzione ha un valore di ritorno booleano che è vero se è stata generata la permutazione successiva e falso se non ce n'è stata una successiva (il caso in cui la permutazione massima in ordine lessicografico viene passata alla funzione).
Ciò rende possibile utilizzare la funzione in un ciclo, che ci consentirà di iterare su tutte le permutazioni contemporaneamente. A causa dell'indicizzazione 0, in pratica è spesso più conveniente lavorare con una permutazione di numeri da 0 a n - 1, sebbene una permutazione contenga formalmente numeri da 1 a n. Ma fortunatamente, questo non porta a ulteriori sovrapposizioni nel codice, perché la funzione next_permutation è adattata alle permutazioni con indice 0 (e persino agli elementi duplicati in un array, ma puoi scoprirne di più da solo).

In generale, il codice per l'iterazione di tutte le permutazioni è simile al seguente:   int; // dimensione della permutazione vettoreperm(n); // perm è l'abbreviazione di "permutazione", cioè "permutazione" for (int i = 0; i < n; i++) perm[i] = i; // inizializza la permutazione iniziale 0, 1, ..., n - 1 Fare { // all'interno del ciclo elaboriamo la permutazione corrente } while (next_permutation(perm.begin(), perm.end())); // se non c'è una permutazione successiva, termina il ciclo

Questo codice viene eseguito in O(n! * f(n)), dove f(n) è il tempo necessario per elaborare una particolare permutazione.