Adattatori di contenitori e contenitori speciali
Scopri stack, queue, priority_queue e i moderni tipi vocabolario come span, string_view e optional. Comprendi quando gli adattatori semplificano il tuo codice.
Cosa sono gli adattatori di contenitori?
Gli adattatori di contenitori sono wrapper attorno a contenitori esistenti che forniscono un'interfaccia ristretta. Impongono un pattern di accesso specifico nascondendo l'API completa del contenitore:
- std::stack — LIFO (Last In, First Out), supportato da deque per impostazione predefinita
- std::queue — FIFO (First In, First Out), supportato da deque per impostazione predefinita
- std::priority_queue — max-heap, supportato da vector per impostazione predefinita
Gli adattatori non forniscono iteratori — puoi accedere solo all'elemento in cima/in testa. Questa restrizione è intenzionale: rende l'intento del codice più chiaro e previene usi impropri accidentali.
Stack e Queue in azione
Stack e queue sono strutture dati fondamentali usate nel parsing, BFS/DFS, sistemi di annullamento e pianificazione delle attività.
#include <stack>
#include <queue>
#include <string>
#include <iostream>
// Check if parentheses are balanced using a stack
bool is_balanced(const std::string& expr) {
std::stack<char> stk;
for (char c : expr) {
if (c == '(' || c == '[' || c == '{') {
stk.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (stk.empty()) return false;
char top = stk.top();
stk.pop();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
return false;
}
}
}
return stk.empty();
}
int main() {
std::cout << std::boolalpha;
std::cout << is_balanced("({[]})") << '\n'; // true
std::cout << is_balanced("({[}])") << '\n'; // false
// Queue — BFS-style task processing
std::queue<std::string> tasks;
tasks.push("compile");
tasks.push("link");
tasks.push("run tests");
while (!tasks.empty()) {
std::cout << "Processing: " << tasks.front() << '\n';
tasks.pop(); // removes from front
}
}Coda con priorità (Heap)
std::priority_queue è un max-heap per impostazione predefinita — top() restituisce l'elemento più grande. Per un min-heap, usa std::greater come comparatore.
#include <queue>
#include <vector>
#include <functional>
#include <iostream>
#include <string>
struct Task {
int priority;
std::string name;
};
int main() {
// Max-heap (default) — largest first
std::priority_queue<int> max_heap;
max_heap.push(30);
max_heap.push(10);
max_heap.push(50);
max_heap.push(20);
while (!max_heap.empty()) {
std::cout << max_heap.top() << ' '; // 50 30 20 10
max_heap.pop();
}
std::cout << '\n';
// Min-heap — smallest first
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
min_heap.push(30);
min_heap.push(10);
min_heap.push(50);
std::cout << "Min: " << min_heap.top() << '\n'; // 10
// Custom comparator with lambda
auto cmp = [](const Task& a, const Task& b) {
return a.priority < b.priority; // higher priority first
};
std::priority_queue<Task, std::vector<Task>, decltype(cmp)> task_queue(cmp);
task_queue.push({3, "low priority"});
task_queue.push({10, "critical"});
task_queue.push({7, "medium"});
while (!task_queue.empty()) {
auto& t = task_queue.top();
std::cout << "[" << t.priority << "] " << t.name << '\n';
task_queue.pop();
}
}std::span — Vista non proprietaria di dati contigui (C++20)
std::span è una vista leggera e non proprietaria su una sequenza contigua di elementi. Sostituisce il pattern soggetto a errori di passare coppie (puntatore, dimensione).
#include <span>
#include <vector>
#include <array>
#include <iostream>
#include <numeric>
// span accepts vector, array, C-array — anything contiguous
void print_stats(std::span<const int> data) {
if (data.empty()) return;
std::cout << "Size: " << data.size() << '\n';
std::cout << "First: " << data.front() << '\n';
std::cout << "Last: " << data.back() << '\n';
int sum = std::accumulate(data.begin(), data.end(), 0);
std::cout << "Sum: " << sum << '\n';
// Subviews
auto first3 = data.first(3); // first 3 elements
auto last2 = data.last(2); // last 2 elements
auto mid = data.subspan(1, 3); // 3 elements starting at index 1
}
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
std::array<int, 5> arr = {10, 20, 30, 40, 50};
int c_arr[] = {100, 200, 300, 400, 500};
print_stats(vec); // works with vector
print_stats(arr); // works with array
print_stats(c_arr); // works with C-array
}string_view e optional
std::string_view (C++17) è un riferimento non proprietario e di sola lettura a una stringa. Evita il costo di copiare o allocare std::string per funzioni che devono solo leggere:
void greet(std::string_view name) { // nessuna copia, nessuna allocazione
std::cout << "Hello, " << name << '\n';
}
greet("world"); // funziona con i literal di stringa
greet(std::string{"world"}); // funziona con std::stringstd::optional (C++17) rappresenta un valore che potrebbe o potrebbe non essere presente — un sostituto type-safe per "valori magici" o puntatori grezzi per indicare l'assenza:
std::optional<int> find_index(std::span<const int> data, int target) {
for (int i = 0; i < data.size(); ++i)
if (data[i] == target) return i;
return std::nullopt; // non trovato
}
auto idx = find_index(vec, 42);
if (idx) std::cout << "Found at " << *idx << '\n';
std::cout << idx.value_or(-1) << '\n'; // -1 se vuotoPoiché std::string_view e std::span sono non proprietari, possono facilmente diventare pendenti se i dati sottostanti vengono distrutti:
std::string_view bad() {
std::string temp = "hello";
return temp; // PENDENTE — temp distrutto alla fine dello scope
}Non restituire mai un string_view o span a una variabile locale. Sono sicuri per i parametri delle funzioni (i dati del chiamante sopravvivono alla chiamata), ma pericolosi come valori di ritorno a meno che tu non possa garantire che la sorgente sopravviva alla vista.
Lo stesso vale per std::span — internamente è solo un puntatore e una dimensione, senza semantica di proprietà.
Usa gli adattatori di contenitori quando vuoi imporre una disciplina su come gli elementi vengono acceduti:
- Usa std::stack al posto di un deque o vector grezzo quando solo l'accesso LIFO è significativo. Questo rende l'intento evidente e previene accessi casuali accidentali.
- Usa std::queue per l'elaborazione FIFO (code di attività, BFS).
- Usa std::priority_queue per lo scheduling, l'algoritmo di Dijkstra o qualsiasi scenario in cui vuoi sempre l'elemento estremo.
Se hai bisogno di iterazione, query sulla dimensione in punti arbitrari o accesso a metà sequenza, usa direttamente il contenitore sottostante.
- Gli adattatori di contenitori (
stack,queue,priority_queue) restringono l'interfaccia per imporre una disciplina d'uso std::priority_queueè un max-heap per impostazione predefinita — usastd::greaterper un min-heapstd::span(C++20) fornisce una vista non proprietaria su dati contigui, sostituendo le coppie(puntatore, dimensione)std::string_view(C++17) evita di copiare stringhe per uso in sola lettura — ma attenzione ai riferimenti pendentistd::optional(C++17) è il modo type-safe per rappresentare "forse nessun valore" senza valori sentinella magici- Le viste non proprietarie (
span,string_view) non devono mai sopravvivere ai dati a cui fanno riferimento
Quiz — Metti alla prova le tue conoscenze
(15 XP)1. Quale adattatore di contenitore fornisce il comportamento FIFO (First In, First Out)?
2. Quale tipo restituisce `std::priority_queue<int>` da `top()` per impostazione predefinita?
3. Perché è pericoloso restituire un `std::string_view` a una `std::string` locale?