std::multiset

#include <set>

template <class T, class Compare = std::less<T>,
          class Allocator = std::allocator<T>>
class multiset;        

std::multiset trong C++ là một container liên kết (associative container) lưu trữ các phần tử được sắp xếp (sorted) theo một thứ tự nhất định. Khác với std::set, std::multiset cho phép lưu trữ các phần tử trùng lặp (duplicates). Nó cũng được triển khai bằng cây tìm kiếm nhị phân cân bằng (thường là cây đỏ-đen), cho phép tìm kiếm, chèn và xóa phần tử một cách hiệu quả.

Tham số

T

• Kiểu dữ liệu của các phần tử trong std::multiset.

Compare

• Hàm so sánh (comparison function object) xác định thứ tự sắp xếp của các phần tử. Mặc định là std::less<T>, tức là sắp xếp tăng dần.

Allocator

• Kiểu cấp phát bộ nhớ, mặc định là std::allocator<T>. Thường bạn không cần quan tâm đến tham số này.

multiset

• Tên của std::multiset bạn muốn tạo.

Đặc điểm

1. Phần tử trùng lặp: std::multiset cho phép lưu trữ các phần tử trùng lặp.
2. Phần tử được sắp xếp: Các phần tử trong std::multiset luôn được sắp xếp theo một thứ tự nhất định, mặc định là tăng dần (sử dụng std::less). Bạn có thể thay đổi thứ tự sắp xếp bằng cách cung cấp một hàm so sánh tùy chỉnh (tham số Compare).
3. Tìm kiếm hiệu quả: Nhờ cấu trúc cây tìm kiếm nhị phân, việc tìm kiếm phần tử trong std::multiset có độ phức tạp O(log n), với n là số phần tử trong multiset.
4. Không hỗ trợ truy cập theo chỉ số: Bạn không thể truy cập các phần tử trong std::multiset bằng chỉ số như mảng hay vector. Thay vào đó, bạn phải sử dụng iterator.
5. Iterator không bị thay đổi (invalidate) khi chèn: Không giống như std::vector, iterator của std::multiset không bị thay đổi (invalidate) khi bạn chèn thêm phần tử mới, trừ khi bạn xóa chính phần tử mà iterator đang trỏ tới.
6. Chèn và xóa: Việc chèn và xóa phần tử trong std::multiset có độ phức tạp trung bình O(log n).
7. Ưu điểm:
   • Lưu trữ các phần tử được sắp xếp.
   • Cho phép các phần tử trùng lặp.
   • Tìm kiếm, chèn và xóa phần tử tương đối hiệu quả.
8. Nhược điểm:
   • Không thể truy cập phần tử theo chỉ số.
   • Việc sửa đổi trực tiếp giá trị của phần tử (key) có thể làm hỏng thứ tự sắp xếp. Bạn cần xóa đi chèn lại nếu muốn thay đổi giá trị phần tử.
9. Khi nào nên sử dụng std::multiset:
   • Khi bạn cần lưu trữ một tập hợp các phần tử được sắp xếp.
   • Khi bạn cho phép các phần tử trùng lặp.
   • Khi bạn cần thực hiện các thao tác tìm kiếm, chèn và xóa phần tử một cách hiệu quả.

Phân biệt std::set và std::multiset

• std::set: Lưu trữ các phần tử duy nhất, không cho phép trùng lặp.
• std::multiset: Cho phép lưu trữ các phần tử trùng lặp.

Ví dụ:

#include <iostream>
#include <set>
#include <string>
#include <functional> // std::greater

int main() {
  // 1. Khởi tạo multiset rỗng
  std::multiset<int> mset1;

  // 2. Chèn phần tử vào multiset
  mset1.insert(30);
  mset1.insert(10);
  mset1.insert(50);
  mset1.insert(20);
  mset1.insert(30); // Phần tử trùng lặp được cho phép

  // 3. Duyệt multiset (các phần tử đã được sắp xếp)
  std::cout << "mset1:";
  for (int x : mset1) {
    std::cout << ' ' << x;
  }
  std::cout << '\n'; // Output: mset1: 10 20 30 30 50

  // 4. Tìm kiếm phần tử
  auto it = mset1.find(20);
  if (it != mset1.end()) {
    std::cout << "Found element 20\n"; // Output: Found element 20
  }

  // 5. Xóa phần tử
  mset1.erase(20);

  // 6. Kiểm tra multiset rỗng
  if (mset1.empty()) {
    std::cout << "mset1 is empty\n";
  } else {
    std::cout << "mset1 is not empty\n"; // Output: mset1 is not empty
  }

  // 7. Lấy kích thước multiset
  std::cout << "mset1.size(): " << mset1.size() << '\n'; // Output: mset1.size(): 4

  // 8. Khởi tạo multiset với initializer list (C++11)
  std::multiset<std::string> mset2 = {"apple", "banana", "orange", "apple"}; // "apple" xuất hiện 2 lần

  // 9. Khởi tạo multiset với custom comparison function (sắp xếp giảm dần)
  std::multiset<int, std::greater<int>> mset3;
  mset3.insert(30);
  mset3.insert(10);
  mset3.insert(50);
  mset3.insert(30);
  std::cout << "mset3:";
  for (int x : mset3) {
    std::cout << ' ' << x;
  }
  std::cout << '\n'; // Output: mset3: 50 30 30 10

  // 10. Xóa tất cả các phần tử
  mset1.clear();

  // 11. Hoán đổi nội dung 2 multiset
  mset1.swap(mset3);

  // 12. Trích xuất 1 node
  auto extractedNode = mset1.extract(mset1.begin());

  // 13. Hợp nhất 2 multiset
  std::multiset<int> mset4 = {1, 2, 3};
  std::multiset<int> mset5 = {3, 4, 5};
  mset4.merge(mset5); // {1, 2, 3, 3, 4, 5} , mset5 sẽ rỗng, mset4 và mset5 phải cùng comparison function

  return 0;
}

Các cách phổ biến khai báo và khởi tạo một std::multiset

lưu ý

• std::multiset luôn lưu trữ các phần tử được sắp xếp.
• Mặc định, std::multiset sử dụng std::less để so sánh các phần tử (sắp xếp tăng dần). Bạn có thể cung cấp một hàm so sánh tùy chỉnh (comparison function object) khi khai báo std::multiset để thay đổi thứ tự sắp xếp.
• Khi khởi tạo std::multiset từ một range hoặc một container khác, các phần tử sẽ được sao chép vào std::multiset và sau đó được sắp xếp.
• Khi khởi tạo std::multiset từ một initializer list, các phần tử sẽ được sắp xếp.

1. Khai báo một std::multiset rỗng (sử dụng so sánh mặc định std::less):

   #include <set>
   
   std::multiset<int> mset1; // multiset rỗng, kiểu int, sử dụng so sánh mặc định (tăng dần)

2. Khai báo một std::multiset rỗng với hàm so sánh tùy chỉnh:

   #include <set>
   #include <functional> // std::greater
   
   std::multiset<int, std::greater<int>> mset2; // multiset rỗng, kiểu int, sử dụng std::greater để sắp xếp giảm dần

3. Khai báo và khởi tạo từ một range (copy):

   #include <set>
   #include <vector>
   #include <iostream>
   
   int main() {
     std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};
   
     std::multiset<int> mset3(vec.begin(), vec.end()); // Khởi tạo từ một range (copy)
   
     std::cout << "mset3:";
     for (int x : mset3) std::cout << ' ' << x; // Output: mset3: 1 1 2 3 4 5 6 9
     std::cout << '\n';
     
     return 0;
   }

4. Khai báo và khởi tạo từ một std::multiset khác (copy constructor):

   #include <set>
   
   int main() {
       std::multiset<int> mset4 = {1, 2, 3, 2, 1};
       std::multiset<int> mset5(mset4); // Sao chép từ mset4
       return 0;
   }

5. Khai báo và khởi tạo từ một initializer list (C++11):

   #include <set>
   
   std::multiset<int> mset6 = {3, 1, 4, 1, 5, 9, 2, 6}; // Khởi tạo từ initializer list, các phần tử sẽ được sắp xếp

6. Khai báo std::multiset và sau đó chèn phần tử:

   #include <set>
   
   std::multiset<int> mset7;
   mset7.insert(3);
   mset7.insert(1);
   mset7.insert(4);
   mset7.insert(1); // Phần tử trùng lặp được cho phép

7. Khai báo và khởi tạo bằng cách di chuyển (move constructor - C++11):

   #include <set>
   
   std::multiset<int> mset8 = {7,8,9,10,9};
   std::multiset<int> mset9(std::move(mset8)); // mset8 sẽ trở thành rỗng sau đó

Các kiểu dữ liệu của std::multiset

lưu ý

std::multiset cũng giống như std::set, nó có thể chứa hầu hết các kiểu dữ liệu trong C++, ngoài các kiểu cơ bản như int, float, double, ..., miễn là kiểu dữ liệu đó đáp ứng một số yêu cầu nhất định.

1. Con trỏ:

   • int*, float*, double*
   • char* (C-style strings) - Cần cẩn thận với việc so sánh và quản lý bộ nhớ.
   • Con trỏ đến các đối tượng của lớp tự định nghĩa.
   • Con trỏ hàm.
   lưu ý khi sử dụng con trỏ

   • std::multiset sẽ so sánh giá trị của con trỏ (địa chỉ bộ nhớ) chứ không phải so sánh nội dung mà con trỏ trỏ tới (trừ khi bạn cung cấp hàm so sánh tùy chỉnh).
   • Bạn cần đảm bảo rằng việc quản lý bộ nhớ cho các đối tượng được trỏ đến là chính xác để tránh rò rỉ bộ nhớ hoặc lỗi khi std::multiset bị hủy.

2. Các kiểu dữ liệu chuẩn (Standard Library Types):

   • std::string: Chuỗi ký tự. std::multiset sẽ so sánh các chuỗi theo thứ tự từ điển.

     std::multiset<std::string> names;
     names.insert("Alice");
     names.insert("Bob");
     names.insert("Alice"); // Cho phép trùng lặp

   • Containers: Bao gồm std::vector, std::list, std::deque, std::array, std::set, std::map, std::multiset (chính nó), std::forward_list, ... (với lưu ý về việc so sánh, xem bên dưới).

     std::multiset<std::vector<int>> multiset_of_vectors; // Cần định nghĩa cách so sánh 2 vector
     std::multiset<std::list<int>> multiset_of_lists;

   • std::pair và std::tuple: (với lưu ý về việc so sánh, xem bên dưới).

     std::multiset<std::pair<int, std::string>> multiset_of_pairs;
     std::multiset<std::tuple<int, float, char>> multiset_of_tuples;
     Lưu ý khi sử dụng container, std::pair, std::tuple

     • Bạn cần đảm bảo rằng các kiểu dữ liệu này hỗ trợ toán tử < (hoặc cung cấp hàm so sánh tùy chỉnh) để std::multiset có thể sắp xếp chúng.
     • Với std::pair và std::tuple, toán tử < mặc định sẽ so sánh từng thành phần tương ứng theo thứ tự từ trái sang phải.

   • Các kiểu khác: std::complex, std::bitset,...

3. Kiểu dữ liệu do người dùng định nghĩa (Classes và Structs):
   Bạn có thể tạo std::multiset chứa các đối tượng của bất kỳ lớp (class) hoặc cấu trúc (struct) nào do bạn định nghĩa, miễn là chúng thỏa mãn các yêu cầu sau:

   • Phải có cách so sánh: Bạn cần định nghĩa toán tử < cho lớp/struct của mình, hoặc cung cấp một hàm so sánh tùy chỉnh (comparison function object) khi khai báo std::multiset. Cách này giúp std::multiset biết cách sắp xếp các đối tượng.
   • CopyConstructible: Có copy constructor
   • Destructible: Có destructor
   • MoveConstructible (từ C++11): Nên có, để tối ưu hiệu suất
   • MoveAssignable (từ C++11): Nên có, để tối ưu hiệu suất
   • CopyAssignable: Nên có, để tối ưu hiệu suất

     class Person {
     public:
       std::string name;
       int age;
     
       Person(std::string n, int a) : name(n), age(a) {}
     
       // Định nghĩa toán tử < để so sánh Person theo tên
       bool operator<(const Person& other) const {
         return name < other.name;
       }
     };
     
     int main() {
       std::multiset<Person> people;
       people.insert(Person("Alice", 30));
       people.insert(Person("Bob", 25));
       people.insert(Person("Charlie", 35));
       people.insert(Person("Bob", 40)); // Bob được thêm vào 2 lần
     
       return 0;
     }

4. Smart Pointers (từ C++11):
   Bạn có thể sử dụng std::multiset để lưu trữ các smart pointers như std::unique_ptr hoặc std::shared_ptr.

   • Với std::unique_ptr: Bạn cần cung cấp hàm so sánh tùy chỉnh, vì std::unique_ptr không hỗ trợ toán tử < mặc định.
   • Với std::shared_ptr: std::shared_ptr hỗ trợ toán tử < (so sánh địa chỉ), nên bạn có thể sử dụng std::multiset với std::shared_ptr mà không cần hàm so sánh tùy chỉnh (nhưng hãy cẩn thận về ý nghĩa của việc so sánh này).

     #include <set>
     #include <memory>
     #include <iostream>
     
     // Hàm so sánh cho unique_ptr<int>
     struct CompareUniquePtr {
       bool operator()(const std::unique_ptr<int>& a, const std::unique_ptr<int>& b) const {
         return *a < *b;
       }
     };
     
     int main() {
       std::multiset<std::unique_ptr<int>, CompareUniquePtr> mset_of_unique_ptrs;
       mset_of_unique_ptrs.insert(std::make_unique<int>(5));
       mset_of_unique_ptrs.insert(std::make_unique<int>(2));
       mset_of_unique_ptrs.insert(std::make_unique<int>(2)); // Cho phép trùng lặp
     
       std::multiset<std::shared_ptr<int>> mset_of_shared_ptrs;
       mset_of_shared_ptrs.insert(std::make_shared<int>(10));
       mset_of_shared_ptrs.insert(std::make_shared<int>(3));
     
         for (const auto& ptr : mset_of_unique_ptrs) {
             std::cout << *ptr << " ";
         }
         std::cout << std::endl;
     
         for (const auto& ptr : mset_of_shared_ptrs) {
             std::cout << *ptr << " ";
         }
         std::cout << std::endl;
       return 0;
     }

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

=	Gán nội dung của một std::multiset khác hoặc một initializer_list cho std::multiset hiện tại

Trình lặp (Iterators)

begin	Trả về một iterator trỏ đến phần tử đầu tiên trong std::multiset
end	Trả về một iterator trỏ đến vị trí sau phần tử cuối cùng trong std::multiset
rbegin	Trả về một reverse_iterator trỏ đến phần tử cuối cùng trong std::multiset
rend	Trả về một reverse_iterator trỏ đến phần tử trước phần tử đầu tiên của std::multiset
cbegin	Trả về một const_iterator trỏ đến phần tử đầu tiên trong std::multiset
cend	Trả về một const_iterator trỏ đến vị trí sau phần tử cuối cùng trong std::multiset
crbegin	Trả về một const_reverse_iterator trỏ đến phần tử cuối cùng trong std::multiset
crend	Trả về một const_reverse_iterator trỏ đến phần tử trước phần tử đầu tiên của std::multiset

Dung lượng (Capacity)

empty	Kiểm tra xem std::multiset có rỗng hay không
size	Trả về số lượng phần tử hiện có trong std::multiset
max_size	Trả về số lượng phần tử tối đa mà std::multiset có thể chứa

Thay đổi nội dung (Modifiers)

insert	Chèn một hoặc nhiều phần tử mới vào std::multiset
erase	Xóa một hoặc nhiều phần tử khỏi std::multiset
swap	Hoán đổi nội dung của hai std::multiset với nhau
clear	Xóa tất cả các phần tử khỏi std::multiset
emplace	Xây dựng (construct) một phần tử mới trực tiếp trong std::multiset tại vị trí thích hợp
emplace_hint	Xây dựng (construct) một phần tử mới trực tiếp trong std::multiset với một gợi ý (hint)

Quan sát (Observers)

key_comp	Trả về một bản sao của hàm so sánh được sử dụng bởi std::multiset để sắp xếp các phần tử
value_comp	Trả về một bản sao của hàm so sánh được sử dụng bởi std::multiset để so sánh các phần tử

Thao tác (Operations)

find	Tìm kiếm một phần tử có giá trị bằng với giá trị cho trước trong std::multiset
count	Đếm số lượng phần tử có giá trị bằng với giá trị cho trước trong std::multiset
lower_bound	Trả về một iterator trỏ đến phần tử đầu tiên trong std::multiset có giá trị lớn hơn hoặc bằng giá trị key cho trước
upper_bound	Trả về một iterator trỏ đến phần tử đầu tiên trong std::multiset có giá trị lớn hơn giá trị key cho trước
equal_range	Trả về một cặp iterator xác định phạm vi các phần tử trong std::multiset có giá trị bằng với giá trị key cho trước

Cấp phát (Allocator)

get_allocator	Trả về một bản sao của bộ cấp phát (allocator) được liên kết với std::multiset