std::set::insert

#include <set>

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

// Phiên bản 2: Chèn một phần tử với gợi ý vị trí (C++98 và C++11)
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 range (C++98 và C++11)
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 phần tử mới vào std::set. std::set sẽ tự động sắp xếp phần tử mới được chèn vào đúng vị trí để duy trì thứ tự đã sắp xếp của các phần tử trong 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:
  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 (chưa tồn tại), false nếu phần tử đã tồn tại.
• Phiên bản 2:
  • iterator: 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 có giá trị trả về

Đặc điểm

1. Chèn phần tử duy nhất: std::set chỉ lưu trữ các phần tử duy nhất. Nếu bạn cố gắng chèn một phần tử đã tồn tại, thao tác chèn sẽ bị bỏ qua.
2. Tự động sắp xếp: std::set tự động sắp xếp các phần tử khi chèn vào.
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.
4. Hỗ trợ move semantics (từ C++11): 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::set có thể làm thay đổi (invalidate) các iterator đang trỏ đến các phần tử trong std::set. Tuy nhiên, các iterator trỏ đến phần tử trước vị trí chèn vẫn hợp lệ (trong phiên bản 2).
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:
   • Phiên bản 1 và 4: O(log n), với n là số phần tử trong std::set.
   • Phiên bản 2: O(log n) trong trường hợp bình thường, amortized O(1) nếu hint chính xác.
   • Phiên bản 3: O(m log(n + m)), với n là số phần tử trong std::set và m là số phần tử được chèn.

Ví dụ

#include <iostream>
#include <set>
#include <vector>

int main() {
  std::set<int> myset;

  // Phiên bản 1: Chèn từng phần tử
  auto ret = myset.insert(30);
  if (ret.second == false) {
      std::cout << "30 already exists in set" << std::endl;
  }
  myset.insert(10);
  myset.insert(50);
  myset.insert(20);
  myset.insert(30); // Phần tử 30 đã tồn tại, sẽ không được chèn

  std::cout << "myset after inserting elements:";
  for (int x : myset) std::cout << ' ' << x; // Output: myset after inserting elements: 10 20 30 50
  std::cout << '\n';

  // Phiên bản 2: Chèn với gợi ý vị trí
  auto it = myset.find(20); // Giả sử ta biết 20 ở gần vị trí cần chèn 25
  myset.insert(it, 25); // Chèn 25 gần vị trí của 20 (có thể nhanh hơn)

  // Phiên bản 3: Chèn từ một range
  std::vector<int> vec = {40, 60, 15};
  myset.insert(vec.begin(), vec.end());

  // Phiên bản 4: Chèn từ initializer list
  myset.insert({5, 35, 45});

  std::cout << "myset after more insertions:";
  for (int x : myset) std::cout << ' ' << x; // Output: myset after more insertions: 5 10 15 20 25 30 35 40 45 50 60
  std::cout << '\n';

  return 0;
}

Các hàm liên quan

erase	Xóa một hoặc nhiều phần tử khỏi std::set
find	Tìm kiếm một phần tử có giá trị bằng với giá trị cho trước trong std::set