Bài 13.3: Kiểu dữ liệu Pair trong C++

Trong thế giới lập trình C++, đôi khi chúng ta cần nhóm hai giá trị lại với nhau như một đơn vị duy nhất. Ví dụ: một cặp tọa độ (x, y), một cặp giá trị nhỏ nhất và lớn nhất, hoặc một cặp khóa và giá trị trong cấu trúc dữ liệu. C++ Standard Library cung cấp một công cụ tuyệt vời cho việc này: pair.

pair là một template struct đơn giản được định nghĩa trong header <utility>. Nó cho phép bạn lưu trữ một cặp các đối tượng, mà các đối tượng này có thể có kiểu dữ liệu khác nhau. Hãy cùng khám phá chi tiết về người bạn đồng hành nhỏ gọn nhưng đầy quyền năng này nhé!

`pair` là gì?

Đơn giản nhất, pair<T1, T2> là một cấu trúc chứa hai thành viên dữ liệu công khai (public data members). Thành viên đầu tiên có kiểu T1 và được đặt tên là .first. Thành viên thứ hai có kiểu T2 và được đặt tên là .second.

Sự linh hoạt của pair nằm ở chỗ T1 và T2 có thể là bất kỳ kiểu dữ liệu nào, kể cả các kiểu phức tạp như các container khác (vector, map) hoặc các đối tượng do bạn tự định nghĩa.

Làm thế nào để sử dụng `pair`?

Để sử dụng pair, bạn cần include header <utility>.

1. Khai báo và khởi tạo

Có nhiều cách để tạo và khởi tạo một pair:

Khởi tạo mặc định: Tạo một pair với các thành viên được khởi tạo theo giá trị mặc định của kiểu dữ liệu tương ứng (0 cho số, chuỗi rỗng cho string, nullptr cho con trỏ, v.v.).
```
#include <iostream>
#include <utility> // Cần include header này

int main() {
    pair<int, string> p1; // p1.first = 0, p1.second = "" (chuỗi rỗng)

    cout << "p1: " << p1.first << ", " << p1.second << endl;

    return 0;
}
```
Giải thích: Đoạn code trên khai báo một pair có kiểu int cho phần tử đầu tiên và string cho phần tử thứ hai. Vì không cung cấp giá trị ban đầu, p1.first được khởi tạo thành 0 (giá trị mặc định cho int), và p1.second được khởi tạo thành chuỗi rỗng (giá trị mặc định cho string).
Sử dụng constructor với hai đối số: Cung cấp trực tiếp giá trị cho cả hai thành viên khi tạo pair.
```
#include <iostream>
#include <utility>

int main() {
    pair<int, string> p2(101, "Alice"); // Khởi tạo với giá trị cụ thể

    cout << "p2: " << p2.first << ", " << p2.second << endl;

    return 0;
}
```
Giải thích: Cách này cho phép bạn gán giá trị ngay khi khai báo. 101 được gán cho p2.first và "Alice" được gán cho p2.second.
Sử dụng make_pair: Đây là một hàm tiện ích rất phổ biến, đặc biệt hữu ích khi kiểu dữ liệu của pair phức tạp hoặc khi bạn muốn tận dụng suy luận kiểu (auto).
```
#include <iostream>
#include <utility>
#include <vector>

int main() {
    auto p3 = make_pair("Product A", 25.5); // Tự động suy luận kiểu pair<const char*, double>

    cout << "p3: " << p3.first << ", " << p3.second << endl;

    // make_pair cũng hoạt động tốt với các kiểu phức tạp
    auto p4 = make_pair(1, vector<int>{10, 20, 30});
    cout << "p4.first: " << p4.first << endl;
    cout << "p4.second size: " << p4.second.size() << endl;

    return 0;
}
```
Giải thích: make_pair là một template function giúp bạn không cần viết lại kiểu dữ liệu đầy đủ của pair. Trình biên dịch sẽ tự suy luận kiểu dựa trên các đối số bạn truyền vào. Ví dụ make_pair("Product A", 25.5) sẽ tạo ra một pair<const char*, double>. Điều này làm cho code ngắn gọn và dễ đọc hơn, đặc biệt khi kết hợp với từ khóa auto.
Sử dụng danh sách khởi tạo (C++11 trở lên): Cách này rất gọn gàng và hiện đại.
```
#include <iostream>
#include <utility>

int main() {
    pair<string, int> p5 = {"Bob", 30}; // Sử dụng danh sách khởi tạo

    cout << "p5: " << p5.first << ", " << p5.second << endl;

    return 0;
}
```
Giải thích: Từ C++11, bạn có thể sử dụng cặp dấu ngoặc nhọn {} để khởi tạo đối tượng, bao gồm cả pair. Các giá trị bên trong ngoặc nhọn sẽ được gán cho .first và .second theo thứ tự.

2. Truy cập các thành viên

Như đã đề cập, các thành viên của pair được truy cập thông qua .first và .second.

#include <iostream>
#include <utility>

int main() {
    pair<double, double> coordinates(10.5, 20.2);

    // Truy cập và in giá trị
    cout << "X coordinate: " << coordinates.first << endl;
    cout << "Y coordinate: " << coordinates.second << endl;

    // Thay đổi giá trị
    coordinates.first = 5.0;
    coordinates.second = 15.0;

    cout << "New X: " << coordinates.first << ", New Y: " << coordinates.second << endl;

    return 0;
}

Giải thích: Đoạn code này tạo một pair coordinates để lưu trữ tọa độ. Chúng ta sử dụng .first để truy cập và in giá trị của tọa độ X, và .second cho tọa độ Y. Sau đó, chúng ta cũng có thể dễ dàng gán giá trị mới cho các thành viên này.

3. So sánh `pair`

Bạn có thể so sánh hai đối tượng pair (có cùng kiểu T1 và T2) bằng các toán tử ==, !=, <, >, <=, >=. Việc so sánh được thực hiện theo thứ tự từ điển (lexicographical order):

Hai pair bằng nhau (==) nếu .first của chúng bằng nhau và .second của chúng bằng nhau.
Pair A nhỏ hơn Pair B (<) nếu A.first < B.first, HOẶC (A.first == B.first VÀ A.second < B.second).
Các toán tử khác tương tự.

#include <iostream>
#include <utility>

int main() {
    pair<int, int> pA(1, 5);
    pair<int, int> pB(2, 3);
    pair<int, int> pC(1, 10);
    pair<int, int> pD(1, 5);

    cout << "pA: (" << pA.first << ", " << pA.second << ")" << endl;
    cout << "pB: (" << pB.first << ", " << pB.second << ")" << endl;
    cout << "pC: (" << pC.first << ", " << pC.second << ")" << endl;
    cout << "pD: (" << pD.first << ", " << pD.second << ")" << endl;


    cout << "pA == pD: " << (pA == pD ? "true" : "false") << endl; // true (1==1 && 5==5)
    cout << "pA == pB: " << (pA == pB ? "true" : "false") << endl; // false
    cout << "pA < pB: " << (pA < pB ? "true" : "false") << endl;   // true (1 < 2)
    cout << "pA < pC: " << (pA < pC ? "true" : "false") << endl;   // true (1 == 1 && 5 < 10)
    cout << "pC < pB: " << (pC < pB ? "true" : "false") << endl;   // false (1 < 2 is false, then compare second) Oh wait, this is wrong. 1 < 2 is true, so pC < pB is FALSE. pB < pC is TRUE (2 > 1).
    // Let's correct the logic and output.
    cout << "pC < pB: " << (pC < pB ? "true" : "false") << endl;   // false (1 < 2 -> pA < pB -> true; pC < pB -> 1 < 2 -> false) Let's re-evaluate pC < pB. 1 < 2 is true, so pC IS NOT < pB. pB is > pC.

    cout << "pB > pC: " << (pB > pC ? "true" : "false") << endl;   // true (2 > 1)


    return 0;
}

Giải thích: So sánh pair dựa trên thứ tự phần tử đầu tiên, sau đó mới đến phần tử thứ hai nếu phần tử đầu tiên bằng nhau. pA == pD vì cả .first và .second đều bằng nhau. pA < pB vì pA.first (1) nhỏ hơn pB.first (2). pA < pC vì pA.first (1) bằng pC.first (1), nên mới xét đến .second; pA.second (5) nhỏ hơn pC.second (10). pB > pC vì pB.first (2) lớn hơn pC.first (1).

Các ứng dụng phổ biến của `pair`

pair xuất hiện ở nhiều nơi trong C++ Standard Library và cũng rất hữu ích trong code của chính bạn.

1. Trả về nhiều giá trị từ một hàm

Đây là một trường hợp sử dụng rất phổ biến. Nếu một hàm cần trả về hai giá trị khác nhau, thay vì sử dụng con trỏ hoặc tham chiếu (out-parameters), bạn có thể trả về một pair.

#include <iostream>
#include <vector>
#include <utility> // for pair and make_pair
#include <limits>  // for numeric_limits

// Hàm tìm giá trị nhỏ nhất và lớn nhất trong vector
pair<int, int> findMinMax(const vector<int>& numbers) {
    if (numbers.empty()) {
        // Trả về một pair với các giá trị đặc biệt hoặc ném ngoại lệ
        return {numeric_limits<int>::max(), numeric_limits<int>::min()};
    }

    int min_val = numbers[0];
    int max_val = numbers[0];

    for (size_t i = 1; i < numbers.size(); ++i) {
        if (numbers[i] < min_val) {
            min_val = numbers[i];
        }
        if (numbers[i] > max_val) {
            max_val = numbers[i];
        }
    }

    return make_pair(min_val, max_val); // Sử dụng make_pair tiện lợi
}

int main() {
    vector<int> my_numbers = {5, 2, 8, 1, 9, 4};

    pair<int, int> result = findMinMax(my_numbers);

    cout << "Min value: " << result.first << endl;
    cout << "Max value: " << result.second << endl;

    // Ví dụ với vector rỗng
    vector<int> empty_numbers;
    pair<int, int> empty_result = findMinMax(empty_numbers);
    cout << "Empty vector result: " << empty_result.first << ", " << empty_result.second << endl;


    return 0;
}

Giải thích: Hàm findMinMax trả về một pair<int, int> chứa giá trị nhỏ nhất và lớn nhất tìm được. Trong main, chúng ta nhận kết quả vào một biến pair và truy cập từng giá trị bằng .first và .second. Cách này rõ ràng hơn so với việc truyền vào hai tham chiếu int& min_val, int& max_val.

2. Là thành viên của các container

pair là "trái tim" của các container liên kết như map và unordered_map. Các phần tử trong map<Key, Value> thực chất được lưu trữ dưới dạng pair<const Key, Value>.

#include <iostream>
#include <map>
#include <string>
#include <utility> // Dù map cũng có thể include utility, minh họa rõ ràng

int main() {
    map<string, int> student_scores;

    // Khi insert vào map, chúng ta thường dùng pair
    student_scores.insert(make_pair("Alice", 95));
    student_scores.insert({"Bob", 88}); // C++11 initializer list cũng tạo ra pair ngầm

    // map::insert trả về một pair!
    // pair<iterator, bool> result = map.insert(...)
    // result.first là iterator tới phần tử được thêm (hoặc đã tồn tại)
    // result.second là true nếu thêm mới thành công, false nếu phần tử đã tồn tại

    auto insert_result = student_scores.insert(make_pair("Alice", 98)); // Alice đã tồn tại

    cout << "Insert Alice (again): " << (insert_result.second ? "Success (new)" : "Failed (exists)") << endl;
    cout << "Alice's score in map: " << insert_result.first->second << endl; // result.first là iterator -> dereference để lấy pair -> .second để lấy score


    // Khi duyệt map, các phần tử iterator trỏ tới là pair
    for (const auto& pair : student_scores) {
        cout << "Student: " << pair.first << ", Score: " << pair.second << endl;
    }

    return 0;
}

Giải thích: Code minh họa cách pair được sử dụng ngầm khi làm việc với map. Hàm insert của map trả về một pair cho biết kết quả của thao tác. Khi duyệt map bằng vòng lặp range-based for, biến lặp pair thực chất là một tham chiếu tới pair<const string, int>.

3. Nhóm các dữ liệu liên quan

Đôi khi bạn chỉ đơn giản là muốn gói hai mẩu thông tin có liên quan vào một đối tượng duy nhất mà không cần định nghĩa một struct hoặc class riêng.

#include <iostream>
#include <utility>

int main() {
    // Lưu thông tin sản phẩm: Tên và giá
    pair<string, double> product_info = {"Laptop", 1200.50};

    cout << "Product Name: " << product_info.first << endl;
    cout << "Product Price: $" << product_info.second << endl;

    // Lưu cặp email và trạng thái (đã xác minh hay chưa)
    pair<string, bool> user_email_status = {"testuser@example.com", true};

    cout << "Email: " << user_email_status.first << ", Verified: " << (user_email_status.second ? "Yes" : "No") << endl;


    return 0;
}

Giải thích: Các pair product_info và user_email_status được sử dụng để nhóm hai mẩu thông tin có ý nghĩa liên quan với nhau. Điều này giúp giữ cho dữ liệu gọn gàng và dễ quản lý hơn là lưu trữ chúng trong các biến riêng lẻ không liên kết rõ ràng.

C++17 và Structured Bindings

Với C++17, việc làm việc với pair trở nên thậm chí còn dễ dàng hơn nhờ tính năng Structured Bindings. Nó cho phép bạn "giải nén" các thành viên của pair (hoặc tuple, hoặc struct) vào các biến riêng biệt ngay tại điểm khai báo.

#include <iostream>
#include <vector>
#include <utility> // For pair and make_pair
#include <limits>  // For numeric_limits

// Hàm findMinMax giống ví dụ trên
pair<int, int> findMinMax(const vector<int>& numbers) {
     if (numbers.empty()) {
        return {numeric_limits<int>::max(), numeric_limits<int>::min()};
    }

    int min_val = numbers[0];
    int max_val = numbers[0];

    for (size_t i = 1; i < numbers.size(); ++i) {
        if (numbers[i] < min_val) {
            min_val = numbers[i];
        }
        if (numbers[i] > max_val) {
            max_val = numbers[i];
        }
    }

    return make_pair(min_val, max_val);
}

int main() {
    vector<int> my_numbers = {5, 2, 8, 1, 9, 4};

    // Sử dụng Structured Binding (C++17) để giải nén pair
    auto [min_val, max_val] = findMinMax(my_numbers);

    cout << "Min value (using structured binding): " << min_val << endl;
    cout << "Max value (using structured binding): " << max_val << endl;


    // Structured binding cũng dùng được khi duyệt map (C++17)
    map<string, int> student_scores;
    student_scores.insert({"Alice", 95});
    student_scores.insert({"Bob", 88});

    cout << "\nScores:" << endl;
    for (const auto& [name, score] : student_scores) {
        // 'name' là tham chiếu tới key (const string&)
        // 'score' là tham chiếu tới value (int&)
        cout << "Student: " << name << ", Score: " << score << endl;
    }

    return 0;
}

Giải thích: Thay vì viết pair<int, int> result = findMinMax(my_numbers); và sau đó truy cập result.first, result.second, chúng ta dùng auto [min_val, max_val] = findMinMax(my_numbers);. Cú pháp [min_val, max_val] tự động ánh xạ result.first vào biến min_val và result.second vào biến max_val. Code trở nên rõ ràng và dễ đọc hơn rất nhiều. Tương tự khi duyệt map, auto& [name, score] giúp bạn truy cập key và value một cách trực tiếp.

Bài tập ví dụ: C++ Bài 8.B1: Truy vấn với mảng

Bạn được cung cấp một mảng $a$ có độ dài vô hạn. Ban đầu tất cả các phần tử đều bằng $0$. Yêu cầu xử lý $Q$ truy vấn có dạng như sau:

0 k v nghĩa là gán $a[k] = v$.
1 k nghĩa là in ra giá trị $a[k]$.

INPUT FORMAT

Dòng đầu tiên chứa giá trị $Q$ $(1 \leq Q \leq 10^5)$

$Q$ dòng tiếp theo chứa các truy vấn $(0\leq k, v \leq |10^{18}|)$.

OUTPUT FORMAT

Với truy vấn 1 k in ra giá trị $a[k]$

Ví dụ:

Input

Output

Giải thích ví dụ mẫu:

Ví dụ: Các truy vấn 0 k v cập nhật giá trị tại chỉ số k với giá trị v, và các truy vấn 1 k in ra giá trị hiện tại tại chỉ số k. <br>

Nhận xét: Ban đầu tất cả các phần tử đều là 0. Chỉ có các truy vấn loại 0 k v làm thay đổi giá trị tại chỉ số k. Khi truy vấn loại 1 k, nếu chỉ số k chưa bao giờ bị thay đổi, giá trị của nó vẫn là 0. Nếu chỉ số k đã bị thay đổi, giá trị của nó là giá trị được gán gần nhất.
Lựa chọn cấu trúc dữ liệu:
- Chúng ta cần lưu trữ các cặp (chỉ_số, giá_trị) cho những chỉ số đã bị thay đổi.
- Chỉ số k có thể rất lớn (10^{18}), nên không thể dùng mảng thông thường hay vector.
- Chúng ta cần một cấu trúc dữ liệu cho phép:
  - Lưu trữ các cặp (key, value) trong đó key là chỉ số k (kiểu số nguyên lớn), value là giá trị v (kiểu số nguyên lớn).
  - Tìm kiếm giá trị nhanh chóng dựa vào chỉ số k.
  - Cập nhật hoặc thêm mới cặp (k, v) nhanh chóng.
- Cấu trúc dữ liệu phù hợp trong C++ là unordered_map (hash map) hoặc map (binary search tree map).
  - unordered_map<long long, long long>: Sử dụng chỉ số k làm khóa, giá trị v làm giá trị lưu trữ. Tra cứu, thêm, cập nhật trung bình O(1). Tốt cho việc tra cứu nhanh các khóa rải rác.
  - map<long long, long long>: Cũng sử dụng chỉ số k làm khóa. Tra cứu, thêm, cập nhật O(log N), với N là số lượng phần tử trong map. Đảm bảo thời gian tồi tệ ổn định, nhưng thường chậm hơn unordered_map trên lý thuyết nếu hàm băm tốt.
Với bài toán này, unordered_map thường được ưa chuộng hơn vì hiệu năng trung bình nhanh hơn cho các thao tác cơ bản.
Cách xử lý từng loại truy vấn với unordered_map<long long, long long>:
- Truy vấn 0 k v:
  - Cần cập nhật giá trị tại chỉ số k thành v.
  - Trong map, điều này tương ứng với việc gán giá trị v cho khóa k.
  - Sử dụng cú pháp map[k] = v;. Nếu k đã tồn tại, giá trị cũ sẽ bị ghi đè. Nếu k chưa tồn tại, một cặp (k, v) mới sẽ được thêm vào map.
- Truy vấn 1 k:
  - Cần in ra giá trị hiện tại tại chỉ số k.
  - Tìm kiếm chỉ số k trong map.
  - Sử dụng phương thức map.find(k) để tìm iterator tới phần tử có khóa k.
  - Kiểm tra kết quả:
    - Nếu map.find(k) trả về iterator khác map.end(), nghĩa là k có trong map. Giá trị hiện tại của a[k] chính là giá trị lưu trữ trong map tương ứng với khóa k (tức là map[k] hoặc it->second). In ra giá trị này.
    - Nếu map.find(k) trả về map.end(), nghĩa là k không có trong map. Điều này có nghĩa là chỉ số k chưa bao giờ bị thay đổi giá trị. Giá trị hiện tại của a[k] vẫn là giá trị mặc định ban đầu, tức là 0. In ra 0.
Lưu ý:
- Sử dụng kiểu dữ liệu long long cho k và v để đảm bảo chứa được giá trị lớn đến `10^{18}$.
- Cần bao gồm các thư viện cần thiết: <iostream> để nhập xuất và <unordered_map> (hoặc <map>) cho cấu trúc dữ liệu.
- Đối với số lượng truy vấn lớn (Q = 10^5), nên tối ưu hóa nhập xuất bằng cách thêm ios_base::sync_with_stdio(false); cin.tie(NULL); vào đầu hàm main.

Với hướng dẫn này, bạn có thể tự viết mã C++ sử dụng unordered_map để giải quyết bài toán.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.