std::multiset::emplace_hint

#include <set>

Xây dựng (construct) một phần tử mới trực tiếp trong std::multiset, tương tự như emplace(), nhưng bạn có thể cung cấp thêm một gợi ý (hint) về vị trí chèn để tối ưu hóa hiệu suất.

template <class... Args>
iterator emplace_hint(const_iterator hint, Args&&... args);

Tham số

hint

• const_iterator trỏ đến vị trí gợi ý để chèn phần tử mới.

args

• Danh sách các đối số (có thể trống) được sử dụng để khởi tạo phần tử mới. Các đối số này sẽ được truyền đến constructor của kiểu phần tử value_type của std::multiset.

Giá trị trả về

• Trả về một iterator trỏ đến phần tử vừa được chèn vào.

Đặc điểm

1. Xây dựng phần tử tại chỗ (In-place construction): Giống như emplace(), emplace_hint() tạo phần tử mới trực tiếp trong bộ nhớ của std::multiset, tránh việc tạo ra các đối tượng tạm thời không cần thiết.
2. Tránh sao chép và di chuyển: Bằng cách xây dựng phần tử tại chỗ, emplace_hint() giúp tránh việc sao chép (copy) hoặc di chuyển (move) các đối tượng.
3. Hỗ trợ variadic template: emplace_hint() sử dụng variadic template (Args&&... args), cho phép nó nhận số lượng đối số tùy ý, phù hợp với constructor của kiểu phần tử.
4. Gợi ý vị trí chèn (hint): Tham số hint cho phép bạn cung cấp gợi ý về vị trí chèn, có thể cải thiện hiệu suất nếu gợi ý chính xác.
5. Có thể làm thay đổi iterator: Việc chèn phần tử vào std::multiset có thể làm thay đổi (invalidate) các iterator đang trỏ đến các phần tử trong std::multiset.
6. Phân biệt với emplace(): emplace_hint() tương tự emplace() nhưng có thêm tham số hint để gợi ý vị trí chèn, giúp tối ưu hiệu suất trong trường hợp hint chính xác.
7. Phân biệt với insert(): insert() sẽ tạo bản sao hoặc di chuyển phần tử được truyền vào trong khi đó emplace_hint() sẽ xây dựng phần tử tại chỗ trong std::multiset.
8. Có thể ném ngoại lệ: Nếu việc cấp phát bộ nhớ cho phần tử mới thất bại, emplace_hint() có thể ném ra ngoại lệ std::bad_alloc. Ngoài ra, nếu constructor của value_type ném ngoại lệ, emplace_hint() cũng sẽ ném ngoại lệ.
9. Thứ tự được duy trì: emplace_hint() vẫn đảm bảo các phần tử trong std::multiset được sắp xếp đúng thứ tự sau khi chèn, bất kể gợi ý có chính xác hay không.
10. Độ phức tạp:
    • O(log n) trong trường hợp bình thường (khi hint không chính xác), với n là số phần tử trong std::multiset.
    • Amortized O(1) nếu hint trỏ đến ngay trước vị trí mà phần tử mới nên được chèn.

Ví dụ

#include <iostream>
#include <set>
#include <string>

int main() {
  std::multiset<std::string> mymultiset;

  // Chèn các phần tử, sử dụng emplace_hint() với gợi ý
  auto it = mymultiset.emplace_hint(mymultiset.end(), "banana"); // Gợi ý chèn vào cuối (có thể sai)
  it = mymultiset.emplace_hint(it, "apple");   // Gợi ý chèn vào trước "banana" (có thể đúng)
  it = mymultiset.emplace_hint(mymultiset.end(), "cherry"); // Gợi ý chèn vào cuối (có thể đúng)
  it = mymultiset.emplace_hint(it, "apple"); // Thêm "apple" lần nữa

  std::cout << "mymultiset:";
  for (const std::string& str : mymultiset) {
    std::cout << ' ' << str;
  }
  std::cout << '\n'; // Output: mymultiset: apple apple banana cherry

  return 0;
}

Các hàm liên quan

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
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