std::unordered_set::insert

#include <unordered_set>

// Phiên bản 1: Chèn một phần tử
pair<iterator, bool> insert(const value_type& val);
pair<iterator, bool> insert(value_type&& val); // (since C++11)

// Phiên bản 2: Chèn với gợi ý vị trí
iterator insert(const_iterator hint, const value_type& val);
iterator insert(const_iterator hint, value_type&& val); // (since C++11)

// Phiên bản 3: Chèn các phần tử từ một phạm vi khác
template <class InputIterator>
void insert(InputIterator first, InputIterator last);

// Phiên bản 4: Chèn các phần tử từ initializer list (C++11)
void insert(initializer_list<value_type> ilist);

Chèn một hoặc nhiều phần tử mới vào std::unordered_set.

Tham số

val

• Giá trị của phần tử cần chèn (phiên bản 1 và 2).

hint

• Iterator gợi ý vị trí chèn (phiên bản 2).

first, last

• Iterator xác định phạm vi các phần tử cần chèn (phiên bản 3).

ilist

• initializer_list chứa các phần tử cần chèn (phiên bản 4).

Giá trị trả về

• Phiên bản 1:
  • Trả về std::pair<iterator, bool>.
  • iterator: Trỏ đến phần tử có giá trị tương đương với giá trị đã chèn (có thể là phần tử đã tồn tại hoặc phần tử mới được chèn).
  • bool: true nếu phần tử được chèn thành công (phần tử mới), false nếu phần tử đã tồn tại (chèn thất bại).
• Phiên bản 2:
  • Trả về iterator trỏ đến phần tử có giá trị tương đương với giá trị đã chèn (có thể là phần tử đã tồn tại hoặc phần tử mới được chèn).
• Phiên bản 3 và 4:
  • void: Không trả về giá trị nào.

Đặc điểm

1. Chèn phần tử duy nhất: std::unordered_set chỉ lưu trữ các phần tử duy nhất. Việc chèn phần tử đã tồn tại sẽ bị bỏ qua (đối với insert()).
2. Không đảm bảo thứ tự: std::unordered_set không lưu trữ phần tử theo thứ tự, vì vậy vị trí chèn không ảnh hưởng đến thứ tự duyệt.
3. Hỗ trợ gợi ý vị trí: Phiên bản insert(hint, val) cho phép bạn cung cấp gợi ý vị trí chèn, có thể giúp cải thiện hiệu suất nếu bạn biết vị trí chèn gần đúng (ít dùng với std::unordered_set).
4. Hỗ trợ move semantics: Phiên bản insert(const_iterator pos, value_type&& val) (từ C++11) hỗ trợ di chuyển (move semantics), giúp tối ưu hiệu suất khi chèn các đối tượng lớn hoặc phức tạp.
5. Có thể làm thay đổi iterator: Việc chèn phần tử vào std::unordered_set có thể làm thay đổi (invalidate) các iterator đang trỏ đến các phần tử trong std::unordered_set do việc rehash có thể xảy ra.
6. 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, insert() có thể ném ra ngoại lệ std::bad_alloc. Ngoài ra, nếu copy constructor (phiên bản 1) hoặc move constructor (phiên bản 2) của value_type ném ngoại lệ, insert() cũng sẽ ném ngoại lệ.
7. Độ phức tạp:
   • Chèn một phần tử: Trung bình O(1), trường hợp xấu nhất O(n), với n là số phần tử trong std::unordered_set.
   • Chèn nhiều phần tử (phiên bản 3 và 4): Trung bình O(k), trường hợp xấu nhất O(k*n), với k là số phần tử được chèn và n là số phần tử trong std::unordered_set.
8. std::unordered_set chỉ lưu trữ các phần tử duy nhất, do đó:
   • Nếu phần tử được chèn chưa tồn tại trong std::unordered_set, nó sẽ được thêm vào.
   • Nếu phần tử được chèn đã tồn tại (dựa trên hàm băm và so sánh bằng), việc chèn sẽ thất bại và std::unordered_set không thay đổi.

Ví dụ

#include <iostream>
#include <unordered_set>
#include <string>
#include <vector>

int main() {
  std::unordered_set<std::string> myset;

  // Phiên bản 1: Chèn từng phần tử
  auto ret = myset.insert("apple");
  if (ret.second) {
    std::cout << "'apple' inserted successfully.\n";
  }
  myset.insert("banana");
  myset.insert("orange");

  // Thử chèn một phần tử đã tồn tại
  ret = myset.insert("apple"); // Chèn thất bại
  if (!ret.second) {
    std::cout << "'apple' already exists.\n";
  }

  // Phiên bản 2: Chèn với gợi ý vị trí (ít ý nghĩa với unordered_set)
  auto it = myset.find("banana"); // Giả sử ta biết "banana" ở gần vị trí cần chèn
  myset.insert(it, "grape");

  // Phiên bản 3: Chèn từ một range
  std::vector<std::string> vec = {"kiwi", "mango", "apple"};
  myset.insert(vec.begin(), vec.end());

  // Phiên bản 4: Chèn từ initializer list
  myset.insert({"pear", "avocado", "banana"});

  std::cout << "myset after insertions:";
  for (const auto& str : myset) std::cout << ' ' << str;
  // Output: myset after insertions: pear avocado mango orange kiwi grape banana apple (thứ tự có thể khác)
  std::cout << '\n';

  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::unordered_set
emplace_hint	Xây dựng (construct) một phần tử mới trực tiếp trong std::unordered_set với một gợi ý (hint)
=	Gán nội dung của một std::unordered_set khác hoặc một initializer_list cho std::unordered_set hiện tại
erase	Xóa một hoặc nhiều phần tử khỏi std::unordered_set