Multiset (tập hợp) trong C++

Multiset giống như Set nhưng có thể chứa các khóa có giá trị giống nhau.

Đọc thêm về Set tại: https://yeulaptrinh.pw/938/set-trong-c/

Khai báo : giống như set.

Các hàm thành viên:

Capacity:

  • size : trả về kích thước hiện tại của multiset. ĐPT O(1)
  • empty : true nếu multiset rỗng, và ngược lại. ĐPT O(1).

Chỉnh sửa:

  • insert : Chèn phần tử vào set. ĐPT O(logN).
  • erase :
    • xóa theo iterator ĐPT O(logN)
    • xóa theo khóa: xóa tất cả các phần tử bằng khóa trong multiset. ĐPT: O(logN) + số phần tử bị xóa.
  • clear : xóa tất cả set. ĐPT O(n).
  • swap : đổi 2 set cho nhau. ĐPT O(n).

Operations:

  • find : trả về itarator trỏ đến phần tử cần tìm kiếm. Nếu không tìm thấy itarator trỏ về “end” của set. ĐPT O(logN). Dù trong multiset có nhiều phần tử bằng khóa thì nó cũng chỉ iterator đến một phần tử.
  • lower_bound : trả về iterator đến vị trí phần tử bé nhất mà không bé hơn (lớn hơn hoặc bằng) khóa (dĩ nhiên là theo phép so sánh), nếu không tìm thấy trả về vị trí “end” của set. ĐPT O(logN).
  • upper_bound: trả về iterator đến vị trí phần tử bé nhất mà lớn hơn khóa, nếu không tìm thấy trả về vị trí “end” của set.. ĐPT O(logN).
  • count : trả về số lần xuất hiện của khóa trong multiset. ĐPT O(logN) + số phần tử tìm được.

Chương trình Demo:

#include <iostream>

#include <set>

using namespace std;

main() {
    multiset <int> s;

    multiset <int> :: iterator it;

    int i;

    for (i=1;i<=5;i++) s.insert(i*10); // s={10,20,30,40,50}
    s.insert(30);    // s={10,20,30,30,40,50}
    cout << s.count(30) << endl;    // In ra 2
    cout << s.count(20) << endl;    // In ra 1
    s.erase(30);    // s={10,20,40,50}

    /* Duyet set */
    for (it=s.begin();it!=s.end();it++) {
    cout << *it <<  " ";
    }

    //In ra 10 20 40 50 
    cout << endl; system("pause");
}
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*