Thứ tự giảm dần trong Map và Multimap của C++ STL

Mặc định, map và multimap trong C++ STL lưu trữ các phần tử theo thứ tự tăng dần của khóa. Tuy nhiên, chúng ta có thể lưu trữ theo thứ tự giảm dần bằng cách sử dụng hàm so sánh std::greater.

Các hàm được sử dụng

• m::find() – Trả về iterator đến phần tử có khóa 'b' nếu tìm thấy, ngược lại trả về iterator end().
• m::erase() – Xóa phần tử có khóa chỉ định khỏi map.
• m::equal_range() – Trả về cặp iterator chỉ phạm vi các phần tử có khóa tương đương.
• m::insert() – Chèn phần tử vào map.
• m::size() – Trả về số lượng phần tử trong map.
• m::count() – Trả về số lần xuất hiện của khóa (luôn là 0 hoặc 1 với map).

Ví dụ mã: Map theo thứ tự giảm dần

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    // Khai báo map với comparator greater<char> để sắp xếp giảm dần theo khóa
    map<char, int, greater<char>> m;
    map<char, int>::iterator it;

    m.insert(pair<char, int>('a', 10));
    m.insert(pair<char, int>('b', 20));
    m.insert(pair<char, int>('c', 30));
    m.insert(pair<char, int>('d', 40));

    cout << "Kích thước map: " << m.size() << endl;
    cout << "Nội dung map:\n";
    for (it = m.begin(); it != m.end(); ++it)
        cout << (*it).first << " => " << (*it).second << '\n';

    for (char c = 'a'; c <= 'd'; c++) {
        cout << "Số phần tử với khóa " << c << ": " << m.count(c) << ": ";
        for (it = m.equal_range(c).first; it != m.equal_range(c).second; ++it)
            cout << ' ' << (*it).second;
        cout << endl;
    }

    if (m.count('a')) cout << "Khóa 'a' tồn tại\n";
    else cout << "Khóa 'a' không tồn tại\n";

    if (m.count('f')) cout << "Khóa 'f' tồn tại\n";
    else cout << "Khóa 'f' không tồn tại\n";

    it = m.find('b');
    m.erase(it);

    cout << "Kích thước map sau xóa: " << m.size() << endl;
    cout << "Nội dung map:\n";
    for (it = m.begin(); it != m.end(); ++it)
        cout << (*it).first << " => " << (*it).second << '\n';

    return 0;
}

Kết quả đầu ra

Kích thước map: 4
Nội dung map:
d => 40
c => 30
b => 20
a => 10
Số phần tử với khóa a: 10
Số phần tử với khóa b: 20
Số phần tử với khóa c: 30
Số phần tử với khóa d: 40
Khóa 'a' tồn tại
Khóa 'f' không tồn tại
Kích thước map sau xóa: 3
Nội dung map:
d => 40
c => 30
a => 10

Multimap theo thứ tự giảm dần

multimap cho phép nhiều phần tử có cùng khóa. Cách khai báo tương tự map nhưng dùng greater<char> cho khóa.

Các hàm được sử dụng

• mm::find() – Trả về iterator đến phần tử đầu tiên có khóa 'b'.
• mm::erase() – Xóa phần tử (chỉ xóa một phần tử nếu có nhiều khóa trùng).
• mm::equal_range() – Trả về phạm vi các phần tử cùng khóa.
• mm::insert() – Chèn phần tử vào multimap.
• mm::size() – Trả về số lượng phần tử.

Ví dụ mã: Multimap giảm dần

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    multimap<char, int, greater<char>> mm;
    multimap<char, int>::iterator it;

    mm.insert(pair<char, int>('a', 10));
    mm.insert(pair<char, int>('b', 20));
    mm.insert(pair<char, int>('a', 30));
    mm.insert(pair<char, int>('b', 40));

    cout << "Kích thước multimap: " << mm.size() << endl;
    cout << "Nội dung multimap:\n";
    for (it = mm.begin(); it != mm.end(); ++it)
        cout << (*it).first << " => " << (*it).second << '\n';

    for (char c = 'a'; c <= 'd'; c++) {
        cout << "Số phần tử với khóa " << c << ": " << mm.count(c) << ": ";
        for (it = mm.equal_range(c).first; it != mm.equal_range(c).second; ++it)
            cout << ' ' << (*it).second;
        cout << endl;
    }

    if (mm.count('a')) cout << "Khóa 'a' tồn tại\n";
    else cout << "Khóa 'a' không tồn tại\n";

    if (mm.count('f')) cout << "Khóa 'f' tồn tại\n";
    else cout << "Khóa 'f' không tồn tại\n";

    it = mm.find('b');
    mm.erase(it); // Chỉ xóa một phần tử có khóa 'b'

    cout << "Kích thước multimap sau xóa: " << mm.size() << endl;
    cout << "Nội dung multimap:\n";
    for (it = mm.begin(); it != mm.end(); ++it)
        cout << (*it).first << " => " << (*it).second << '\n';

    return 0;
}

Kết quả đầu ra

Kích thước multimap: 4
Nội dung multimap:
b => 20
b => 40
a => 10
a => 30
Số phần tử với khóa a: 10 30
Số phần tử với khóa b: 20 40
Số phần tử với khóa c: 
Số phần tử với khóa d: 
Khóa 'a' tồn tại
Khóa 'f' không tồn tại
Kích thước multimap sau xóa: 3
Nội dung multimap:
b => 40
a => 10
a => 30