std::unordered_map::insert

#include <unordered_map>

// Phiên bản 1: Chèn một cặp giá trị (pair) (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 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 phạm vi khác (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 hoặc nhiều phần tử mới (cặp key-value) vào std::unordered_map.

Tham số

val

• Giá trị của phần tử cần chèn, là một std::pair chứa key và value (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ó key tương đương với key đã 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 (key 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ó key tương đương với key đã 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 theo key: std::unordered_map chỉ lưu trữ các phần tử có key duy nhất. Việc chèn phần tử có key đã tồn tại sẽ bị bỏ qua (đối với insert()).
2. Không đảm bảo thứ tự: std::unordered_map 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_map).
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_map có thể làm thay đổi (invalidate) các iterator đang trỏ đến các phần tử trong std::unordered_map 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_map.
   • 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_map.

Ví dụ

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>

int main() {
  std::unordered_map<std::string, int> myumap;

  // Phiên bản 1: Chèn từng phần tử
  auto ret = myumap.insert(std::make_pair("apple", 1));
  if (ret.second) {
    std::cout << "Insertion of apple successful.\n";
  }
  myumap.insert(std::pair<std::string, int>("banana", 2)); // C++98
  myumap.insert({"orange", 3}); // C++11 initializer list trong hàm insert

  // Thử chèn một phần tử có key đã tồn tại
  ret = myumap.insert(std::make_pair("apple", 10)); // Chèn thất bại
  if (!ret.second) {
    std::cout << "Insertion of apple failed (key already exists).\n";
    std::cout << "Existing value for apple: " << ret.first->second << std::endl;
  }

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

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

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

  std::cout << "myumap after insertions:\n";
  for (const auto& pair : myumap) {
    std::cout << pair.first << ": " << pair.second << '\n';
  }
  // Output:
  // Insertion of apple successful.
  // Insertion of apple failed (key already exists).
  // Existing value for apple: 1
  // myumap after insertions:
  // (thứ tự các phần tử có thể khác)
  // pear: 7
  // avocado: 8
  // mango: 6
  // kiwi: 5
  // grape: 4
  // orange: 3
  // banana: 2
  // apple: 1

  return 0;
}

Các hàm liên quan

emplace	Xây dựng (construct) một phần tử mới (cặp key-value) trực tiếp trong std::unordered_map tại vị trí thích hợp
emplace_hint	Xây dựng (construct) một phần tử mới (cặp key-value) trực tiếp trong std::unordered_map với một gợi ý (hint)
[]	Truy cập phần tử có key tương ứng
at	Truy cập phần tử có key cho trước