std::deque::insert

#include <deque>

// Phiên bản 1: Chèn một phần tử
iterator insert(const_iterator pos, const value_type& value);
iterator insert(const_iterator pos, value_type&& value); // (since C++11)

// Phiên bản 2: Chèn nhiều phần tử có cùng giá trị
iterator insert(const_iterator pos, size_type count, const value_type& value);

// Phiên bản 3: Chèn các phần tử từ một initializer_list
iterator insert(const_iterator pos, initializer_list<value_type> ilist);

// Phiên bản 4: Chèn các phần tử từ một iterator range
template <class InputIterator>
iterator insert(const_iterator pos, InputIterator first, InputIterator last);

Chèn một hoặc nhiều phần tử mới vào một vị trí cụ thể trong deque.

Tham số

pos

• Iterator trỏ đến vị trí trước vị trí cần chèn phần tử mới. pos phải là một iterator hợp lệ và có thể dereference được trong deque. pos có thể bằng end() để chèn vào cuối deque.

value

• Giá trị của phần tử cần chèn.

count

• Số lượng phần tử cần chèn.

ilist

• Danh sách khởi tạo (initializer_list) chứa các phần tử cần chèn.

first, last

• Iterator xác định phạm vi các phần tử cần chèn.

Giá trị trả về

• Trả về một iterator trỏ đến phần tử đầu tiên được chèn vào. Nếu không có phần tử nào được chèn (ví dụ: count bằng 0 hoặc first bằng last), hàm trả về chính pos.

Đặc điểm

1. insert() cho phép bạn chèn phần tử vào bất kỳ vị trí hợp lệ nào trong deque.
2. insert() làm tăng kích thước của deque tương ứng với số lượng phần tử được chèn.
3. insert() có thể chèn các phần tử đơn lẻ, nhiều phần tử có cùng giá trị, các phần tử từ initializer_list hoặc từ một phạm vi được xác định bởi iterator.
4. Phiên bản insert(const_iterator pos, value_type&& value) (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. Việc chèn phần tử vào deque có thể làm thay đổi (invalidate) các iterator khác đang trỏ đến các phần tử trong deque (trừ khi chèn vào cuối).
6. Độ phức tạp:
   • Chèn một phần tử: O(n) trong trường hợp xấu nhất (khi chèn vào đầu), O(1) trong trường hợp tốt nhất (khi chèn vào cuối), với n là số phần tử trong deque. Trung bình là O(min(m, n-m)) với n là khoảng cách từ pos tới đầu deque và n-m là khoảng cách từ pos đến cuối deque.
   • Chèn nhiều phần tử: Độ phức tạp phụ thuộc vào số lượng phần tử được chèn và vị trí chèn.

Ví dụ

#include <iostream>
#include <deque>
#include <vector>

int main() {
  std::deque<int> myDeque = {10, 20, 30, 40};

  // Phiên bản 1: Chèn 15 vào trước phần tử thứ hai (có giá trị 20)
  auto it = myDeque.begin() + 1;
  myDeque.insert(it, 15);
  std::cout << "myDeque after insert(it, 15):";
  for (int x : myDeque) std::cout << ' ' << x; // Output: myDeque after insert(it, 15): 10 15 20 30 40
  std::cout << '\n';
  
  // Phiên bản 1 (move): Chèn 16 vào trước phần tử thứ 3 (có giá trị 20)
  int val = 16;
  myDeque.insert(myDeque.begin() + 2, std::move(val)); 
  std::cout << "myDeque after insert(it, std::move(16)) :";
  for (int x : myDeque) std::cout << ' ' << x; // Output: myDeque after insert(it, 15): 10 15 16 20 30 40
  std::cout << '\n';

  // Phiên bản 2: Chèn hai phần tử có giá trị 5 vào đầu deque
  myDeque.insert(myDeque.begin(), 2, 5);
  std::cout << "myDeque after insert(myDeque.begin(), 2, 5):";
  for (int x : myDeque) std::cout << ' ' << x; // Output: myDeque after insert(myDeque.begin(), 2, 5): 5 5 10 15 16 20 30 40
  std::cout << '\n';

  // Phiên bản 3: Chèn các phần tử từ initializer list vào trước phần tử cuối cùng
  myDeque.insert(myDeque.end(), {99, 88, 77});
  std::cout << "myDeque after insert(myDeque.end(), {99, 88, 77}):";
  for (int x : myDeque) std::cout << ' ' << x; // Output: myDeque after insert(myDeque.end(), {99, 88, 77}): 5 5 10 15 16 20 30 40 99 88 77
  std::cout << '\n';

  // Phiên bản 4: Chèn các phần tử từ một vector vào giữa deque
  std::vector<int> myVector = {1, 2, 3};
  myDeque.insert(myDeque.begin() + 4, myVector.begin(), myVector.end());
  std::cout << "myDeque after insert(myDeque.begin() + 4, myVector.begin(), myVector.end()):";
  for (int x : myDeque) std::cout << ' ' << x; // Output: myDeque after insert(myDeque.begin() + 4, myVector.begin(), myVector.end()): 5 5 10 15 1 2 3 16 20 30 40 99 88 77
  std::cout << '\n';

  return 0;
}

Các hàm liên quan

push_back	Thêm một phần tử mới vào cuối deque
push_front	Thêm một phần tử mới vào đầu deque
erase	Xóa một hoặc nhiều phần tử khỏi deque tại một vị trí cụ thể hoặc trong một phạm vi