C++

Προσαρμογείς Εμπορευματοκιβωτίων & Ειδικά Εμπορευματοκιβώτια

Μάθετε για το stack, queue, priority_queue και σύγχρονους τύπους λεξιλογίου όπως span, string_view και προαιρετικό. Κατανοήστε πότε οι προσαρμογείς απλοποιούν τον κώδικά σας.

Τι είναι οι προσαρμογείς κοντέινερ;

Οι προσαρμογείς κοντέινερ είναι περιτυλίγματα γύρω από υπάρχοντα κοντέινερ που παρέχουν περιορισμένη διεπαφή. Επιβάλλουν ένα συγκεκριμένο μοτίβο πρόσβασης αποκρύπτοντας το πλήρες API κοντέινερ:

- std::stack — LIFO (Τελευταία είσοδος, πρώτη έξοδος), που υποστηρίζεται από τοdequeαπό προεπιλογή
- std::queue — FIFO (First In, First Out), που υποστηρίζεται από τοdequeαπό προεπιλογή
- std::priority_queue — max-heap, που υποστηρίζεται από τοvectorαπό προεπιλογή

Οι προσαρμογείς δεν παρέχουν επαναλήπτες — μπορείτε να έχετε πρόσβαση μόνο στο επάνω/μπροστινό στοιχείο. Αυτός ο περιορισμός είναι σκόπιμος: καθιστά σαφέστερη την πρόθεση του κώδικα και αποτρέπει την τυχαία κακή χρήση.

Στοίβα και ουρά σε δράση

Οι στοίβες και οι ουρές είναι θεμελιώδεις δομές δεδομένων που χρησιμοποιούνται στην ανάλυση, το BFS/DFS, τα συστήματα αναίρεσης και τον προγραμματισμό εργασιών.

stack_queue.cpp
#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
    }
}

Ουρά προτεραιότητας (Σωρός)

Τοstd::priority_queueείναι ένα μέγιστο σωρό από προεπιλογή — τοtop()επιστρέφει το μεγαλύτερο στοιχείο. Για ελάχιστο σωρό, χρησιμοποιήστε τοstd::greaterως σύγκριση.

priority_queue.cpp
#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 — Προβολή μη ιδιόκτητων συνεχόμενων δεδομένων (C++20)

Τοstd::spanείναι μια ελαφριά προβολή που δεν ανήκει σε μια συνεχόμενη ακολουθία στοιχείων. Αντικαθιστά το επιρρεπές σε σφάλματα μοτίβο μετάδοσης ζευγών(pointer, size).

span_example.cpp
#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 και προαιρετικό

Το std::string_view (C++17) είναι μια αναφορά που δεν ανήκει σε μια συμβολοσειρά μόνο για ανάγνωση. Αποφεύγει το κόστος αντιγραφής ή εκχώρησηςstd::stringγια λειτουργίες που χρειάζεται μόνο να διαβάσουν:

void greet(std::string_view name) { // no copy, no allocation
 std::cout << "Hello, " << name << '\n';
}
greet("world"); // works with string literals
greet(std::string{"world"}); // works with std::string

std::προαιρετικό (C++17) represents a value that might or might not be present — a type-safe replacement for "magic values" or raw pointers to indicate absence:

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; // not found
}
auto idx = find_index(vec, 42);
if (idx) std::cout << "Found at " << *idx << '\n';
std::cout << idx.value_or(-1) << '\n'; // -1 if empty
Παγίδα

Δεδομένου ότι ταstd::string_viewκαιstd::spanείναι δεν ανήκουν, μπορούν εύκολα να κρέμονται εάν καταστραφούν τα υποκείμενα δεδομένα:

std::string_view bad() {
    std::string temp = "hello";
    return temp;  // DANGLING — temp destroyed at end of scope
}

Never return a string_view or span to a local variable. They are safe for function parameters (the caller's data outlives the call), but dangerous as return values unless you can guarantee the source outlives the view.

The same applies to std::span — είναι απλώς ένας δείκτης και ένα μέγεθος εσωτερικά, χωρίς σημασιολογία ιδιοκτησίας.

Βέλτιστη πρακτική

Χρησιμοποιήστε προσαρμογείς κοντέινερ όταν θέλετε να επιβάλετε μια πειθαρχία σχετικά με τον τρόπο πρόσβασης στα στοιχεία:

- Χρησιμοποιήστεstd::stackαντί για ακατέργαστοdequeήvectorόταν μόνο η πρόσβαση LIFO έχει νόημα. Αυτό καθιστά προφανή την πρόθεση και αποτρέπει την τυχαία τυχαία πρόσβαση.
- Χρησιμοποιήστε τοstd::queueγια επεξεργασία FIFO (ουρές εργασιών, BFS).
- Χρησιμοποιήστε τοstd::priority_queueγια προγραμματισμό, τον αλγόριθμο του Dijkstra ή οποιοδήποτε σενάριο όπου θέλετε πάντα το ακραίο στοιχείο.

Εάν χρειάζεστε επανάληψη, ερωτήματα μεγέθους σε αυθαίρετα σημεία ή πρόσβαση στη μέση ακολουθία, χρησιμοποιήστε απευθείας το υποκείμενο κοντέινερ.

Βασικά συμπεράσματα
  • Οι προσαρμογείς κοντέινερ (stack,queue,priority_queue) περιορίζουν τη διεπαφή για την επιβολή της πειθαρχίας χρήσης
  • Τοstd::priority_queueείναι ένα μέγιστο σωρό από προεπιλογή — χρησιμοποιήστε τοstd::greaterγια ένα ελάχιστο σωρό
  • Τοstd::span(C++20) παρέχει μια προβολή που δεν ανήκει σε συνεχόμενα δεδομένα, αντικαθιστώντας τα ζεύγη(pointer, size)
  • Τοstd::string_view(C++17) αποφεύγει την αντιγραφή συμβολοσειρών για χρήση μόνο για ανάγνωση — αλλά προσέξτε για κρέμονται αναφορές
  • Τοstd::optional(C++17) είναι ο ασφαλής τύπος τρόπος αναπαράστασης "ίσως καμία τιμή" χωρίς μαγικές τιμές φρουρού
  • Οι προβολές που δεν ανήκουν (span,string_view) δεν πρέπει ποτέ να υπερβαίνουν τα δεδομένα που αναφέρονται

Κουίζ — Δοκιμάστε τις γνώσεις σας

(15 XP)

1. Ποιος προσαρμογέας κοντέινερ παρέχει συμπεριφορά FIFO (First In, First Out);

2. Τι τύπο επιστρέφει το`std::priority_queue<int>`από το`top()`από προεπιλογή;

3. Γιατί είναι επικίνδυνη η επιστροφή ενός`std::string_view`σε ένα τοπικό`std::string`;

Προηγούμενο
Associative Containers: map, set, unordered_map
Επόμενο
Iterators: Η κόλλα STL